本文主要是介绍读Ludo Hashing: Compact, Fast, and Dynamic Key-value Lookups for Practical Network Systems论文笔记,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
一种新的键值查找设计,在已知的紧凑型查找解决方案(包括Cuckoo)中,其空间最小(对于l位值,每个键值项为3.76 + 1.05l位)和Bloomier完美哈希。支持快速查找,快速更新和并发写入/读取。与现有的动态解决方案相比,Ludo Hashing实际上节省了40%至80%以上的内存成本。它仅花费几个GB的内存即可存储10亿个键值项目,并实现了高查找吞吐量:在具有多个线程的单个节点上,每秒超过6500万次查询。
简介
ludo hashing通过删除the key storage同时在值上保持较低的放大因子(amplification factor, AF)来节省空间。AF是当values的长度增加1位时每项占用的更多位数。 Ludo Hashing的核心思想可以分为两个步骤:
- 我们首先使用一种设计合理的方法将所有key-value项划分为多个小组。每个组最多只能包含四个项目。
- 对于每个组,我们找到一个哈希函数H,以使H将四个key映射到整数0到3,而不会发生冲突。对于大多数现代随机哈希函数算法,我们可以使用不同的种子s生成独立的哈希函数Hs。
通过使用暴力尝试不同的种子,我们为每个组找到了正确的哈希函数。由于每个组仅包含4个密钥,因此可以在有限的尝试次数内找到种子,并且仅花费几比特。在每个组中,只需要存储一个种子和四个值(每个密钥k的Hs(k)结果的顺序)。在查找过程中,两个步骤都花费O(1)时间,并且每次插入/删除/更改都可以O(1)摊销时间进行更新。最终,我们通过使用仅花费5位的种子节省了存储四个密钥(数百位或更多)的空间!
问题定义
给定一组key-value的集合S,|S|=n。集合中,每个key唯一,且values的size(二进制位数)相同。功能如下:
- 查找函数query(k)返回查询键k的对应值v,其中⟨k,v⟩∈S。
- 构造函数Construct(S)构造集合S的表。
- 插入函数insert(k,v)将项目⟨k,v⟩插入当前表。
- 删除功能delete(k)从当前表中删除键为k的项目。
- 值更改函数remap(k,v’)在当前表中把键为k的项目的值改为v’。
系统模型
ludo hashing包括查找结构和维护结构。
- 快速存储器中的查找结构着重于查找功能。它的空间成本和查找时间最小化。
- 维护结构维护完整的键值状态,并执行构造和更新功能。它可以在查找结构所在的其他线程中运行,甚至可以在其他计算机上运行。
- 必要的更新信息将由维护结构构造并发送到查找结构。每次更新的时间复杂度是一个重要指标。对于不存储完整密钥的节省空间的查找引擎,需要单独的维护结构来支持更新。否则,无法保证更新的正确性。实际上,查找结构托管在快速且较小的内存中,而维护结构托管在较慢但较大的内存中。
Ludo Hashing设计
主要思想
典型的MPHF包含两级哈希。
- 第一级散列:整个n个key-value item随机划分到r个存储桶。
- 第二级散列:为每个存储桶Bi找到一个哈希函数Bi桶中每个key的哈希结果不与所有先前存储桶中的任何其他key冲突。
- 在大多数情况下,插入将导致O( r )第二级散列的重构。
而Ludo hashing利用(2,4)-Cuckoo和Othello,使每次更新都能在O(1)时间内完成。 Ludo先用(2,4)-Cuckoo和Othello共同构建函数F,该函数将键划分为r个存储桶,每个存储桶最多具有4个键,然后找到种子来解决每个存储桶之间的冲突。这种设计有两个独特的好处:
1)每次插入仅影响O(1)个桶;
2)在每个存储桶中,Ludo仅需要找到一个哈希即可将四个键映射到[0,3]而不会发生冲突,这比需要结果在所有存储桶中均无冲突的其他MPHF容易。
用(2,4)-Cuckoo和Othello共同构建函数F:
(2,4)-Ccuckoo中,每个键k分到索引为h0(k)和h1(k)的两个备用存储桶之一中。随机分容易不均匀。用一个Bloomier过滤器就可以每个密钥仅维护1位信息(h0/h1),Othello哈希是对原始Bloomier过滤器的动态扩展,并且Othello支持对键值查找的100%正确性,每个键使用2.33位的1位值。因此,在构造的(2,4)-Cuckoo中,每个密钥需要2.33位才能将每个密钥定位到存储该密钥的存储桶。
系统概述
完整的Ludo哈希包含Ludo查找结构和Ludo维护结构。
- Ludo查找结构被视为数据平面,在快速内存中运行并支持查找查询。
- Ludo维护结构(被视为控制平面)可以在较慢的内存中运行,可能在单独的计算机上运行。查找结构从维护结构接收更新信息,并相应地进行更新。
Ludo查找结构
Ludo查找结构是元组⟨O,B,h0,h1,H⟩,其中
- B是存储桶的数组,每个存储桶B [i]包括一个哈希种子s和4个存储槽,最多可存储4个值;
- h0和h1是两个统一的哈希函数 ;
- O是Othello查找结构,它返回1位值以指示密钥k是映射到存储桶h0(k)还是h1(k);
- H是通用哈希函数族。查询键k将输出值vk。
Ludo查找结构将依次查询两个定位器:存储桶定位器指示存储值的存储桶,以及插槽定位器确定存储值的插槽。桶定位器将在Othello中查找k并得到结果b∈{0,1}。然后v在存储桶hb(k)中。时隙定位器计算t = Hs(k),其中s是存储在此存储桶中的种子,t∈{0,1,2,3}。最后,将存储区hb(k)的插槽t中的值返回vk。
Ludo维护结构
Ludo维护结构由两个主要部分组成:
- 完整的(2,4)-cuckoo,其中包含所有插入的键值项,每个存储区都为插槽定位器存储种子。
- Othello维护结构,用于存储每个密钥是否在存储区h0(k)或h1(k)中。它可以生成在存储桶定位器中使用的Othello查找结构。种子s是通过蛮力找到的,因此Hs将存储桶中的键映射到不同的插槽而不会发生冲突。
Ludo维护结构支持更新,包括项目插入,删除和值更改,并将其反映在查找结构中。可以从维护结构中生成多个Ludo查找结构并将其与维护结构相关联,以接收更新消息并在本地进行更新。
Ludo hashing搭建算法
Ludo维护结构支持快速构建和更新Ludo查找结构。
该构造需要O(n)个键值项,并且每次更新都需要摊销O(1)时间。
Ludo维护结构包括
- (2,4)-Cuckoo,它维护所有插入的键值项并确定它们的键到桶映射;
- 在每个存储桶中确定一个种子的位置值;
- Othello维护结构,以跟踪当前的Othello查找结构。
从头开始构建Ludo维护结构和Ludo查找结构包括以下步骤。
- 开始进行标准(2,4)-cuckoo构造。所有键值项都按顺序插入到Cuckoo表中,该表的大小由负载系数0.95估算。
- 对于每个存储桶,有效种子都是将密钥散列到插槽而不会发生冲突的种子。依次测试数字0,1,···,30,以查看是否无效种子。如果从0到30的所有s均无效,则算法将存储31以指示溢出。
- 对于每个键,获取1位存储桶放置信息:0表示该项目存储在存储桶h0(k)中,1表示该项目存储在存储桶h1(k)中。然后,该算法构造Othello维护结构O来跟踪所有密钥的此信息。
- 通过简单地从Othello维护结构复制两个数据数组来构造Othello查找结构。因此,Othello的查找和维护结构会为每个输入键提供相同的查找结果。
- 构造一个表,该表具有与源Cuckoo表相同的存储桶数。对于源杜鹃表中的每个存储桶(称为源存储桶),将种子s复制到目标表中相同位置的存储桶(称为目标存储桶)。对于源存储桶中的每个键值项⟨k,v⟩,将v复制到目标存储桶的第Hs(k)个插槽。
Ludo hashing更新算法
插入
Ludo维护程序需要三个步骤来构造用于插入项目的更新消息。
- 首先将这个键值项⟨k,v⟩插入到源cuckoo表中,并记录路径。项目插入的布谷鸟路径定义为键重定位位置的顺序,其中每个位置由(bucket_index,slot_index)确定。
- 对于每个重定位键值项,其位置在其备用存储桶h0(k)和h1(k)之间切换。在图14中,k2和k8都在它们的备用存储桶之间切换。 Ludo维护程序会更新Othello维护结构中的相应值,并在Othello查找结构中进行更改。
- 对于每个经过修改的bucket,Ludo维护程序都会通过蛮力找到一个新的槽定位器种子。
当Ludo维护程序通过上述步骤完成更新时。它创建一个包含三个字段的更新消息:type指示更新消息的类型(插入,删除或更改),val是要插入的新项的值,update_sequence是节点序列,表示应用于Ludo查找的更新结构体。update_sequence中每个节点对应于布谷鸟路径中的一个位置,并包括以下内容:存储桶索引,插槽索引,此存储桶s的新种子,此存储桶的插槽中值的新顺序以及对Othello查找结构。所有关联的Ludo查找程序都会收到相同的更新消息,并按照该消息中的更新顺序执行插入。每个Ludo查找程序都以相反的顺序遍历更新序列的节点,并在每个节点上执行三个步骤:1)将节点中指示的存储区复制到临时存储器中。 2)将新种子写入存储桶,根据vodr重新排序值。 3)将存储桶写回到表中,并将更改应用于Othello查找结构。
删除
在Ludo维护程序中,删除用于将来的新项目的空间回收,并且删除是通过删除源Cuckoo表中的项目以及Othello维护结构中的关联存储桶位置信息来实现的。 Ludo查找结构没有变化。
更新
值更改仅涉及对单个插槽的更新,不需要对存储桶/插槽定位器进行任何更改。 Ludo维护程序将在源Cuckoo表中执行查找,以找到项目的存储桶/插槽位置,更改相应的值,并向查找结构发送值更改消息,并在其中指定新值及其位置。 Ludo查找程序将根据消息执行值更改。
这篇关于读Ludo Hashing: Compact, Fast, and Dynamic Key-value Lookups for Practical Network Systems论文笔记的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!