Loading...
[This is a hard question. It has an interesting algorithm component. The risk is to over-focus on the algorithm, and will run out of time to do overall design and think about non-func requirements. As is any system design question, we believe top-down approach is better. Draw some boxes and details will come to your mind.]
[This is a rare problem in which they give us the API. Just use them.]
startEvent(event_id, timestamp): Record the start of an event.endEvent(event_id, timestamp): Record the end of an event.getOngoingEvents(timestamp): Return the count of events ongoing as of the specified timestamp.We assume timestamps are in seconds.
[Mid-level deep dive topic]
It helps to separate write path and read path while thinking about this problem.
Write path is data intensive. 1M events come in every second. It is important to design a system that can capture all the events. As the system receives a lot of small writes (events), and the data are immutable, LSM based database would fit the workload well. Wide-column DB like Cassandra or Time Series DB comes to mind. Time Series DB is a better choice because time is an important component, e.g., we would like to do time range based query.
Read path is looking for a simple data - just one integer representing the number of ongoing events.
[A chain of tradeoff thoughts.]
If we calculate this number on the fly, it would require the Read Service to query the Events DB (which is massive) and count events. This has two challenges: (a) it takes a long time. (b) read would hit Events DB, which is very busy just writing data. We'd like to protect Events DB.
So, we need the middle step between the write path and read path. Some step that transforms data from the Events DB into something read path can access.
What would the middle process look like? One way is batch processing. Read all the relevant events from Events DB, count them, and write to Summary DB.
We can design stream processing instead of batch processing. Crucially, though, timing requirement for the read path is pretty relaxed. getOngoingEvents() needs to look at only 1 day or older data. The main advantage of streaming is its speed (e.g. real time response time requirement). Because of this, we can use batch processing, making the architecture simpler.
Event data model should contain: {event_id, timestamp, event_arrival_time}
event_arrival_time is important for handling of out-of-order messages. More about this later.
Summary DB should contain: {timestamp, number of ongoing events}
Events DB and Summary DB are LSM based Time Sequence DBs.
As discussed above, we separate three functionalities:
startEvent() and endEvent() requests are forwarded to Count Service, which writes the events into Message Queue. Queue Worker takes them from Message Queue and write them to Event DB.
Summary Service runs periodically (e.g. every 10 min or 30 min). Summarizes
[Senior Level Deep Dive Topic - This is one of the most important parts of this problem.]
At a given timestamp T, the number of ongoing events can be calculated by:
Since the whole system receives 1M events / second. That means 3.6B events / hour. Each event being 24 bytes, that'll be 86.4GB. This would fit a modern server's main memory. For future growth and scalability, let's design parallel batch system.
We can easily split the workload to multiple servers. E.g. if the hash of event_ID is even number, server 1 is responsible for that event. If not, it's server 2's responsibility. We can then add up the numbers from both servers.
We don't have to do this calculation for every minute. After running the previous algorithm, we can calculate the delta for the next minute (T+1):
[Mid-Level Deep Dive Topic]
The Message Queue between Count Service and Events DB is for absorbing request spikes.
Without the Message Queue, If the number of requests burst in a short period of time, it may overwhelm Events DB and Count Service.
Message Queue acts as a buffer between Count Service and Events DB. As soon as Count Service writes events in Message Queue, the data would be robustly protected by the queue's replication and fault tolerance mechanisms. Queue Worker would read these events and writes to Events DB, when Events DB has enough writing capacity.
The disadvantage of this message queue approach is (1) it would add processing time for each event, and (2) it would make the architecture more complex.
(1) is not a significant problem in this system. Because getOngoingEvents() queries only 1 day old (or older) data, writing events quickly is not necessary.
(2) is a fair point, but this is a well established architectural pattern. We feel the benefit outweighs this challenge.
[Senior-Level Deep Dive Topic. This is probably the second most important part of this problem.]
The challenge of out of order messages is that we don't know how late they may arrive. If there's a time guarantee, e.g., at latest they arrive after 4 hours - Summary Service can simply wait for all the messages to arrive, and then calculate the number of ongoing events.
But since there's no such guarantee, we need to take two step processes: (1) calculate the number of ongoing events as best we could, using the messages already arrived, and (2) reconcile summary by messages that arrive after we do (1).
Summary Service has to remember the event_arrival_time of the last message it processed. It runs the main algorithm described in Detailed component design above.
After that, a reconciliation process (perhaps a different batch functionality of Summary Service) runs periodically, e.g., every hour.
Note that this algorithm is more expensive than the main Summary Service algorithm. The idea is that, if the main algorithm runs some time after the fact, e.g., 4 hours after T, most out of order messages should have already arrived. (This is an assumption that should be verified by monitoring the system.)
[Mid-Level Deep Dive Topic. Scalability and partitioning discussions are almost mandatory deep dive topics.]
Because Count Service receives a massive number of requests (1M/s), it has to have multiple nodes. Partitioned by a hash of event_id. We expect hash of event_id to be evenly distributed.
Similarly, Events DB has to store massive number of events. Therefore, partition is critical. The same partitioning key (event_id) makes sense here. Sort the events by timestamp.
Summary Service can also be partitioned by hash of event_id.
Summary DB. Because this only stores number of ongoing events for every minute, the storage size is not huge. A Time Sequence DB should scale fine without partitioning. It should have replication for fault tolerance and scalability. We can also introduce caching to optimize read path response time and scalability.
If the read requirements get a lot more demanding, e.g., multiple clients want to see the number of ongoing events at a real time, how should we evolve the architecture? We might want to transition from batch processing to stream processing.