histore的产品优势

• 高性能分析型查询，支持百亿数据场景下的多维度adhoc分析型查询,相比mysql，查询速度提升数倍至数十倍
• 低存储成本，histore基于列存储和特定领域优化的高效压缩技术
• 低维护成本，通过知识网络+自适配参数调整，无需通过传统搜索引擎的索引，数据分区，预测等调整

1. 数据查询与压缩分析

1.1 Trie

histore是基于列存储的，每列的数据类型都是一样的，所以可以针对特定的数据类型进行高效压缩与查询 其中针对字符串类型的数据，采用的是 Succintct Trie技术。 Trie指的是字符串前缀树,例如字符串 CDWP 和 CDH 拥有共同前缀CD，当查询CDH字符串时，只需比较一次CD前缀。他的优点是大限度地减少前缀字符串比较，查询效率比哈希表高，用空间换时间。 histore团队在Trie基础上又进行了压缩，用位图来表示节点之间的关系，减少空间换取时间的成本。

1.2 Trie位图压缩

1. LOUDS: 存储每个节点的子节点个数，每个节点后面必须以0结尾，每个节点1的总数就代表了子节点个数，Trie树有一个总的root例如上图中有一个root指向节点C，所以LOUDS存储的位数: 2*节点数+1,
2. Terminals: 存储每个节点是否对应一个单词的信息，为0代表不对应单词，为1代表从根节点到该节点组成到字符串代表一个单词,Terminals存储位数: 节点数 +1
3. base：存储每个节点的内容，不用位图存储，占用空间: (节点数+1)*char占用空间

1.3 DataPack

histore每列的数据分成一个个DataPack写入磁盘，每个DataPack包含64K行的数据。字符串前缀树从根节点到Terminals标记为1到节点，，所有节点内容拼起来就是一个字符串，给Terminals标记为1到节点一个ID，DataPack每行的数据存储行数和节点ID，通过ID可以获取到该节点，根据该节点获取从该节点到根节点的路径，从而查询到字符串数据，反过来，给定一个数据，可以通过Trie树查到一个节点，然后找到节点对应的ID。

1.4 知识网格(KG)

histore使用知识网格架构来支持查询优化，在查询计划构建中，通过知识网格减少需要解压的DataPack数量，对于统计与聚合查询，知识网格有记录信息，无需解压DataPack就可以返回结果。知识网格由数据元信息节点和知识节点组成。

数据元信息节点：与每个DataPack一一对应，包含对应的DataPack的信息

1 .数据聚合函数值（MAX,MIN,AVG,SUM等）

2 .数量

3 .数据null标记

知识节点：与列一一对应

1 .该列的数据类型定义，约束条件

2 .标示BitMap，按照列数据的范围切分多段，每个bit记录数据是否存在与该段的范围内。例如列数据类型与为整形，MIN为0，MAX为1000,按照0-9 ，10-19.....格式切分成100段，如果有列数据在0-9之间，该段的bit为1。

3 .关系位图，记录不同列DataPack的对应关系，提高join查询性能

4 .列数据的值分布信息

2. 数据更新

2.1 MVCC协议

在读取数据库时，如果有人在写数据，有可能读取数据的人会看到半写的数据或者不一致的数据，所以需要进行并发控制，最简单的是加锁，但是读写加锁效率不高，MVVC协议中，读写分离，在写操作时，会创建一个新版本数据，在这版数据进行写操作，其他读操作在老版本上读取数据，当写操作完成时，用新版数据替换老版数据，同时需要定时清理老版数据。

2.2 histore中的数据更新

histore在写操作时，以DataPack为单位，将要写的数据所在的DataPack复制一份，由于Succintct Trie是不可修改的，所以需要将DataPack还原至内存,更新DataPack，重新构造Succintct Trie，写操作完成再压缩写回。

产品比较

Hbase：支持海量数据存储，由于数据结构为KV结构，只支持单一条件查询，不支持条件组合查询，只支持String存储，压缩效率不高。

Mysql：海量数据存储成本高，虽然支持各种条件查询，但是海量数据下查询性能差。

odps：支持海量数据存储，但是查询性能低，不支持实时查询。

Histore：支持海量数据存储，支持多条件查询，查询速度快，压缩率高，但是不支持delete操作