【摘要】：針對因果一致性模型約束過多且表達(dá)能力不足的問題,提出一種強的分布式上下文一致性模型。剔除同一用戶的操作中非強制性的依賴關(guān)系,以及在不同客戶端間定義所需的操作依賴;在此基礎(chǔ)上,設(shè)計一種解決Paxos不能滿足上層一致性需求問題的、實現(xiàn)分布式上下文一致性模型的共識算法CC-Paxos。利用時間戳給分布式上下文中的操作定序,采用細(xì)粒度的依賴檢測,高效減少沖突操作的數(shù)目。實驗結(jié)果表明,與在上層使用causal+一致性、下層用Egalitarian Paxos的方法相比,CC-Paxos顯著降低了延遲,增加了吞吐量,且不需犧牲可擴展性。
【圖文】：

，客戶端不斷發(fā)送請求。副本在請求執(zhí)行后回復(fù)客戶端，通過測試單位時間內(nèi)客戶端收到的回復(fù)來測量吞吐量。延時是指從發(fā)送請求到收到副本回復(fù)之間經(jīng)過的時間。我們測量的是所有請求執(zhí)行延遲的中值。在實驗過程中，客戶端一共發(fā)送６４０００個請求，每個上下文對應(yīng)２０個客戶端。３．２自相關(guān)率自相關(guān)率是兩條命令屬于同一上下文的概率，高自相關(guān)率意味著同一上下文中的命令數(shù)增加，即更多的命令需要保持順序關(guān)系，因此我們預(yù)期吞吐量會下降和延時增加。在這組實驗中設(shè)定上下文的數(shù)目和鍵群組的數(shù)目為４。圖４和圖５展現(xiàn)了不同自相關(guān)率下ＣＣ－Ｐａｘｏｓ和ＣＥ－Ｐａｘｏｓ的吞吐量和延時。從圖４中可以看出，隨著自相關(guān)率的從０％變化到１０％，ＣＥＰａｘｏｓ的吞吐量猛烈下降。當(dāng)自相關(guān)率為０％時，所有的請求都是沒有依賴的，全部都可以并行執(zhí)行。在這種情況下，ＣＣ－Ｐａｘｏｓ的吞吐量比ＣＥＰａｘｏｓ略低（０．８９１％），因為與ＣＥＰａｘｏｓ相比，ＣＣ－Ｐａｘｏｓ在提交圖４吞吐量隨著自相關(guān)率的變化圖５執(zhí)行延遲中值隨著自相關(guān)率的變化·６３０·

斷發(fā)送請求。副本在請求執(zhí)行后回復(fù)客戶端，通過測試單位時間內(nèi)客戶端收到的回復(fù)來測量吞吐量。延時是指從發(fā)送請求到收到副本回復(fù)之間經(jīng)過的時間。我們測量的是所有請求執(zhí)行延遲的中值。在實驗過程中，客戶端一共發(fā)送６４０００個請求，每個上下文對應(yīng)２０個客戶端。３．２自相關(guān)率自相關(guān)率是兩條命令屬于同一上下文的概率，高自相關(guān)率意味著同一上下文中的命令數(shù)增加，即更多的命令需要保持順序關(guān)系，因此我們預(yù)期吞吐量會下降和延時增加。在這組實驗中設(shè)定上下文的數(shù)目和鍵群組的數(shù)目為４。圖４和圖５展現(xiàn)了不同自相關(guān)率下ＣＣ－Ｐａｘｏｓ和ＣＥ－Ｐａｘｏｓ的吞吐量和延時。從圖４中可以看出，隨著自相關(guān)率的從０％變化到１０％，ＣＥＰａｘｏｓ的吞吐量猛烈下降。當(dāng)自相關(guān)率為０％時，所有的請求都是沒有依賴的，全部都可以并行執(zhí)行。在這種情況下，ＣＣ－Ｐａｘｏｓ的吞吐量比ＣＥＰａｘｏｓ略低（０．８９１％），因為與ＣＥＰａｘｏｓ相比，ＣＣ－Ｐａｘｏｓ在提交圖４吞吐量隨著自相關(guān)率的變化圖５執(zhí)行延遲中值隨著自相關(guān)率的變化·６３０·

般情況下，ＣＣ－Ｐａｘｏｓ的吞吐量明顯優(yōu)于ＣＥＰａｘｏｓ，這是因為ＣＣ－Ｐａｘｏｓ高效的處理并發(fā)的請求。隨著自相關(guān)率的增加，ＣＣ－Ｐａｘｏｓ性能相對穩(wěn)定。從自相關(guān)率在５０％左右開始，ＣＣ－Ｐａｘｏｓ的延時中值開始優(yōu)于ＣＥＰａｘｏｓ，并隨著自相關(guān)率的增加，持續(xù)好于ＣＥＰａｘｏｓ。３．３鍵群組大小我們還檢測鍵群組大小即每個鍵群組包含的鍵的數(shù)目Ｋ對系統(tǒng)性能的影響。在這系列的實驗中我們設(shè)置上下文數(shù)目為Ｐ從１變換或者４，而自相關(guān)率設(shè)置為７０％。圖６和圖７分別展示了Ｋ對ＣＣ－Ｐａｘｏｓ和ＣＥＰａｘｏｓ的吞吐量和延時的影響。很容易可以看出，在不同的上下文數(shù)目的情況下，隨著Ｋ的增加，兩個算法的吞吐量和延時的性能都有所提升。在更高的上下文數(shù)目情況下，兩個算法都取得更好的性能。這是因為每個鍵群組的鍵數(shù)目越多，上下文的數(shù)目越多，命令的鍵分布的更廣，從而導(dǎo)致沖突率降低。因此請求的平均沖突依賴降低，減少了遞歸計算沖突依賴集以及遞歸構(gòu)建依賴圖的時間，更加重要的是，減少了客戶端和副本間為保持一致性所進行的協(xié)調(diào)。圖６吞吐量隨著健群組大小的變化圖７執(zhí)行延遲中值隨著鍵群組大小的變化如圖６當(dāng)上下文的數(shù)目為４時，ＣＣ－Ｐａｘｏｓ的吞吐量比ＣＥＰａｘｏｓ高１７％。當(dāng)上下文為１時，這個比例變?yōu)椋保保叮ァ＿@種性能的優(yōu)勢來源于高效的監(jiān)測到可并發(fā)執(zhí)行的請求。圖７展示了兩個算法的執(zhí)行延時的中位值。無論每個鍵群組包含多少鍵值或者上下文的數(shù)目，ＣＣ－Ｐａｘｏｓ這方面的性能都好于ＣＥＰａｘｏｓ。３．４上下文數(shù)目如上文所述，上下文數(shù)目Ｐ影響相關(guān)率和

本文編號：2752523