python 的双下划线

“单下划线”“_”开始的成员为保护成员,只有类对象和子类对象可以访问到这些变量/方法。

“双下划线”“__”开始的是私有成员,只有类对象能够访问,子类对象都不可以访问。

“from xxx import ”不可以导入“_”开始的变量/方法

私有变量/方法在代码生成前会被转化成为长格式(变为保护类型),转换机制为:变量/方法前加上类名,再将前端加上下划线字符。

比如A 类中有方法和变量 __private 会在代码解释前替换为 _A__private(类似于C 中的宏替换)

上面的如果明白了,可以到这里测试下。

“__xxxx__”这类双下划线开始,双下划线结束的变量为python 特殊变量,常见的有“__name__”“__file__”“__loader__”“__package__”。如果一个文件是作为主程序调用的,其值就会设为__main__,如果是作为模块被其他文件导入,它的值就是其文件名,常可用于模块内置测试。在python 的官方文档中有这样的解释:

 

The special global variables __name__, __file__, __loader__ and __package__are set in the globals dictionary before the module code is executed (Note that this is a minimal set of variables – other variables may be set implicitly as an interpreter implementation detail).

__name__ is set to run_name if this optional argument is not None, to mod_name + '.__main__' if the named module is a package and to the mod_nameargument otherwise.

__file__ is set to the name provided by the module loader. If the loader does not make filename information available, this variable is set to None.

__loader__ is set to the PEP 302module loader used to retrieve the code for the module (This loader may be a wrapper around the standard import mechanism).

__package__ is set to mod_name if the named module is a package and to mod_name.rpartition('.')[0]otherwise.

If the argument alter_sys is supplied and evaluates to True, then sys.argv[0] is updated with the value of __file__and sys.modules[__name__] is updated with a temporary module object for the module being executed. Both sys.argv[0] andsys.modules[__name__] are restored to their original values before the function returns.

Cuckoo Hash 布谷鸟哈希

布谷鸟哈希最早于2001 年由Rasmus PaghFlemming 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)下的块可用概率

假设:

  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