Loading...
The counter will be triggered by user actions on a massive scale social network. Use youtube as example.
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.
Read should return as fresh data as possible.
Counter value should be accurate.
Eventual consistency.
Highly available, scalable.
Assumption:
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 prefer a nosql db with key-value store like access interface(Cassandra for example), over in-memory db like redis, as not every counter will be read frequently, hence using in-memory only storage would be a waste of resource. DB with persistence might be slower than Redis, but is more cost-effective.
We can use Redis to cache hot counter data to balance latency vs cost.
Stateless API service that takes get/post requests from user.
Request hitting Counter service will be protected via rate limiter in API gateway. API servers are stateless and globally available.
Partitioned, replicated nosql db system, storing counters. The db is globally available, aka, replicated across data centers.
Redis as look aside cache for API servers to store and retrieve hot counter values from db.
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.
Counter Service
The service keeps updated list of DB servers, logical shard to physical shard mapping, as well as counter to number of shard mapping.
Upon write, Counter service calls finds the right DB host for the counter to increment the value, based on the above information.
Upon read, if the value is not present in cache, the api server collect value from all shards and sum them up and store the value in Redis Cache.
DB Design
Ideally the db will use leaderless or multi-leader replication to ensure high availability, as well as CRDT to ensure data consistency.
1. Handling Write Request
1.1 To ensure normal write requests are fast, each data center has at least a leader per shard. Write requests are routed to the nearest data center. Synchronization between leader and followers within the same data center is fast. Data is asynchronously replicated between data centers.
This will raise issue in data consistency that I'll cover later.
1.2 For hot counter, a routing service will route the request to an available shard, hence the write load is split across multiple nodes, and write contention is reduced.
2.Handling Read
Read request could be served from replica to alleviate load from leaders.
3.Handling Data Consistency
DB with Last write win like Cassandra or DynamoDB isn't a good choice as this will cause significant data loss when leaders concurrently receives lots of writes during write spike, and we want data to be accurate.
The db should adopt conflict free replicated data type(CRDT) to sync up between leaders. This is particularly suitable for counter operations, as number of increment and decrement will converge eventually across leaders, regardless of sequence.
Redis Cache Design
Cache Invalidation
Invalidate cache upon every write request is bad idea, which will cause write contention, especially upon allowed traffic burst. Instead, we'll have do the invalidation asynchronously.
We can have a worker set that processes DB changes via techniques like CDC, and remove the counter that was recently changed from cache.
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.
What are some future improvements you would make? How would you mitigate the failure scenario(s) you described above?
Potentially have a request table, to record the latest committed write request. This ensure that a single request doesn't get commited twice. This will help implement idempotency in write path, to avoid double counting from partial failure.