zfec 源码分析

zfec 是Tahoe(一个基于云的文件系统)中纠删码的一个模块,其中的fec 模块是核心部分,实现了基于范德蒙矩阵的系统纠删码,对外提供以下接口:

  1. fec_t :这是一个结构,通过fec_new() 返回可以得到,不用自己初始化。fec->k 是数据块的数目,fec->n 是所有块总数(数据块+校验块)
  2. fec_new():初始化,生成fec_t 结构,并给定了k,m(需要重建数据块数,总数据块数)
  3. fec_free():释放初始化的空间
  4. fec_encode():编码 (具体参数如下)
  5. fec_decode():解码 (具体参数如下)

继续阅读

Max-flow min-cut (最大流-最小割定理)

最大流-最小割定理是网络信息流理论(Network infomation flow)的基石。这个定理我的理解就是“多粗的管子,水就最多多大流量”,比如从自来水厂到用水大户工业小区A 能达到的水的最大流量是多大?考虑到可能从水厂到小区有不少到达的水管,那么最大的流量等于拆掉最少最细的水管后水厂不能给小区A 供水的那些水管流量的集合。当然这种说法并不不严谨,因为这里水管不是双向的,而在网络中谈论的信息流却可是是双向的。下面详细介绍最大流—-最小割定理。

继续阅读