第七期 block生成之rabin分割法

1

平均分割法与变长分割法

数据分块方法分为固定长度分块和可变长度分块，固定长度分块即为平均分割法,可变长分块是按照一定的规则(特殊标志或算法)将数据进行分块，这种切割方式产生的block块长度一般都是不固定的。rabin分割法即是可变长分块中的一种。两种分割方法优缺点如下：

平均分割法实现简单，但数据变化后从变化位置开始，后面所有block的内容都需要重新分块，特别是数据重复较少时尤其明显；

变长分割法在数据中找到一种规律或定义一种规则对文件进行分块，最优规则应使分块后的block在一个大小周围成正态分布，可以看出变长分割实现比较复杂。优点在于数据内容变化只会影响到变化位置周围的block分块，别的分块内容不会产生变化。

最优分割

如数据:碧云天，黄花地，西风紧，北雁南飞。我们定义分块规则:按逗号分割，这时分块后的数据为:b1:[碧云天,],b2:[黄花地,],b3:[西风紧,],b4:[北雁南飞.]，将数据改为西风正紧,在分块规则不变的情况下只有b3:[西风正紧,]变了,其他的分块不会变化。

2

Rabin分割法

rabin参数形式为：-s=rabin-min-ave-max，min表示block块最小字节数，max表示block块最大字节数，ave表示文件分割后所有块平均大小的理想状态。

Rabin使用一个固定大小(ipfs中是16)字节的滑动窗口对数据计算数据指纹。如果指纹满足某个条件(ipfs中条件是(c.digest&c.sizeMask)==0)，则把窗口位置作为块的边界。这种算法可能会出现病态现象，即指纹条件不能满足，块边界不能确定，导致数据块过大。所以使用min和max对数据块的大小进行限定，设定上下限,解决这种问题。

Ipfs中rabin算法的核心代码为：

for_,b:=rangec.buf[c.bpos:c.bmax] {

// inline c.slide(b) and append(b)to increase performance

out:= c.window[c.wpos]

c.window[c.wpos]= b

c.digest^=uint64(c.tables.out[out])//按位异或:相同为0,不相同为1

c.wpos= (c.wpos +1) % windowSize//与16取模,0,1,2...,15轮流转

// c.append(b)

index:= c.digest >> c.polShift//右移运算

c.digest

c.digest|=uint64(b)//位或运算

c.digest^=uint64(c.tables.mod[index])//异或运算

// end inline

add++

ifadd

continue

}

if(c.digest&c.sizeMask) ==|| add >= c.MaxSize {

...//这里构造产生的block块

}

}

基本思想是将数据转为[]byte数组,然后循环遍历数组中每一个字节元素,通过一系列运算(见上面代码)判断是不是边界元素,如果是则以此字节为分界点生成一个block,在遍历过程中如果当前字节已经超出max(最大字节)还没有符合条件的元素,就以前面max个字节生成一个block分块。

这里参数min>=16,如果小于16那么文件就不会进行分块,代码对这个没有做判断,应该是一个bug.因为pre是uint64,如果Minsize=min

windowSize=16

typeChunkerstruct{

preuint64

MinSizeuint64

}

Ipfs中使用方法:

ipfs add -s=rabin-16-32-512 C:\Users\IPFSFORCE-002\Desktop\1.txt

IPFS原力区

IPFS原力区是全球第一大IPFS价值生态社区，总部位于上海，聚集了众多技术大咖和IPFS爱好者；IPFS原力区秉持：价值，共建，共赢，荣耀的文化理念；提供全面、精细、优质的IPFS咨询和技术支持，将生态中的爱好者转化为IPFS支持者和参与者。

未来，IPFS原力区做好价值文化基因传播、紧盯人工智能，量子计算，大数据等前沿科技，把IPFS区块链技术随时架设在最新的技术基础之上，推动IPFS生态的健康发展。

更多分享，敬请关注