面向长尾现象的数据缓存技术研究

Access pattern of big data has changed from traditional Zipf-like distribution to Stretched Exponential (SE) distribution, conventional caching approaches are no longer suitable for big data access. The root cause for SE distribution’s long tail and lower caching efficiency than Zipf-like distribution is that big data access locality is weaker and cache space is insufficient. In this project, we proposed long tail phenomenon oriented big data caching structure, so as to improve cold file hit ratio through exploiting blocks of cold file co-resided in hot files, as well as guaranteeing hot files’ hit ratio; We also proposed attribute set and similarity detection based file classification to realize distributed caching management; Locality-Sensitive Hashing technology was adopted to group similar files and narrow query scope of duplicated data; Furthermore, Dynamic Counting Bloom filter Array was used to accelerate the judgment of duplicated items, so as to improve the performance of searching full set of cold data in long tail. In this project, we broke the regular thinking pattern on caching research where only hot data are focused and paid attention to the cold data with increasingly higher volume and value, so as to provide new solution for big data caching.

大数据访问模式由传统的Zipf分布变为扩展指数（SE）分布，传统数据缓存技术不再适用于大数据访问。造成SE分布的长尾现象及缓存效率远低于Zipf分布的根源在于大数据访问的局部性减弱且缓存空间不足。本项目提出面向长尾现象的大数据缓存结构，通过挖掘热文件中所包含的冷文件数据块，在保证热文件缓存访问命中率的前提下，提高冷文件缓存访问命中率；提出基于属性集和相似度检测的文件分类方法来实现分布式缓存管理，采用局部敏感哈希技术对文件进行分组，缩小重复数据的查找范围；进一步采用动态计数型布隆过滤器阵列技术加快重复数据的判断，提高缓存检索长尾全集冷数据的性能。本项目突破传统缓存研究只针对热数据的思维定势，聚焦规模及价值不断增长的SE分布下的冷数据，为大数据缓存设计提供新的思路。

缓存对计算机系统及其应用的性能提升起着至关重要的作用。然而在大数据环境下，提高缓存效率面临诸多挑战，其主要原因在于,数据访问的弱局部性使得传统数据缓存方式不再适应长尾现象下的大数据处理。. 本项目围绕面向长尾现象的大数据缓存技术开展研究，主要研究内容包括大数据缓存结构、大数据缓存替换算法及基于文件相似度检测的缓存预处理三个方面。代表性研究成果如下：. 大数据缓存结构方面，提出了基于相似性和融合性的重删方法RMD，实现了大数据访问模式下的重复数据指纹的快速查找，进而设计了基于内容感知的集群级层次去重存储系统CACH-Dedup，实现高效全局去重；缓存替换算法方面，基于实际系统的IO trace分析，挖掘出了大数据访问蕴含的特征，提出了“一次访问过滤”的智能准入策略和懒惰替换策略（LEA），在提高缓存命中率的同时，大幅降低SSD的写次数，延长了SSD寿命；缓存预处理方面，提出一种深度自学习哈希算法（DSTH），将深度哈希算法应用于无标签数据集预处理，实现高效的图像数据处理。. 本项目一共发表学术论文16篇，其中在CCF的B类及以上的国际期刊/会议上发表11篇；申请发明专利10项，获得发明专利授权7项；参与制订3项国家标准（均已发布）；培养研究生8名；获得2017年第三届“互联网＋”大学生创新创业大赛金奖。. 本项目构建了包括预取、智能准入、替换等功能的原型系统，关键技术用于腾讯云存储系统，有效缓解了腾讯云亟待解决的存储性能和价格之间的矛盾。基于项目研发的块级缓存优化技术，参与研发了腾讯FCBS系统，FCBS因其能够大幅降低企业的总拥有成本并提高性能，成为腾讯云的新一代存储系统。FCBS的成功上线运行标志着本项目的科研成果实现了产业化。