percolator 逻辑代码分析
2017-08-15 本文已影响32人
luomoxyz
1 整个逻辑时间是作为版本号
2 单行事务有底层数据库保障
3 2PC的典型实现
4 外部需要Chubby做协调
总结： 用单行事务实现跨行、 跨表事务
场景分析过程(单行事务本身就存在由底层bigtable决定 )
1 初始状态, bob 账户有10美金, joe 有2个美金. write 列中的 6:data @ 5 表示 当前的数据是 version 为 5（一般是时间戳re）
key bal:data bal:lock bal:write
Bob 6: 6: 6: data @ 5
5: $10 5: 5:
Joe 6: 6: 6: data @ 5
5: $2 5: 5:
2 事务的第一个阶段, bob的账户变成3美金了. 注意 lock 列被加锁, 并且标明自己是 primary. 每个事务中, 只有一个primary, 也正是这个primary的存在, 使得我们能够用行原子性来实现分布式事务.
Bob 7:$3 7: I am primary 7:
6: 6: 6: data @ 5
5: $10 5: 5:
Joe 6: 6: 6: data @ 5
5: $2 5: 5:
3 现在给joe加上7美金, 所以joe是9美元了, 注意 joe 这一行的 lock 是指向 primary 的一个指针.
Bob 7: $3 7: I am primary 7:
6: 6: 6: data @ 5
5: $10 5: 5:
Joe 7: $9 7: primary@Bob.bal 7:
6: 6: 6: data @ 5
5: $2 5: 5:
4 事务提交的第一阶段, 提交 primary, 移除lock 列的内容 在 write 列写入最新数据的 version
Bob 8: 8: 8: data@7
7: $3 7: 7:
6: 6: 6: data @ 5
5: $10 5: 5:
Joe 7: $9 7: primary @ Bob.bal 7:
6: 6: 6:data @ 5
5: $2 5: 5:
5 事务提交的第二阶段, 提交除 primary 之外其它部分. 提交的方式也是移除 lock, 同时在 write 列写入新数据的 version
Bob 8: 8: 8: data @ 7
7: $3 7: 7:
6: 6: 6: data @ 5
5: $10 5: 5:
Joe 8: 8: 8: data@7
7: $9 7: 7:
6: 6: 6: data @ 5
5:$2 5: 5:
代码分析
class Transaction{
struct Write { Row row; Column col; string value; };
vector<Write> writes_;
// 每一个事务都有一个start timestamp
// 读事务只关心[0, start_ts_]时间区间之内数据逻辑是否一致
// 写事务则需要关心[0, infinate)时间区间之内数据逻辑是否一致
int start_ts_;
// 初始化当前事务的timestamp，note: 此oracle非彼Oracle
Transaction() : start_ts_(oracle.GetTimestamp())
{
}
void Set(Write w)
{
writes_.push_back(w);
}
// 读事务
void Get(Row row, Column c, string *value)
{
while (true)
{
// 利用了Google Bigtable的单行事务特性。
// 单行事务的特征为：
// 在单行数据的操作上保证事务性（ACID）
bigtable::Txn T = bigtable::StartRowTransaction(row);
// 检查在读操作的同时是否有并发的写操作，如果有并发写操作
// (包括那些没有彻底完成写操作就挂掉的情况)则需要执行比较
// 复杂的重试/清理操作 - BackoffAndMaybeCleanupLock()
//
// 这里需要注意时间区间为[0, start_ts]，也就是说Get只关心
// 在本事务发起前的数据快照是否具有一致性，对start_ts_之后
// 发起的事务它并不关心。这反映了Percolator表现出来的
// snapshot isolation特性，Get操作的是start_ts_之前的一个快照
if (T.Read(row, c+"lock", [0, start_ts]))
{
// 执行到这里的时候说明有尚未解开的锁
// (pending lock)，可能来自：
// 1. 在start_ts_之前发起的一个写事务正在进行中
// 2. 在start_ts_之前发起的一个写事务没有完全commit就死掉了
// ps. Back off的意思是后退，滚开，
// 貌似一群警察踢门的时候常喊?
BackoffAndMaybeCleanupLock(row, c);
continue;
}
// 执行到这里的时候说明start_ts_之前的数据具有一个一致的snapshot
last_write = T.Read(row, c+"write", [0, start_ts_]);
// sanity check. 没有找到任何数据可读，返回。
if (!latest_write.found())
{
return false;
}
// write列记录了data所在的timestamp，
// 为了读到一条数据，需要先得到该数据所在的
// timestamp，然后通过timestamp读到最终数据，
// 有点间接寻址的味道
int data_ts = latest_write.start_timestamp();
*value = T.Read(row, c+"data", [data_ts, data_ts]);
return true;
}
}
bool Prewrite(Write w, Write primary)
{
Column c = w.col;
bigtable::Txn T = bigtable::StartRowTransaction(w.row);
// 如果在本事务开始后([start_ts_, inf))也有其他事务执行写操作，
// 并且已经完成了部分/全部数据写操作，则abort
//
// 对于start_ts_之前的写操作，分为两种情况
// 1. 整个事务都提交完成了得写操作，这是正常情况，结果一致
// 2. 只写了一半的事务，这由后面的lock检查来处理
if (T.Read(w.row, c+"write", [start_ts_, inf])
{
return false;
}
// 如果在当前操作的cell上还有锁的话，则abort
// 这个检查比较狠，只要有锁，无论timestamp为多少均abort，这是
// 因为只要有锁，就说明还有一个并发事务(dead or not)在写当前cell
if (T.Read(w.row, c+"lock", [0, inf])) // 只要有锁， 全部则返回错误
{
return false;
}
// 检查到这里就可以放心地预写入数据和锁了
// 此时data对Get还不可见，因为write还没有写入
// 时间相当于版本号，这个依赖于google的提供GPS和原子钟提供的严格递增的时间. 其他公司怎么做...找一个统一授时集群？？
T.Write(w.row, c+"data", start_ts_, w.value); //start_ts_@w.value
T.Write(w.row, c+"lock", start_ts_, {primary.row, primary.col}); // start_ts_@{primary.row, primary.col}
// 提交bigtable单行事务
return T.commit();
}
bool Commit()
{
// 任选一个write作为primary，这里primary的作用类似于一个标志点primary行被提交后，整个事务必须提交
Write primary = writes_[0];
vector<Write> secondaries(writes_.begin() + 1, writes_end());
// 预提交
// primary和secondarise的预提交如果失败，
// 则说明还有别的并发事务在写当前cell，当前commit需要abort
//
// 我对并发事务的理解：在时间轴上有交集的事务。
// Timeline -------------------------------------------->
// Trans0: ^-$
// Trans1: ^-----$
// Trans2: ^----------$
// Trans3: ^------------$
// Trans4: ^----$
// Trans5: ^----x
// ^标志事务开始，$标志事务结束，x表示执行事务的进程中途死掉
// 0,5; 1,2; 1,3; 1,5; 2,3; 2,5均为并发事务
if (!Prewrite(primary, primary))
{
return false;
}
for (Write w : secondaries)
{
// 如果在这里挂了， 谁来清理
if (!Prewrite(w, primary))
{
return false;
}
}
int commit_ts = oracle_.GetTimestamp();
Write p = primary;
bigtable::Txn T = bigtable::StartRowTransaction(p.row);
// 读取Prewrite阶段写入的lock，如果读取失败，则abort
// 执行这一步的原因在于lock可能由于某种原因被Get操作清理掉了
// 某种原因包括：
// 1. 真死了
// 2. 假死，等下可能活过来的
// 1) 执行当前事务的线程被调度器调度出去了，执行优先级较低
// 2) 系统中出现了一些工作特别繁重的线程，把系统暂时性压死
// 3) 等待IO。等等
// 另外，这里只读取primary lock，而没有读取其它lock，是Percolator
// 的一个约定，它相对简化了检查过程，不需要检查secondaries的lock。
if (!T.Read(p.row, p.col+"lock", [start_ts_, start_ts_])) // 注意整个时间就是版本
{
return false;
}
T.Write(p.row, p.col+"write", commit_ts, start_ts_); // commit_ts@start_ts_
// 成功执行下面的Commit操作后，写操作对Get可见
T.Erase(p.row, p.col+"lock", commit_ts);
// *NOTE* 提交点，T.Commit执行成功后一旦系统出现故障，恢复后
// 只能rollforward，不能rollback
if(!T.Commit())
{
return false;
}
// 此时的写操作已经不需要用行事务来保证了，因为这里只有写操作
// 并且也不可能有两个并发写操作都写同一个commit_ts下的cell
for (Write w : secondaries)
{
bigtable.Write(w.row, w.col+"write", commit_ts, start_ts_);
bigtable.Erase(w.row, w.col+"lock", commit_ts);
}
return true;
}
// 确认造成冲突的进程是否已经退出，如果退出则做清理，否则忽略
void BackoffAndMaybeCleanupLock(Row row, Column c)
{
//------------分布式锁的常用用法-------------
// 判断写这个锁的worker是否还活着(liveness)的方法：
// 每个worker会写一个token到Chunbby lockservice中，并且定期
// 更新这个token中的last_update_time，其它worker检查这个worker
// 是否存活的方法就是去检查这个token是否存在，如果存在，其
// last_update_time是否太旧，通过这两重检查才判定该worker活着，
// -------------如果判定该worker已死，则根据primary lock的状态来决定动作---------
// 1. primary lock不存在: roll-forward, 将所有未提交的secondary write都提交掉，相应的lock都擦除掉
// 2. primary lock存在 : roll-back, 将primary的数据清除掉，write的值也擦除掉。
// --------lock应该是被清除的, 只要读到任意版本的lock 都应该调用该函数-----------
// 如果worker还活着，则不进行数据操作，可能小睡眠一下，等待
// worker主动将锁清除。
// Get操作会因此等待较长一段时间，这是Percolator需要注意的一个特点。
}
} // class Transaction
锁冲突的处理
当一个client在事务提交阶段，crash掉了，那么锁还保留，这样后续的client访问就会被阻止，这种情况叫做锁冲突，Percolator提供了一种简单的机制来解决这个问题。
每个client定期向Chubby Server写入token，表明自己还活着，当某个client发现锁冲突，那么会检查持有锁的client是否还活着，如果client是working状态，那么client等待锁释放。否则client要清除掉当前锁。
Roll forward or roll back ：
Client先检查primary lock是否存在，因为事务提交先从primary开始，如果primary不存在，那么说明前面的client已经提交了数据，所以client执行roll forward操作：把non-primary对应的数据提交，并且清除non-primary lock；如果primary存在，说明前面的client还没有提交数据就crash了，此时client执行roll back操作：把primary和non-primary的数据清除掉，并且清除lock。
