Question
Implement an in-memory chat service in which users subscribe to channels, messages are appended to channel histories, and users read messages from their current subscriptions.
```python
class ChatSystem:
def subscribe(self, user_id: str, channel_id: str) -> None: ...
def unsubscribe(self, user_id: str, channel_id: str) -> None: ...
def send_message(self, user_id: str, channel_id: str, message: str) -> None: ...
def get_messages(self, user_id: str) -> list: ...
```
## Requirements
- Methods may run concurrently and shared state must be protected explicitly.
- Sending appends `[channel_id, user_id, message]` even if the sender is not subscribed.
- Reading concatenates histories for the user's current subscriptions in sorted channel-id order; each channel remains in send order.
- Unsubscribing hides that channel's history from subsequent reads.
- Repeated subscribe or unsubscribe operations should be idempotent.
- Define the consistency point of each operation and avoid exposing partially written messages.
- Each operation is atomic relative to the others. A read captures subscriptions and their histories at one consistency point; concurrent sends are ordered by their append points, not thread creation or wall-clock start time.
- Return fresh outer and per-message lists, so callers cannot edit stored history through a result. Inputs are string identifiers and string messages. Unknown users read `[]`; subscriptions include existing history, including messages sent before subscription. The constructor takes no arguments.
- The supplied `run_case` drives sequential public fixtures. Passing them alone does not demonstrate thread safety; native concurrency checks are separate.
## Design discussion (not graded)
1. Reduce lock contention with per-channel synchronization.
2. Add message IDs and incremental reads rather than replaying full history.
3. Persist history and recover after a crash.
4. Scale channels across processes while preserving ordering guarantees.