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生态的健康发展。
更多分享,敬请关注
领取专属 10元无门槛券
私享最新 技术干货