Hello friends, Lets discuss the following question. I'll attempt to share my thoughts.
Design question: Given an internet server with 12 cores , 60 GB of memory and a big network pipe (he specified, but I can't remember the actual value), how would you implement a caching service with 3 functions that boils down to void set(string key, byte[] data); byte[] get(string key) void delete(string key) where the key is between 1 and 255 characters, and where the data block can be up to 1 MB. Further, how would you design the system to be effective when some key becomes part of something that goes viral, such that there is suddenly a much higher rate of requests for it.
The following is my response. What exactly is missing in designing such systems with specific numbers in requirement? Some help would be appreciated from folks esp who have encountered/asked these type of problems before. How do you expect the candidate to proceed or what information is expected in these designs?
Requirement Gathering
It is not known what the cache is going to be used for. The byte[] data suggests some specific binary objects like scaled-down pics like profile images etc. However, it seems like the requirements are derived from the constraints that the question has.
Thinking about System/Functional requirements
As opposed to other questions, where one has to estimate traffic and data requirements per request, this one states the resources in advance. This can impose an upperbound or throughput of the system that we might have to deal with. Lets talk memory.
The value we're storing in cache is not String data but byte[] data. Simplistically, the key is 255 chars or 256 Bytes (assuming UTF-8 English chars only) and the 'value' or data is '1 MB'. With room for other metadata we can assume '1.5 MB' per single get Request. 60 GB can accommodate 40K entries assuming 60GB/1.5MB.
Given a network capacity we can have an upper limit on the throughput given infinite computation and the memory constraint of 60GB. Assuming it is 100Gbps, this can be around 12.5GBps which is 12.5GB/1.5MB = ~8300 requests per second
However, this is the upper limit given we have enough CPU to handle this. With 12 cores, I think the interviewer would like us to estimate the throughput??? (I'm not very sure)
Assuming a 80/20 read/write ratio, we can assume 80% of the requests will not be writing to the memory. Perhaps we can do something with this??? (Brainstorming encouraged)
Non-functional requirements
Consistency: I think for any cache, consistency has to be favored over availability in the CAP theorem. For reads following writes, a cache is often considered as the source of truth in many applications.
Availability: While we'd like our cache instance to be highly available the fact that we have only 1 server instance kinda limits our availability and couples us with it. Not sure what else to say here.
Data Partitioning: I'm not really sure but perhaps the cache memory of 60GB can be partitioned into 12 partitions each exclusively serviced by a specific core. I'm not sure if we can use consistent hashing directly but the idea does sound relatable.
Cache eviction strategy
Common caching strategy like LRU would work well with this but perhaps it is worth discussing difference between LRU and LFU?? Is there any other caching strategy for byte[] data???
Product choice
Redis or Memcached??? It depends on whether we'd like to go for the simplicity of memcached for just a volatile key-value storage or if we'd like to go for the datasrtucture, database, on-disk storage, message broker etc of Redis.
12 core CPU strategy
Can we perhaps think in partitioning these 12 cores such the based on the hash each of the 12 cores handle the hash equally distributed? (I think more discussion is needed here)
For Viral situations
So in Viral scenarios, there's going to be assymetric demand for some keys. But I'm not sure what we can do about it. Honestly, I cannot think of this scenario except that some byte[] data can be perhaps globally distributed in CDNs??? Perhaps the data partitioning strategy can be tuned???