第七期 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生态的健康发展。

更多分享,敬请关注

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20180903A17UNI00?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。

扫码关注云+社区

领取腾讯云代金券