知识卡片
短标签索引仍需核验主键
SILT将KV追加到Flash,在内存保留标签和偏移以压缩索引;部分主键Cuckoo设计还让被驱逐项能定位另一候选桶,减少搬迁时读Flash。标签是候选匹配,真实记录仍需核对完整key。图3-15显示h1桶存h2标签、h2桶存h1标签,原书相邻文字把位置与内容写混,不能照其字面实现。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 大数据常用的算法与数据结构 · 查看原书依据
SILT哈希大体和Cuckoo哈希相同,但是有两个优化点:其一是哈希空间的桶里不是存放KV数据的主键(Key),因为主键太长,所以SILT使用了较短的主键“标签”(Tag)来代替主键,这样可以大大减少内存空间占用量,这也是为何SILT能够单机存储十亿级别数据的关键之一。其二是如图3-15所示,对于某个主键x 来说,假设其h 1 (x )对应的哈希空间位置是a ,h 2 (x )对应的哈希空间位置为b ,SILT哈希在h 2 (x )对应位置写入b ,h 1 (x )对应位置写入a ,也就是说两个哈希函数相互将对方的哈希空间位置作为自己的标签,这是与Cuckoo哈希的第2个主要区别。为什么要这么做呢?这与第1个优化有关,因为第1个优化进行以后,存储的不是记录的主键而是标签,如果此时Cuckoo哈希需要替换掉某个主键y 的时候,需要根据主键y 重新计算哈希函数值寻找空桶,但是因为没有存储主键y 而是存储的y 的标签t ,所以此时需要先从Flash里读出标签t 对应的主键y ,才能进行后续的操作,这明显效率是很低的。为了避免在Cuckoo哈希替换数据的时候读Flash操作,SILT采取上述第2个优化操作,其核心思想是:如果某个位置要被替换,可以直接从位置存储的内容获得下一个应该存储的位置,这样就省去了读Flash的过程。举例来说,如果此时h 1 (x )位置需要被替换掉,此时读出h 1 (x )位置存储的值b ,位置b 即为应该安排的新位置,所以读出h 1 (x )的内容并用其值替换掉哈希空间位置b 的内容,即用内容b 替换掉位置b 原先的内容a 。这样就完成了一次替换操作。