Percolator

思考

Google的三驾马车提供了Google的搜索引擎功能。建立网页我过程如下

爬取互联网的内容进行解析
提取出关键字确认反向索引
对反向索引的URL进行整理
形成了搜索引擎所需的网页引擎

在构建网页索引的过程中，我们初始状态是由大量URL到页面内容这个键值对。我们把它处理成从关键字到URL这样一个反向的键值对（倒排索引）。reduce函数合并共同的反向索引。如果多个URL的内容一样，那么只有pageRank高的网页才会进行展示。

但是一旦有网页更新，新的网页产生。我们需要更新到索引库中。网页之间的关系非常复杂。加入在新URL产生后需要内容去重然后重新pagerank。但是MapReduce这套生成网页索引的机制是全量的。没办法单独为新增的网页跑一套这个流程。

MapReduce只能权利生成不能增量更新。

Google长期采用的方法是通过MapReduce批处理过程，定期重新生成一个新的索引库。假设原来索引库索引了1000个页面，这时候五个页面新加入。MapReduce需要重新处理10005个页面才能得到新索引库。

那么能不能只处理5个新增页面通过一个增量的更新呢？

其实增量这个操作就是select+insert/update的过程。还需要保证整个过程的一致性和隔离性。如果这个索引库支持事务就能解决我们的问题了。

那么如何让Bigtable支持事务呢？我们需要一个支持事务的DBMS来索引存储库。因此出现了percolator，在Bigtable上面做了一层封装。支持事务解决了问题并成为了分布式数据库。也就是newSQL的雏形。

原论文中说：percolator是专门为了增量处理而构建的，并不是为了取代大多数数据任务处理的解决方案，MapReduce可以更好地处理无法将结果分解为小更新。此外计算应该有强烈的一致性要求不然Bigtable就足够了。计算在某些维度上应该非常大。传统的DBMS可以处理不适合Mapreduce或Bigtable的较小计算。

但后续的Spanner到现在的各种newsql数据库已经在现有的解决方案商越走越远了。在性能差异不大的情况下，NewSQL能支持近乎无限容量的数据。提供强大的扩展性，又能弥补原有分布式的种种限制。（变得all in one）

基本原理

percolator是基于俩阶段提交的改进版本。

prepare阶段：协调器向各个节点发送paepare消息，各节点决定该节点事务部分是提交还是中止。
commit阶段：协调者收到各节点的ready或不能提交响应。

所有节点都ready则提交成功，任一阶段无法提交就回滚。

俩阶段提交的特点是

强一致性
失去了并发能力：不能使用MVCC
需要一个特殊实现的协调者，这个协调者需要单独实现并存储一些日志和锁内容。（这个协调者是脱离bigtable的，所以更难控制）
需要付出更大的性能。

percolator基于此做了最核心的俩个改造

提交过程中的第一个参与者设计为一个类似俩阶段提交协调者的角色，整个事务的原子性状态也以它为准。由此，借用Bigtable的高可用存储能力，免去了特殊设计协调者的麻烦和风险。
percolator采用全局授时机制，通过全局时间戳实现多版本的管理，从而实现了snapshot isolation（快照隔离），具有一定的并发能力和first-commiter-win的特性。

percolator存储了四个列：key，data，lock（锁状态），write（提交状态）

字段前5或6是时间戳（我们用一个简单的自增整数来代替，时间戳由Bigtable负责存储）

write下时间戳为data@5表示时间戳为5已经提交

data字段的写入不表示这个事务已经提交了，没有提交的数据是不可以读的。

读的流程为先查询write字段，找到最近的一个提交记录。再按照这个时间戳找到已提交的数据进行读取。

接下里Bob给Joe转账7元。我们首先扣除Bob账户的7元。并在Bob账户上加锁。

因为这是分布式事务的第一把锁，所以我们设定它为primary锁。这里最新的write字段还是时间戳6，只能查询到时间戳5的数据。所以现在Bob的余额还是10（MVCC）

然后给Joe账户增加7元，余额变为9，并在Joe的账户上加锁。因为这是分布式事务的第二把锁，它指向primary锁的位置。

这是为了让分布式事务的提交与成功有一个原子性的标志。

一个事务中除了第一个锁是Primary锁其他的锁都是secondary锁。

这样我们的prepare阶段就完成。

事务进入commit阶段，事务释放掉primary锁，并申请时间戳8，在时间戳8写入write列。

时间戳8就是这个事务的提交时间戳。

底层实现

我们可以简单把Bigtable当做一个整体来看待，Bigtable上面就是运行percolator程序的服务器了。percolator其实是作为Bigtable的client来调用Bigtable的接口的。

在这里percolator在系统中的角色非常像一个中间件。可以看做是一个proxy代理。

percolator需要在保证持久化的部分都借用Bigtable高可用的能力。因此他们都是无状态的，因此在考虑后续流程的情况下我们需要考虑proxy节点宕机的情况。

先是事务的执行阶段

写入根据start_ts前最后一个快照进行修改，并且只写入proxy本地缓存，无任何持久化和上锁操作（proxy挂掉了就丢掉）
（强一致性读取）
1. 先要校验读取在start_ts之前是否有锁，如果有所要尝试清理掉这个锁。（因为proxy可能在俩阶段提交的过程中崩溃，这里是lazy清理。）
  - 如果是primary锁直接清理掉
  - 如果是secondary锁，那么找的哦啊primary锁的位置。根据primary锁的状态判断释放与否；
  - 如果token的时间戳很旧，大概率是之前的事务出问题了。那么可以清理锁
2. 如果没锁，就去找到start_ts前最后write的一个字段，再根据这个write字段指向的时间戳去读取数据。

来看prepare阶段