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
Tip revision: 19076c95aa2bcee55c26fcf0960cc844ad86ee9c authored by Levi Tamasi on 21 January 2021, 22:18:25 UTC
Update HISTORY.md for PR 7888 (#7890)
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 |
Computing file changes ...