Erlang/Elixir Erlang ETS Linear Hash Implementation
ETS 可以简单理解为 Erlang 的 in memory key/value storage。
Erlang 所有的变量都是不可变的，一些有状态的东西，可以存储在 ETS 里。
ETS 使用的存储结构有两种，一种是 B-Tree，一种是 Linear Hash。
B-Tree 用来存 ordered set，其他类型都是用 Linear Hash 存。
Redis 也是 in memory key/value storage，ETS 同 Redis 最大的区别是，ETS 可以利用多核资源。
下面介绍 ETS Linear Hash 的实现。
Linear Hash Brief Introduction
hash 首先需要声明一个数组，然后将 key 映射到这个数组的某个位置上。
例如：
def hash_val(key)
key.hash % @array_size
end
如果这个数组“满”了的话，我们需要将数组扩大，这个过程一般被称为 resizing。
resizing 后，会改变 @array_size 的值，而同一个 key，被不同的 @array_size 取模运算后，得到的值不同，既会被映射到数组的不同的地方。
所以需要对原有数组内的元素重新计算位置，并填入到新的位置。很显然，这是个耗时的过程。
Linear Hash 用了一种聪明的方式做 resizing，避免一次 resizing 会消耗过多时间的问题。
ETS Linear Hash Implementation
ETS 使用 HashDbTerm(bucket) 存储 key、val。通过 hash function 将 key 映射到某个 bucket 上。
如果这个 bucket 已经被占用，则创建一个新的 bucket1，并通过 Bucket 的 next 字段，将他们链接起来。
既 bucket.next = bucket1。
在每次插入数据之后，都会根据情况，判断是否做 grow 操作。
grow 主要操作是把某个 bucket 分（split）成两 bucket，并把它们放入对应的位置上去。
被 split 的 bucket 和刚才被插入的 bucket 可以不是同一个 bucket。
所以每次可以只增加一个 bucket，这样就避免了一次性移动大量 bucket 代理的性能损耗。下面是具体实现。
Data Structure
-
bucket
typedef struct hash_db_term { struct hash_db_term* next; /* next bucket */ Uint32 hvalue; Uint32 pseudo_deleted; # define MAX_HASH_MASK ((Uint32)(Sint32)-1) DbTerm dbterm; /* The actual term */ } HashDbTerm;next 字段从来解决冲突，dbterm 会存实际的 term。
-
segenment
struct segment { HashDbTerm* buckets[1]; };segment 是一个 buckets 的数组。
table
typedef struct db_table_hash {
DbTableCommon common;
/* SMP: szm and nactive are write-protected by is_resizing or table write lock */
erts_atomic_t szm; /* current size mask. */
erts_atomic_t nactive; /* Number of "active" slots */
erts_atomic_t segtab; /* The segment table (struct segment**) */
struct segment* first_segtab[1];
/* SMP: nslots and nsegs are protected by is_resizing or table write lock */
int nslots; /* Total number of slots */
int nsegs; /* Size of segment table */
/* List of slots where elements have been deleted while table was fixed */
erts_atomic_t fixdel; /* (FixedDeletion*) */
erts_atomic_t is_resizing; /* grow/shrink in progress */
DbTableHashFineLocks* locks;
} DbTableHash;
segtab 是一个 segnments 的数组。szm、nactive 等字段可以先不用关注，后面会介绍具体用途。
Grow
ETS 的时候，每次插入数据后，会根据当前的情况，判断是否需要 grow。
每次 grow 会把一个 bucket 分成两个，新生成的会被放到 segtab 的末尾。
比如：
b0, b1
grow
b0', b1, b2
grow again
b0', b1', b2, b3
grow 的流程是，每一轮，把当前的 bucket split 一遍。之后再从第一个 bucket 开始 split。
假设当前有一个 bucket b0，grow 一次，变成 b10, b11。第一个轮完成。
下一轮，再从第一个 bucket（b10）开始 split。变成 b20, b11, b22。
下一次 grow，变成 b20, b21, b22，b23，第二轮 grow 完成。
也可以用下面的图表示
| round | grow times | buckets before grow | bucket to split | buckets after grow |
|---|---|---|---|---|
| 1 | 1 | b0 | b0 | b10, b11 |
| 2 | 2 | b10, b11 | b10 | b20, b11, b22 |
| 2 | 3 | b20, b11, b22 | b11 | b20, b21, b22, b23 |
| 3 | 4 | b20, b21, b22, b23 | b20 | b30, b21, b22, b23, b34 |
Location
了解完 ETS 的 hash 如何做 resizing（grow）的，现在我们看看 ETS 是如何找到某个 key 所对应 bucket 的。
Mask
ETS 首先会把 key MAKE_HASH 转换成整数。
unsigned long hash_val = MAKE_HASH(key)
得到的 hash_val 可能是一个非常长的数字，很可能远远多于我们 buckets 的数量。
这个时候，ETS 使用 szm 将 hash_val 再次映射到可表示的 buckets 内。
假设现在一共有 4 个 bucket，那么只需要 2 位二进制数就可以表示所有的 bucket。如果有 6 ~ 8 个 bucket，则需要 3 位。
具体映射情况如下：
| key | zsm | result |
|---|---|---|
| 0 | 1 | 0 |
| 1 | 1 | 1 |
| 2 | 1 | 0 |
| 3 | 1 | 1 |
| 0 | 3(11) | 0 |
| 1 | 3 | 1 |
| 2 | 3 | 2 |
| 3 | 3 | 3 |
但是，我们知道 ETS linear hash 是每次增加一个 bucket 的，而 szm 是成倍增长的。所以经过 szm 的映射，可能会映射到一个不存在的 bucket 里。
例如现在有 3 个 bucket，szm 是 3，如果 key 的 hash val 是 3，那么会被映射到第 4 个 bucket 里。
而实际上，此时这个 key 应该是在第一个 bucket 里。
具体过程如下：
假设有 2 个 bueckt，当前的 szm 是 2，这个时候插入 hash value 是 4 的 key0，则这个 key0 会被存储到第一个 bucket 内。
之后进行了 grow 操作。szm 需要变为 3。这个时候再查找 key0。直接使用 szm 做 mask 的话，会被映射到第 4 个 bucket 里。
而实际上，这个 key0 是在第 1 个 bucket 里。
为了解决这个问题，ETS 记录了一个 hash 的 nactive 字段，这个字段表明有多少活跃的 bucket。比如这个例子，nactive 就是 3。
在定位的时候，当用 szm 进行 mask 的时候，如果得到的结果大约 nactive，那么说明这个 bucket 还没有被 grow 出来。
所以要把 mask 向右移一位，再进行 mask，代码如下：
static ERTS_INLINE Uint hash_to_ix(DbTableHash* tb, HashValue hval)
{
Uint mask = (DB_USING_FINE_LOCKING(tb)
? erts_atomic_read_acqb(&tb->szm)
: erts_atomic_read_nob(&tb->szm));
Uint ix = hval & mask;
if (ix >= erts_atomic_read_nob(&tb->nactive)) {
ix &= mask>>1;
ASSERT(ix < erts_atomic_read_nob(&tb->nactive));
}
return ix;
}
Bucket
ETS linear hash 并不是直接由 bucket 组成，而是由 bucket 组成 segnment，之后再由 segnment 组成 table（具体可以看前面的章节）。
所以要找到具体某个 bucket，需要先找到对应的 segnment。
ETS 查找对应 segnment 的宏是
#define SLOT_IX_TO_SEG_IX(i) (((i)+(EXT_SEGSZ-FIRST_SEGSZ)) >> EXT_SEGSZ_EXP)
FIRST_SEGSZ 是在创建 hash 的时候，第一个 segnment 的长度，为 2 的 8 次方个。
EXT_SEGSZ 是在需要 grow 的时候，创建的 segnment 的长度，为 2 的 11 次方个。
因为有的时候，我们在使用 ets 的时候，数据量可能会比较小，所以 FIRST_SEGSZ 设置的比较小，可以节省内存。Redis 也有类似的机制。
EXT_SEGSZ_EXP 是额外的 segnment 的长度，二级制的位数，是 11。
因为是向右移 11 位，是 EXT_SEG 的位数，所以用 (EXT_SEGSZ-FIRST_SEGSZ) 相当于补齐了两者的差值。
这样可以使 0 ~ 256（2 的 8 次方，第一个 segnment 的长度）落到第 0 个 segnment 内。
计算 bucket 的宏是：
#define BUCKET(tb, i) SEGTAB(tb)[SLOT_IX_TO_SEG_IX(i)]->buckets[(i) & EXT_SEGSZ_MASK]
(i) & EXT_SEGSZ_MASK 是用来计算在 bucket 内的位置。
EXT_SEGSZ_MASK 是二进制 1111111111，具体定义是：
#define EXT_SEGSZ_EXP 11
#define EXT_SEGSZ (1 << EXT_SEGSZ_EXP)
#define EXT_SEGSZ_MASK (EXT_SEGSZ-1)
Grow Detail
上面说完了 ETS lineary hash 是如何 grow 和 查找 key 的位置的，现在再来看 grow 的一些细节。
grow 的判定条件
#define GROW_LIMIT(NACTIVE) ((NACTIVE)*1)
if (nitems > GROW_LIMIT(nactive) && !IS_FIXED(tb)) {
grow(tb, nitems);
}
nitems 是当前存储的 entry 的数目，既存储的数目大于活跃的数目，就进行一次 grow。
nitems 在插入后，就会 + 1，而 nactive 是在 grow 内 + 1 的。
allo_seg
tb->nslots 是当前，创建出来的所有 segnment 的，所有 bucket 数目。
if (nactive == tb->nslots) {
/* Time to get a new segment */
ASSERT(((nactive-FIRST_SEGSZ) & EXT_SEGSZ_MASK) == 0);
alloc_seg(tb);
}
static void alloc_seg(DbTableHash *tb)
{
int seg_ix = SLOT_IX_TO_SEG_IX(tb->nslots);
struct segment** segtab;
ASSERT(seg_ix > 0);
if (seg_ix == tb->nsegs) { /* New segtab needed */
struct ext_segtab* est = alloc_ext_segtab(tb, seg_ix);
SET_SEGTAB(tb, est->segtab);
tb->nsegs = est->nsegs;
}
ASSERT(seg_ix < tb->nsegs);
segtab = SEGTAB(tb);
segtab[seg_ix] = (struct segment*) erts_db_alloc(ERTS_ALC_T_DB_SEG,
(DbTable *) tb,
SIZEOF_SEGMENT(EXT_SEGSZ));
sys_memset(segtab[seg_ix], 0, SIZEOF_SEGMENT(EXT_SEGSZ));
tb->nslots += EXT_SEGSZ;
}
segtab 是 segnment 指针的数组。所以在 segnment 都用尽的时候，会一次性增加多个 segnment 的存储位置。
这样可以避免频繁申请内存，也可以减少内存碎片。
segtab[seg_ix] = (struct segment*) erts_db_alloc(ERTS_ALC_T_DB_SEG,
(DbTable *) tb,
SIZEOF_SEGMENT(EXT_SEGSZ));
申请 segnment 的内存，并放到 segtab 的最后。
Update szm
szm = erts_atomic_read_nob(&tb->szm);
if (nactive <= szm) {
from_ix = nactive & (szm >> 1);
} else {
ASSERT(nactive == szm+1);
from_ix = 0;
szm = (szm<<1) | 1;
}
to_ix = nactive;
如果 nactive 比 szm 大，则 szm 增加 1 位。
from_ix 是需要被 split 的 bucket 的 index，to_ix 是新增加的 bucket 的 index。
Split
因为新增加了 bucket，所以 from_ix 的 bucket 内不属于自己的数据分给新的 bucket。
具体实现如下：
pnext = &BUCKET(tb, from_ix);
p = *pnext;
to_pnext = &BUCKET(tb, to_ix);
while (p != NULL) {
if (is_pseudo_deleted(p)) { /* rare but possible with fine locking */
*pnext = p->next;
free_term(tb, p);
p = *pnext;
} else {
int ix = p->hvalue & szm;
if (ix != from_ix) {
ASSERT(ix == (from_ix ^ ((szm+1)>>1)));
*to_pnext = p; // move to to index
/* Swap "from" and "to": */
from_ix = ix;
to_pnext = pnext;
}
pnext = &p->next;
p = *pnext;
}
}