20180323周报

Waterwheel关键技术理解

数据插入

• 数据根据时间戳和主键值两个维度划分为多个region，region的数据通过template BPlus Tree形式进行存储，主键值作为node value。当BPlus Tree的大小超过指定阈值（eg. 16MB）时，将其落盘到本地或者HDFS中，且不可改变。

• 考虑到时间范围的正增长性，从而将主键值作为查询索引的关键。当主键值由多个字段组成时，通过z-ordering方式将维度降到一维，使得能够使用BPlus Tree作为存储和索引方法（聚簇索引）。

• 负载均衡。建立一个检测数key值倾斜的函数，一个更新key值范围的函数。每个indexing server处理的tuples负载平衡，当某个Server的负载量超过平均负载量的20%时，重新进行全局的key值范围划分。当region的key范围进行更新后，部分数据的范围会发生变化，此时原本在region 1中的数据会同样备份到region 2中。内存中的数据缓存到文件系统中后，key值范围才真正进行更新，此时，因为每个indexing server的查询效率不同，region范围可能会部分覆盖临近区间的region范围。此时子查询会在两个数据块中都进行，以避免查询结果的丢失。

数据插入

• 将查询分解为独立的子查询，这些子查询可以跨节点并行查询。每个子查询指定一个区域，覆盖了一批数据。通过查询内存或者文件系统中的BPlus Tree来查找满足查询条件的元祖。

• 查询数据本地化。相同数据块上的查询，分配到同个查询服务器中。LADA算法，将子查询放入哈希集合中。算法启动时，每个查询服务器都会重复尝试从挂起的组中为未处理的子查询进行排序，并在下一次排序前按照其首选队列中指定的顺序执行子查询。该算法在待处理集为空时终止，此时所有子查询都已分派。空闲查询服务器在挂起的集合不为空时总是可以获得未处理的子查询，因此该调度算法可以实现负载均衡。

• 块局部性：将子查询分派到数据块所在的查询服务器。即数据块与查询服务器在同个节点时，其查询优先级较高

• 缓存局部性：同一个子查询由相同的查询服务器查询。通过在不同查询中，查询服务器对于同个子查询的优先级不变，且每个查询服务器偏好不同，来使得同一个子查询由相同的查询服务器查询的可能性更高。

• 处理无序到达：设定一个参数t，约定数据的延迟时间不超过该值则可访问。在通过R树查询数据块过程中，由于数据块延迟所带来的时间右偏移问题，将时间查询区间从T(t-,t+)改为T（t- - t,t+）

相关技术学习

1. 聚簇索引（主键索引、辅助二级索引），非聚簇索引
2. 位图算法，布隆过滤器
3. lz4,gzip,bzip等压缩算法

问题

1. 通过布隆过滤器将切分的时间范围进行过滤
2. B+tree达到阈值时的snappy压缩
3. 生成的B+tree leaf node 2MB左右
4. 查询结果压缩后通过socket 返回时无响应