【IPFS原力区技术周报】第七期 block生成之rabin分割法

【IPFS原力区技术周报】第七期 block生成之rabin分割法

1

平均分割法与变长分割法

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

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

如有数据:123456789按照-s=size-3分块,结果为:b1:123,b2:456,b3:789;现在在34之间加数字0,数据内容为:1230456789,这时切片为:b1:123,b2:045,b3:678,b4:9,可以看出,从数据变化位置3以后的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 := range c.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<<= 8// 左移8位

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

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

            // end inline

            add++

            if add < c.MinSize {

                continue

            }

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

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

            }

        }

 

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

这里参数min>=16,如果小于16那么文件就不会进行分块,代码对这个没有做判断,应该是一个bug.因为pre是uint64,如果Minsize=min<windowsize=16,这个时候c.pre就会是个负数,而其类型是uint64,故会产生错误。

 

windowSize = 16

typeChunkerstruct {

    pre uint64

MinSize uint64

}

Ipfs中使用方法: ipfs add -s=rabin-16-32-512  C:UsersIPFSFORCE-002Desktop1.txt
IPFS原力区
IPFS原力区是全球第一大IPFS价值生态社区,总部位于上海,聚集了众多技术大咖和IPFS爱好者;IPFS原力区秉持:价值,共建,共赢,荣耀的文化理念;提供全面、精细、优质的IPFS咨询和技术支持,将生态中的爱好者转化为IPFS支持者和参与者。 未来,IPFS原力区做好价值文化基因传播、紧盯人工智能,量子计算,大数据等前沿科技,把IPFS区块链技术随时架设在最新的技术基础之上,推动IPFS生态的健康发展。

ipfs原创,作者:IPFSforce,转载请注明出处:http://ipfser.org/2018/09/04/block-rabin/

2

扫一扫,分享到微信

猜你喜欢

文章评论

电子邮件地址不会被公开。 必填项已用*标注

获取验证码
后发表评论

微信公众号

知识星球