再议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%。

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

希腊英雄排名

在介绍希腊英雄之前普及下希腊神话中英雄的小知识。和中国神话中盘古开天辟地前的混沌一样,在希腊神话中混沌之中诞生了第一位神—地神盖亚(gaia),盖亚是女神,生下了天神乌拉诺斯。盖亚和乌拉诺斯又生下了三个独眼巨人,三个百臂巨人和十二泰坦神(六男六女)。十二泰坦神之一的克洛诺斯(Uranus,众神之怒2 中满身岩浆的终极boss)在母亲盖亚的怂恿下杀死了父亲乌拉诺斯,成为新的天神,克洛诺斯和自己姐姐十二泰坦神之一的瑞亚结婚,为防止出现和自己父亲的情况发生,克洛诺斯将自己的子女们都吃了,最小的儿子宙斯在母亲瑞亚的保护下成长并推翻了父亲的统治,成为新的天神,因为杀手锏是雷电,故也称雷神。

一般而言,神和神生下品质优良的还是神,品质较差的则是怪兽(一般为英雄和神所杀),神可永生,并具有较强魔法技能。神和人所生为半神,为英雄(Hero,物理攻击比较强悍)或者巫师(wizard,具有神的部分魔法技能)。

继续阅读

链接任意目录下库文件(解决错误“/usr/bin/ld: cannot find -lxxx”)

g++ 编译中链接库文件选项有: -L **  -lxxx

其中 -L 告诉编译器哪里去寻找库文件,** 指的是库文件所在路径,xxx 是库文件的名称,那么-lxxx 告诉编译器去找库文件libxxx.a(而不是xxx.a)。

如果生成的库文件时bplus.a ,就需要将其重命名为libbplus.a 这样才会找到该文件。否则,报如下错误

/usr/bin/ld: cannot find -lbplus
collect2: ld returned 1 exit status

继续阅读

自然辩证法论文(决定论)

此乃吾自然辩证法小论文,甚是无聊,看官非无聊至极勿看也,悼逝去的东九、西十二。

从论文录用谈开来

摘要

本文从影响理工科研究生们论文录用和被拒的因素谈开,分析了事物发展变化是否有具有决定性因素。并讨论了决定论等理论如何看待一般自然现象,以及其在量子力学面前所遇的瓶颈。最终将决定论与宿命论划分开来,总结研究生发表论文应该衡量论文价值,正确面对论文被拒。

关键字:论文录用、决定论、概率论

继续阅读