Cuckoo Hash 布谷鸟哈希

Posted on by
2

布谷鸟哈希最早于2001 年由Rasmus Pagh 和Flemming Friche Rodler 提出。该哈希方法是为了解决哈希冲突的问题而提出，利用较少计算换取了较大空间。名称源于该哈希方法行为类似于布谷鸟在别的鸟巢中下蛋，并将别的鸟蛋挤出的行为。它具有占用空间小、查询迅速等特性，可用于Bloom filter 和内存管理。

算法描述

算法使用hashA 和hashB 计算对应key 的位置。

  1. 当两个哈希任意位置为空，则选择一个位置插入
  2. 让两个哈希有位置为空时，则插入到空位置
  3. 当两个哈希位置均不为空时，随机选择两者之一的位置上keyx 踢出，计算踢出的keyx 另一个哈希值对应的位置进行插入，转至2执行（即当再次插入位置为空时插入，仍旧不为空时，踢出这个keyy）

图例

1. 插入key1 两个位置均为空,则插入任意位置.

1

2. 插入后

2

3. 插入key2 两个位置有一个位置为空,则插入空的位置中

3

4. 插入后效果

4

5. 新插入keyi 发现对应两个位置均被占据

 

5

6. 随机选择一个位置提出所在位置的key（key1），将踢出的key 放置在另一个哈希结果对应的位置上

6

7. 如果踢出的key（key1）又占据/踢出了其他key（keyj）的位置，则反复执行上面的过程直到结束

7

其他

  1. Cockoo hash 有两种变形。一种通过增加哈希函数进一步提高空间利用率；另一种是增加哈希表，每个哈希函数对应一个哈希表，每次选择多个张表中空余位置进行放置。三个哈希表可以达到80% 的空间利用率。
  2. Cockoo hash 的过程可能因为反复踢出无限循环下去，这时候就需要进行一次循环踢出的限制，超过限制则认为需要添加新的哈希函数。
  3. 在SOSP 11 的SLIT 文章中有使用Cockoo hash。

增加哈希表过程如下：

当新插入一个key hashA 在上面哈希表位置和hashB 在下面哈希表的位置分别被key1 和keyx 占据，任选一个key 提出（这里选择key1）。

11

计算key1 hashB 的值然后插入到下面的hashB 对应的哈希表中。

 

12

PS

文中图使用graphviz 绘制，图例第七张图片生成文件如下：

   1: digraph G {

   2: "node0" [

   3: label = "<f0>null | <f1>null | <f2>keyi | <f3>null | <f4>null | <f5>key1 | <f6>key2 | <f7>......"

   4: shape = "record"

   5: ];

   6: 

   7: "node2"[

   8: label="key1"

   9: ];

  10: 

  11: "node3"[

  12: label="key2"

  13: ];

  14: 

  15: "node1"[

  16: label="keyi"

  17: ];

  18: 

  19: "node1"->"node0":f2[color="red",shape="record",label="hashA"];

  20: "node1"->;"node0":f6[color="red",shape="record",label="hashB"];

  21:  

  22: "node0":f2->;"node2";

  23: "node0":f5->;"node2"[style="dotted"];

  24:  

  25: "node0":f2->;"node3"[style="dotted"];

  26: "node0":f6->;"node3";

  27:  

  28: "node0":f5:s->;"node0":f7:s[color="blue",shape="record",label="keyj"];

  29: }

在GVEdit 在使用的时候，F5 是生成图片，并在对应的目下生成了响应的图形文件，相关设置在Graph setting 里面，第一次用的时候总是找不到export image 的方法，总导出不了对应图片。

纠删码（erasure correct code）下的块可用概率

Posted on by
1

假设：

  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 是篇好论文

Posted on by
回复

不考虑内容，我心目中的好的论文应该是让读者明白文章解决了什么问题，做了什么工作。而不是使之复杂化，将“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

Posted on by
回复

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

我的自白书

Posted on by
回复

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

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

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

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

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

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