分类目录归档：分布式

纠删码（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
回复

一致性哈希（consistent hashing）和分布式哈希表（DHT: Distributed Hash Table）在最近的学习中经常用到，但是两个概念经常纠缠在一起，不容易分清楚。有时候就不明白这里为什么说的是consistent hashing，而不是用DHT。

从字面的意思来区分：consistent hashing 是一种满足特殊需求的哈希；DHT 是通过哈希实现的分布式的表，归根到底是一个分布式系统。consistent hashing 是理论上节点变化最少数据迁移的哈希方法，而DHT 在实现上更加具体，DHT 把传统的单个K-V 表在分布式多个节点中进行划分，既可以采用consistent hashing 实现，也可以采用其他哈希方法。

继续阅读 →

Dynamo: Amazon’s highly available key-value store

Posted on by
回复

原文  中文翻译  参考：Kai – An Open Source Implementation of Amazon’s Dynamo

本文一直为分布式key-value 存储系统以及分布式存储的业内人士所推崇，个人觉得有两个原因：

  1. 分布式key-value 存储近年发展迅速。Dynamo 更是集成了近些年最新的技术如：DHT（分布式哈希表）、consistent hashing（一致性哈希）、多版本、副本策略和Merkle tree 等。
  2. 文章从设计、实施者的角度分析了分布式key-value 存储在实践中的问题和解决方法，并总结了Dynamo 在实现、配置等方面的经验与教训，对后来者非常有借鉴意义。

继续阅读 →