• Y
    Add a new mem-table representation based on cuckoo hash. · 9d9d2965
    Yueh-Hsuan Chiang 提交于
    Summary:
    = Major Changes =
    * Add a new mem-table representation, HashCuckooRep, which is based cuckoo hash.
      Cuckoo hash uses multiple hash functions.  This allows each key to have multiple
      possible locations in the mem-table.
    
      - Put: When insert a key, it will try to find whether one of its possible
        locations is vacant and store the key.  If none of its possible
        locations are available, then it will kick out a victim key and
        store at that location.  The kicked-out victim key will then be
        stored at a vacant space of its possible locations or kick-out
        another victim.  In this diff, the kick-out path (known as
        cuckoo-path) is found using BFS, which guarantees to be the shortest.
    
     - Get: Simply tries all possible locations of a key --- this guarantees
       worst-case constant time complexity.
    
     - Time complexity: O(1) for Get, and average O(1) for Put if the
       fullness of the mem-table is below 80%.
    
     - Default using two hash functions, the number of hash functions used
       by the cuckoo-hash may dynamically increase if it fails to find a
       short-enough kick-out path.
    
     - Currently, HashCuckooRep does not support iteration and snapshots,
       as our current main purpose of this is to optimize point access.
    
    = Minor Changes =
    * Add IsSnapshotSupported() to DB to indicate whether the current DB
      supports snapshots.  If it returns false, then DB::GetSnapshot() will
      always return nullptr.
    
    Test Plan:
    Run existing tests.  Will develop a test specifically for cuckoo hash in
    the next diff.
    
    Reviewers: sdong, haobo
    
    Reviewed By: sdong
    
    CC: leveldb, dhruba, igor
    
    Differential Revision: https://reviews.facebook.net/D16155
    9d9d2965
memtable.h 7.4 KB