Concise Hash Table

1. Join性能深入分析

probe端必须流水的要求，使得访问hashtable是完全随机的，空间局部性几乎不起作用。
如下图所示, 由于input没有序，HT(1)～HT§任一entry都可能会被访问，其中P为分区数。
此时尽管hashtable被分成P个分区，但是和一个全局的global hash table并没有差别。

要想提高空间局部性，只有2种方法：

• 阻塞probe，对所有input分区，每次一个线程只处理一个分区，这样只会同时访问dop（线程总数）个HT，同时访问的地址空间为原来的dop/P。但这会使得probe无法流水，消耗更多的内存来存储probe的input，可能会触发不必要的落盘。这一部分在3.4小节讨论。
• 改进单次查询hashtable的时间,这取决于hashtable的设计方式，这一小节要解决的问题。

2. 当前hashtable的实现

目前的hashtable采取了常用的linear probing策略(即发生冲突时寻找下一个空的bucket并将其占据)。由于hashtable是动态插入的，当填充率达到75%会扩张。采取了倍增的扩展策略，均摊代价后使得每个插入耗时翻一倍。最小的hashtable默认是512条entry

上图展现了hash表的结构，分列存储，最小的hashtable占据 257 L (L表示cacheline大小, 64byte)大小的空间：

• bitmap表示这一行是否有值；
• hashkey=hashfunction(key), uint64；
• key 完整的值，用于最后的相等判断，如果key变长则为指针；
• payload指针，指向payload(payload为offset/RowId), 用于处理大量duplicate key, 避免单个key有多个payload; payload分为8个一block，block之间链表连接。
• numpayload 表示某个key的payload的数量。

hash表的查找分为4步：

• 查找bitmap[idx]，为1继续, 否则未命中；
• 比较hashkey，相等继续, 否则idx+1 返回第一步重复查找；
• 比较完整的key,相等则命中,否则idx+1 返回第一步重复查找；
• 遍历payload链表。

不难发现现有hashtable是列存的，则命中一个entry至少需要6条cacheline(bitmap, hashkey, key，num, *payload, payload)，带来的收益是未命中entry时，idx+1向下访问时带来缓存收益。
只有向下嗅探次数很多时候才需要列式存储，例如需要比较多个hashkey才能真正找到匹配的slot。
列式的另一个有点是可以用SIMD比较多个key。

3. Concise Hash Table

将hashtable转为行存后需要尽可能降低其单个查找linear proing的深度。 linear probing的深度与填充因子有关，将填充因子设为10%的时候，深度几乎不会超过2次，即访问总是在1个cacheline中。
因此一个可行的思路是将merge过后的HT(75%填充率)转为填充率10%的新hashtable,以限制linear probing深度。但填充率10%会让内存利用率降低到10%。进一步的，可以将稀疏的10% hashtable通过纵向压缩的方式将内存利用率弄到100%。 下图展示了2次转化的流程：1. 首先将75%填充率稀释到10%； 2. 纵向压缩生成Concise HT
对于CHT来说，查找一个entry，首先统计bitmap[0~idx]有多少个1来获得KV在紧凑KV数组中的偏移，然后再访问KV。可以通过每64bit记录一次1个数的前缀和来加速统计过程。

转化过程会使得merge阶段的耗时增加10倍左右，但如果不构建上图中红圈的KV表则耗时只会增加一倍，如果probe的表远大于build的表，这样的tradeoff即是值得的。
在75%->10%这一步骤中只构建bitmap+prefix，在构成CHT的KV表的时候再真正插入KV。
注意：那么是否可以直接建立CHT那？因为CHT的KV是紧凑的dynamic insert需要做shift，所以CHT是静态hash表，不能动态扩展。
CHT相比于原本的hashtable内存占用减少了35%～42%，提高了空间局性，hash碰撞率大幅减少，将能够很明显提升probing的性能。
内存开销计算设hashtable中有效的entry数目为n, KV的长度分别为8-Byte，即单个KV共128bit
原有方案：
fill factor = (75%+75%/2)/2 = 56%
n/56%*|KV|128bit = |KV|128bit + 77%128bit|KV| = |KV| (128+98.5bit )
10%改进方案：
均摊每个entry多付出1bit for bitmap, 1 bit for prefix
2bit/10%|KV|+128|KV| = |KV|(128+20bit)
(128+20)/(128+98.5) = 65%, 内存占用减少35%
如果不改变碰撞率：(128+2/75%)/(128+98.5)= 57.7%, 内存占用减少42.3%

碰撞率导致hash的线性嗅探次数大大减少
当probe端的表大小与build的表不在一个数量级上时候(Q4, Q12)，转化为CHT这个tradeoff是有收益的。但build与probe的表大小接近时(Q14), 可能反而没有收益。
那么能不能跳过75%的hashtable，直接构建CHT那？答案是可行的，但是需要处理duplicate key。因为CHT并不真正构建10%阶段的KV表，无法判断是否有duplicate key。如果有75%的hashtable，那么duplicate key已经被聚合一次了，所以没有影响。但如果跳过75%的HT, 那么在构建10%table过程中，当insert entry时发现连续2个bitmap已经被占用，则需要使用插入到一个溢出HT中来保留key的值。

4. 字段压缩

通过trick干掉一些没必要的开销

• 去掉numpayload，改为记录当前block中的numpayload，将范围搜小为blocksize(默认为8，最大不超过64)，并且将其记录在*payload的高8位(*payload是指针高12位没用)。
• 当key的length固定，且不超过16byte的时候去掉hashkey

这样hashtable的一个entry就变为了(key, *payload)

5. ConciseHashMap性能提升

没有字段压缩时候内存占用为原来的60%，字段压缩后为原来的30%
测试参数: imci_max_dop=26, imci_query_memory_limit=274877906900
taskset 绑定core