#concurrent #hashmap #map #tree #index

scc

Scalable concurrent data structures for database management systems

16 releases

0.4.14 Apr 2, 2021
0.4.12 Mar 28, 2021
0.3.11 Dec 29, 2020
0.3.1 Nov 27, 2020

#64 in Concurrency

Download history 78/week @ 2021-01-13 70/week @ 2021-01-20 45/week @ 2021-01-27 64/week @ 2021-02-03 105/week @ 2021-02-10 118/week @ 2021-02-17 65/week @ 2021-02-24 64/week @ 2021-03-03 52/week @ 2021-03-10 37/week @ 2021-03-17 126/week @ 2021-03-24 90/week @ 2021-03-31 57/week @ 2021-04-07 109/week @ 2021-04-14 86/week @ 2021-04-21 3/week @ 2021-04-28

320 downloads per month

Apache-2.0

310KB
6.5K SLoC

Scalable Concurrent Containers

The crate offers highly scalable concurrent containers written in the Rust language.

scc::HashMap

scc::HashMap is a scalable in-memory unique key-value store that is targeted at highly concurrent heavy workloads. It does not distribute data to a fixed number of shards as most concurrent hash maps do, instead it has only one single dynamically resizable array of entry metadata. The entry metadata, called a cell, is a 64-byte data structure for managing an array of consecutive 32 key-value pairs. The fixed size key-value pair array is only reachable through its corresponding cell, and its entries are protected by a mutex in the cell; this means that the number of mutex instances increases as the hash map grows, thereby reducing the chance of multiple threads trying to acquire the same mutex. In addition to the array and mutex, the metadata cell has a linked list of key-value pair arrays for hash collision resolution. Apart from scc::HashMap having a single cell array, it automatically enlarges and shrinks the capacity of the cell array without blocking other operations and threads; the cell array is resized without relocating all the entries at once, instead it delegates the rehashing workload to future access to the data structure to keep the latency predictable.

Performance

Test setup

  • OS: SUSE Linux Enterprise Server 15 SP1
  • CPU: Intel(R) Xeon(R) CPU E7-8880 v4 @ 2.20GHz x 4
  • RAM: 1TB
  • Rust: 1.50.0
  • SCC: 0.4.11
  • HashMap<usize, usize, RandomState> = Default::default()

Test data

  • Each thread is assigned a disjoint range of u64 integers.
  • The entropy of the test input is low, however it does not undermine the test result as scc::HashMap shuffles the hash value to maximize entropy.
  • The performance test code asserts the expected outcome of each operation, and the post state of the hash map instance.

Test workload: local

  • Each test is run twice in a single process in order to minimize the effect of page faults as the overhead is unpredictable.
  • Insert: each thread inserts 128M records.
  • Read: each thread reads 128M records.
  • Scan: each thread scans the entire hash map once.
  • Remove: each thread removes 128M records.
  • The read/scan/remove data is populated by the insert test.
11 threads 22 threads 44 threads 88 threads
Insert 134.519639194s 165.001678899s 231.081117542s 351.286311763s
Read 92.83194805s 104.560364479s 114.468443191s 124.8641862s
Scan 42.086156353s 108.655462554s 229.909702447s 474.113480956s
Remove 109.926310571s 123.499814546s 139.1093042s 154.684509984s

Test workload: local-remote

  • Insert, remove: each thread additionally tries to perform operations using keys belonging to other threads.
  • Mixed: each thread performs 128M insert-local -> insert-remote -> read-local -> read-remote -> remove-local -> remove-remote.
  • The data for mixed/remove tests is populated by the insert test.
  • The target remote thread is randomly chosen.
11 threads 22 threads 44 threads 88 threads
Insert 249.260816589s 301.757140479s 399.315496693s 598.363026383s
Mixed 310.705241166s 337.750491321s 363.707265976s 410.698464196s
Remove 208.355622788s 226.59800359s 251.086396624s 266.482387949s

scc::HashIndex

scc::HashIndex is an index version of scc::HashMap. It inherits all the characteristics of scc::HashMap except for the fact that it allows readers to access key-value pairs without performing a single write operation on the data structure. In order to make read and scan operations write-free, the key-value pair array is immutable; once a key-value pair is inserted into the array, it never gets modified until the entire array is dropped. The array is seldom coalesced when the array is full and the majority of key-value pairs are marked invalid. Due to the immutability and coalescing operation, it requires the key and value types to implement the Clone trait. Since no locks are acquire when reading a key-value pair, the semantics of scc::HashIndex::read is different from that of scc::HashMap; it is not guaranteed to read the latest snapshot of the key-value pair.

Performance

Test setup

  • OS: SUSE Linux Enterprise Server 15 SP1
  • CPU: Intel(R) Xeon(R) CPU E7-8880 v4 @ 2.20GHz x 4
  • RAM: 1TB
  • Rust: 1.50.0
  • SCC: 0.4.11
  • HashIndex<String, String, RandomState> = Default::default()

Test data

  • Each thread is assigned a disjoint range of u64 integers, and each u64 integer is converted into a String.
  • The performance test code asserts the expected outcome of each operation, and the post state of the hash index instance.

Test workload

  • Each test is run twice in a single process in order to minimize the effect of page faults as the overhead is unpredictable.
  • Insert: each thread inserts 16M records.
  • Read: each thread reads 16M records.
  • Scan: each thread scans the entire hash index once.
  • Remove: each thread removes 16M records.
  • The read/scan/remove data is populated by the insert test.
11 threads 22 threads 44 threads 88 threads
Insert 89.015914443s 116.402345094s 143.86420979s 223.296876115s
Read 18.975302649s 19.858082662s 20.862552983s 22.646245396s
Scan 3.640621149s 7.327157641s 15.847438364s 31.771622377s
Remove 69.259331734s 82.053630018s 98.725056905s 109.829727509s

scc::TreeIndex

scc::TreeIndex is an order-8 B+ tree variant optimized for read operations. Locks are only acquired on structural changes, and read/scan operations are neither blocked nor interrupted by other threads. The semantics of the read operation on a single key is similar to snapshot isolation in terms of database management software, as readers may not see the latest snapshot of data. The strategy to make the data structure lock-free is similar to that of scc::HashIndex; it harnesses immutability. All the key-value pairs stored in a leaf are never dropped until the leaf becomes completely unreachable, thereby ensuring immutability of all the reachable key-value pairs. The leaf data structure is unique to scc::TreeIndex, that it allows non-blocking multi-threaded modification while it keeps the key-value pair ordering information and the metadata consistent.

Performance

Test setup

  • OS: SUSE Linux Enterprise Server 15 SP1
  • CPU: Intel(R) Xeon(R) CPU E7-8880 v4 @ 2.20GHz x 4
  • RAM: 1TB
  • Rust: 1.51.0
  • SCC: 0.4.12
  • TreeIndex<String, String> = Default::default()

Test data

  • Each thread is assigned a disjoint range of u64 integers, and each u64 integer is converted into a String.
  • The performance test code asserts the expected outcome of each operation, and the post state of the tree index instance.

Test workload

  • Each test is run twice in a single process in order to minimize the effect of page faults as the overhead is unpredictable.
  • Insert: each thread inserts 16M records.
  • Read: each thread reads 16M records.
  • Scan: each thread scans the entire tree index once.
  • Remove: each thread removes 16M records.
  • The read/scan/remove data is populated by the insert test.
11 threads 22 threads 44 threads 88 threads
Insert 75.312037299s 75.9613236s 73.590353581s 79.835608473s
Read 26.027856123s 28.522993002s 32.284400279s 33.907327607s
Scan 17.745212214s 34.334674985s 67.668828349s 135.802180234s
Remove 82.458748986s 112.610040412s 164.552950283s 135.285141432s

Changelog

0.4.14

API enhancement: #41, HashMap::book -> HashMap::reserve

0.4.13

API enhancement: #40

0.4.12

Optimize TreeIndex: #24

Milestones

Milestones

Dependencies

~320KB