一份数据搞定OLAP+OLTP（下）

在上片文章中，简单地介绍了L-store的数据结构和基本操作，在本篇文章中将会介绍L-store

的merge 步骤及方法

3.1 无冲突的合并

在L-Store中，坚持一个原则，那就是“永远都在稳定的数据上进行操作”。

首先对Merge的步骤进行讲解

1.在tail page中识别已经提交的修改

2.从base pages中导入tail page中对应的需要更新的页面

3.融合base page和tail page

4.对页面目录进行更新

5.对过时的数据进行重新放置

在这里使用一个简单的例子进行讲解

可以看到在这个表中包含了base page，tail page以及merged page。

简单地说merge的过程就是去tail page中读取连续的修改记录，将他们合并后合入base page。在合入之后表级的tail page将会被永久性地销毁。

在通过简单的例子分析之后作者给出了几条保证merge 方法不会导致数据冲突的引理与定理

引理1. Merge操作被严格地限制于稳定的数据上

引理2.Merge操作在不违反任何查询snapshot的情况下会安全地对过期的base page进行删除

根据引理1 与 引理2， 可以得到

定理1 ：Merge 过程以及用户的交易过程都不会在base page和 tail page中产生竞争，从而merge过程不会有冲突影响。

3.2 维持数据之间的血缘关系

在L-store 数据库中，数据的血缘关系是非常重要的，因为这关系到merge 与 update 过程的独立性。以及可以使得各列之间的merge过程相互独立。

在L-store 中，用了一个既简单又优雅的方式来对数据间的血缘得以记录和保留，那就是tail-page sequence number(TPS). 这个可以理解为在tail page 中一个自然增长的序号。 在原始的base page中，这个tps被设置为0，这表示数据从来没有被更改过。

引理3：在并发merge的情况下，

定理2：即使在并发状态下的merge也是可以被构建snapshot的

在表-5中展示的是一个根据数据血缘关系进行更新的例子。

可以看到base page中的b2 指向的是(TPS)t12。 我们从Last Updated Time 中可以发现在t7的时候这个累积式的更新被打断了，所以t12 里面所携带的数据不再是t1-t7的数据的累积式更新。

举例一个在并发情况下的例子：如果正在查找b2所对应的数据，有可能从t2开始读取，也有可能从合入后的t7开始读取，但是这都不会影响最后所获得的数据的正确性

3.3 对历史数据进行压缩

历史数据的压缩分成两步

1.根据RID对相同行数据的操作进行分组

2.对分组好的数据进行合并并且以存储在同一行

对于已经被合入到base page之后的tail page数据，系统会对这些历史数据进行压缩并作为较低优先级的冷数据进行保存。