swh:1:snp:5115096b921df712aeb2a08114fede57fb3331fb
Revision 9d9d2965cb4df6163624a31d2b5dd7364813f27f authored by Yueh-Hsuan Chiang on 30 April 2014, 00:13:46 UTC, committed by Yueh-Hsuan Chiang on 30 April 2014, 00:13:46 UTC
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
1 parent f1c9aa6
History
Tip revision: 19076c95aa2bcee55c26fcf0960cc844ad86ee9c authored by Levi Tamasi on 21 January 2021, 22:18:25 UTC
Update HISTORY.md for PR 7888 (#7890)
Tip revision: 19076c9
File Mode Size
build_tools
coverage
db
doc
hdfs
helpers
include
java
linters
port
table
tools
util
utilities
.arcconfig -rw-r--r-- 246 bytes
.clang-format -rw-r--r-- 138 bytes
.gitignore -rw-r--r-- 317 bytes
CONTRIBUTING.md -rw-r--r-- 759 bytes
HISTORY.md -rw-r--r-- 5.3 KB
INSTALL.md -rw-r--r-- 3.3 KB
LICENSE -rw-r--r-- 1.6 KB
Makefile -rw-r--r-- 20.3 KB
PATENTS -rw-r--r-- 1.4 KB
README -rw-r--r-- 2.9 KB
ROCKSDB_LITE.md -rw-r--r-- 1020 bytes

README

back to top