1 整個邏輯時間是作為版本號
2 單行事務(wù)有底層數(shù)據(jù)庫保障
3 2PC的典型實(shí)現(xiàn)
4 外部需要Chubby做協(xié)調(diào)
總結(jié)： 用單行事務(wù)實(shí)現(xiàn)跨行、 跨表事務(wù)

場景分析過程(單行事務(wù)本身就存在由底層bigtable決定 )

1 初始狀態(tài), bob 賬戶有10美金, joe 有2個美金. write 列中的 6:data @ 5 表示 當(dāng)前的數(shù)據(jù)是 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 事務(wù)的第一個階段, bob的賬戶變成3美金了. 注意 lock 列被加鎖, 并且標(biāo)明自己是 primary. 每個事務(wù)中, 只有一個primary, 也正是這個primary的存在, 使得我們能夠用行原子性來實(shí)現(xiàn)分布式事務(wù).

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 現(xiàn)在給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 事務(wù)提交的第一階段, 提交 primary, 移除lock 列的內(nèi)容 在 write 列寫入最新數(shù)據(jù)的 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 事務(wù)提交的第二階段, 提交除 primary 之外其它部分. 提交的方式也是移除 lock, 同時在 write 列寫入新數(shù)據(jù)的 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_;  

    // 每一個事務(wù)都有一個start timestamp
    // 讀事務(wù)只關(guān)心[0, start_ts_]時間區(qū)間之內(nèi)數(shù)據(jù)邏輯是否一致
    // 寫事務(wù)則需要關(guān)心[0, infinate)時間區(qū)間之內(nèi)數(shù)據(jù)邏輯是否一致
    int start_ts_;  

    // 初始化當(dāng)前事務(wù)的timestamp，note: 此oracle非彼Oracle
    Transaction() : start_ts_(oracle.GetTimestamp())
    {
    }  

    void Set(Write w)
    {
        writes_.push_back(w);
    }  

    // 讀事務(wù)
    void Get(Row row, Column c, string *value)
    {
        while (true)
        {
            // 利用了Google Bigtable的單行事務(wù)特性。
            // 單行事務(wù)的特征為：
            // 在單行數(shù)據(jù)的操作上保證事務(wù)性（ACID）
            bigtable::Txn T = bigtable::StartRowTransaction(row);
            // 檢查在讀操作的同時是否有并發(fā)的寫操作，如果有并發(fā)寫操作
            // (包括那些沒有徹底完成寫操作就掛掉的情況)則需要執(zhí)行比較
            // 復(fù)雜的重試/清理操作 - BackoffAndMaybeCleanupLock()
            //
            // 這里需要注意時間區(qū)間為[0, start_ts]，也就是說Get只關(guān)心
            // 在本事務(wù)發(fā)起前的數(shù)據(jù)快照是否具有一致性，對start_ts_之后
            // 發(fā)起的事務(wù)它并不關(guān)心。這反映了Percolator表現(xiàn)出來的
            // snapshot isolation特性，Get操作的是start_ts_之前的一個快照
            if (T.Read(row, c+"lock", [0, start_ts]))
            {
                 // 執(zhí)行到這里的時候說明有尚未解開的鎖
                  // (pending lock)，可能來自：
                //  1. 在start_ts_之前發(fā)起的一個寫事務(wù)正在進(jìn)行中
                //  2. 在start_ts_之前發(fā)起的一個寫事務(wù)沒有完全commit就死掉了
                // ps. Back off的意思是后退，滾開，
                 // 貌似一群警察踢門的時候常喊?
                BackoffAndMaybeCleanupLock(row, c);
                continue;
            }  

            // 執(zhí)行到這里的時候說明start_ts_之前的數(shù)據(jù)具有一個一致的snapshot
            last_write = T.Read(row, c+"write", [0, start_ts_]);
            // sanity check. 沒有找到任何數(shù)據(jù)可讀，返回。
            if (!latest_write.found())
            {
                return false;
            }
            // write列記錄了data所在的timestamp，
              // 為了讀到一條數(shù)據(jù)，需要先得到該數(shù)據(jù)所在的
             // timestamp，然后通過timestamp讀到最終數(shù)據(jù)，
             // 有點(diǎn)間接尋址的味道
            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);  

        // 如果在本事務(wù)開始后([start_ts_, inf))也有其他事務(wù)執(zhí)行寫操作，
        // 并且已經(jīng)完成了部分/全部數(shù)據(jù)寫操作，則abort
        //
        // 對于start_ts_之前的寫操作，分為兩種情況
        //  1. 整個事務(wù)都提交完成了得寫操作，這是正常情況，結(jié)果一致
        //  2. 只寫了一半的事務(wù)，這由后面的lock檢查來處理
        if (T.Read(w.row, c+"write", [start_ts_, inf])
        {
            return false;
        }  

        // 如果在當(dāng)前操作的cell上還有鎖的話，則abort
        // 這個檢查比較狠，只要有鎖，無論timestamp為多少均abort，這是
        // 因?yàn)橹灰墟i，就說明還有一個并發(fā)事務(wù)(dead or not)在寫當(dāng)前cell
        
        if (T.Read(w.row, c+"lock", [0, inf])) // 只要有鎖， 全部則返回錯誤
        {
            return false;
        }  

        // 檢查到這里就可以放心地預(yù)寫入數(shù)據(jù)和鎖了
        // 此時data對Get還不可見，因?yàn)閣rite還沒有寫入
        // 時間相當(dāng)于版本號，這個依賴于google的提供GPS和原子鐘提供的嚴(yán)格遞增的時間. 其他公司怎么做...找一個統(tǒng)一授時集群？？ 
        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單行事務(wù)
        return T.commit();
    }  

    bool Commit()
    {
        // 任選一個write作為primary，這里primary的作用類似于一個標(biāo)志點(diǎn)primary行被提交后，整個事務(wù)必須提交
        Write primary = writes_[0];
        vector<Write> secondaries(writes_.begin() + 1, writes_end());  

        // 預(yù)提交
        // primary和secondarise的預(yù)提交如果失敗，
        // 則說明還有別的并發(fā)事務(wù)在寫當(dāng)前cell，當(dāng)前commit需要abort
        //
        // 我對并發(fā)事務(wù)的理解：在時間軸上有交集的事務(wù)。
        //  Timeline -------------------------------------------->
        //  Trans0:   ^-$
        //  Trans1:       ^-----$
        //  Trans2:       ^----------$
        //  Trans3:          ^------------$
        //  Trans4:                           ^----$
        //  Trans5:  ^----x
        // ^標(biāo)志事務(wù)開始，$標(biāo)志事務(wù)結(jié)束，x表示執(zhí)行事務(wù)的進(jìn)程中途死掉
        //  0,5; 1,2; 1,3; 1,5; 2,3; 2,5均為并發(fā)事務(wù)
        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
        // 執(zhí)行這一步的原因在于lock可能由于某種原因被Get操作清理掉了
        // 某種原因包括：
        //  1. 真死了
        //  2. 假死，等下可能活過來的
        //    1) 執(zhí)行當(dāng)前事務(wù)的線程被調(diào)度器調(diào)度出去了，執(zhí)行優(yōu)先級較低
        //    2) 系統(tǒng)中出現(xiàn)了一些工作特別繁重的線程，把系統(tǒng)暫時性壓死
        //    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_
        // 成功執(zhí)行下面的Commit操作后，寫操作對Get可見
        T.Erase(p.row, p.col+"lock", commit_ts);  

        // *NOTE* 提交點(diǎn)，T.Commit執(zhí)行成功后一旦系統(tǒng)出現(xiàn)故障，恢復(fù)后
        // 只能rollforward，不能rollback
        if(!T.Commit())
        {
            return false;
        }  

        // 此時的寫操作已經(jīng)不需要用行事務(wù)來保證了，因?yàn)檫@里只有寫操作
        // 并且也不可能有兩個并發(fā)寫操作都寫同一個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;
    }  

    // 確認(rèn)造成沖突的進(jìn)程是否已經(jīng)退出，如果退出則做清理，否則忽略
    void BackoffAndMaybeCleanupLock(Row row, Column c)
    {
         //------------分布式鎖的常用用法-------------
        // 判斷寫這個鎖的worker是否還活著(liveness)的方法：
        // 每個worker會寫一個token到Chunbby lockservice中，并且定期
        // 更新這個token中的last_update_time，其它worker檢查這個worker
        // 是否存活的方法就是去檢查這個token是否存在，如果存在，其
        // last_update_time是否太舊，通過這兩重檢查才判定該worker活著，

        // -------------如果判定該worker已死，則根據(jù)primary lock的狀態(tài)來決定動作---------
        //  1. primary lock不存在: roll-forward, 將所有未提交的secondary write都提交掉，相應(yīng)的lock都擦除掉
        //  2. primary lock存在  : roll-back, 將primary的數(shù)據(jù)清除掉，write的值也擦除掉。
        
        
        // --------lock應(yīng)該是被清除的, 只要讀到任意版本的lock 都應(yīng)該調(diào)用該函數(shù)----------- 

        // 如果worker還活著，則不進(jìn)行數(shù)據(jù)操作，可能小睡眠一下，等待
        // worker主動將鎖清除。
        // Get操作會因此等待較長一段時間，這是Percolator需要注意的一個特點(diǎn)。
    }  

} // class Transaction

鎖沖突的處理

當(dāng)一個client在事務(wù)提交階段，crash掉了，那么鎖還保留，這樣后續(xù)的client訪問就會被阻止，這種情況叫做鎖沖突，Percolator提供了一種簡單的機(jī)制來解決這個問題。

每個client定期向Chubby Server寫入token，表明自己還活著，當(dāng)某個client發(fā)現(xiàn)鎖沖突，那么會檢查持有鎖的client是否還活著，如果client是working狀態(tài)，那么client等待鎖釋放。否則client要清除掉當(dāng)前鎖。

Roll forward or roll back ：

Client先檢查primary lock是否存在，因?yàn)槭聞?wù)提交先從primary開始，如果primary不存在，那么說明前面的client已經(jīng)提交了數(shù)據(jù)，所以client執(zhí)行roll forward操作：把non-primary對應(yīng)的數(shù)據(jù)提交，并且清除non-primary lock；如果primary存在，說明前面的client還沒有提交數(shù)據(jù)就crash了，此時client執(zhí)行roll back操作：把primary和non-primary的數(shù)據(jù)清除掉，并且清除lock。