存储系统中的纠删码(Erasure Codes)—XOR 码和RS 码(二)

纠删码(Erasure Codes)能够总体上分为XOR 码和RS 码两类,XOR 码基于有限域GF(2),编、解码只需要按位异或(bit-wise exclusive-OR)即可完成,速度较快;RS 码基于有限域GF(2w),编、解码需要有限域上(后面的文章将详细介绍)的运算,速度慢于XOR码。常见的XOR码有:

  • 低密度奇偶校验码(Low Density Parity Code, LDPC)
  • 柯西-里德所罗门码(Cauchy-Reed-Solomon Codes,CRS)
  • RAID码(如RAID5、RAID6)
  • 奇偶码(EVENODD)
  • X-码(X-code)

按照编码理论来说,RS码是一个字长为n,维度为k,码字间距为n-k+1 的最小距离可分码(MDS codes),但为了能够让读者能够更容易接受,我们这里的RS 码是基于有限域上GF(2w)编解码运算的编码。

继续阅读

存储系统中的纠删码(Erasure Codes)—综述(一)

一、背景与挑战

数据的爆炸式增长使得存储系统的规模不断增加,存储设备的可靠性却一直没有得到显著提高(SSD 从SLC 到MLC 和TLC 可靠性不断下降,磁盘随着单位面积写入数据更多导致可靠性无法提升),从而给数据的持久化存储带来巨大挑战。另外随着存储系统规模的增大,存储系统中的冷数据的增加将远超过热数据的增加,如何安全保存冷数据,在需要的时候能够获取冷数据也成为存储系统中的重要挑战。下面是近年全球估计的数据量增长情况(GB,TB,PB,EB,ZB,YB…)。

2007    281 EB
2010     1.2 ZB
2011     1.8 ZB
2020      35 ZB

继续阅读

哪些情况会导致"Undefined Reference Error"

“Undefined Reference Error” 是在程序链接(link)时经常遇到的错误,字面意思来说就是没有找到已经定义的引用,在编译器无法找到用户所使用的变量或函数:

一、缺失头文件

例如声明变量 uint64_t tmp,但没有在开头包含 #include<stdint.h>

例如使用 memset() 需要包含头文件 string.h 或 memory.h

二、缺失目标文件或者库文件(.a .o .so …)

编译器查找用户函数,首先会在本文件中的函数中找,然后在系统环境变量定义的目标文件/库(.a .o .so …)文件中找,最后在链接的目标文件/库文件(.a .o .so …)中寻找用户函数;如果没有找到则报”Undefined Reference Error”错

四、库(目标)文件链接顺序有误

库文件的链接顺序是:依赖的库A 放后面,被依赖的库B 放前面。如果A 和B 相互依赖,则使用A B A 或者B A B 的。

例如main 文件中引用func 文件中函数,则编译顺序为main.o func.o

五、C 函数和C++函数引用问题

C++ 程序链接时可以链接C 的库文件,但在.cc(.cpp) 中引用头文件时需要通过extern “C”{ #include “func.h”} 的方式引用该头文件,否则会提示”Undefined Reference Error”

C 程序无法链接C++ 库文件,否则会提示”Undefined Reference Error”,找不到引用C++ 函数的引用

 

参考:http://blog.csdn.net/aiwoziji13/article/details/7330333

内存拷贝速度(memcpy())和异或速度

内存拷贝(memcpy())和异或(bit-wise XOR)是程序中运行最快的操作之一,其速度受到CPU、内存和编译器(GCC版本)的影响。

内存拷贝memcpy(des, src, len) 则是将长度为len 的数据从地址src 拷贝到地址des 。

按位异或(异或)可以分为几类:

  1. a^b:两个数值的异或。相当于两个寄存器内值在CPU 中计算异或,大多数CPU 中一个时钟周期完成。速度取决于CPU 的频率,频率越高,速度越快。
  2. a^Region:一个数值与一块内存Region 中的每个值异或,结果保存在Region 中,速度相当于顺序访存。
  3. RegionA = RegionA^RegionB:两块内存中对应位置上的值异或。
  4. RegionC = RegionA^RegionB:两块内存中对应位置上的值异或,结果保存在另一块内存中。

四类异或速度依次递减。平常中越到的是第3 种,本文中异或速度也是第3 种。

继续阅读

CPU Cache 如何影响程序性能

CPU Cache 是CPU 中用于减少平均访问内存时间的高速存储器件。较内存使用的DRAM ,cache 使用的SRAM 速度更快、价格也更高,所以cache 容量一般较小。与cache 相关的概念有:cache line,associativity(相连性),L1 cache,L2 cache ,cache 命中,cache 失效等。

cache 按层次分为L1、L2 甚至L3级cache,速度依次递减,容量依次增大。CPU 直接能够读取的只有L1 cache。在大多数处理器包括Intel CPU 中,cache按照缓存的指令或者数据分为数据缓存和指令缓存(如L1d 和L1i) 。在多核的CPU 中,每个核心具有独立的L1 级cache,往往公用L2 级cache。公用cache 可能存在多线程缓存污染等问题。

cache 和内存传输的最小单位是cache line,一般大小为64 bytes。cache 每次从内存读取或者写入cache line 大小的数据,而不是我们在程序中定义的数据结构的大小。cache lines 之间的替换常用的是LRU 算法。如果CPU 读取的数据在cache 中,则cache 命中(cache hit),否则cache 失效(cache miss)。每一级的cache 失效将到下一级cache 中寻找数据,直至内存。cache miss 是有开销的,小于访存时间,大于cache hit 时间。每次cache 失效,CPU 就会处于停滞(stall)状态,直至缓存读取到所需要的数据。

因为cache 容量远小于内存(有种说法是1:1000),内存和cache 之间存在映射关系(associativity)。按照映射关系不同,分为:全相连映射(fully associative),多路组相连映射(N-way set associative)和直接映射(directly mapped)。全相连映射缓存和内存是全映射关系,内存中任何一块数据都可以没有限制地放的任何一个cache line 中,缓存利用率高,但设计复杂未被采用;直接映射将一块内存地址映射到一个cache line(the number of cache line = memory address%number of cache lines,其中内存地址以cache line 大小为单位),直接映射设计起来简单,但利用率低;多路组相连映射缓存更为常见,是设计复杂度和性能的权衡。它将一块内存映射到不同路上的cache lines 中,如果是8-路组相连,则一块内存映射到8-路上的cache lines 上(the number of cache line = memory address%(number of cache lines/number of ways)。不同路上的负责缓存相同内存的缓存构成一个集合set,不同set 缓存不同内存地址的数据。number of set = cache size/(ways of associativity * size of cache line)。

继续阅读

为什么要将文件分块编码?

编码指的是冗余编码或者加密编码等。如果能够将大文件一次性读入内存进行编码的话,为什么要选择将连续的文件分成一块一块(packet)地进行编码呢?个人认为原因有几点:

  1. 节省内存,减少I/O 时间
  2. 利用CPU 缓存局部性,适当的选择packet 大小能够提高编码速度

2

上图给出了RS 码在编码1GB、512MB和256MB 时,不同packet 对编码速度的影响。总体来说,文件越大,编码速度越慢;packet 大小在16KB 和1MB 之间(缓存大小)编码速度最快;packet 超过缓存大小时,编码速度有所下降。packet 大小在RDP 码上的影响参考[1]

 

[1] Plank, James S., et al. “A Performance Evaluation and Examination of Open-Source Erasure Coding Libraries for Storage.” FAST. Vol. 9. 2009.