KV Store关键技术研究与原型系统实现

In recent years, with the exponential growth of Internet scale, there are more and more data stored in company websites, consequently, the response speed for user requests become slower and slower. One effective way is to introduce Key-value Store (KV Store) system, which trade data as key-value pairs for storage and retrieval. According to the storage medium, there are two kinds of KV Stores: the first kind is stored in RAM, and the second kind is stored in hard disk. According to the working mode, there are also two kinds of KV Stores: the first kind works in the cache mode, and the second works in the storage mode. This project focuses on the KV Stores that are stored in the RAM and work in the cache mode, and mainly studies three key techniques: hash table design, memory management & cache eviction policy, and parallel acceleration techniques. This project will propose two different designs for hash table and one set of solutions for efficient memory management & cache eviction policy. Then we will study parallel acceleration techniques on four platforms: multi-core CPU, many-core, GPU, FPGA. Last, we will implement KV Store systems based on multiple platforms, conduct extensive experiments to figure out the system bottleneck, and further improve the key algorithms and data structures.

近年来，随着互联网规模的指数式增长，公司网站存储了越来越多的数据，使得用户请求的响应速度越来越慢。一种有效的解决方法是引入键值存储系统（KV Store）。KV Store将数据按照键值对的形式进行存储和索引。按存储介质的不同，KV Store分为基于内存的KV Store和基于磁盘的KV Store。按工作模式的不同，KV Store分为缓存模式的KV Store和存储模式的KV Store。本项目着眼工作于缓存模式的、基于内存的KV Store，主要研究三项关键技术：哈希表设计、内存管理及换入换出策略、并行加速技术。本项目拟提出两种哈希表设计方案、一套高效的、内存冗余少的内存管理方案和置换策略，然后在四个平台（多核CPU、众核、GPU、FPGA）上研究并行加速方案，最后拟实现多个平台的KV原型系统并进行大量实验测试，定位系统瓶颈，进一步优化算法和数据结构。

随着互联网规模的飞速增长，键值存储系统（KV Store）应运而生且发展迅速，其不但在工业界得到了广泛的应用，而且在学术界得到了多个计算机方向的青睐。因此，研究KV Store的关键技术有着非常重要的学术意义和工业价值。本课题的研究目标是提升基于内存的、工作于缓存模式的KV Store的性能。围绕该目标，课题分别从哈希表技术、内存管理及缓存置换策略、硬件并行加速、原型实现和实验验证四个方面展开研究。我们提出了多个兼顾查找、更新速度和内存利用率的哈希表设计方案，并为KV Store定制了一套高效的内存管理及缓存置换策略，实现了快速置换、效果与LRU高度相似、兼顾置换元素代价、内存冗余少等目标。同时我们分别在多核CPU、众核系统、GPU、FPGA四个平台对KV Store进行了并行加速研究,并实现了系统验证。.本课题研究成果主要是以论文与专利的形式展现出来。项目执行期间，我们共发表论文47篇，其中发表在A类期刊及顶级会议中论文共23篇，包含了SIGCOMM，SIGMOD，SIGKDD等在计算机网络、数据库、数据挖掘等领域国际排名第一的会议。我们大部分源代码已经在开源社区开源，并获得了领域内专业人士的广泛关注。我们的研究涵盖了KV store的多个领域，目前已经新申请专利10项。部分研究成果已经在华为、字节跳动等互联网头部公司获得了应用。这也促使我们关注企业发展的实际需求，我们与华为、海思、中兴、字节跳动等公司都有着长期的合作，不断探讨KV store相关技术的落地与实现。未来五年内，我们将会有更多的成果在各大公司实现落地应用，实现产学研的深度融合。除此之外，我们同样注重与其他科研单位的交流与合作，我们与清华大学、中科院计算所、国防科技大学等院校及科研院所有着深入的合作与交流，同时我们与深圳鹏城实验室有着密切联系，我们多篇论文是与其他科研机构共同完成。