| /rocksdb-6.9/docs/_posts/ |
| D | 2018-08-23-data-block-hash-index.markdown | 9 …hash table to the end of the data block for efficient indexing. It is backward compatible with the…
26 kDataBlockBinaryAndHash = 1, // additional hash index
29 // Set to kDataBlockBinaryAndHash to enable hash index
45 
47 We implemented a hash map at the end of the block to index the key to reduce the CPU overhead of th…
49 
52 …hash bucket when storing the location of a key (or more precisely, the restart index of the restar…
58 
110 Orange bars are representing our hash index performance. We use a hash util ratio of 1.0 in this te…
112 
[all …]
|
| D | 2014-09-12-cuckoo.markdown | 46 …le optimizations, including a cache friendly cuckoo hash algorithm. Cuckoo Hashing uses multiple h…
50 …hashes of the key _h1(k), ..., __hn__(k)_. We insert the key in the first hash location that is fr…
52 …hash table and there is an edge from bucket _A_ to bucket _B_ if the element stored in bucket _A_ …
56 …hash functions required and hence the number of memory accesses. In our experiments, with a hash u…
64 …* If the key is not present in first hash location, we jump to second hash location which may not …
67 … prefetching strategy - prefetching all hash locations for a key is wasteful. But prefetching only…
71 …hash location - _h1(k)_, we try to insert it in next few buckets, _h1(k)+1, _h1(k)+2, _..., h1(k)+…
74 …hash utilization, we found that 85% of keys are accommodated in first Cuckoo Block. Prefetching th…
|
| D | 2014-06-23-plaintable-a-new-file-format.markdown | 22 … query performance is not as good as you would see with a nicely-designed hash table, but they are…
26 To meet our requirements, given that only hash prefix iterating is needed, we made two decisions:
28 1. to use a hash index, which is
31 Having addressed our latency goal, the next task was to design a very compact hash index to minimiz…
35 1. Since our file is immutable, we can accurately estimate the number of hash buckets needed.
|
| D | 2014-06-27-rocksdb-3-2-release.markdown | 27 …* Add two paramters to NewHashLinkListRepFactory() for logging on too many entries in a hash bucke…
30 …dex_allow_collision. When enabled, prefix hash index for block-based table will not store prefix a…
|
| D | 2014-05-22-rocksdb-3-1-release.markdown | 14 …* [Materialized hash index](https://github.com/facebook/rocksdb/commit/0b3d03d026a7248e438341264b4…
20 We released 3.1 so fast after 3.0 because one of our internal customers needed materialized hash in…
|
| D | 2014-09-15-rocksdb-3-5-release.markdown | 19 …Options.total_order_seek to force total order seek when block-based table is built with hash index.
35 …4. OptimizeForPointLookup() takes one parameter for block cache size. It now builds hash index, bl…
|
| /rocksdb-6.9/cache/ |
| D | sharded_cache.cc | 49 uint32_t hash = HashSlice(key); in Insert() local
50 return GetShard(Shard(hash)) in Insert()
51 ->Insert(key, hash, value, charge, deleter, handle, priority); in Insert()
55 uint32_t hash = HashSlice(key); in Lookup() local
56 return GetShard(Shard(hash))->Lookup(key, hash); in Lookup()
60 uint32_t hash = GetHash(handle); in Ref() local
61 return GetShard(Shard(hash))->Ref(handle); in Ref()
65 uint32_t hash = GetHash(handle); in Release() local
66 return GetShard(Shard(hash))->Release(handle, force_erase); in Release()
70 uint32_t hash = HashSlice(key); in Erase() local
[all …]
|
| D | clock_cache.cc | 181 uint32_t hash; member
247 static size_t hash(const CacheKey& a) { in hash() function
282 void Erase(const Slice& key, uint32_t hash) override;
283 bool EraseAndConfirm(const Slice& key, uint32_t hash,
514 table_.erase(CacheKey(handle->key, handle->hash)); in TryEvict()
592 handle->hash = hash; in Insert()
599 if (table_.find(accessor, CacheKey(key, hash))) { in Insert()
637 if (!table_.find(accessor, CacheKey(key, hash))) { in Lookup()
650 if (hash != handle->hash || key != handle->key) { in Lookup()
673 EraseAndConfirm(key, hash, &context); in Erase()
[all …]
|
| D | lru_cache.cc | 35 return *FindPointer(key, hash); in Lookup()
55 LRUHandle** ptr = FindPointer(key, hash); in Remove()
65 LRUHandle** ptr = &list_[hash & (length_ - 1)]; in FindPointer()
66 while (*ptr != nullptr && ((*ptr)->hash != hash || key != (*ptr)->key())) { in FindPointer()
84 uint32_t hash = h->hash; in Resize() local
127 table_.Remove(old->key(), old->hash); in EraseUnRefEntries()
242 table_.Remove(old->key(), old->hash); in EvictFromLRU()
273 LRUHandle* e = table_.Lookup(key, hash); in Lookup()
317 table_.Remove(e->key(), e->hash); in Release()
355 e->hash = hash; in Insert()
[all …]
|
| D | lru_cache.h | 61 uint32_t hash; member
161 LRUHandle* Lookup(const Slice& key, uint32_t hash);
163 LRUHandle* Remove(const Slice& key, uint32_t hash);
182 LRUHandle** FindPointer(const Slice& key, uint32_t hash);
213 virtual Status Insert(const Slice& key, uint32_t hash, void* value, in ALIGN_AS()
216 virtual Cache::Handle* Lookup(const Slice& key, uint32_t hash) override; in ALIGN_AS()
220 virtual void Erase(const Slice& key, uint32_t hash) override; in ALIGN_AS()
|
| D | sharded_cache.h | 29 virtual Status Insert(const Slice& key, uint32_t hash, void* value,
32 virtual Cache::Handle* Lookup(const Slice& key, uint32_t hash) = 0;
35 virtual void Erase(const Slice& key, uint32_t hash) = 0;
98 uint32_t Shard(uint32_t hash) { in Shard() argument
100 return (num_shard_bits_ > 0) ? (hash >> (32 - num_shard_bits_)) : 0; in Shard()
|
| /rocksdb-6.9/util/ |
| D | crc32c_test.cc | 147 uint64_t hash = FNV_64_HASH_START) { in fnv64_buf() argument
152 hash += (hash << 1) + (hash << 4) + (hash << 5) + (hash << 7) + in fnv64_buf()
153 (hash << 8) + (hash << 40); in fnv64_buf()
154 hash ^= char_buf[i]; in fnv64_buf()
156 return hash; in fnv64_buf()
|
| D | hash.h | 86 inline uint32_t fastrange32(uint32_t hash, uint32_t range) { in fastrange32() argument
87 uint64_t product = uint64_t{range} * hash; in fastrange32()
95 inline size_t fastrange64(uint64_t hash, size_t range) { in fastrange64() argument
98 __uint128_t wide = __uint128_t{range} * hash; in fastrange64()
107 uint64_t tmp = uint64_t{range64 & 0xffffFFFF} * uint64_t{hash & 0xffffFFFF}; in fastrange64()
109 tmp += uint64_t{range64 & 0xffffFFFF} * uint64_t{hash >> 32}; in fastrange64()
111 uint64_t tmp2 = uint64_t{range64 >> 32} * uint64_t{hash & 0xffffFFFF}; in fastrange64()
115 tmp += uint64_t{range64 >> 32} * uint64_t{hash >> 32}; in fastrange64()
|
| D | dynamic_bloom.h | 60 void AddHash(uint32_t hash);
63 void AddHashConcurrently(uint32_t hash);
71 bool MayContainHash(uint32_t hash) const;
88 void AddHash(uint32_t hash, const OrFunc& or_func);
99 inline void DynamicBloom::AddHash(uint32_t hash) { in AddHash() argument
100 AddHash(hash, [](std::atomic<uint64_t>* ptr, uint64_t mask) { in AddHash()
106 inline void DynamicBloom::AddHashConcurrently(uint32_t hash) { in AddHashConcurrently() argument
107 AddHash(hash, [](std::atomic<uint64_t>* ptr, uint64_t mask) { in AddHashConcurrently()
|
| D | hash.cc.d | 1 util/hash.cc.d util/hash.o: util/hash.cc util/coding.h \
14 include/rocksdb/statistics.h util/hash.h util/util.h util/xxhash.h
|
| D | filter_bench.cc | 375 uint32_t hash = GetSliceHash(kms_[0].Get(filter_id, i)); in Go() local
376 info.plain_table_bloom_->AddHash(hash); in Go()
439 uint32_t hash = GetSliceHash(kms_[0].Get(info.filter_id_, j)); in Go() local
440 ALWAYS_ASSERT(info.plain_table_bloom_->MayContainHash(hash)); in Go()
448 uint32_t hash = in Go() local
450 fps += info.plain_table_bloom_->MayContainHash(hash); in Go()
628 uint32_t hash = GetSliceHash(batch_slices[i]); in RandomQueryTest() local
629 may_match = info.plain_table_bloom_->MayContainHash(hash); in RandomQueryTest()
|
| D | xxhash.cc | 653 XXH_PUBLIC_API void XXH32_canonicalFromHash(XXH32_canonical_t* dst, XXH32_hash_t hash) in XXH32_canonicalFromHash() argument
656 if (XXH_CPU_LITTLE_ENDIAN) hash = XXH_swap32(hash); in XXH32_canonicalFromHash()
657 memcpy(dst, &hash, sizeof(*dst)); in XXH32_canonicalFromHash()
1136 XXH_PUBLIC_API void XXH64_canonicalFromHash(XXH64_canonical_t* dst, XXH64_hash_t hash) in XXH64_canonicalFromHash() argument
1139 if (XXH_CPU_LITTLE_ENDIAN) hash = XXH_swap64(hash); in XXH64_canonicalFromHash()
1140 memcpy(dst, &hash, sizeof(*dst)); in XXH64_canonicalFromHash()
|
| D | hash_test.cc | 364 uint32_t fastrange32(uint32_t hash, uint32_t range) { in fastrange32() argument
365 return ROCKSDB_NAMESPACE::fastrange32(hash, range); in fastrange32()
369 size_t fastrange64(uint64_t hash, size_t range) { in fastrange64() argument
370 return ROCKSDB_NAMESPACE::fastrange64(hash, range); in fastrange64()
|
| D | xxh3p.h | 1368 XXH128_canonicalFromHash(XXH128_canonical_t* dst, XXH128_hash_t hash) in XXH128_canonicalFromHash() argument
1372 hash.high64 = XXH_swap64(hash.high64); in XXH128_canonicalFromHash()
1373 hash.low64 = XXH_swap64(hash.low64); in XXH128_canonicalFromHash()
1375 memcpy(dst, &hash.high64, sizeof(hash.high64)); in XXH128_canonicalFromHash()
1376 memcpy((char*)dst + sizeof(hash.high64), &hash.low64, sizeof(hash.low64)); in XXH128_canonicalFromHash()
|
| /rocksdb-6.9/tools/block_cache_analyzer/ |
| D | block_cache_pysim.py | 143 self.hash = hash
208 def insert(self, key, hash, value): argument
215 index = hash % len(self.table)
222 if self.table[index][i].hash == hash and self.table[index][i].key == key:
269 def delete(self, key, hash): argument
270 index = hash % len(self.table)
278 and self.table[index][i].hash == hash
296 def lookup(self, key, hash): argument
297 index = hash % len(self.table)
303 and self.table[index][i].hash == hash
[all …]
|
| /rocksdb-6.9/table/plain/ |
| D | plain_table_index.cc | 17 inline uint32_t GetBucketIdFromHash(uint32_t hash, uint32_t num_buckets) { in GetBucketIdFromHash() argument
19 return hash % num_buckets; in GetBucketIdFromHash()
56 void PlainTableIndexBuilder::IndexRecordList::AddRecord(uint32_t hash, in AddRecord() argument
63 new_record.hash = hash; in AddRecord()
129 uint32_t cur_hash = index_record->hash; in BucketizeIndexes()
|
| D | plain_table_bloom.h | 47 void AddHash(uint32_t hash);
50 bool MayContainHash(uint32_t hash) const;
52 void Prefetch(uint32_t hash);
|
| D | plain_table_bloom.cc | 70 for (auto hash : keys_hashes) { in AddKeysHashes() local
71 bloom_.AddHash(hash); in AddKeysHashes()
|
| /rocksdb-6.9/table/block_based/ |
| D | filter_policy.cc | 44 uint64_t hash = GetSliceHash64(key); in AddKey() local
45 if (hash_entries_.empty() || hash != hash_entries_.back()) { in AddKey()
46 hash_entries_.push_back(hash); in AddKey()
259 uint32_t hash = BloomHash(key); in AddKey() local
260 if (hash_entries_.size() == 0 || hash != hash_entries_.back()) { in AddKey()
261 hash_entries_.push_back(hash); in AddKey()
403 uint32_t hash = BloomHash(key); in MayMatch() local
406 hash, num_lines_, data_, /*out*/ &byte_offset, log2_cache_line_size_); in MayMatch()
408 hash, num_probes_, data_ + byte_offset, log2_cache_line_size_); in MayMatch()
|
| /rocksdb-6.9/utilities/persistent_cache/ |
| D | block_cache_tier_metadata.h | 88 return std::hash<uint32_t>()(rec->cacheid()); in operator()
107 return std::hash<std::string>()(node->key_); in operator()
|