File ConcurrentCuckooTable.h

↰ Parent directory (ADS/concurrent)

A hash table that many threads read and change at once, beyond the book: the cuckoo hashing with buckets of 4 places and tags of 8 bits of BucketCuckooTable [see File BucketCuckooTable.h], made concurrent with one lock per region of buckets and, for keys and values that can be read atomically, lookups that take no lock at all.

Definition (ADS/concurrent/ConcurrentCuckooTable.h)

Detailed Description

A key with the hash h has two buckets, :math:` b_1 ` given by the top bits of h and :math:`[ b_2 = b_1 oplus left( leftlfloor g( t ) / 2^{64 - r} rightrfloor

vee 1 right) ` for the tag t of h, a mixing g of the tag (the partial-key cuckoo hashing of MemC3) and regions of :math:` R = 2^r ` buckets, so that the other bucket of a key follows from its bucket and its tag and both are in the same region.

The B buckets form :math:` P = min( S , max( 1 , B / 256 ) ) ` regions of :math:` R = B / P ` buckets each, :math:` S = 2048 , and a region has one lock (the lock striping of Herlihy and Shavit, with a stripe per region instead of a stripe of scattered buckets). Each lock is a counter of versions on a line of cache of its own, odd while held, taken by a compare-and-swap from an even value after spinning on plain loads, with the pause of the processor and, after 64 rounds, a yield to the scheduler. An operation on a key thus takes one lock, that of its region, and the cuckoo path of an insertion, which never leaves the region, is searched in breadth and its keys moved under that lock alone, with nothing to check again (where Li et al. search without locks and lock two buckets per move). Only the doubling, reserve(), clear(), forEach() and consistent() take more locks, all those in use, in increasing order from the stripe 0: a thread that holds the stripe i and waits for the stripe j has :math: i < j , so that a cycle of waits :math: i_1 < dots < i_m < i_1 ` cannot exist, whence no deadlock. With uniform keys, two operations contend for a lock with probability :math:` 1 / P `.

When the keys and the values are trivially copyable and std::atomic_ref reads and writes them without locks (e.g., integers and pointers; optimistic is then true), a lookup is a read under the version of the region (a seqlock): it reads the even version v, the table in use, the tags and the places of the key with relaxed atomic loads, and returns what it read if the version is still v after an acquire fence; otherwise it tries again, and takes the lock after 4 tries. A writer makes the version odd and issues a release fence before its relaxed atomic stores, so that a reader that sees one of them sees the odd version afterwards (the analysis of Boehm). No access is a data race in the sense of C++, and a lookup costs no atomic read-modify-write and no store to a shared line. The tables replaced by a doubling are kept until the table is destroyed, since a reader may still be on one; with :math:` B_0 < dots < B_k ` buckets they total :math:` sum_{j < k} B_j < B_k `, less than the table in use. Other keys and values (e.g., std::string) are read under the lock, and the tables replaced are freed at once.

A lookup, an insertion or a removal fetches ahead, at once, the tags of both buckets of its key and the line of the places of the first one (the 4 places of a bucket are aligned to share a line of cache when their size is a power of 2 up to 64 bytes), so that the misses overlap; the places of the second bucket, where fewer keys are, are read only when a tag matches there. The tags and the places of a table of 2 MB or more are on transparent huge pages [see File HugePageAllocator.h], so that the random accesses miss the TLB once per 2 MB instead of once per 4 KB (Navarro et al.).

An insertion puts the new key in a free place of its two buckets if any; otherwise it searches in breadth, from the two buckets, a path of at most :math:` L = 5 ` moves that ends in a bucket with a free place, and moves its keys from the end. A search in breadth over buckets of B places that looks at M places finds a path of at most :math:`[ L = leftlceil log_B left( frac{M}{2} - frac{M}{2B} + 1 right)

rightrceil ` moves, since its two trees have :math:` 2 B^l ` places at the depth l and :math:` 2B( B^L - 1 ) / ( B - 1 ) geq M , against the M / 2 moves of a search in depth (Li et al.); the search stops at :math: L = 5 , the value for :math: M = 2000 ` and B = 4, or at 1024 buckets, all in the region, whose tags are a block of 8R bytes.

The table doubles when a region would pass the load 0.98 or no path is found: the thread takes all the locks in use, those of the new regions too before the new table is seen, checks that no other thread has doubled the table in the meantime, and places every pair again in a new table (stop-the-world). With 2 buckets per key and 4 places per bucket, the cuckoo hashing of n random keys succeeds with high probability while :math:` n / ( 4B ) < c^*_{2,4} approx 0.9803 , the threshold of the 4-orientability of the random graphs (Cain, Sanders and Wormald), here in each region; a region of :math: 4R ` places holds a binomial number of the n keys, of mean :math:` mu = n / P ` and standard deviation :math:` sqrt{ mu ( 1 - 1 / P ) } , i.e., a relative deviation of about :math: 1 / sqrt{ 4 R alpha } ` at the load :math:` alpha , 3.3 % for :math: R = 256 ` and :math:` alpha = 0.9 , so that the fullest region of a large table reaches 0.98 at a mean load of about 0.88 to 0.92 (the restriction of the choices to a part of the table, there a page, is also in Dietzfelbinger, Mitzenmacher and Rink). The doublings cost :math: O( 1 ) ` amortized per insertion. A doubling that would leave the table of at least 256 places less than 1/16 full throws std::length_error, which happens only when more than 8 keys share both buckets at every size, e.g., by equal hashes; the table is unchanged.

Each region counts its pairs, under its lock, so that size() is the sum of P counters read without locks: exact when no operation runs, and otherwise an estimate, since the counters are read at different moments. The operations of a single key are linearizable at the moment they hold the lock of its region, or at the second read of the version for a lookup without locks; reserve(), clear(), forEach() and consistent() take all the locks, and forEach() thus visits the pairs of one moment. Maier, Sanders and Dementiev compare the concurrent hash tables, those that grow without locks among them.

The hash of a key is h( k ), taken as it is if H declares is_avalanching [see File FastHash.h] and mixed by hashWord() otherwise. The keys and the values must be default constructible and movable.

The contracts [see File Contract.h]: the invariant is that each key is in one of its two buckets with its tag, checked on the buckets of the key of the operation under its lock; consistent() checks it on every pair, with the counters of the regions, under all the locks. No postcondition is stated on the key of an operation, since another thread may change it as soon as the lock is released. The operations are defined in ConcurrentCuckooTable.tpp.

  1. Fan, D. G. Andersen, M. Kaminsky, MemC3: compact and concurrent MemCache with dumber caching and smarter hashing, Proceedings of NSDI 2013, 371-384, 2013 (the partial-key cuckoo hashing)

  1. Herlihy, N. Shavit, The Art of Multiprocessor Programming, Morgan Kaufmann, 2008, chapter 13 (the lock striping)

  1. Li, D. G. Andersen, M. Kaminsky, M. J. Freedman, Algorithmic improvements for fast concurrent cuckoo hashing, Proceedings of EuroSys 2014, 27, 2014, doi:10.1145/2592798.2592820

H.-J. Boehm, Can seqlocks get along with programming language memory models?, Proceedings of MSPC 2012, 12-20, 2012, doi:10.1145/2247684.2247688

  1. Navarro, S. Iyer, P. Druschel, A. Cox, Practical, transparent operating system support for superpages, Proceedings of OSDI 2002, 89-104, 2002

    1. Cain, P. Sanders, N. Wormald, The random graph threshold for k-orientiability and a fast algorithm for optimal multiple-choice allocation, Proceedings of SODA 2007, 469-476, 2007, https://publikationen.bibliothek.kit.edu/1000009500

  1. Dietzfelbinger, M. Mitzenmacher, M. Rink, Cuckoo hashing with pages, Proceedings of ESA 2011, 615-627, 2011, https://arxiv.org/abs/1104.5111

  1. Maier, P. Sanders, R. Dementiev, Concurrent hash tables: fast and general(?)!, ACM Transactions on Parallel Computing 5(4), 16, 2019, doi:10.1145/3309206

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Namespaces

Classes