分布式时序数据库 silverDB- 低成本存储

写在前面：



没有底层本的数据存储，时序数据库基本沦为“废材”！所以，我认为时序数据库本身（暂时先不说生态的问题）必须具备三大能力：



1、底成本存储



2、高性能写入



3、交互式查询



因为，前几天和influxDB进行过测试，在底层本存储及资源消耗方面，基本被吊打（杜卷数据先生：分布式时序数据库silverDB-被influxDB吊打）。所以，今天主要基于silverDB目前已经实现的存储和压缩，进行改进的一些思路分享。ok，继续：



面向传统的工业互联网领域，时序数据库要破局成功的关键，除了自身对于工业互联网生态构建的支撑能力外。还需要有底成本的存储能力、高性能的写入和查询能力。之前分布式时序数据库silverDB在底成本存储能力上被influxdb吊打。我想了一下，有以下几点原因：一是存储设计、二是压缩算法。所以，今天我主要想说一下关于压缩算法的事。



对于influxDB来说，其时间和指标值分别以块的形式存储。同时，对于不同类型的指标，也采用了不同的编码方式和压缩算法。所以，这就差距啊。之前写silverDB的时候，偷懒只用了delta-delta一种压缩算法。然后，对于所支持的int、bool、double、float、int等类型，最后都统一转换成了double以进行delta-delta压缩。这么low的做法，使得silverDB在进行数据存储的时候，还未压缩，就对原始数据进行了放大，64-10多倍不等。所以，这也为改进silverDB提供了切实的事实依据。所以，针对每种不同的数据类型，我这边会选择更加合适的压缩算法，对silverDB进行优化。



对于存储设计上来说，silverDB的时间与指标也是统一以delata压缩后的块的形式存储的，如果要拆分出来，则会涉及到存储结构的变化。除此之外，这一块关于存储设计，需要在工程上更加精致一些，但是具体的存储设计方案暂时还没有想到更好的优化方式。唯一需要改变的就是，数据块的元数据信息，需要添加对于不同类型压缩算法的支持。下面可以具体看一下，influxdDB中，针对每种数据类型，所采用的压缩算法和压缩方式。



Timestamp



simple8b encoding



一种基于时间戳结构的自适应编码方式。最多使用8个字节来存储未压缩数据（如果时间粒度为ns级别的话，在golang中需要使用int64来存储）。在整个数据编码过程中，原始的数据首先使用delta-delta进行编码（选取第一个值是开始时间戳，随后的值与前一个取差值，这样可以将值转换为更小的整数，并且更容易压缩）。除此之外，当数据的时间存在一定的频率间隔的时候。比如，每10s/次。这个时候就可以按照最大公约数进行压缩。这样非常大的整数增量可以转换为压缩效果更好的较小增量。还有一种，如果所有的deltas 都是相同的，那么这个时间范围内的数据将使用run-length enconding方式进行编码。



Simple8b是一种64位字对齐的整数编码，它将多个整数打包成一个数位字。如果未压缩数据的增量值超过了最大值，则将不会进行压缩存储。



Float64



Facebook Gorilla paper. http://www.vldb.org/pvldb/vol8/p1816-teller.pdf



在influxDB中，对文中所描述的算法进行了裁剪，只对浮点数进行了编码。原文中主要介绍的是，时间戳和浮点数的编码方式。



Integer



ZigZag encoding



对于整数的编码，influxDB采用了两种不同的策略。根据未压缩数据的取值范围。要编码的数据首先会使用zigzag进行编码。如果zigzag编码取值范围小于 1 << 60 -1 ，那么将会使用simple8b进行编码。如果有任何一个编码的值大于最大值，那么所有数据将不压缩的存储在块中。如果所有的值是相同的，那么将会使用run-length 编码。



注意：zigzag编码算法，其实是一种将由符号的数据编码为无符号数据的一种方案,对于小整数的效果较好。



Booleans



这里对于boolean类型的数据，就可以按照1:1的方式进行存储，直接使用1个bit来存储。当boolean类型的数据编码完成之后，将会使用一种可变字节编码的方式来存储。



String



使用snappy进行数据压缩。



可以看到，influxDB对于每种不同的数据类型，分别使用了不同的编码算法和编码策略。这样一对比，silverDB的压缩真是太粗暴了，得改进。在改进之前，首先针对每种压缩算法做一个简单的测试吧。



这边分别从两种情况做了一个测试。



一、10000条数据，int64和int32，测试数据delta为1，分别采用simple8b、simple9b、run-length 进行编码。长度单位为：byte。



data len: 80000, simple8b encoding len: 18008 



data len: 40000 ,simple9b encoding len: 19608 



data len: 80000 , run-length encoding len: 31744 



二、10000条数据，int64和int32，测试数据delta为0，分别采用simple8b、simple9b、run-length 进行编码。长度单位为：byte。



data len: 80000, simple8b encoding len: 10000



data len: 40000 ,simple9b encoding len: 10000 



data len: 80000 , run-length encoding len: 5 



可以看到，run-length 编码对于数据变化，表现比较敏感。所以，在时序数据库的数据块中，如果所有值相同，可以使用run-length编码。



三、手写zigzag编码，分析编码特性



b1:=compress.ZigZagInt64Encode(-56)
b2:=compress.ZigZagInt64Decode(b1)
buf:=new(bytes.Buffer)
binary.Write(buf,binary.BigEndian,b2)
fmt.Printf("data len: %v,zigzag encoding len: %v \n", len(buf.Bytes()), len(b1))



可以看到，对于小整数，使用zigzag编码，不仅可以将有符号整数编码映射成无符号整数，便于压缩。同时，对小整数可以进行1:1的存储编码。所以，为了节省存储空间，真的可以好好的去研究一下，数据编码和压缩。



data len: 8, zigzag encoding len: 1 



结果如下：原始数据-56，int64类型，需要8个字节存储。而通过zigzag编码之后，只需要一个字节。相当于节省了8倍的存储空间。



那么对silverDB来说的话，基本上可以做如下改进：



1、对于bool类型，使用1:1编码设计，然后使用run-length进行编码压缩。



2、对于时间timestamp，默认直接使用simple8b进行编码。但是首先需要进行zigzag编码转换。



3、对于Int类型，如果所有值相同，则使用run-length编码。如果不同，则将数据进行zigzag编码，并将范围小于1 << 28-1的数据，进行simple9b编码。



4、对于Long类型的数据，如果所有值相同，则使用run-length编码。如果不同，则将数据进行zigzag编码，并将取值范围小于1 << 60 -1，进行simple8b编码。



5、对于double类型的数据，采用delta-delta进行数据压缩。（对于单精度类型，会默认转换为双精度进行存储）。



除此之外，在数据块的设计上，增加对于不同压缩算法类型的支持。看来，silverDB在数据编码、压缩和存储设计上还是有很大改进空间啊。之后，我这边改进完，在测一下，看看情况吧！