键值存储作为云计算的基础，使用简单灵活的数据模型实现了应用的高性能和高扩展性。但现有键值存储地址转换开销较大，需要多次地址转换才能定位键对应的值，包括采用哈希表等索引结构寻找值的虚拟地址、采用TLB以及页表等结构将虚拟地址转换为物理地址。为了加速地址转换过程，文章提出了一种将键映射为物理地址的快速转换系统。该系统包括存储地址映射的新型内存数据结构、实现地址转换的片上结构以及面向键值存储的专有指令。实验结果表明该系统能将典型键值存储系统Redis性能提升1.4倍，能将一些索引数据结构性能提升13倍。
该成果“Hardware-Based Address-Centric Acceleration of Key-Value Store”发布在国际学术期刊International Symposium on High Performance Computer Architecture (HPCA)上，HPCA会议是计算机体系结构领域的顶级国际会议，本届会议共收到258篇投稿，共录用63篇论文，录用率约为24.4%。
论文链接：
背景
键值存储系统为云计算提供了高性能和高可扩展性的保障，而数据检索是键值存储系统的主要性能开销，一次键值查找需要经过计算散列值、根据散列值查找对象的虚拟地址、虚实地址转换等步骤，当产生哈希冲突时，则会出现多次虚实地址转化甚至缺页，从而影响查询效率，实验表明，在经典的键值应用Redis中，翻译和地址查找过程占用了应用程序总时间的一半以上。
HTA[1]和SDC[2]通过建立键值缓存用于存储最近访问的值，我们称之为以值为中心（value-centric），但以值为中心的方式受限于值的大小，一条键值缓存不应该超过一个缓存行的大小，而较大的值也会对缓存产生较大的空间和性能开销。我们通过建立散列值地址缓存的方式，以地址位中心（address-centric），将最近访问的记录存放在片外的表格system translation lookaside table (STLT)中，避免了片上缓存空间受限的问题。在通过键进行查找时，系统将STLT中对应的条目添加到片上全相连缓存system translation buffer（STB）中，同时，系统可以获取目标的物理页标地止，避免了页表查找的开销。除了节省昂贵的寻址开销，这种方法还可以允许使用更简单地散列函数，进一步节省查询时间。
系统的设计面临如下挑战：
（1）如何设计STLT和STB以适应不同的键值存储的特性和需求？
（2）如何以最小的时间开销保持STLT、STB、TLB以及页表之间记录的一致性？
（3）如果更改记录，如何保持一致性？
（4）如何解决一个应用程序中具有多个键值表的情况？
（5）如何保证键值存储系统面临常见的泛洪攻击以及暴露物理地址的安全性？
设计与实现
图1 STLT和相关伪代码
STLT类似于一块用于加快检索的缓存，其中记录了当前散列值的虚拟地址以及对应的页表物理地址。查询过程如图1所示：（1）将key经过哈希函数得到整型值；（2）通过LoadVA指令获得整型值对应的虚拟地址，同时，将STLT中的虚实地址映射记录在片上的缓冲区STB中；（3）检查得到的虚拟地址是否是空指针以及得到的数据是否和键相匹配，若数据匹配，则STLT命中，否则STLT缺失；（4）回溯到传统方式进行检索，通过insertSTLT指令将整型值和相对应的虚实地址映射记录到STLT中。
STLT设计：STLT是位于内核空间的一块组相连缓存。如图2所示，STLT中的每一行为16字节，前4位用于记录访问的频率，最后两项分别记录了虚拟地址和对应的页表物理地址，sub-integer记录了部分整型值的内容，用于加快查找过程。STLT的大小必须是2的指数，且可以根据应用程序定义表格大小。以图3为例，4路组相连的STLT有210行，因此，只有8个位用于定位特定的组，这8个位可以是整型值中任意的8位，在这里采用了整型值中尾部连续的8位，同时，由于两条LoadVA指令对应的整型值可能具有相同的组号，因此，我们需要增加12位的sub-integer来区分不同的指令。由于我们采用了整型值的部分值进行查询，因此，得到的虚拟地址有可能是错误的，后续再由软件方式判断返回值的正确性。
图2 A rowentryofSTLT
图3 STLT设计
LoadVA指令：我们为指令增加了几个片上硬件：（1）几个寄存器CRs用于记录STLT的基地址和大小；（2）一个 invalid page buffer(IPB) 用于记录最近失效的物理页表项；（3）一个STB包含了对应的虚拟地址和物理页表。图4（a）展示了LoadVA的实现过程，CPU发出LoadVA指令，指令中包含了整型值，从整型值中可以提取出STLT的组号以及sub-integer的值，结合CRs中STLT的基地址，可以找到匹配sub-integer的行号，将找到的地址与IPB中的内容相比较，若位于IPB中，说明此地址位最近失效地址，产生STLT 缺失，否则，将查找到的虚实地址映射放入到STB中，并返回虚拟地址。图4（b）展示了地址翻译过程，CPU向TLB发送虚拟地址，TLB 缺失之后，查询STB的内容，STB 缺失之后，进行页表查询。
图4 LoadVA指令设计
insertSTLT指令：insertSTLT指令查找给定虚拟地址的物理页表并将其插入到STLT中，指令的实现依靠一个插入缓冲以及一个simplified page table walker(SPTW)。SPTW和传统页表遍历器的区别在于出现缺页时，返回0而不是进入缺页中断。图5展示了insertSTLT的实现过程，CPU发出insertSTLT指令，根据整型值可以找到匹配sub-integer的行号，插入缓冲中存放着要写入的虚拟地址。之后CPU根据插入缓冲中的虚拟地址送入SPTW进行查询，若没有找到对应物理地址，则丢弃，否则将虚拟地址和物理页表插入到STLT对应的行中。
图5 insertSTLT指令设计
安全性的考虑：传统的键值系统易受DoS攻击，即通过分析哈希函数，使其产生较多哈希冲突，而通过链式地址解决哈希冲突会导致链表长度过长，从而降低系统的搜索速度。为防止这种攻击，现在的键值系统会采用更复杂的哈希函数，如SipHash[3]、MD5、SIPEMD等对哈希函数进行加密。由于STLT只是一个缓存，不需要处理哈希冲突，产生的哈希冲突只会导致一次STLT 缺失，因此，哈希函数的复杂程度对STLT的性能不会造成影响。通常STLT可以使用简单的哈希函数，加速哈希值的生成。由于STLT不仅存储虚拟地址，还存储物理页表地址，为避免用户空间的读写指令对STLT进行更改，我们将其放入在内核空间，用户级别的应用程序只有很少的接口对STLT进行更改，如loadVA指令和insertSTLT指令的输入输出只跟整型值和虚拟地址相关，其余的操作由硬件或者操作系统对STLT进行更改，如页表查询、管理页表。
性能测试
硬件开销：在48 bit虚拟地址以及4KB的页表大小的情况下，系统只需要不到1KB的片上存储开销，如图6所示，寄存器组CRs保留了STLT的36 bit的物理地址和一个64bit的STLT大小。失效页表缓冲有32个条目以及一个6 bit的计数器。STB也包含32个条目，每行STB包含64 bit的虚拟地址和64 bit的物理页表地址。插入缓冲包含8个条目，每行包含64 bit的虚拟地址和64 bit的物理地址以及一个44 bit的虚拟地址。
图6 STLT开销
软件开销（内存开销）：片外存储空间取决于不同的应用程序，大小从零M到几百M不等，这样的开销对于键值存储系统来说微不足道，并且产生较高的性能提升。
软件开销（代码更改）：对于流行的键值存储系统Redis，我们更改了12行代码，插入过程如图1所示，对于其他基准测试程序，我们更改了6行代码。
我们将没有使用STLT的默认基准测试程序版本作为基线，另外引入了之前的工作search lookaside buffer(SLB)[4]作比较。图7记录了SLB和STLT在9个工作负载中对Redis的加速，这些工作负载有三种分布和三种记录大小。平均而言，STLT带来1.38倍的加速，它的表现一直明显优于SLB，性能的提升主要来源于STLT中较少的TLB缺失和缓存缺失，STLT能够降低27%到31%的TLB缺失，然而SLB为-2.6%（增加）到10%。同时，STLT在减少数据缓存失败方面也显示出显著的优势:STLT为5-12%，SLB为-3-3.7%。
图7SLB和STLT对Redis的加速
参考文献：
[1] G. Zhang and D. Sanchez, “Leveraging caches to accelerate hash tables and memoization,” in Proceedings of the 52nd Annual IEEE/ACM International Symposium on Microarchitecture, 2019, pp. 440-52.
[2] F. Ni, S. Jiang, H. Jiang, J. Huang, and X. Wu, “SDC: a software defined cache for efficient data indexing,” in Proceedings of the ACM International Conference on Supercomputing, 2019, pp. 82-93.
[3] J.-P. A um asson and D. J. Bernstein, “SipHash: a fast short-input prf,” in Proceedings of International Conference on Cryptology in India, 2012, pp. 489-508.
[4] X. Wu, F. Ni, and S. Jiang, “Search lookaside buffer: efficient caching for index data structures,” in Proceedings of the 2017 Symposium on Cloud Computing, 2017, pp. 27-39 .
———END———
限 时 特 惠： 本站每日持续更新海量各大最新【内部创业教程】，一年会员只需 98 元，全站资源免费下载 点击查看详情
站 长 微 信： webprojs_com
