ClickHouse / ClickHouse/ClickHouse

Fixed-block allocator for large hashtables

Open
#32,362 6 comments 0 reactions 0 assignees View on GitHub
comp-aggregation external feature
Dominant language
C++
Stars
49.9k
Forks
9k
Avg merge
21h 32m
Merged PRs (30d)
515

Description

Now, CH tries to optimize memory allocation by employing a better general-purpose allocator (jemalloc, hualloc). I propose to research a different approach - identify main memory eaters and individually customize these data structures and their allocation strategies with the goal to reduce their memory fragmentation and/or memory allocation times. In particular, the following analysis targets large hash tables since I know their implementation and I expect that they are among the main CH memory eaters. @alexey-milovidov, I hope you will read it.

### Buddy allocator

In particular, each hash table has its own element size S, and memory segments allocated for a particular hash table are always of S*2^N bytes. So, instead of trying to fit them into segments of 2^N bytes, we can reserve for each S value a large address area (1 TB or so) and use f.e. [buddy memory allocator](https://en.wikipedia.org/wiki/Buddy_memory_allocation) to share this memory area between all hash tables with given S.

### Limit the block size

Another opportunity (that may be considered independently) is to store a large hash table as an array of fixed-size segments rather than one big segment. F.e. we can limit segment size to 2 MB, and thus find the largest N for which S*2^N <= 2^21.

Once the hash table is going to have more than 2^N elements, we alloc its memory as multiple fixed-size blocks of S*2^N bytes, and access hash-table with two-level indexing:

hashtable[i] === hashtable.data[ i / 2^N ][ i % 2^N ]

This way, smaller blocks can still be allocated using the buddy allocator, while all larger blocks have the same size and may be kept in the single global list (for each S).

### Extendible hashing

But wait - CH hashtables are already 2-level, so this adds the 3rd indexing level. We can have only 2 levels and still limit the sub-hash size with [extendible hashing](https://en.wikipedia.org/wiki/Extendible_hashing):
- first level always contains 2^K entries, where K may vary over time
- a sub-hash may be referenced by multiple first-level entries
- so, when K increments by 1, we just duplicate all links to sub-hashes in the first-level table
- when sub-hash should grow over the limit (f.e. 2M bytes), we split it into 2 sub-hashes (each 2MB), un-duplicating a pair of links in the first-level table
- K grows only when we need to split sub-hash already referenced only from one first-level entry

In terms of indexing, it just needs replacing the current `i1 = h >> 24` command with `i1 = h >> V`, increasing the hashtable access latency only by 1 cpu cycle and only on Skylake and older archs.

### All blocks are buddies

Instead of making a private buddy allocator for each S, we can put a non-power-of-2 number of elements in each block. F.e. make all blocks 2 MB large, thus a block will contain `K = 2MB / S` elements. We can use multiplication-based index calculation to accommodate non-power-of-2 hash table size:

```C
i1 = h & SIZE_MASK
i2 = h*K >> 32
subhash = data[i1]
x = subhash[i2]
```

Note that subhash calculation requires 5-6 cpu cycles (mask+load), while i2 calculation requires 4 cpu cycles (mul+shift), so using MUL-based indexing shoudn't make 2-level hashing slower.

This code, however, has some requirements to the hash function: 1) hash value should have high-quality bits both on the lower and upper ends (since we use them both), 2) we need to know the bitness of actual hash values, f.e. 32 for crc32. See #30969.

### Fixed subhash size

We can continue to use AND-based indexing for one-level hash (`x = data1[h & SIZE_MASK]`) and switch to a 2-level hash only when the hashtable is going to become larger than 2 MB. The last condition will give us a nice property: each subhash will have a fixed size of 2 MB (if we never contradict subhashes).

So, for each subhash we need to keep only 64-bit pointer and 32-bit population. Even with 2MB cpu pages, these metadata may pollute LLC only when hashtables will grow to more than 1 TB combined, so this approach should be no worse than the current 256-way hashtables. Also, the population update&check will not affect the hashtable access latency.

Indexing and population accounting can be reversed in order to avoid comparision with K:

```C
if (--i2 < 0) i2 = K-1; // it's even 1 cycle faster than the current i2 = (i2+1) & MASK
if (--population[i1] == 0) extend_subhash();
```

The first-level table can be extended in just two steps - 32 KB and 2 MB.

### Conclusion

This text considers several independent proposals. I will evaluate only the last approach that combines them all together - extendible hashing with fixed-size 2 MB pages and MUL-based indexing:
- for hashtables smaller than 2 MB, the behavior is the same as with the current one-level hashtables. I rely on assumption that the main problem of CH is memory usage and allocation speed of (much) larger hashtables
- data for 2-level hashtables are allocated in fixed 2 MB chunks, making the allocation extremely fast even with global chunk pool - resulting in SPEED and LACK OF EXTERNAL FRAGMENTATION
- MUL-based indexing means that the entire 2 MB chunk space will be used for data - resulting in LACK OF INTERNAL FRAGMENTATION
- the proposed code sequences should make access to the modified hashtables about as fast as the current ones

TLDR: for hashtables larger than 1-2 MB - memory (de)allocation will become extremely fast and both internal and external fragmentation will gone (except for load factor). Access speed and behavior of smaller hashtables will not be affected, but the code complexity will grow.

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.