再议SILT: A Memory-Efficient, High-Performance Key-Value Store

之前的文章谈到了高效key-value 存储系统SILT,谈的不清楚,昨天和付童鞋谈重复数据删除的时候谈到了SILT ,自己再回顾下。

首先要明白,SILT 融合传统的保存key-value 的三种方式:

  • LogStore 以日志结构方式持久化存储key-value 对,内存保留所有key(来了请求就在内存key 中查找)
  • HashStore 将磁盘或者SSD 上的每条key-value 按照内存中HashTable 的顺序排列,内存只保存了key 的部分哈希结构。
  • SortedStore 按照key 的顺序对内存中原来HashTable 索引进行重新组织。SILT 使用的Tire tree。

HashStore 和SortedStore 都具有比较好的内存效率,但只读不可写。

继续阅读

几种分布式网络存储编码的数据恢复问题

在传统的分布式存储系统中,数据为了保证安全、可靠、不丢失,一般采用副本策略,不使用编码技术有几点考虑:一是会增加了额外的计算开销;二是当某个存储节点发生失效时,会有多个存储节点涉及到该节点的恢复,且占用带宽超过副本策略的恢复带宽。下面是五种存储编码方法:

  • Replication 副本策略(分布式文件系统hadoop 等采用)

replication

优点:简单易实现,数据恢复带宽最小(C=1,C 什么意思看后面解释)

缺点:占用存储资源,现在云存储提供商都是按照存储容量来收费。

  • Simple 简单策略

simple

这里“+”代表的是按位加运算(0+0=0,1+0=1,1+1=0),简单策略允许至多两个节点失效,代价就是恢复需要额外的计算和两倍C=2 的恢复带宽。

  • NCCloud (FAST12 中文章)

nccloud

NCCloud 中改进了简单策略,在节点内部如果能够进行计算的情况下,恢复代价C 下降为1.5

  • Infocomm(Infocomm12 中文章)

infocomm

  • RAID5

介绍一个参数向量,<N , T , C , A > 是用于衡量该编码方式应对存储节点失效的能力和效率:

  • N =(单个节点存储容量)/(原始数据容量),反映的是单个节点保存的信息占原始数据信息的比率。
  • T 指最多可失效存储节点的个数。
  • C =(恢复数据带宽)/(单个节点存储容量),反映的是恢复单个失效节点的代价。
  • A 指恢复单个节点涉及到的节点数。

名称

类别

码率 <N,T,C,A> 总结
replication [3,1] 33.3% <1,2,1,1> 副本,存储效率最低
simple [4,2] 50% <1/2,2,2,2> 容错高,数据迁移大
NCCloud [8,4] 50% <1/2,2,2,2> 或 <1/2,2,3/2,2> 内部允许计算时C 减小
Infocomm [12,8] 66.7% <3/8,1,2,2> 再生编码
RAID5 [3,2] 66.7% <1/2,1,2,2>

普通RAID

从编码的角度来看,[n,k] 码最多能检测发现n-k 个错误。同样的,k/n 指码率,即编码的效率,编码的效率越高,存储的效率也就越高,但如果要求存储效率高,那么能进行纠错的能力就弱。将数据通过编码保存在多个节点即将编码后的信息等长分片,分别保存在多个存储节点。这样每个节点保存了编码信息后的多个分片,如果一个存储节点保存的信息分片信息总量越多,节点失效后需要能够检测出的错误就必须越多,相应的n-k 就必须越大,码率越小。上面两种此消彼长的关系如下:

单个节点存储容量*允许失效节点<—>编码效率

存储利用率<—>编码效率

另外还需要重点谈到的是恢复带宽C 和恢复涉及的节点数目A ,当某个存储节点失效后,需要根据已有的节点上的数据恢复失效及诶单,恢复带宽大于或等于原节点存储容量,副本策略就是最优的带宽利用,只需要原始数据容量的带宽,特点策略的恢复带宽比较简单,但要计算出一般的普适规律也不是那么容易,首先来讨论恢复节点问题,我们希望恢复时所涉及到的节点越少越好,传统RAID 在这点表现的比较差劲,当一块盘发生故障时,进行该盘数据重建严重影响了其他磁盘对外服务,我们希望的情况是数据恢复、重建过程中涉及的节点越少越好。

考虑一种情况:将数据n 编码后等分为i 个分片存储,任意j 个分片参与至少可以恢复一个分片,那么任意j 个分片可恢复出整个数据n 。比如将数据a 分为a1/a2/a3/a3(i=4,j=2),任意一数据分片可以由其他两片恢复,那么如果a1+a2 恢复了a3,那么a1+a3 或者a2+a3 又可以恢复出下一个分片,这样所有的分片就都可以恢复出来,故有任意j 个分片具有数据n 的所有信息。(这里不考虑分区的情况,比如数据ab,都按照上面的分片方式,得a1/a2/a3/a3 和b1/b2/b3/b4(i=4,j=2),a 的分片和b 的分片都只能恢复各自的分片)这样根据需要恢复的节点数也可以得到存储效率小于或等于 j/i。比如副本策略j=1,i=3,存储效率 33%;简单策略j=2,i=4,存储效率 50%;infocomm 就出现了上面分区的现象,因为任意每个分片只需要两个分片就可以恢复,但是并不是任意的两个分片都能够恢复出一个分片。

接着考虑上面没有考虑到的第二种情况:任意一个分片可以由指定的j 个分片恢复,但是并不是任意两个分片就可以恢复出一个分片(与上面的不同的地方,这里更像RAID 一条strip 上只能互相恢复,与其他条带上数据无相关性)。其实这样每个条带上的各个数据分片还是满足上面任意j 个分片可以恢复出所有分片的要求的,i代表每个条带上数据分片数目,比如RAID5 j=i-1,RAID6 j=i-2,infocomm 策略 j=2,i=3。

存储节点保存一个或多个分片,分片和存储节点都可以是故障的单位,既可以是存储节点中的某个数据分片发生损坏,也有可能是整个存储节点失效。无论是上面第一种情况中的数据分片还是第二种情况中条带内数据分片必须分布在大于或等于j 存储节点。那么允许失效的节点最大即为所有节点数减去j。

下面结束上面两种情况的话题,继续谈恢复带宽,我们发现给出的replication、simple、NCCloud、Infocomm、RAID 五种编码方法中除了replication 副本策略,恢复一个节点的代价C 都是大于等于二(例子里都等于二),这是因为恢复的数据分片都是通过其他数据异或运算得到的,异或运算最少需要两个参数,所以一个恢复一个分片至少需要两个分片,而节点是由数据分片组成的,所以恢复一个节点至少需要两倍的数据量。而副本策略存储的是数据的副本,恢复时不需要计算,节省了带宽。那么我们可以考虑每个存储节点上一部分分片采用副本策略,一部分使用异或运算提高存储效率。下面给出这样一种混合编码Hybrid。

  • Hybrid 策略

Hybrid

恢复每个节点的代价C 是8/5,存储效率是3/5,以恢复节点{A1/A2/A3/B1/C2+D2}为例:

A1 = A1

A2 = (A2+B2)+B2

A3 = (A3+B3)+B3

B1 = B1

C2+D2 = C2+D2

很明显,这样恢复代价C 越大,存储节点副本使用的就越少,恢复代价越大,也就是采用了更多的编码,恢复一个分片需要的分片数也就越多。恢复代价越小也就是存储节点内数据分片更多的采用了副本保存在其他节点,当存储节点恢复代价C=1 时,该节点上所有数据都在其他节点上保存有副本,这样存储效率也就<50%。

总结:存储效率等价于编码效率,反比于检错能力。恢复带宽正比于副本的使用,反比于异或编码比率。容最多节点反比于节点保存信息量,反比于编码效率和存储效率,即是码率越高,在节点保存信息一定的情况下,容失效节点越少。以上都是比较感性上的讨论,希望能够把信息论和编码的知识运用进去给出一个更加数学的结论。

磁盘测速

一、写在测试之前的

程序测试磁盘速度应该考虑到几点:

  1. 首先是内存的存在。内存作为读写的缓冲区,写入一个文件到磁盘时fflush() 会将写入数据从用户态转为核态,只有核态命令fsync() 才能够将数据真正的刷新的硬盘。内存作为缓存在读时可能影响更大。
  2. 其次是磁盘缓存,磁盘缓存是非易失性的,速度接近于内存,但容量一般在16MB~64MB 之间。会对写入速度的测试有较大影响。比如对于64MB 缓存硬盘,只写入一个小于64MB 文件后计算速度会非常大。
  3. 不同磁道上扇区密度不同。如下左图是比较旧磁盘采用的磁道上扇区分法,这样的在同样一圈磁道上扇区数相同,内外径不同磁道上磁头旋转一圈读取的数据量相同,缺点就在于外径扇区没有充分利用较大的磁道。而右边采用的近似等线密度的扇区分区,外径上磁道比内径上磁道具有更多的扇区,也就是说磁头在外径磁道上旋转一周的时间会读取更多的数据,这点在后面的实验中也有证实。
  4. 还有一个需要考虑到得是文件系统的影响,文件系统决定了文件的放置,很大程度上决定了测试的读写性能,比如Linux ext 文件系统就和windows 的文件系统不同(因为不需要碎片整理了)。在下面大部分测试中都使用的是打开文件、写文件、关闭文件,然后对同一个文件重复同样流程。

  1  2

继续阅读