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。