RIPQ: Advanced Photo Caching on Flash for Facebook

Abstract:

Facebook uses flash devices extensively in its photocaching
stack. The key design challenge for an effi-
cient photo cache on flash at Facebook is its workload:
many small random writes are generated by inserting
cache-missed content, or updating cache-hit
content for advanced caching algorithms. The Flash
Translation Layer on flash devices performs poorly
with such a workload, lowering throughput and decreasing
device lifespan. Existing coping strategies
under-utilize the space on flash devices, sacrificing
cache capacity, or are limited to simple caching algorithms
like FIFO, sacrificing hit ratios.
We overcome these limitations with the novel
Restricted Insertion Priority Queue (RIPQ) framework
that supports advanced caching algorithms
with large cache sizes, high throughput, and long
device lifespan. RIPQ aggregates small random
writes, co-locates similarly prioritized content, and
lazily moves updated content to further reduce device
overhead. We show that two families of advanced
caching algorithms, Segmented-LRU and
Greedy-Dual-Size-Frequency, can be easily implemented
with RIPQ. Our evaluation on Facebook’s
photo trace shows that these algorithms running on
RIPQ increase hit ratios up to ~20% over the current
FIFO system, incur low overhead, and achieve
high throughput.