使用SSD解决10亿条元数据读写问题

一、问题描述

将10亿个元数据通过SSD 存储起来，能够实现快速的存和取

 

二、解决思路

2.1 联合使用三级存储设备

DRAM：作为数据缓存区

SSD ： 作为热数据存储区

HDD ：作为冷数据存储区

2.2 设计文件存储格式

 

2.2.1关键字解释

①头结构：包含有一个Hash表，用以维护元数据项的标识符在元数据缓冲区中偏移量，通过这个Hash表，系统可以迅速在元数据缓冲区中定位所需元数据项

②元数据缓存区：是一个可追加的结构，新来的元数据保存在上一个元数据后面，缓存区满了就往SSD中的元数据存储单元写，然后清空缓存区

③读缓存块：用于读数据的时候，做缓存用

④元数据索引单元：包括了一个Bloom  Filter文件（纪录每块元数据缓存区内的元数据）和一个无效元数据项标识符链表

⑤元数据文件：由多个元数据存储单元组成，每个单元内有许多元数据项，其结构与DRAM中的元数据缓存区一致

⑥元数据索引文件：保存的就是每个元数据存储单元的索引信息，由DRAM内的元数据索引单元拷贝而来

⑦元数据日志文件：存放在HHD上面的冷元数据单元

2.2.2 机制介绍

首先元数据由外到内，最开始来到DRAM内的元数据缓冲区；

在头结构纪录下标识符和偏移量，通过Bloom Filter 在元数据索引单元内登记

如果缓冲区数据满了，将元数据缓冲区数据迁移到元数据存储单元中去，然后清空缓冲区；同时还将相应的元数据索引单元内的内容备份到元数据索引文件，且不删除索引单元的内容，起将一直在内存中

在SSD上的元数据存储单元做周期的垃圾回收，清除剩余空间

执行居于热度的数据迁移线程，将元数据存储单元内的数据迁移到缓冲区，或者元数据日志文件

2.3 元文件写机制

 
    其中的关键字和上部分介绍的数据存储格式关键字一致

机制介绍：

【1】新元数据项append到元数据缓冲区

【2】在元数据索引单元内的Bloom Filter表内做元数据内容登记

【3】如果缓冲区满了，数据写回到SSD，其中写的时候查询无效元数据项ID表，对于无效的数据，直接丢弃，并将元数据索引单元写入元数据索引项中

2.4 元文件读取机制

【1】首先查找缓冲池中是否含有所要找的元数据，如果有则直接返回，读取操作结束，否者继续执行

【2】缓冲池没有则需要到元数据单元或元数据日志文件上查找，其将通过Bloom Filter找到所属于那个数据单元，

【3】然后将数据单元读入到DRAM的写缓存中

【4】根据头结构快速的定位到元数据

重点介绍如何通过Bloom Filter来找到元数据单元位置：

创建一个64叉树，每一个数据单元的数据索引单元的Bloom  Filter表作为叶子节点，树的深度不超过2，非叶子结点的Bloom  Filter表为各叶子节点Bloom Filter表做异或运算的结果。

64个Bloom Filter构成一个Bloom Filter Group、

64个Bloom Filter Group构成一个Bloom Filter Tree、

维护一张链表，记录下多个Bloom Filter Tree的根节点。

本机制可以使原来一个一个搜索的时间复杂度O(n)，降低为O(logn)

搜索时，先快速的定位到哪个Tree下，再定位到哪个Group下，再遍历到目的原文件存储单元

2.5元文件修改机制

【1】先找到将要被修改的元数据

【2】在该元数据缓冲区中插入一条已经修改好的新元数据

【3】标记元数据索引单元中旧元数据为无效数据

【4】下次元数据缓冲写回时直接将旧数据丢弃 

2.6获得元文件存储单元热度机制

记录k表示该元数据存储单元在该时间段内被访问的次数

记录num表示该时间段内上层总共发出的元数据读请求个数

k/num表示在某时间段内该元数据存储单元的访问次数占总访问次数的比例,访问比例越高,表明在该时间段内该元数据存储单元的访问越频繁,该元数据存储单元的热度就越大

使用最近一段时间内的访问比例来衡量数据热度，因为该值能够准确反映数据在最近一段时间的访问频度，避免很久之前的访问对当前热度的影响．

加入对之前访问热度的考虑，防止某些元数据存储单元短期内访问频度的剧烈变化所造成热度的波动。

系统会周期性迭代计算每个元数据存储单元的热度，使热度能够反映当前数据的访问情况，这种热度判定算法综合数据的访问频率和最近访问时间两方面的因素，判定更加准确、合理，且在实现简单，时间和空间开销较小． 

2.7 数据迁移机制

开启一个线程执行迁移指令

处理到当前的元数据单元时，判断其热度值大小，热度值有一个范围区，如果小于最小值，则移入HHD，如果大于最大最则移入DRAM缓冲区

2.8 空间周期性回收机制

回收无效元数据项占用的SSD空间，对元数据的更新操作采用异地更新的策略会造成元数据存储单元中含有无效的元数据项

迁移线程会周期性回收那些无效元数据项比例超过50%的元数据存储单元，将其中有效的元数据项写入元数据缓冲区中，并对该存储单元做上标志．

当迁移到该元数据存储单元时，系统不需要判定其访问热度，直接回收其占用的空

三、相关的技术点

3.1 什么是HDD，什么是SSD，它的优点是什么？

HDD是基于磁盘存储架构

SSD是Solid State Drive固态硬盘

寿命：Flash memory有擦写次数限制，大量小粒度随机写操作很影响使用寿命

优点：高带宽，低时延

3.2 使用SSD的几种类型：

① SSD作HDD缓存（速度加快，随机读写次数很多，影响SSD寿命）

② HDD作SSD写缓存（速度加快，容量受限制于SSD）

③ 数据分别存储在SSD和HDD上（速度加快，SSD寿命受影响）

④ 针对特定负载所设计的SSD存储系统（速度加快，依赖于负载特征）

3.3 Bloom filter 布隆过滤器

布隆过滤器用于检索一个元素是否在一个集合中

布隆过滤器是1970年由布隆提出的。实质上是一个很长的二进制矢量和一系列随机映射Hash函数。

原理是，当一个元素被加入集合时，通过K个散列函数将这个元素映射成一个位数组中的K个点，把它们置为1。检索时，我们只要看看这些点是不是都是1就（大约）知道集合中有没有它了：如果这些点有任何一个0，则被检元素一定不在；如果都是1，则被检元素很可能在。这就是布隆过滤器的基本思想。

优点,相比于其它的数据结构，布隆过滤器在空间和时间方面都有巨大的优势。布隆过滤器存储空间和插入/查询时间都是常数(O(K))。另外, 散列函数相互之间没有关系，方便由硬件并行实现。布隆过滤器不需要存储元素本身，在某些对保密要求非常严格的场合有优势;布隆过滤器可以表示全集，其它任何数据结构都不能.

缺点，误算率是其中之一。随着存入的元素数量增加，误算率随之增加。但是如果元素数量太少，则使用散列表足矣。

判断结果在集合里面的不一定在集合内

判断结果不在集合里面的一定不在集合内

另外，一般情况下不能从布隆过滤器中删除元素

评论

1 楼 ljbupc 2014-12-15  

FB的flash cache？