时间戳压缩算法
1. 首先普通的时间戳如下:
2017年3月3日 3:00:00 1488481200
2017年3月3日 3:01:02 1488481262
2017年3月3日 3:02:02 1488481322
2017年3月3日 3:03:02 1488481382
秒级别的时间戳用long类型存储需要占用8bytes。 如果直接存储以上数据需要32个bytes(256 bits).
2. 最简单的优化自然是存储差值 Delta = T(n)-T(n-1) , 这个时候需要引入一个起始时间戳和Delta阈值,比如:起始时间为3:00:00,阈值为2个小时。以下为阀值之内的位点数:
2017年3月3日 3:00:00 | 1488481200 | 0 |
2017年3月3日 3:01:02 | 1488481262 | 62 |
2017年3月3日 3:02:02 | 1488481322 | 60 |
2017年3月3日 3:03:02 | 1488481382 | 60 |
**每个Delta数值的范围从long.MAX缩小到(0~7200)用13个bit就可以存储。因此存储以上数据需要103bits(64+ 13*3 ) **
3. 再进一步,如果存储差值的差值呢delta-of-delta(本文中用D表示)? 我们来看一下效果:
2017年3月3日 3:00:00 | 1488481200 | 0 | 0 |
2017年3月3日 3:01:02 | 1488481262 | 62 | 62 |
2017年3月3日 3:02:02 | 1488481322 | 60 | -2 |
2017年3月3日 3:03:02 | 1488481382 | 60 | 0 |
数值的范围变得很小了,并且可以进行压缩,根据以下压缩算法
// '0' = delta of delta did not change
// '10' followed by a value length of 7
// '110' followed by a value length of 9
// '1110' followed by a value length of 12
// '1111' followed by a value length of 32
0 | 0(1bits) | 0 | 1 |
[-63,64] | 10(2bits) | 7 | 9 |
[-255,256] | 110(3bits) | 9 | 12 |
[-2047,2048] | 1110(4bits) | 12 | 16 |
大于2048 | 1111(4bits) | 32 | 36 |
- 起始时间戳需要64bits,
- “2017年3月3日 03:01:02”的D值为62,所以标识位是10,7个数值位,总共9个bits.
- "2017年3月3日 03:03:02"的D值为0, 标识位0,共需要1个bit
采用压缩算法后只需要64+9+9+1=73个bits存储。
2017年3月3日 3:00:00 | / | / | / |
2017年3月3日 3:01:02 | 62 | 62 | 9 |
2017年3月3日 3:02:02 | 60 | -2 | 9 |
2017年3月3日 3:03:02 | 60 | 0 | 1 |
结论:4个时间戳(32bytes),通过delta,再通过delta-of-delta算法,从32个bytes(256 bits),到103bits,再到73bits,整体的压缩比为:3.5;
数值压缩算法:
看完了时间戳的压缩,我们再来看一下数值的压缩。类似于时间戳Delta, 数值采用的是异或而不是差值。
12 | 0x4028000000000000 |
24 | 0x4038000000000000 |
15 | 0x402E000000000000 |
12 | 0x4028000000000000 |
35 | 0x4041800000000000 |
15.5 | 0x402F000000000000 |
14.0625 | 0x402C200000000000 |
3.25 | 0x400A000000000000 |
8.625 | 0x4021400000000000 |
以浮点数为例采用XOR运算后:
15.5 | 0x402F000000000000 | |
14.0625 | 0x402C200000000000 | 0x0003200000000000 |
3.25 | 0x400A000000000000 | 0x0026200000000000 |
8.625 | 0x4021400000000000 | 0x002b400000000000 |
XOR后的数值压缩有众多算法可以选择,比如gzip, 7zip等等。
“Fast Lossless Compression of Scientific Floating-Point Data”这篇论文提出了DFCM压缩算法。并且从压缩率,压缩/解压效率方面与一些通用压缩算法进行了评测,如下:
相比gzip,DFCM的压缩速度和压缩率都要更胜一筹。
参考浮点数无损压缩算法DFCM:
XOR的值可以按照leading zero, meaningful bits, trailing zeros 划分。
- Leading Zeros: 就是XOR后非零数值前面零的个数
- Trailing Zeros: 就是XOR后非零数值后面零的个数
- Meaningful Bits: 中间非零的个数
划分后,对DFCM简化,预测算子采用前一个XOR的值,编码规则如下:
- 第一个值不压缩
- XOR后的数据计算控制位,如下:
- 如果XOR是0, 存储一个bit 0。
- 如果XOR不是0,控制位第一个bit设置1,第二个bit以及随后的数据按照以下方式计算:
- meaningful bits落在了前一个XOR的meaningful bits区域内,控制位的第二个bit为1,接下来是XOR数值.
- 否则控制位的第二个bit为0 .并且接下来存放:
- 5 bits: Leading bits 个数
- 6 bits: Meaningful bits 个数
- 随后放置数值
数据由原来的256bits压缩到117bits
15.5 | 无压缩 | / |
14.0625 | 13bits(头部控制位)+5bits(实际数值) | 0x0003200000000000 |
3.25 | 13bits(头部控制位)+10bits(实际数值) | 0x0026200000000000 |
8.625 | 2bits(头部控制位)+10bits(实际数值) | 0x002b400000000000 |
参考:
https://yq.aliyun.com/articles/69354?spm=5176.8278999.602941.2
相关推荐
阿里云专有云企业版高性能时间序列数据库TSDB产品简介 本文档是阿里云专有云企业版高性能时间序列数据库TSDB产品的简介,版本号为V3.8.1,文档版本号为20190829。该产品是一种高性能的时间序列数据库,能够处理大量...
阿里云专有云企业版V3.8.1高性能时间序列数据库TSDB用户指南20190910 阿里云专有云企业版V3.8.1高性能时间序列数据库TSDB用户指南是阿里云提供的一份详细的用户指南,旨在帮助用户快速了解和使用阿里云的高性能时间...
阿里云栖大会中介绍的阿里高性能时间序列数据库HiTSDB,是专门为物联网(IoT)设计的数据库解决方案,它针对物联网应用中的大规模、高频率数据处理需求进行了优化。时间序列数据库是一种专门处理时间序列数据的数据库...
本技术白皮书主要介绍了阿里云专有云企业版 V3.8.1 高性能时间序列数据库TSDB 的技术细节和实现原理。该技术白皮书适用于了解阿里云TSDB 产品的开发者和使用者。 1. 什么是时间序列数据库 时间序列数据库(TSDB)...
"阿里云 专有云企业版 V3.8.1 高性能时间序列数据库TSDB 运维手册 20190910" 本文档是阿里云专有云企业版V3.8.1高性能时间序列数据库TSDB运维手册,旨在指导用户正确地使用和维护TSDB数据库。下面是本文档中的重要...
**高性能时间序列数据库TSDB简介** 时间序列数据库(Time Series Database, 简称TSDB)是一种专门用于处理和存储时间序列数据的数据库系统。在阿里云专有云企业版V3.8.0中,TSDB是一款针对高并发、低延迟、大规模...
【阿里云专有云企业版 V3.8.0 高性能时间序列数据库TSDB 用户指南】是针对阿里云专有云环境下,高性能时间序列数据库TSDB的产品文档,旨在帮助用户理解和使用这款专为处理时间序列数据设计的数据库系统。时间序列...
- 高性能:TSDB设计为高性能数据库,支持大规模并发写入和查询,优化了对时间序列数据的处理效率。 - 高可用性:通过分布式架构保证服务的稳定性,支持数据备份和恢复,确保数据安全。 - 高压缩比:针对时间序列...
**阿里云专有云企业版 V3.7.0 高性能时间序列数据库TSDB 开发指南** **一、产品概述** 阿里云专有云企业版高性能时间序列数据库TSDB是一款针对时间序列数据进行高效存储和处理的数据库服务。它专为监控、物联网(IoT...
"阿里云专有云企业版V3.8.1高性能时间序列数据库TSDB开发指南" 本文档是阿里云专有云企业版V3.8.1高性能时间序列数据库TSDB的开发指南,旨在为用户提供详细的指南和参考信息,以帮助用户快速了解和使用TSDB产品。 ...
《阿里云专有云企业版 V3.7.1 高性能时间序列数据库TSDB用户指南》是针对阿里云专有云企业版中的一款高性能时间序列数据库TSDB的详细使用手册,适用于V3.7.1版本。该指南旨在帮助用户理解和操作TSDB,以实现高效的...
**阿里云专有云企业版高性能时间序列数据库TSDB产品简介** 阿里云的高性能时间序列数据库TSDB(Time Series Database)是一款专为企业级应用设计的数据库服务,主要针对处理大量的时间序列数据。在V3.7.1版本中,...
综上所述,Go-BTrDB是针对高密度时间序列数据存储应用设计的一款高性能数据库。其设计理念、数据结构、分布式架构以及Go语言的特性,共同构建了一个强大、可靠且易于使用的存储解决方案。无论是在物联网、金融、科研...
**高性能时间序列数据库TSDB产品简介** **一、什么是时间序列数据库TSDB** 时间序列数据库(Time Series Database,简称TSDB)是一种专门针对时间序列数据进行高效存储和处理的数据库系统。时间序列数据是指按照...
阿里云 专有云企业版 V3.8.1 高性能时间序列数据库TSDB 安全白皮书 20190910
阿里云专有云企业版V3.7.0中的高性能时间序列数据库TSDB是一款专为处理大规模时间序列数据而设计的高效存储和分析系统。这款数据库适用于监控、物联网(IoT)、金融交易、智能制造等多个领域,具备高吞吐、低延迟、强...
【阿里云专有云企业版 V3.7.1 高性能时间序列数据库TSDB技术白皮书】详细解析 高性能时间序列数据库TSDB(Time Series Database)是针对处理大量时间序列数据而设计的一种数据库系统,它专注于高效存储、检索和分析...
阿里云 专有云企业版 V3.8.0 高性能时间序列数据库TSDB 安全白皮书 20190621.pdf
阿里云专有云企业版V3.8.0高性能时间序列数据库TSDB开发指南是针对企业用户的一份详细文档,旨在帮助用户理解和开发基于阿里云TSDB的时间序列数据管理应用。时间序列数据库(Time Series Database,TSDB)是一种专门...