Q: What is the amount of data that we need to cache?
A: Let's assume we are looking to cache on the scale of Google or Twitter. The total size of the cache would be a few TBs.
A: Let's assume we are looking to cache on the scale of Google or Twitter. The total size of the cache would be a few TBs.
Q: What should be the eviction strategy?
A: It is possible that we might get entries when we would not have space to accommodate new entries. In such cases, we would need to remove one or more entries to make space for the new entry.
Which entry should we evict? There are multiple strategies possible. Following are a few standard ones :
FIFO ( First in, first out ) : The entry that was first added to the queue would be evicted/removed first. In other words, Elements are evicted in the same order as they come in. This is the simplest to implement and performs well when either, access pattern is completely random ( All elements are equally probably to be accessed ) OR if the use of an element makes it less likely to be used in the future.
LRU ( Least Recently Used ) : Default. As the name suggests, the element evicted is the ones which has the oldest last access time. The last accessed timestamp is updated when an element is put into the cache or an element is retrieved from the cache with a get call. This is by far the most popular eviction strategy.
LFU ( Least Frequently Used ) : Again, as the name suggests, every entry has a frequency associated with it. At the time of eviction, the entry with lowest frequency is evicted. This is most effective in cases when most of access is limited to a very small portion of the data ( pareto distribution ).
As you can see, every eviction strategy has its own set of cases when they are most effective. The choice of which eviction strategy to choose is largely dependent on the expected access pattern. We will go with the default here which is LRU.
A: It is possible that we might get entries when we would not have space to accommodate new entries. In such cases, we would need to remove one or more entries to make space for the new entry.
Which entry should we evict? There are multiple strategies possible. Following are a few standard ones :
FIFO ( First in, first out ) : The entry that was first added to the queue would be evicted/removed first. In other words, Elements are evicted in the same order as they come in. This is the simplest to implement and performs well when either, access pattern is completely random ( All elements are equally probably to be accessed ) OR if the use of an element makes it less likely to be used in the future.
LRU ( Least Recently Used ) : Default. As the name suggests, the element evicted is the ones which has the oldest last access time. The last accessed timestamp is updated when an element is put into the cache or an element is retrieved from the cache with a get call. This is by far the most popular eviction strategy.
LFU ( Least Frequently Used ) : Again, as the name suggests, every entry has a frequency associated with it. At the time of eviction, the entry with lowest frequency is evicted. This is most effective in cases when most of access is limited to a very small portion of the data ( pareto distribution ).
As you can see, every eviction strategy has its own set of cases when they are most effective. The choice of which eviction strategy to choose is largely dependent on the expected access pattern. We will go with the default here which is LRU.
Q: What should be the access pattern for the given cache?
A: There are majorly three kinds of caching systems:
Write through cache: This is a caching system where writes go through the cache and write is confirmed as success only if writes to DB and the cache BOTH succeed. This is really useful for applications which write and re-read the information quickly. However, write latency will be higher in this case as there are writes to 2 separate systems.
Write around cache: This is a caching system where write directly goes to the DB. The cache system reads the information from DB incase of a miss. While this ensures lower write load to the cache and faster writes, this can lead to higher read latency incase of applications which write and re-read the information quickly.
Write back cache: This is a caching system where the write is directly done to the caching layer and the write is confirmed as soon as the write to the cache completes. The cache then asynchronously syncs this write to the DB. This would lead to a really quick write latency and high write throughput. But, as is the case with any non-persistent / in-memory write, we stand the risk of losing the data incase the caching layer dies. We can improve our odds by introducing having more than one replica acknowledging the write ( so that we don’t lose data if just one of the replica dies ).
More details at http://www.computerweekly.com/feature/Write-through-write-around-write-back-Cache-explained.
Let's assume we are building a write around cache here.
A: There are majorly three kinds of caching systems:
Write through cache: This is a caching system where writes go through the cache and write is confirmed as success only if writes to DB and the cache BOTH succeed. This is really useful for applications which write and re-read the information quickly. However, write latency will be higher in this case as there are writes to 2 separate systems.
Write around cache: This is a caching system where write directly goes to the DB. The cache system reads the information from DB incase of a miss. While this ensures lower write load to the cache and faster writes, this can lead to higher read latency incase of applications which write and re-read the information quickly.
Write back cache: This is a caching system where the write is directly done to the caching layer and the write is confirmed as soon as the write to the cache completes. The cache then asynchronously syncs this write to the DB. This would lead to a really quick write latency and high write throughput. But, as is the case with any non-persistent / in-memory write, we stand the risk of losing the data incase the caching layer dies. We can improve our odds by introducing having more than one replica acknowledging the write ( so that we don’t lose data if just one of the replica dies ).
More details at http://www.computerweekly.com/feature/Write-through-write-around-write-back-Cache-explained.
Let's assume we are building a write around cache here.