← 返回刚才阅读的位置

知识卡片

普通读书笔记卡 · 1770.e.1

短标签索引仍需核验主键

理解等级:高级

SILT将KV追加到Flash,在内存保留标签和偏移以压缩索引;部分主键Cuckoo设计还让被驱逐项能定位另一候选桶,减少搬迁时读Flash。标签是候选匹配,真实记录仍需核对完整key。图3-15显示h1桶存h2标签、h2桶存h1标签,原书相邻文字把位置与内容写混,不能照其字面实现。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 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 。这样就完成了一次替换操作。

    参考来源

    - 位置:《大数据日知录:架构与算法》第3章《大数据常用的算法与数据结构》(来源项目:book-sources;源文件:extracted/大数据日知录_架构与算法/_epub-src/OEBPS/text00008.html) - 结论依据:原文以“SILT使用了较短的主键“标签””所在段落解释具体机制;本卡保留其条件,另将实现限制、勘误和教学推导在正文中明确区分。 - 原始内容: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 。这样就完成了一次替换操作。 - 边界对照:[LevelDB实现说明](https://raw.githubusercontent.com/google/leveldb/main/doc/impl.md)、[Bitcoin原论文](https://bitcoin.org/bitcoin.pdf)、[SILT原论文](https://www.cs.cmu.edu/~dga/papers/silt-sosp2011.pdf);用于校正原书简化,未将书外观点伪作原文。