纠删码(erasure correct code)下的块可用概率

假设:

  1. 一个系统中有N 台机器,M 台为当前故障机器
  2. 使用的纠缠码保证每个块被划分为n 个分片,每个机最多保存一个分片
  3. 需要恢复一个分片最少需要m 个分片

那么一个块在当前可用性概率为:

$P_0 = \sum^{n-m}_{i=0}\frac{\binom{M}{i}\binom{N-M}{n-i}}{\binom{N}{n}}$

  • $P_0$ 是一个块可用的概率
  • n 是所有分片的数目
  • m 为恢复块所需分片的最少数目
  • N 是所有可保存分片的机器
  • M 是当前不可用的机器

说明:

根据全概率公式(某个事件的概率,是该事件在所有情况下的概率的总和)

$\Omega = \sum^{n}_{k=1}A_k   P(B)=\sum^{n}_{k=1}P(A_k)P(B|A_k)$

$\Omega = \sum^{n}_{k=1}A_k $是对B 的一个空间全划分,即包含了B 所有情况。这里的划分是将所有故障机器可能包含的分片(从0 到 n-m,如果超过n-m,那么可用的机器保存的分片少于m 个,也就无法恢复该块数据)。每一个$P_x=\frac{\binom{M}{i}\binom{N-M}{n-i}}{\binom{N}{n}}$ 都代表着:当M 个故障机器中有i 个分片情况下,该事件(块可以被恢复)在所有可能情况下的概率。

既然$\Omega = \sum^{n}_{k=1}A_k $可以是对所有故障机器可能包含分片的划分,也就可以是对所有正常机器可能包含的分片有:

$P_0 = \sum^{n}_{i=m}\frac{\binom{N-M}{i}\binom{M}{n-i}}{\binom{N}{n}}$

即概率等于将i 个可用分片放置到N-M 个可用机器乘以将n-i 个分片放置到M 个故障机器上,除以将全部n 个分片放置到所有N 个机器上的概率。

实例:

举例:n=4,m=2,N=5,M=2 。很容易知道,这个块可用的概率为1 。根据公式

$P_0 = \sum^{2}_{i=0}\frac{\binom{2}{i}\binom{3}{4-i}}{\binom{5}{4}}=\frac{(C^{1}_{2}C^{3}_{3}+C^{2}_{2}C^{2}_{3})}{5}=1$

其中有当i=0 时排除该一项,因为三个节点不可能保存四个分片。

根据另外一个公式可以得到同样结果。

为什么说DEPSKY 是篇好论文

不考虑内容,我心目中的好的论文应该是让读者明白文章解决了什么问题,做了什么工作。而不是使之复杂化,将“1”写成“sin^{2}x+cos^{2}x”的形式。下面就说说为什么Eurosys11 的这篇文章(DEPSKY:Dependable and Secure Storage Cloud-of-Clouds )是篇好文章。

 

  1. 文章解决的问题明确。文章在Introduction 就很清楚的指出了单个云可能存在的问题,并指出DEPSKY 将解决这些问题。
  2. 相关工作有介绍。接着文章有一段是说已经有的类似工作,并指出这些工作要不就是需要在服务器上执行一些代码,要么就是对连接敏感,而DEPSKY 基础是多个云,所以解决问题有所不同。
  3. 直接给出文章工作。我曾在之前的日志中指出快读论文的几个技巧,其中之一就是如果Introduction 最后一段不是讲文章结构的话,就将是谈文章最大的贡献。此文就是这样做的。
  4. 系统应用场景介绍清楚(section 2)。文章很善用编号和分类,使得更有条理。
  5. DEPSKY 系统介绍清楚。从结构到模型、从原理到具体的算法和协议。
  6. Implementation 和Evaluation 就不谈了,基本套路

通读全文,有的section 比较长,但都避免了第三级编号。

Cloud-of-Clouds

Cloud-of-Clouds provides?

  1. Fault-tolerance :容错
  2. Security :通过编码或者secret splitting 提供安全存储

Papers about Cloud-of-Clouds

  1. DepSky – Dependable and Secure Storage in a Cloud-of-Clouds【Eurosys11】
  2. NCCloud: Applying Network Coding for the Storage Repair in a Cloud-of-Clouds【FAST12】

What we can do next?

  1. Using Cloud-of-Clouds provides secure storage with costing less space and less flow.

Main

我的自白书

翻之前的日志发现了08 年写的稿子:


和长辈说话时,他们往往会议过去种种,常常计算自己的一生之中时间是如何流淌过去的,有多长的时间花费在学习上,有过多少时间沉溺于游戏人生,有多少时间花费在亲人和朋友身边,无论是为没有虚度人生而宽慰,还是因碌碌无为而不安,生命中的黄昏总让他们感到不安和遗憾,即使是朝气蓬勃的年轻人,不也为自己的未来或暗淡或迷茫而苦恼么?难道不会为与一起步入大学校门的好友至今却感到恍若隔世的巨大差距而懊悔么?走过人生的每一级台阶,我们或欣喜、或骄傲、或繁忙、或彷徨、或懊悔、或痛苦。我们异或为逃脱惩罚而庆幸,异或为他人超出自己许多而抱怨上天的不公。每个人的想法都是大同小异的,而与此相应我们却会发现人生的轨迹会小同大异。

  二十余年的记忆仍旧觉得匆匆和短促,我不惧去怕死亡和衰老,我却害怕自己年岁大后会不记得现在的自己,我也害怕未来的自己想起现在的自己而多生懊悔,但我尽力去保持住记忆中那最鲜艳的部分,虽然鲜艳背后的灰色半点同样挥之不去,那又会是些生么呢?有时是盛夏长江边的楼顶上,相伴的是抚面的江风和远处发电站隐约的轰鸣、年久失修的隔热层、白天晒化又凝固的陈沥青,踏上去总会给孩童许多额外的惊喜,没有城市亮化工程带来的光污染,亦没有城市建设带来的空气污染,一切洁净得让繁星都起了倦意……不久迁到了城市,在这个陌生的环境中我慢慢的体会成长的痛苦,我也第一次有了回忆过去,因为环境、性格、家庭等原因,我深深被一种情愫所折磨,在四面恶意和伤害中捕捉偶尔闪现的善意和机会,或是友谊或是给予我的善意的期待,就像在黑暗中不停碰撞受伤从没有想象在阳光下会是如何,而一切都只会象倾盆大雨过后的头盔盛满的水,多年过后,我才发现失去的不仅仅是几年的时间、更是在心理上失去了某些本来属于我的东西,而这也将一直影响着我,后来,自己也渐渐学会了一个词汇去描述当时的情愫,这个词就是无助。

   江边城市的天气总体就象我的生活一样波澜不惊的平和,可是真正的突袭一场暴风骤雨也会让你对它改观很多。这种天气通常在午后,瞬时的天气变化令原本阳光明媚的气氛完全打乱,天空变得如同昼夜,风会击碎玻璃夹杂着碎片划伤同学,电压会因为电线的摇摆变得不稳定甚至中断,于是一切似乎都在一瞬间被破坏,一切又都在一瞬间改变。在记忆中也就是那一瞬间,一天早晨起来,对着镜子发现自己长高了不少,也发现脸上不知从何冒出了小痘痘,当发现自己身边环境又完全改变时,我告诉自己,不回避但不关注过去,即使无法决定要走向何处,但我努力做好我自己。接下来的记忆也就是最清晰的部分,这里有叫我多去观察的老师,告诉我面包会有的、房子会有的。还有一起上黄山,爬庐山的朋友和一段段美丽和激动的情感,其中失败和挫折过后的些许快乐就如同晌午空寂的校园的广播中放送着你最喜爱的beyond的歌曲。

  在百多年历史的九江一中里度过了我的高中三年,高一经历了学校的百年校庆,觉得中午免费的午餐特别美味,高二800 米穿着钉鞋昏天暗地跑了第一名的我,高三,看着和自己一起学竞赛的同学报送到了北大(上了college 才发现当时的自己还不够获得成绩的觉悟),失衡了段时间,后来,时间又是同样平静的把我推倒了华中科技大学的门口。

   我大步的跨过了这扇门,而也学明年我又将同样平静而从容的跨过这扇门,过去的几年里,我迎面接受了许多,有些事情做后不久我便能辨别自己做错了或对了,而许多事也许只有期待未来的我来评判,最后还是老套的用萨特的话来结尾:人,就是他行为的全部,这也许最能概括现在的我,因为我在走我毕生都未走过的路。

If you miss the train I’m on,You will know that I am gone

Five hundred miles 是最喜欢的英文歌曲之一,淡淡的忧伤和惆怅中讲述了一个外出工作的男人,在没有挣得钱后害怕也没能力回到自己的家乡,见到自己的爱人,仿佛就像一个落魄的铁道工人圣诞前夕在自己工作的铁路上走着,口袋没有一分钱,没勇气回家。火车从身边一趟趟地飞驰而过,笛声渐近又渐远,这火车上会有自己的爱人么?会不会离自己越来越远呢?……此情此景,这个工人想到了离开家时的情景,不也是这样么——自己在火车上向她们道别,恋恋不舍,自己当时却对未来充满期望,希望能够富足而归,衣锦还乡,结果却是现在此般穷困潦倒。怎么不能叫同样身处异地,为事业和爱情奋斗的人唏嘘感叹、伤感酸楚呢?

歌词中“一百里,两百里,三百里…五百里”和“away from home”反复出现,声音低沉缓慢,无不表现了歌中人对家的眷恋,而“no penny to my name”和“no shirt on my back”却又说明了他穷困潦倒的尴尬处境。道出了外乡人在异地的人生酸楚。

继续阅读