算法 Linear Hash 原理及实现

yfractal · 2020年01月27日 · 最后由 passerby 回复于 2020年04月20日 · 12050 次阅读

本帖已被管理员设置为精华贴

写在前面

这篇我写的比较啰嗦，大家也可以看 Berkeley CS186: Hash-based Indexes。

或者直接看实现。

写的比较啰嗦的原因，我没有一下子讲清楚 Linear Hash 是什么，而是一点一点增加“功能”，比如 bucket_index 唠叨了几次，才唠叨完。

有点类似 tdd 的开发方式，先写一个简单的功能，加测试，再加测试，再改。这样可能会比较方便理解。

以下是正文：

Hash 在计算机中，非常重要。除了会被用来存键值对（key val pair），还会被用作数据库存储索引的数据结构。

简单来说，一个 Hash 会首先申请一个数组，然后通过 hash function 将 key 映射成数组的 index，之后将 key、value 存储到数组内。

那么，有两个地方可能会影响性能。一个是并行，一个是在数组长度不够用的时候，需要创建更大的数组。

Redis 是单线程，Rust 可以使用读写锁。而 Erlang 自带的内存型存储 ETS，使用了 linear hash 作为 key value pair 的存储结构，提供了更好的并行能力。

下面简单介绍一下 Linear Hash 的原理及实现。

Segment & Table

一个 hash 首先会创建一个数组，然后使用 hash function 将 key 映射到对应的位置上去。

一个简单 hash function 可以是

def hash_val(key)
  key.hash % @total_size
end

如果这个数组“满”了的话，我们需要将数组扩大，数组扩大后，由于影响了 @total_size，则需要重新计算 hash 值后，将数据填入到对应的位置里。

很显然，当数据量较大的时候，会非常影响性能。这个过程一般被称为 resizing。

Linear Hash 为了解决这个问题，让一个 hash 可以对应多个数组，每次做 resizing 的时候，只会影响一个数组。

我们将存储的具体内容的结构称为 bucket，我们将由 bucket 组成的数组称为 segment，由 segment 组成的数组称为 table。

用代码表示，大体是这样：

segment0 = [bucket00, bucket00, bucket00, bucket00]
segment1 = [bucket10, bucket10, bucket10, bucket10]

table = [segment0, segment1]

所以，当我们需要查找一个 key 的时候，首先要计算所在的 segment，之后还要计算所在 segment 内的位置。

为了方便叙述，我们假定 segment 的长度为 4，假设 key 都是正整数（这样可以省去 key -> intger 的运算，比较直观）。

先来计算在 bucket 在 segment 内的位置，由于 @total_size 是 4，所以用 key 的 hash 指的二进制的后两位作为 bucket index，

方法如下：

def bucket_index(hash_val)
  hash_val & 3 # 取后两位
end

例如：

hash_val = 3 # hash_val.to_s(2) == "11"
hash_val & 3 = 3 # 11 & 11 = 11 == 3

hash_val = 7 # 111
hash_val & 3 == 3 # 111 & 11 = 11 == 3

现在我们来计算 segment index。

目前，我们有两个 segment，key 的 hash 值的后两位被用来表示再 segment 中的索引。

所以我们用倒数第三位表示 segment index。

代码如下：

def segment_index(hash_val)
  # 对 hash_val 取后 3 位 减去 取后 2 位的值，在向右移两位。
  (hash_val & 7 - hash_val & 3) >> 2
end

为了实现简单，在做 key 到 hash_val 的运算的时候，通过模运算，取到我们能存储的总长度范围之内的值。

相应方法则变为：

def hash_val(key)
  total_buckets = 2 * 4 # table array's size * segment array's size
  key % total_buckets
end

def segment_index(hash_val)
  hash_val >> 2 # drop last 2 bits
end

def bucket_index(hash_val)
  hash_val & 3 # get last 2 bits
end

Solve Conflict

目前，我们每个 segment 的长度为 4，一共有 2 个 segment。

假设我们存入的 key 有：1 和 9，那么通过 hash_val 方法得到的值，都是 1，所以最后得到的位置是一样的，既所谓的 hash value conflict。

为了解决这个问题，我们为每个 segment 增加一个 overflow_segment，当某个 key 的 hash_val 已经存在的时候，

则将 key、val 存到 overflow_segment 内。代码如下：

class Segment
  attr_reader :segment, :overflow_segment

  def initialize
    @segment = []
    @overflow_segment = []
  end

  def put(index, key, val)
    if @segment[index]
      @overflow_segment << [key, val]
    else
      @segment[index] = [key, val]
    end
  end

  def get(index, key)
    bucket = @segment[index] || []

    k, v = bucket[0], bucket[1]

    if k == key
      v
    else
      @overflow_segment.each do |k, v|
        return v if k == key
      end
      nil
    end
  end
end

Dynamic Grow

Split

Linear Hash 会根据情况（下一个章节介绍），动态增加 segment。而且每次 resizing 的时候，只移动一个 segment 内的 buckets。

依旧假设现在有 2 个 segment，分别为 segment0，segment1。未增加 segment 前，对应的最后两位为 0，1

bit    segment
0      segment0
1      segment1

这时候，我们增加一个 segment2，取 hash val 中的 1 位，无法满足需求，所以我们取 2 位，则

bit     segment
00      segment0
x1      segment1
10      segment1

我们假设 segment0 里存的 key 是 0，8。

则在增加 segment 前，对应的值：

key	in binary	segment index	bucket index
0	0000	0	00
8	1000	0	00

存储情况：

bit    segment   overflow_segment
0      [0]             [8] # 忽略 key 对应的 val
1      []

增加 segment 后，取倒数 3、4 为作为 segment index

key	in binary	segment index	bucket index
0	0000	00	00
8	1000	10	00

存储情况：

bit    segment
00      [0] # 忽略 key 对应的 val
x1      []
10      [8]

我们可以看出来，这次 grow，只需要将 segment0 分到一个 new_segment0 和 segment3 里。

之后，用 new_segment0 替换掉之前的 segment0，并将 segment3 放到 table 的末尾即可。

伪代码如下

new_segment0, segment3 = split_segment_with_2_bit_for_segment_index(segment0)
table[0] = new_segment0
table << segment3

Find Location

因为我们增加了 segnment，所以我们需要新的方法找到一个 key 的存储位置。

原来有 2 个 segment，一次 grow 之后，变成了 3 个。

00 segment0
 1 segment1
10 segment2

在 grow 之前，我们仅需要 1 位，就可以定位到对应的 segment。现在有 3 个，所以为了找到 segment 的位置，我们需要 2 位。

2 位二进制，可以表示 0、1、2、3。既可计算出的 segment_index 有 0、1、2、3。

如果，segment_index 为 0、1、2 的时候，我们可以找到对应的 segment。

但如是 3，我们则需要想办法将其映射到 1。

首先 hash_val 需要多计算一位

def hash_val(key)
  slots = 2.pow(2) * 4 * 2
  key % slots
end

bucket_index 不变。

segment_index 依然是去掉后两位，但需要处理两种情况：

如果计算出来的 index 小于当前的 table_size，则返回 index。

如果大于等于 table_size，则说明还没有被分裂出来，则去掉已经计算好的 index 的第一位。

伪代码：

def segment_index(hash_val)
  index = hash_val >> 2
  if index < @table.size
    index
  else
    drop_first_bit(index)
  end
end

Make General -- Level

为了可以更灵活，我们引入 level 这个概念。

当对当前所有的 segments 都进行了一次 spit，则认为完成一轮 resizing，level 加 1.

依旧假设当前的 segment 为 2 个，当 grow 两次后，segment 变为 4，认为完成了一轮的 resizing，level 加 1。

当我们创建 hash table 的时候，为这个 table 创建一个 segment，并且设置 level 为 0。

hash_val 则变为

def hash_val(key)
  slots = 2.pow(@level + 1) * 4  # 当前可以表示的 segment 数目 * segment 内 bucket 的数量
  key % slots
end

segment_index 为

def segment_index(hash_val)
  segment_bit = Math.log @segment_size, 2
  index = hash_val >> segment_bit
  if index < @table.size
    index
  else
    # drop first bit
    index & (2.pow(@level) - 1)
  end
end

同时使用 @next_segment_index 记录将要被 split 的 segment 的 index。

def grow
  from_segment_index = @next_segment_index
  segment = @table[@next_segment_index]
  new_segment1, new_segment2 = split_segment(segment)

  @table[@next_segment_index] = new_segment1
  @table << new_segment2
  @next_segment_index += 1
end

Grow Condition

为了实现简单，每个 bucket 第一次出现 key hash val 冲突的时候，就认为需要做一次 resizing。

每次插入一对 key、val 之后，都检查一下，是否需要 resizing。


class Bucket
  def put(index, key, val)
    if @segment[index]
      @overflow_segment << [key, val]
      if !@overflowed
        @overflowed = true
        :need_grow
      end
    else
      @segment[index] = [key, val]
    end
  end
end

class Hash
  def put_segment(segment, bucket_index, key, val)
    @times_to_grow += 1 if :need_grow == segment.put(bucket_index, key, val)
  end

  def put(key, val)
    // xxxxx
    put_segment(segment, bucket_index, key, val)

    maybe_grow
  end

  def maybe_grow
    return if @times_to_grow == 0
    // xxxx
  end
end