随机数种子的选择

  随机数生成器的质量七绝于其产生的序列是否在任意输入下拟合均匀分布,相对而言,选择一个优秀的随机数生成器不是件特别困难的事情,然而选择优质的随机数种子却有许多需要注意的地方。在只需要产生拟合均匀分布的随机序列时,选取随机数种子没有特别的要求。然而随机数生成器往往会被用于产生密钥的哈希算法,此时对于种子的选取就有特定的要求。

  有一些反面教材可供参考:

1995年9月时,当时流行的Netscape浏览器使用当前时间、当前Netscape的进程号和父进程号产生随机数种子。当时加州大学伯克利分校的研究员就实现了暴力破解Netscape的加密信息。

另一个例子是Kerberos协议的v4版本,它将当前时间与一些其他信息异或起来产生随机数种子。这个异或位运算直接将其他有效的信息屏蔽了,只留下20位容易预测的值,将密钥的空间从72万亿左右直接减少到1百万多一点,几秒钟时间就可以被暴力破解。

  在选择随机数种子的时候容易犯下面这些错误:

  1. 从一个很小的空间里选取种子:如果你选择的随机数种子只有8位长度,那么无论随机算法怎样,都最多只有256种可能的随机数序列。
  2. 仅将当前时间作为随机数种子:尽管UNIX API返回精确到毫秒级的时间,但是大多数操作系统处理时间的精度都不到1/60秒,那么,即使在1个小时是邻域内,也只有216000种可能的取值,对于暴力破解来说太容易了。
  3. 自己泄漏随机数种子:如果种子中使用了当前时间作为产生随机数种子的依据之一,那么就不要以任何方式泄露这个信息,例如不要在未加密的消息头部包含被作为随机数种子产生依据的时间信息。
  4. 使用网卡或硬件序列号:这种信息往往都是结构化的,而非散列的,结构化的信息被穷举的难度大大降低了。

  对于选择安全的随机数种子,有一些比较好的方案:

  1. 使用真正随机的数据源,比如一些噪点,装配相应的传感器,分析传入的信号的噪声,各种自然界的信号都是可以的。当然设备提供的现成的模拟信号也是可以的,例如/dev/audio在没有插入麦克风时提供的随机噪音,cat /dev/audio | compress,压缩一下可以进一步模糊值的实际含义。
  2. 获取系统底层的数据,也就是只有本机进程才有权限获取到的,不容易猜测到相近值,无法预先缩小取值范围的数据。比如系统当前使用的内存分页情况、CPU的温度、到某点的网络延迟的情况之类的。
  3. 让用户输入一串字符,分析用户按键的间隔时间,作为产生随机数种子的依据。千万不要只是取一个平均什么的,从统计的规律来看,按键的间隔时间一般也是在一个比较小的区间内的,要做取模、相乘等运算,产生不能预知可能分布情况的无意义的值。当然,要是结合鼠标移动的信息,就更好了。

 

CRUSH:受控的、可扩展的数据副本分散存储方案(Part 3)

** 以下内容为翻译
** 原文及版权声明:http://ssrc.ucsc.edu/Papers/weil-sc06.pdf
** 翻译:softrank.net@gmail.com
** 转载请保留以上信息
** 欢迎各位游客指正翻译中的错误,或提出建议
 

CRUSH:受控的、可扩展的数据副本分散存储方案

作者:Sage A. Weil Scott A. Brandt Ethan L. Miller Carlos Maltzahn
美国加州大学圣克鲁兹分校存储系统研究中心
{sage, scott, elm, carlosm}@cs.ucsc.edu
 

3.2 副本位置策略

  CRUSH的设计使数据得以均匀地分布在带权重的设备上,在统计意义上保持了存储和设备带宽的均衡使用。副本在树状结构中放置的位置对于数据安全性也有着关键性的影响。通过对于系统本质物理结构的映射,CRUSH能够建模,从而定位潜在的相关设备故障源。典型的故障源包括物理位置上接近、共享电源、共享网络。通过将这些信息编码到Cluster Map中,CRUSH的位置策略能够将对象副本分隔到不同的故障域中,同时维持预期的数据分布形式。例如,为了应对出现并发故障的可能性,也许会需要确保数据副本在不同机架、不同机柜、不同电源、不同控制器、不同物理位置的设备上。
  CRUSH可以被用于不同的数据副本策略和不同的硬件配置下,为了适应这样的多样性场景的需求,CRUSH为其使用的每个副本策略或分布策略定义Placement Rule,以保证系统或管理员可以确切地指定数据副本如何定位。例如,某人可能设定了某种规则,在某两个目标上使用双重镜像,在某三个设备上使用三重镜像,在某六个存储设备上使用RAID-4等等[注释1:尽管可以用各种各样的数据冗余机制,我们为了简化问题只讨论以副本形式存放的数据对象,也不损失任何的通用性]
  每条规则包含用户简单执行环境的用于树状结构的指令序列,这个运行环境可以用[算法1]中的伪代码来描述。CRUSH算法的输入参数x通常是对象的名称或者其他标识符,比如将被存放在同一个设备上的一组对象的标识符。take(a)操作从层次结构中选中一个项目(往往是一个桶),并将其赋予将作为后续操作的输入。select(n,t)操作对中的每一个元素i进行迭代,选择n个以i节点为根的子树下具有t类型的项。存储设备都有一个已知的、确定的类型,系统中的每个桶有一个类型字段用于区分不同类型的桶(例如,某些代表“rows”,有些代表“cabinets”)。对中的每一个元素i,select(n,t)操作对于1到n之间的每一个数r被迭代调用,n是请求的项数,操作将递归向下经过任何中间节点的桶,用c(r,x)函数(在章节3.4中为每种类型的桶分别定义)伪随机地在每个桶中选中一个被嵌套的项目,直到找到了满足要求类型t的项。结果的个项,被放回到输入变量,可以作为后续的select(n,t)操作的输入参数,也可以通过emit操作将其移入结果向量。
  举例说明,[表1]中定义的规则从[图1]中层次结构的root开始,通过第一次select(1,row)操作选中了一个类型为“row”的桶(它选中了row2)。后续的select(3,cabinet)操作在之前选择的row2下面选择了三个各不相同的cabinet(cab21、cab23、cab24),最后一次select(1,disk)在三个cabinet桶之间进行了迭代,对每个cabinet桶在其子树中各选择了1个disk。结果就是分散在3个cabinet中的3个disk,但都在同一个row中。这种方式使得副本能够被同时分发到指定类型(例如row、cabinet、shelf)的设备上,这对提升可靠性与性能都很有帮助。规则包含多个take、emit块,使存储目标可以从不同的存储池中被显式选取出来,在存在远程副本的场景下(某一个副本被存放在远程站点)或者分层架构中(例如高速的近线存储搭配低速大容量阵列)也许会被采用。
 
 
图1:某四级集群映射层次结构的部分视图,包含row、cabinet、shelf和disk。粗体字标出的表示在[表1]中描述的Placement Rules和假想的映射关系中,被每次select操作选中的项。
[图1:某四级集群映射层次结构的部分视图,包含row、cabinet、shelf和disk。粗体字标出的表示在[表1]中描述的Placement Rules和假想的映射关系中,被每次select操作选中的项。]
 
动作序列 结果
take(root) root
select(1,row) row2
select(3,cabinet) cab21 cab23 cab24
select(1,disk) disk2107 disk2313 disk 2437
emit  
[表1:一条简单的规则,将三个副本分发到同一个row的三个不同的cabinet中。]

[算法1:CRUSH确定对象x的存放位置]

3.2.1 冲突、故障和过载

 
  select(n,t)操作可能为了定位n个各不相同的t类型的项而从起点开始向下遍历而经过许多层,递归过程的次数由r=1,...,n确定,n是选择的副本个数。处理过程中,CRUSH可能会由于下面三个不同的原因而用修改过的输入r'来拒绝并重选项:某个项已经在当前的集合中了(发生了冲突,select(n,t)的结果必须是各不相同的);有一个设备失效了;有一个设备过载了。失效或过载的设备会在Cluster Map中进行相应的标记,但为了避免不必要的数据移动,不会从层次结构中移除它们。CRUSH通过根据Cluster Map中指定的概率伪随机地拒绝选择过载设备,来选择性地转移此过载设备上的少部分数据,这个概率则是与报告的过载情况有关的。对于失效或过载的设备,CRUSH通过重新启动select(n,t)开始部分的递归过程(详见[算法1第11行]),均匀地在存储集群中重新分布这些项。而对于冲突的情况,则在递归内层使用r'替换r来进行局部搜索(详见[算法1第14行]),不至于在那些很可能发生冲突的子树中(例如,桶的容量小于n)改变总体的数据分布。
 

3.2.2 副本排序

 
  与奇偶校验码、擦除码相比,副本方式在存储位置要求上有些许的不同。在主拷贝副本模式中,发生故障时让之前的副本目标(已经有数据的一份拷贝)成为新的主拷贝是可取的。在这种情况下,CRUSH可以通过用r'=r+f进行重选,来使用“前n个”合适的目标,f是当前select(n,t)操作中确定放置位置失败的次数(详见[算法1第16行])。而对于奇偶校验码或者擦除码模式,CRUSH算法输出的存储设备的顺序就至关重要了,因为每个目标都存放了数据对象的不同比特位。特别地,当某个存储设备发生故障时,它需要在CRUSH的输出列表的对应位置上被替换,其他列表中的设备要维持位置不变(位置就是指在的对应位置,详见[图2])。在这种情况下,CRUSH通过进行重选,其中是第r此迭代时失败的次数,这样就为每一个向量位置上的项定义了一系列候选项,每个候选项与其他位置上的候选项是无关的。相比之下,RUSH对于发生故障的设备没有特殊处理,就像其他现有的散列分布式函数,它隐式地假设使用“前n个”的策略在结果中跳过失效的设备,在奇偶校验这样的模式下就难以使用了。
 
[图2:select(6,disk)当设备r=2(b)被拒绝时的重选行为,方框中包含了CRUSH当n=6台设备时按编号顺序输出的。左边表示“前n个”方案,已有设备(c、d、e、f)的序号可能发生改变。在右边,每个序号都有独立的一系列可能的目标,在这里=1,且=8(设备h)。]
 

3.3 映射变更与数据移动

 
  大型文件系统中数据分布的一个关键问题是增删存储资源时的响应方式。CRUSH始终保持数据的均匀分布,以避免负载的不均衡,以及可用资源没有得到充分利用的情况。当某个设备发生故障的时候,CRUSH会为其置上标记,但仍然将其保留在层次结构中,下次选择时将被CRUSH算法拒绝,并根据位置算法(详见[章节3.2.1])均匀地将将其内容分发到其他的设备上。这样的Cluster 
Map变化使得需要重新映射到新存储目标上的数据最少,这个比例是(其中W是所有设备的权重总和),因为只有失效设备上的数据被移动了。
  当集群的层次结构由于增删存储资源而发生改变时情况要更加复杂。CRUSH的映射过程,将Cluster Map作为带权的决策树,可能导致额外的数据移动,超过理论上最佳的比例。在层次结构的每一层,每一次相关子树的权值改变,都要改变数据分布,一部分数据对象就需要从权值下降的子树移动到权值上升的子树中。由于层次结构中每个节点上的伪随机位置决策在统计意义上是相互独立的,移入某个子树的数据被均匀地分布在那一点下,而且并不一定需要被重新映射到直接导致权值变化的那个叶子节点中。只有在定位过程相对比较深的层次,才会为维持总体的数据分布而移动数据。在一个二叉树结构中的大致效果在[图3]中进行了展示。
  数据移动的最小量是,这一部分数据会被移动到新增的权值为的设备上。数据的移动量随着层次结构的高度h的增加而增加,数据移动量渐进地趋向。当相对于W足够小的时候,数据的移动量就趋近于上界,因为递归过程的每一步数据对象移动到一颗子树时,被映射到权值很小的项上的概率很小。
 
[图3:在二叉树结构中由于增加一个节点,一系列权值改变造成的数据移动示意图。]
 

3.4 桶的类型

 
  一般地,CRUSH算法的设计是为了权衡两个互斥的目标:映射算法的效率与可靠性,增删设备导致的集群变更时恢复平衡的数据迁移成本最小化。为此,CRUSH定义了四种不同类型的桶来代表集群层次结构中的中间节点(非叶子节点):Uniform Bucket、List Bucket、Tree Bucket、Straw Bucket。每种桶都基于一种不同的内部数据结构,并且分别使用了不同的在定位过程中选择嵌套项的伪随机函数c(r,x),体现了计算效率和数据重组效率之间的不同权衡方法。Uniform Bucket要求桶内所有的项权值必须相等(更像那种传统的散列分布函数),而其他类型的桶可以包含任意权值的项的任意组合。这些区别在[表2]中进行了总结。
 
项目名 Uniform List Tree Straw
速度 O(1) O(n) O(log n) O(n)
添加项 最优 最优
移除项 最优
[表2:不同类型的桶当从桶中增加或移除项时,映射速度和数据重组效率的总结。]
 

3.4.1 Uniform Bucket

 
  在大型系统中设备很少一个一个添加,相反,新的存储往往部署一批相同的设备来提供的,通常是一个服务器机架甚至是一整个机柜。超过年限的设备也通常是成组退役(单点故障除外),那么就很自然可以将它们视为一个整体。CRUSH的Uniform Bucket就可以表示这种情况下的一组相同设备。这样做的关键优势与性能有关:CRUSH可以在常数级的时间复杂度内将副本映射到Uniform Bucket。在不满足这种均匀的限制条件的时候,就可以使用其他类型的桶。
  给定一个CRUSH输入参数x和副本数量r,我们在大小为m的Uniform Bucket中使用函数c(r,x)=(hash(x)+rp) mod m选择一个项,p是一个比m大的随机选出的(但确定性的)素数。对于任意的,根据一些数论原理,我们总能够根据输入选出各不相同的项。[注释2:等差数列的素数定理[Granville 1993]说明了,这个函数会提供mφ(m)种不同的方式,将对象x的副本进行分发,每种分发方式的选取都是等概率的,φ()是欧拉φ函数。]对于的情况这一点就无法保证了,这表示同一个输入的两个不同副本也许会被映射到同一个项中。实际应用中,这就表示位置算法产生冲突并导致后续的回溯动作并不是不可能的(详见[章节3.2.1])。
  Uniform Bucket的大小如果改变,那么设备中的数据会被完全重组,更像是那种传统的基于散列函数的分布策略。
 

3.4.2 List Bucket

 
  List Bucket将其中的内容组织为链表,并能容纳任意权重的项。定位一个副本时,CRUSH从存有最近添加的项的链表头部开始,并比较其权重与所有其余项的总和。根据hash(x,r,item)的结果,要么当前项按一定合适概率被选中,要么就继续处理列表中的下一项。这种方式来源于RUSHP,将定位的问题改造为“是最近添加的还是以前添加的项”。在一个不断扩展的集群中这是一种自然而又符合直觉的办法:要么对象按一定合适的概率被分配到最新的设备中,要么对象还是留在以前的设备中。这使增删桶中的项时数据移动最小化。而当列表中间或者末尾的项被移除的时候,会导致大量不必要的数据移动,因此List Bucket适用于从不或很少收缩的桶。
  RUSHP算法大致相当于两层的CRUSH层次结构,由一个List Bucket包含许多Uniform Bucket。这种固定的表示形式,不包含Placement Rule的使用,或者CRUSH中为了增强可靠性的、用于控制数据定位的失效域。
 

3.4.3 Tree Bucket

 
  和任何链式的数据结构一样,List Bucket在比较小的项目集合下还算高效,但对于大的集合就不那么理想了,O(n)的运行时间就显得太多了。由RUSH[T]演变而来的Tree Bucket通过以二叉树形式存放项来解决这个问题,将定位时间降低为O(log(n)),使其适用于管理大得多的设备数量,或者嵌套的桶结构。RUSHT等效于一个两层的CRUSH层次结构,一个Tree Bucket,每个节点是Uniform Bucket。
  Tree Bucket是带权的二叉排序树,所有项位于叶子节点。每个内部节点都知道其左右子树的总权重,并以一种固定的策略进行标记(将在后面详述)。要在桶中选出一项,CRUSH从树的根节点开始,计算输入参数x、副本数量r、桶标识符和当前节点(初始是根节点)的标记的散列值。结果将分别与左右子树的权重比进行比较,以决定接下来访问哪个子节点。过程循环至到达叶子节点为止,最终指向的对应桶中的项就被选中了。要定位一个项只需要log(n)次散列计算和节点比较。
  桶的二叉树节点总是用一种简单固定的从策略进行二进制值标记,以避免树的增长和收缩导致标记的变化。树最左侧的叶子节点总是被标记为“1”。每次树扩展的时候,旧的根节点就成为新的根节点的左孩子,新根节点的标记是旧根节点标记左移一位(1、10、100……)。右孩子的标记和左孩子标记的基础上在每个标记左侧增加一个“1”。一棵有6个节点的二叉树标记如[图4]所示。这一策略保证了当新的项添加(或删除),桶和树结构增长(或收缩),通向现有叶子节点的项仅通过增加(或删除)根节点,在决策树的初始位置发生变化。一旦某个对象被放置在某个特定的子树中,只要这棵子树中的项保持固定不变,这项的最终映射就只与权值和节点标记有关了,并且节点标记也保持不变。尽管层次化的决策树造成了嵌套项之间一些额外的数据迁移,不过额外的数据迁移还是控制在合理的范围之内,并且能为很大规模的桶提供高效的映射。
 
[图4:组成Tree Bucket的二叉树节点标记策略。]
 

3.4.4 Straw Bucket

 
  List Bucket和Tree Bucket的结构,使得选择一个桶中的项只需要有限次的散列值计算和权重比较。这样做时,它们使用分而治之的方法,给特定项提供优先选择的机会(例如,在列表首部的项),或消除了考察整棵子树中所有项的必要。这提升了定位副本过程的性能,不过桶的内容因为设备增删或调整权重而改变的时候,就不能保证数据重组的最优化了。
  Straw Bucket让所有项能够通过类似抽签的方法与其他项公平“竞争”。要定位一个副本,每个桶中的项都被分配到一根随机长度的麦秆,抽到最长麦秆的项就胜出了。每根麦秆的初始长度都是某个固定范围内基于CRUSH的输入x、副本数量r、桶中的项i的散列值的一个值。每根麦秆的长度再根据基于项权值的因子进行缩放,因此权值较大的项比较容易胜出,即[注释3:尽管的简单封闭形式还没有找到,但通过程序方式来计算权值因子还是比较简单易行的(源代码可供参考)。只有在桶发生修改时,才需要重新计算一次这个因子。]尽管这一过程要比List Bucket慢上(平均)几乎一倍,比Tree Bucket(对数数量级)更慢,Straw Bucket却提供了修改时嵌套项间的最佳数据移动。
 
  桶类型的选择应该是由预期的集群增长模式来指导,以权衡映射方法的运算量和数据移动的效率,我们总该做好这样的权衡。当桶预期是固定的(比如,一个机架的相同磁盘),Uniform Bucket最快。当桶预期只会增长,List Bucket在列表头部添加新项时能提供最少的数据移动,这使CRUSH可以准确地转移恰当的数据量到新添加的设备中而不去影响其他桶中的项,缺点是O(n)的映射速度和当旧项被移除或改变权重时的额外数据移动。在很可能移除设备,并且数据重组效率要求很高的场合(例如,靠近存储层次根节点处),Straw Bucket提供了子树间最少的数据迁移。而Tree Bucket则是全面妥协,提供了出色的性能的同时,也保证了令人满意的数据重组效率。

CRUSH:受控的、可扩展的数据副本分散存储方案(Part 2)

 

** 以下内容为翻译
** 原文及版权声明:http://ssrc.ucsc.edu/Papers/weil-sc06.pdf
** 翻译:softrank.net@gmail.com
** 转载请保留以上信息
** 欢迎各位游客指正翻译中的错误,或提出建议
 

CRUSH:受控的、可扩展的数据副本分散存储方案

作者:Sage A. Weil Scott A. Brandt Ethan L. Miller Carlos Maltzahn
美国加州大学圣克鲁兹分校存储系统研究中心
{sage, scott, elm, carlosm}@cs.ucsc.edu
 

2 相关工作

 
  基于对象的存储作为一种提高存储系统扩展能力的机制,受到了广泛的关注。一些研究项目和生产文件系统已经开始使用这种基于对象的思想,包括影响力很大的NASD文件系统[Gobioff et al. 1997]、Panasas文件系统[Nagle et al. 2004]、Lustre[Braam 2004]等等[Rodeh and Teperman 2003; Ghemawat et al. 2003]。其他基于块的文件系统例如GPFS[Schmuck and Haskin 2002]和Federated Array of Bricks(FAB)[Saito et al. 2004]在数据分布问题上都面临着相似的挑战。在这种系统中,使用半随机或者启发式的方法来将新数据分配到可用的设备,但随着时间推移,数据也很少为了维持负载平衡而被重定向。更重要的是,所有这些系统都通过某种元数据目录来定位数据,而CRUSH则是依赖一个紧凑的集群描述和确定性的映射函数。这种特点的优势在写入数据时尤为显著,使用CRUSH的系统可以独立计算出新数据的存储目标位置,而不需要询问中心分配器。Sorrento[Tang et al. 2004]存储系统使用一致性散列函数[Karger et al. 1997],与CRUSH最为相似,但是缺少对于设备权重控制、数据负载平衡以及保障数据安全的故障域的支持。
  尽管在具有显式分配映射表[Anderson et al. 2001; Anderson et al. 2002]的系统中,数据迁移的问题已经得到了广泛的研究,但这种方式带来的庞大的元数据,正是CRUSH算法通过函数式的思想加以避免的。Choy, et al. [1996]描述了一种在磁盘间分发数据的算法,目标是使得在增加磁盘时移动的对象数量最少,但这个算法不支持权重设定、复制以及磁盘移除。Brinkmann, et al. [2000]使用散列函数在异构的集群中分发数据,但这个集群必须是静态的。SCADDAR[Goel et al. 2002]解决了增加和移除磁盘的问题,但是只支持容灾策略的一个有限的子集。以上这些算法,都不像CRUSH一样既提供灵活性,又提供增强可靠性的故障域控制。
  CRUSH算法与RUSH系列算法[Honicky and Miller 2004]最为近似,CRUSH算法是以RUSH为基础的。RUSH是这篇文章中提到的算法中,唯一使用映射函数代替元数据列表,并支持带权重的设备的高效添加与移除。尽管已经具备了这些特性,仍然有一系列的问题,导致RUSH还无法应用于实际问题。CRUSH算法完全泛化了RUSHP和RUSHT中有用的元素,并且解决了之前遗留的可靠性问题、副本问题,并实现了性能和灵活性的提升。
 

3 CRUSH算法

 
  CRUSH算法根据每台设备的权重在存储设备间分发数据,大致是均匀分布的。数据分发是由一个层次化的Cluster Map控制的,Cluster Map描述了可用的存储资源,由建立集群映射的一些逻辑元素所组成。例如,某个Cluster Map可能描述了一个大型装置,包含了一排机柜,每个机柜有许多磁盘架,每个磁盘架上有许多存储设备。数据分配策略是由Placement Rules定义的,Placement Rules指定了从及群众选中的副本目标的数量,以及放置这些副本的限制条件。例如,某个Placement Rule也许会指定三个镜像副本要被放置在不同的物理机柜上,以避免这些副本共享同一条供电线路。
  给出一个整型输入值x,CRUSH会输出一个有序的、包含n个各不相同的存储目标的R向量。CRUSH使用一个多输入的整形散列函数,参数列表包含x,使得映射是完全独立且确定性的,仅仅依赖于Cluster Map、Placement Rules和输入参数值x。数据分发是伪随机的,输出结果与输入值或者设备中现有的对象之间没有明显的相关性。我们说CRUSH提供了一个去集群化的副本分布方案,包含某对象的共享副本的这些设备也是相对其他对象而独立的。
 

3.1 层次化Cluster Map

 
  Cluster Map由设备和桶组成,它们都有数值型的标识符和权值。桶可以包含任意数量的设备或是其他桶,使它们形成存储的树状结构中的内部节点,设备总是这个树结构的叶子节点。每个存储设备都由管理员赋予权值,控制该设备的相对数据存储能力。尽管一个大型系统往往包含了存储能力和性能特点都不相同的设备,但是随机的数据分布,在统计意义上将设备的使用情况与负载关联起来,可以将设备的负载占总体的比例保持在平均的水平上。这就使得这个描述数据放置规则的一位标量(权重)是取决于设备的容量的。而桶的权重则由其包含的所有项的权重总和。
  桶可以以任意形式组织成树状结构来描述可用的存储结构。例如某人可以创建名叫“shelf”的桶,以包含一组相同的存储设备,然后将“shelf”组装成“cabinet”,以此将同一个机架上的存储设备组织到一起,“cabinet”也可以被组装成名叫“row”或“room”的桶来适应一个更大的系统。数据通过类似伪随机的散列函数递归选择嵌套项目,将数据存放到层次结构中。在传统的散列技术下,任何目标设备数量的改变,都会导致一次很大规模的数据迁移,相比之下,CRUSH基于四种不同类型的桶,每种对应一种不同的选择算法,来解决增删设备时导致的数据移动和总体计算复杂度。

 

CRUSH:受控的、可扩展的数据副本分散存储方案(Part 1)

 

** 以下内容为翻译
** 原文及版权声明:http://ssrc.ucsc.edu/Papers/weil-sc06.pdf
** 翻译:softrank.net@gmail.com
** 转载请保留以上信息
** 欢迎各位游客指正翻译中的错误,或提出建议
 

CRUSH:受控的、可扩展的数据副本分散存储方案

作者:Sage A. Weil Scott A. Brandt Ethan L. Miller Carlos Maltzahn
美国加州大学圣克鲁兹分校存储系统研究中心
{sage, scott, elm, carlosm}@cs.ucsc.edu
 

摘要

 
  新兴的大规模分布式存储系统正面临着将PB级的数据分散到成千上万个存储设备上的挑战,这样的系统必须要均匀分布数据与负载,是的系统资源及性能能够得到最大程度的利用,同时应对系统的增长和硬件故障。我们开发了CRUSH算法,它是一个可扩展的伪随机数据分布函数,用于在基于对象的存储系统中,将数据对象高效地与存储设备建立映射,而无需通过查找中心目录的机制。由于大规模的系统向来都是动态化的,因此CRUSH的设计有利于存储设备的增加和移除,并尽可能减少不必要的数据移动。算法能够适应各种数据冗余和可靠性机制的要求,按照用户定义的方式管理数据的分布,增强了跨故障域数据副本的隔离性。
 

1 简介

 
  基于对象的存储是一种新兴的存储架构,增强了可维护性、可扩展性和性能[Azagury et al. 2003]。与基于块存储的传统硬盘驱动器不同,基于对象的存储设备在内部管理物理块的分配,仅对外提供读写不同大小的命名对象。在这种系统中,每个文件的数据通常都被条带化地分散于相对较少数的命名对象中,分散地存储于存储集群中。对象在多个设备间保留副本(或者使用其他某种数据冗余模式),以防止发生故障时可能导致的数据丢失。基于对象的存储系统用较小的对象列表代替庞大的块映射表,分散了底层块分配问题的处理压力,使得数据的布局更加简化。尽管通过减少文件分配元信息的复杂性,已经极大提高了可扩展性,然而如何在成千上万的设备上(尤其是容量、性能迥异的设备)分发数据的基本问题仍然存在。
  大多数系统只是简单地将新数据写入到尚有空余的设备上,这种方法的基本问题是,数据只有在被写入时可能会移动,其他情况几乎不会移动。即便是一种完美的分布,随着系统规模的增长也会变得难以平衡,因为新磁盘要么是空的,要么包含了新数据,要么旧的磁盘忙,要么新的磁盘忙,这取决于系统的负载,而只有在某种极为罕见的特定情况下,才能使得可用资源平衡地得到最大限度的充分利用。
  一种健壮的解决方案是将所有数据随机分布在可用的存储设备中。这实现了依概率的均衡数据分布,以及新老数据以类似的方式的混合存放在一起。当新设备添加到系统中时,一些随机的数据样本会被迁移到新的设备上以维持其负载的平衡。这种做法的好处是,平均来讲,所有设备的负载情况都差不多,使得系统在各种可能的负载情况下都能够高效运作[Santos et al. 2000]。此外,在一个大的存储系统中,单个大文件会被随机分布到许多可用的存储设备中,提供了高度的并行性和聚合带宽。然而简单的基于散列函数的分布无法应对设备数量的变化,将造成了大规模的数据迁移。而现有的随机分布模式将磁盘副本随机分配到其他设备上,增加了由于意外的设备故障导致数据丢失的可能性。
  我们开发了CRUSH(可扩展散列下的受控复制算法)是一个伪随机数据分布算法,高效且可靠地将数据分发到异构的、结构化的存储集群中。CRUSH是伪随机的、确定性的算法,将一个输入值(往往是对象或对象组标识符)映射到一组存有相应对象副本的设备上。与其他传统方法明显不同的一点是,我们不需要任何形式的文件或对象目录,CRUSH只需要一个包含存储集群及其数据存放策略的紧凑的而层次化的设备描述。这种方式有两个关键的优越性:首先,它是完全分布式的,这意味着一个大型系统的任何参与者都可以独立计算出对象所在的位置;第二,仅需要的少量元数据是静态的,这些元数据仅当增加或移除设备时才发生变化。
  CRUSH的设计使得它能够以最佳的方式分发数据,充分地利用资源,在设备增加或移除时高效地组织数据,灵活地限定数据对象副本的存放策略,最大程度地保障设备的意外或相关故障下的数据安全。各种数据安全策略都有广泛的支持,包括n-way复制(镜像)、RAID奇偶校验策略或者其他的校验策略,或者是其他某种混合的方式(例如RAID-10)。这些特性使得CRUSH非常适合在扩展能力、性能和可靠性都非常关键的存储系统中,管理超大规模的数据(PB级数据量)。

在C++中使用成员函数指针

函数指针的语法相对比较复杂,成员函数指针则在此基础上进一步引入了类作用域限定。让我们来了解一下成员函数指针的写法。

首先回顾一下函数指针的使用方法。有这样一个函数:

 

double func(double x)
{
	return 3.14 * x;
}

我们这样声明函数指针,并且进行调用:

 

	double (*pfunc)(double x);
	pfunc = &func;
	cout << (*pfunc)(1.1) << endl;

指针的声明包括返回类型、指针名和函数的参数表,对于一个强类型的编译型语言,这些要素都必不可少。由于运算符优先级的规定,还要特别注意在适当的位置加上括号。

对于成员函数指针,就是增加了一个作用域限定。

首先有一个类A,包含几个类型相同的函数。

 

class A
{
public:
	void f1(int x)
	{
		cout << "f1:" << x << endl;
	}
	void f2(int x)
	{
		cout << "f2:" << x << endl;
	}
	void f3(int x)
	{
		cout << "f3:" << x << endl;
	}
};

然后类B的对象会调用类A的对象的成员函数,然而具体调用哪一个还不知道,我们通过指针的方式来实现,在运行时将指针指向一个类型兼容的成员函数。

 

class B
{
public:
	void (A::*pf) (int x); //注意作用域运算符和*的次序,括号不能省略

	void callF(int x)
	{
		A a;
		(a.*pf)(x);
	}
};

我们在外部实例化B的对象,然后为B的成员函数指针赋值,确定将要调用的是哪一个函数。

 

	cout << "Hello world!" << endl;
	B b;
	b.pf = &A::f2;
	b.callF(5);

MySQL事件调度器的基本使用方法

  根据MySQL的官方文档,从MySQL的5.1.6版本开始,MySQL支持了事件调度器,用于处理事件的调度与执行。触发器用于根据DML操作来触发事件,而事件调度器则是定时触发事件,功能类似于Linux的crontab计划任务,但是控制更为精确。在MySQL支持这项功能之前,往往通过Linux的crontab来辅助进行定时任务的触发,而当我们对于任务有更高的定时要求时,或者考虑调用接口处的性能瓶颈时,就需要使用到事件调度器(Event Scheduler)。

  首先确保数据库选项event_scheduler处于开启状态。

 

show variables like 'event_scheduler';

  如果我们看到ON,就表示这个功能处于开启状态,如果为OFF,表示关闭,DISABLED表示禁用。请注意,在数据库实例启动的情况下,我们可以随时在on和off间进行切换,但是,无法从on或off切换到disabled,也无法从disabled切换到on或off。只有在数据库关闭的状态下,这种转换才会生效。(DISABLED状态是在5.1.12版本中引入的)

 

set @@global.event_scheduler=on;

  设置完成后,事件调度器就被开启了,实质上,是在MySQL实例中新建了一个事件调度器线程,通过show processlist\G命令,可以找到一个User为event_scheduler的线程,就表示事件调度器现在可以使用了。

  接着我们随便创建一个存储过程,比如往某个表插入一条记录,好让事件调度器进行调度。

 

delimiter //
create procedure `do_something`()
begin

insert into timelog values ();

end; //
delimiter ;

  创建完毕后,我们就开始创建事件,事件最重要的部分有以下几个:

  • 事件名称,这个很简单,就是给事件起个名字,加上IF NOT EXISTS的话,如果给定名称的事件已经存在了就不会再创建,并且只抛出一个Warning。
  • 调度时间(ON SCHEDULE),可以定义事件被触发的具体时间,也可以指定事件被触发的周期,如果指定周期性任务,还可以指定开始时间和结束时间。
  • 事件完成后的行为(ON COMPLETION),默认为NOT PRESERVED,即事件完成以后删除任务本身,注意,对于周期性的任务,不表示事件只做一次,而是指到达结束时间后,再删除这个事件。可以将它指定为PRESERVED,那么当事件完成以后,不会被删除。
  • 事件体,就是事件具体需要做什么,定义方式和存储过程类似。

 

CREATE EVENT IF NOT EXISTS `log_every_minute`
ON SCHEDULE EVERY 1 MINUTE
ON COMPLETION PRESERVE
DO
CALL do_something();

  在event_scheduler为on的情况下,事件一经创建就会生效。

  这样,我们就成功创建了一个事件,每分钟会在timelog表中插入一条记录,当然,我们可以根据自己的需要,让MySQL去做一些更为复杂的任务。

C++中的函数对象与Lambda表达式

  函数对象是C++中以参数形式传递函数的一个很好的方法,我们将函数包装成类,并且利用()运算符重载实现。

 

typedef class hello {
public:
	void operator()(double x) {
		cout << x << endl;
	}
} hello;

  这时候hello是一个类,我们可以实例化一个对象hello h;,然后通过h(3.14)的方式来调用这个类的成员函数,如果某个函数需要这个函数作为回调函数,则可以将这个hello类的对象传入即可。

  因为这是一个类的定义,因此我们完全可以在其中定义一些包含额外信息的成员和一些构造函数,让这个函数对象可以做更多不同的可定制的任务,最终的行为实际上只是调用了这个()运算符重载函数。这种做法比C++函数指针要容易理解得多,也不容易写错。

  而Lambda表达式则是C++中的新语法,实现了许多程序员渴望的部分闭包特性。C++中Lambda表达式可以被视为一种匿名函数,这样,对于一些非常短,而且不太可能被其他地方的复用的小函数,可以通过Lambda表达式提高代码的可读性。

  在Lambda表达式中对于变量生命期的控制还是与完全支持闭包的JavaScript非常不同,总而言之,C++对于变量声明期的控制在新标准中完全向前兼容,也就是局部变量一定在退出代码块时被销毁,而不是观察其是否被引用。因此,尽管C++的Lambda表达式中允许引用其代码上下文中的值,但是实际上并不能够保证引用的对象一定没有被销毁。

  Lambda表达式对于上下文变量的引用有值传递和引用传递两种方式,实际上,无论是哪种方式,在产生Lambda表达式对象时,这些上下文值就已经从属于Lambda表达式对象了,也就是说,代码运行至定义Lambda表达式处时,通过值传递方式访问的上下文变量值已经被写入Lambda表达式的栈中,而引用方式传递的上下文变量地址被写入Lambda表达式的栈中。因此,调用Lambda表达式时得到的上下文变量值就是定义Lambda表达式时这些变量的值,而引用的上下文变量,如果已经被销毁,则会出现运行时异常。

  Lambda表达式的基本语法是:

  [上下文变量说明](Lambda表达式参数表) -> 返回类型 { 语句块 }

  上下文变量说明部分就是说明对于上下文变量的引用方式,=表示值传递,&表示引用传递,例如,&s就表示s变量采用引用传递,不同的说明项之间用逗号分隔,可以为空,但是方括号不能够省略。第一项可以是单独的一个=或者&,表示,所有上下文变量若无特殊说明一律采用值传递/引用传递,什么都不写默认为值传递。

  Lambda表达式和TR1标准对应的function<返回类型 (参数表)>对象是可以互相类型转换的,这样,我们也可以将Lambda表达式作为参数进行传递,也可以作为返回值返回。

  下面看一个Lambda表达式各种使用方法的完整例子:

 

// compile with: /EHsc
#include <iostream>
#include <string>
#include <functional> //这是TR1的头文件,定义了function类模板
using namespace std;

typedef class hello {
public:
	void operator()(double x) {
		cout << x << endl;
	}
} hello; //函数对象的定义,也是非常常用的回调函数实现方法

void callhello(string s, hello func) {
	cout << s;
	func(3.14);
} //一个普通的函数

void callhello(string s, const function<void (double x)>& func) {
	cout << s;
	func(3.14);
} //这个函数会接受一个字符串和一个Lambda表达式作为参数

void callhello(string s, double d) {
	[=] (double x) {
		cout << s << x << endl;
	}(d);
} //这个函数体内定义了一个Lambda表达式并立即调用

function<void (double x)> returnLambda(string s) {
	cout << s << endl;
	function<void (double x)> f = ([=/*这里必须使用值传递,因为s变量在returnLambda返回后就被销毁*/] (double x) {
		cout << s << x << endl;
	});
	s = "changed"; //这里对s的修改Lambda表达式是无法感知的,调用这句语句前s在Lambda表达式中的值已经确定了
	return f;
} //这个函数接受了一个值传递的字符串变量s,我们将Lambda表达式作为返回值返回

function<void (double x)> returnLambda2(string& s) {
	cout << s << endl;
	function<void (double x)> f = ([&s/*这里可以使用引用传递,因为s是引用方式传入的,不随函数返回而消亡*/] (double x) {
		cout << s << x << endl;
	});
	s = "changed"; //这里对s的修改Lambda表达式是可以感知的,因为s以引用方式参与到Lambda表达式上下文中
	return f;
} //这个函数接受了一个引用传递的字符串变量s,将Lambda表达式作为返回值返回

int main() 
{
	hello h;
	callhello("hello:", h); //用函数对象的方式实现功能
	callhello("hello lambda:", -3.14); //这个函数体内定义了一个Lambda表达式并立即调用
	int temp = 6;
	callhello("hello lambda2:", [&] (double x) -> void {
		cout << x << endl;
		cout << temp++ << endl;
	}); //这个函数会接受一个字符串和一个Lambda表达式作为参数
	cout << temp << endl;

	function<void (double x)> f = returnLambda("lambda string"); //这个函数接受了一个值传递的字符串变量s,我们将Lambda表达式作为返回值返回
	f(3.3);
	string lambdastring2 = "lambda string2"; //这个变量在main函数返回时才被销毁
	f = returnLambda2(lambdastring2); //这个函数接受了一个引用传递的字符串变量s,将Lambda表达式作为返回值返回
	f(6.6);
	
	system("pause");
}

 

C++中的typedef语法简介

  根据名字也可以猜测到,typedef这种语法可以用于定义类型,如果某种类型的名称很长,或者未类型增加语义,那么我们就可以考虑使用typedef。看看最简单的例子:

 

typedef int INT;

  上面的一行代码就表示INT也能代表int,这条定义可以在Windows头文件中找到。有什么意义呢?这是一种跨平台编译的考虑,看一下另一个Windows头文件中的例子:

 

#ifndef UNICODE 
typedef char TCHAR; 
#else 
typede wchar_t TCHAR; 
#endif 

  如果当前环境支持Unicode,那么TCHAR就会等价于wchar_t宽字符类型,否则TCHAR等价于char类型,那么程序员就可以借助TCHAR来隐藏具体的编译环境。

  此外,typedef还可以增强语义,在Windows中所有的句柄本质都是void*类型,而为了增强语义,产生了HWND、HMENU、HBRUSH等不同的类型,让程序可读性增强。

  大多数情况下,typedef是可以用#define来进行替换的,例如:

 

#define INT int

不过问题在于,#define只是进行了简单的字符替换,在编译前就被预编译器处理了,而typedef的处理则是编译器行为,因此使用typedef,编译器将能够视INT为一个类型,而不是其他东西。下面还有一个用#define容易引起混淆的例子。

 

#define pINT int*;
typedef int *pINT2;

pINT a, b;
pINT2 c, d;

  一般而言,我们通过类型定义,是希望将pINT定义成一种类型,那么用这种类型进行定义得到的变量,都应该是这种类型。而如果使用#define,那么看起来我们用pINT定义了a和b,实际上只有a是int*,而b只是int。使用typedef很好地避免了这个问题,c和d都是int*类型,这样不至于产生混乱的语义。

  另外,因为typedef不是预编译指令,而被当作语句执行,因此也是有作用域的,typedef的作用域和一般变量相同。冲突的定义会进行覆盖,较晚执行的typedef会覆盖较早执行的typedef。

  最后,typedef还可以用来定义类、结构体、联合体、数组,甚至是函数类型,下面有一个比较全面的代码例子,可以参考注释理解其中的含义:

 

#include <iostream>
using namespace std;

typedef int* _int, _int2; //_int是int*类型,而_int2是int类型
typedef int INT; //INT是int类型
typedef _int *INT2, *INT3; //INT2和INT3都是*_int类型,也就是**int类型

typedef void (*funcptr)(double); //funcptr是一个函数指针类型,指向返回值为void,接受一个double类型参数的函数

typedef union {
	char c;
	int i;
	bool b;
} Foo; //Foo是一个联合体

typedef class TestClass {
	int a, b, c;
public:
	TestClass(int a, int b, int c) : a(a), b(b), c(c) {
	}
} TESTCLASS; //TESTCLASS就是TestClass类

void hello(double x) { //funcptr可以指向这个函数
	cout << x << endl;
}

int main() {
	INT a = 6;
	_int2 e = 7;
	_int c = &a;
	INT2 b = &c;
	INT3 d = &c;
	cout << a << e << *c << **b << **d << endl;

	funcptr p = hello;
	p(3.333);
	cout << p << endl;

	Foo foo;
	foo.i = 65;
	cout << foo.b << foo.c << foo.i << endl;

	TESTCLASS tc(1, 2, 3);

	system("pause");
	return 0;
}

C++断言与静态断言

  断言是很早之前就有的东西了,只需要引入cassert头文件即可使用。往往assert被用于检查不可能发生的行为,来确保开发者在调试阶段尽早发现“不可能”事件真的发生了,如果真的发生了,那么就表示代码的逻辑存在问题。最好的一点就是,断言只在Debug中生效,因此对于Release版本是没有效率上的影响的。

 

#include <iostream>
#include <cassert>
using namespace std;

int main() {
	int i = 22;
	assert(i != 22);
	system("pause");
	return 0;
}

  上面的代码就表示,你确认在这里i一定不会等于22,如果事实上真的是22,那么程序就会无情地被abort,并报告出现问题的源文件和行号(使用了魔法常量__FILE__和__LINE__),有助于及时定位问题。

  断言有一个问题,就是一定会abort,强制整个程序退出而导致调试也无法继续进行,就像上图这样,出现问题后,我们知道了出现问题的行号,但是我们需要手动在该行的上面设置断点,重新开始调试才能够检查到发生问题时各个变量的状态。而且,有时问题不是那么容易重现,于是就可能出现没法重现错误再检查状态的问题。

  所以,我们可以自己写一个类似的宏来解决这个问题,我们希望在违反断言时触发断点陷阱门中断而不是调用abort,这样,在违反断言时程序会暂停下来,等待程序员来检查当前的状态有何异常。

  下面是一个Visual C++中的实现。

 

#include <iostream>
#include <cassert>
using namespace std;

#define _ASSERT(x) if (!(x)) __asm {int 3};

int main() {
	int i = 22;
	//assert(i != 22);
	_ASSERT(i != 22);
	system("pause");
	return 0;
}

  上面定义了一个宏,名字当然可以自己取,实际上做的一件事就是检查断言,然后如果断言结果为false(0),那么就调用内联汇编指令int 3陷入调试中断。

  在2011年的C++标准中出现了静态断言(static_assert)的语法,所谓静态断言,就是在编译时就能够进行检查的断言,static_assert是C++的标准语法,不需要引用头文件。静态断言的另一个好处是,可以自定义违反断言时的编译错误信息。

 

#include <iostream>
using namespace std;

int main() {
	const int i = 22;
	static_assert(i != 22, "i equals to 22");
	system("pause");
	return 0;
}

  这个代码,将无法通过编译,因为i的值违反了静态断言。

  静态断言的限制是,断言本身必须是常量表达式,如果这样的i不是常量,静态断言是不符合语法的。

 

大规模中英文单词模糊搜索问题的分析(二)

  经过了大约一个星期时间的考虑,也研究了一下各种开源项目的情况。

  本来满怀期待地发现了拼写检查器Jazzy的源码研究起来,不过后来发现Jazzy已经两年无人问津了,还是有那么点失望的,不过总的来讲,从拼写检查这个思路上,还是找到了一点新的思路的。

  原来使用编辑距离的方法计算单词之间的距离,现在这个核心思想还是没有变,在索引的问题上也有了更多一些的考虑。

  目前考虑下来的主要处理流程是这样的:

1. 对所有库中的人名进行分词,英文按照单词边界进行拆分,而中文按照单个汉字进行拆分,拆分完的汉字全部转换为拼音,这一步比较简单。完成以后就产生了两张二维表,分别是单词表(词典,包含单词、引用计数、是否来自黑名单数据)和倒排索引表(包含单词id、数据库原始条目的id、单词index)。这样就完成了类似Lucene的倒排索引。

2. 为了更好地计算编辑距离,需要建立四张编辑距离权值表(二维表replacement、swap和一维表insert、delete),四张表都不是十分精确的,但是作为索引确实没有十分精确的必要,因为具体的相似度还是依赖于对于单条记录的详细检查。

3. 服务器守护进程随时以流水线方式处理单词与单词之间的相似关系,采用拼写检查器的方法找到字典中的近似单词。

4. 实际向服务器送出查找请求时,服务器首先找到能够精确匹配所有单词的条目,逐条进行相似度检查。如果结果已经过多,那么没有必要再进行后续的查找。如结果较少,那么继续匹配部分单词完全匹配的条目。

5. 如果结果仍然较少,则首先根据编辑距离权值表进行短距离的变换,尝试匹配变换后的结果。

6. 如果仍然没有足够的结果,那么去查找单词近似关系表,如果该单词的近似条目可用,则立即查询得到结果。

7. 如果该单词的近似关系表还没有建立完成,那么提高该单词近似关系处理的优先级,使其立即完成,并进行结果查询。

8. 如果根据待测样本中存在于字典中的单词无法找到足够的项,那么进一步查找不存在于字典中的项,查找流程按照5、6、7的方式进行,建立完成后该单词会被增加到字典中,用以加速下一次的查找。