Most interesting is a new caching algorithm that outperforms LFU and LRU:<p>S4LRU: Quadruply-segmented LRU. Four queues are maintained at levels 0 to 3. On a cache miss, the item is inserted at the head of queue 0. On a cache hit, the item is moved to the head of the next higher queue (items in queue 3 move to the head of queue 3). Each queue is allocated 1/4 of the total cache size and items are evicted from the tail of a queue to the head of the next lower queue to maintain the size invariants. Items evicted from queue 0 are evicted from the cache.<p>Paper: <a href="http://www.cs.cornell.edu/~qhuang/papers/sosp_fbanalysis.pdf" rel="nofollow">http://www.cs.cornell.edu/~qhuang/papers/sosp_fbanalysis.pdf</a>
Ttheir origin cache handled but 5% of all traffic and did very little to help the system. The big takeaway should be to understand the usefullness of every level, both in terms of added cost in maintaining, complexity and equipment so that you know where to invest your energy and what sorts of gains you cab have from that investment. Very nice write up.
Interesting that they spend so much time thinking about photo caching, considering that they recompress them down to quality 70 JPEGs, making them not worth looking at in the first place. Everybody involved with that decision at Facebook should be prosecuted for crimes against image quality.