Loading...
Clients should be able to increment and decrement a value globally.
Clients should be able to retrieve the global value.
Examples: video views in youtube.
All operations should be fast, even on highly concurrent write scenario.
Counter value should be accurate.
Eventual consistency.
Highly available, scalable.
Peak Write QPS per counter = 20M/h = 5k
Average Write QPS 1B user * 10 video views / 24h = 120k
Average Read QPS = 10 read per write = 1M
Storage = 1B * 1 Video per day * 5 year * 20 byte = 36Tb
\readCounter:
parameter:counter_id
\createCounter:
parameter:
counter_id :based on object type and metric type
shard_number: estimated based on popularity of authors etc
\updateCounter
parameter:
counter_id
action_type: increment, decrement
The data has no relation.
I would go with no sql, consist of
counter_id (key), counter_value
I would choose cassandra over redis as not every counter will be read frequently, hence using in-memory only storage would be a waste of resource.
Stateless API service that takes get/post requests from user.
Partitioned, replicated cassandra db system.
For write request, it gets routed to nearest data center and routed to a random shard.
Because the hot counter is sharded, upon traffic spike, the traffic is spread across multiple shard, hence request should be slown down. And if a shard gets hit heavy, it can queue up the requests and process them in batches, before committing the change into disk, hence reduce request latency.
For read request, the api service will first query cache; upon cache miss, it will query counter value from all shards and sum them up, and store the value in cache.
The cache has a very short ttl, within seconds.
For hot counter, one single leader might not be able to process all the updates efficiently, which could cause delay on user end.
To solve this problem, we may shard hot counter into multiple multiple shards. Each shard has a leader and multiple followers. Data can be replicated from leader to followers asynchronously. To ensure write is fast. This solution would cause data loss upon leader failure. Another solution should be to have multiple leaders per shard, and the synchronizations between leaders can be based on deterministic rule, like leader_id + timestamp. Alternatively, db system with conflict free replicated data type could work too.
Upon write, user requests get routed to one shard with hashing algorithm like consistent hash, or the system can randomly pick a shard, as long as the write request are evenly distributed among shards. .
Upon read, the api server collect value from all shards and sum them up.
The sum can be stored in cache to speed up request, and need to be frequently synced with db. Write through cache won't be very good because the writer wouldn't know the sum value, besides knowing its own effect; we could have the cache have short TTL like second, then have read requests refresh it every second. So I'd prefer look-aside cache in this case.
We relaxed consistency, to allow eventual consistency, aka user can read a few seconds of outdated counter value; to ensure write requests get processed fast.
Some read requests can be slower than others, due to the fact that we have to query multiple shards of counter value then sum it up; however having multiple shards is necessary to avoid concurrent writes get processed fast.
A single shard leader could experience load issue and can't process write request upon traffic spike. In this case, a metrics based routing algorithm might be better, which will route request to another shard that has more resource.
Since each shard can have multiple replica, read requests can be routed to replica, hence traffic spike can be mitigated.
Generally applications should have rate limiter either in API gateway or at API service, to ensure system availability upon traffic spike.
What are some future improvements you would make? How would you mitigate the failure scenario(s) you described above?