• K
    Persistent Read Cache (Part 2) Data structure for building persistent read cache index · 1f0142ce
    krad 提交于
    Summary:
    We expect the persistent read cache to perform at speeds upto 8 GB/s. In order
    to accomplish that, we need build a index mechanism which operate in the order
    of multiple millions per sec rate.
    
    This patch provide the basic data structure to accomplish that:
    
    (1) Hash table implementation with lock contention spread
        It is based on the StripedHashSet<T> implementation in
        The Art of multiprocessor programming by Maurice Henry & Nir Shavit
    (2) LRU implementation
        Place holder algorithm for further optimizing
    (3) Evictable Hash Table implementation
        Building block for building index data structure that evicts data like files
        etc
    
    TODO:
    (1) Figure if the sharded hash table and LRU can be used instead
    (2) Figure if we need to support configurable eviction algorithm for
    EvictableHashTable
    
    Test Plan: Run unit tests
    
    Subscribers: andrewkr, dhruba, leveldb
    
    Differential Revision: https://reviews.facebook.net/D55785
    1f0142ce
Makefile 44.6 KB