An Evaluation of Concurrency Control with One Thousand Cores

Staring into the Abyss: An Evaluation of Concurrency Control with One Thousand Cores

ABSTRACT

隨著多核處理器的發(fā)展，一個芯片可能有幾十乃至上百個core。在數(shù)百個線程并行運行的情況下，協(xié)調對數(shù)據(jù)的競爭訪問的復雜性可能會減少增加的核心數(shù)所帶來的收益。探索當前DBMS的設計對于未來超多核數(shù)的CPU的適應性，在多核芯片上跑OLTP來進行評估，使用7種并發(fā)控制算法在內存數(shù)據(jù)庫，使用計算機模擬的1024核來進行測試，所有算法都無法適配，所有數(shù)據(jù)庫都有基本的性能瓶頸，因此與追求增量解決方案相比，以后應該考慮針對多核芯片完全重新設計的DBMS體系結構，該體系結構從頭開始構建，并與（新）硬件緊密耦合。

1. INTRODUCTION

單核性能的提升已經(jīng)很難了，考慮到當前的功率限制和單線程處理的低效率，除非出現(xiàn)顛覆性技術，否則增加內核數(shù)量是架構師目前能夠提高計算能力的唯一方法。因此我們正在進入多核機器的時代。指令級的并行和單線程的這種性能改進將讓位于大規(guī)模線程級的并行的性能改進（更有意義）。

可能很快One Chip就有a thousand cores，這時對于單節(jié)點共享內存的DBMS來說scalability就非常重要了，如果不能充分利用這些cores，那么DBMS ????。聚焦于千核下，事務處理的并發(fā)控制的具體表現(xiàn)，通過OLTP來研究DBMS的伸縮性。

在主存DBMS中實現(xiàn)了七種并發(fā)控制算法，并使用高性能分布式CPU模擬器將系統(tǒng)擴展到1000核。暫時缺少針對多核CPU，來大規(guī)模評估單個DBMS上的多個并發(fā)控制算法。

• 本文主要contributions：
  • 對7個并發(fā)控制方案的可擴展性進行了全面的評估
  • 在1000核上的OLTP DBMS的第一次評估
  • 確定了非特定于實現(xiàn)（與數(shù)據(jù)庫實現(xiàn)無關）的并發(fā)控制方案中的瓶頸

2. CONCURRENCY CONTROL SCHEMES

A transaction in the context of one of these systems is the execution of a sequence of one or more operations (e.g., SQL queries) on a shared database to perform some higher-level function.

• 現(xiàn)代OLTP工作負載中的事務有三個顯著特征:

  (1) they are short-lived (i.e., no user stalls)

  (2) 使用索引查找一小部分數(shù)據(jù)來完成事務，沒有全表掃描或者規(guī)模很大的join

  (3) they are repetitive (i.e., executing the same queries with different inputs)

OLTP DBMS期望為它執(zhí)行的每個事務維護四個屬性:ACID，并發(fā)控制允許終端用戶以Multi-programmed fashion來訪問數(shù)據(jù)庫，同時保持他們每個人都在專用系統(tǒng)上單獨執(zhí)行事務的錯覺，并發(fā)控制本質上提供了系統(tǒng)中的原子性和隔離性保證。

進行探索的并發(fā)控制方案是2PL 或者 T/O的變體。

2.1 Two-Phase Locking

鎖的所有權的規(guī)則：(1) 不同事物不能擁有沖突的locks (2) 一旦事務放棄了鎖的所有權，可能永遠無法獲得其他的鎖（餓死？）

2PL的兩個階段，第一個階段增長growing phase階段：獲取鎖不需要釋放；第二階段收縮shrinking phase階段：禁止獲取額外的鎖，釋放鎖，事務commit/abort的時候所有鎖返回給coordinator。 可能會產(chǎn)生死鎖。

• 2PL with Deadlock Detection(DL_DETECT)

  DBMS通過監(jiān)視waits-for graph Jakob_Hu’blog CSDN（類似于進程資源圖 如果有環(huán)則有死鎖）來檢查死鎖，如果出現(xiàn)死鎖則選擇一個代價最?。ㄙY源量，擁有鎖的數(shù)量）的事務進行終止來打破死鎖

• 2PL with Non-waiting Deadlock Prevention (NO_WAIT)

  死鎖預防，如果出現(xiàn)沖突則立刻回滾?？赡莛I死所以有了wait die

• 2PL with Waiting Deadlock Prevention (WAIT_DIE):

  No-Wait的非搶占式變體，如果事務比持有鎖的事務老，則允許等待，如果年輕則終止這個請求鎖的事務。每個事務在執(zhí)行之前都需要獲得一個時間戳，時間戳排序保證不會發(fā)生死鎖。

2.2 Timestamp Ordering

T/O先驗生成事務的可串行化執(zhí)行順序。事務在執(zhí)行前被分配一個唯一的、單調遞增的時間戳;這個時間戳被DBMS用來以適當?shù)捻樞蛱幚頉_突的操作。

對T/O的一些改進主要是(1) DBMS的檢查粒度：tuples or partitions (2) DBMS檢查沖突的時間，事務運行中或者結束的時候。

• Basic T/O

  事務每次讀寫元組的時候對時間戳進行比較，如果事務的時間戳<該元組最后一次寫入的時間戳，則拒絕該事務的請求； 如果事務的時間戳小于該元組最后一次讀的時間戳，DBMS將拒絕它。讀查詢讀的是元組的副本，可以并發(fā)讀。

  Basic T/O是一個中心化的scheduler 然后本文的實現(xiàn)是一個decentralized 分散的scheduler。

• MVCC

  MVCC下每個寫操作都會在數(shù)據(jù)庫中創(chuàng)建一個元組的一個新版本出來， 每個版本有個時間戳對應最后對他寫的事務的時間戳？還是寫的時間戳，讀操作由DBMS決定讀版本，MVCC不延遲操作，假設要讀的正在被寫還是能讀（對不對另說了）

• OCC

  DBMS需要track 讀寫集，在事務提交的時候檢查該事務的讀集是否和其他并發(fā)事務的寫集有依賴，如果沒有可以直接commit，如果有則需要abort restart。并發(fā)度高，只在commit階段提交更新的時候才會check。Modern OCC： Silo and Hekaton，本文的OCC實現(xiàn)類似于Hekaton 將驗證階段并行化。

• T/O with Partition-level Locking(H-STORE)

  分區(qū)劃分，每個分區(qū)都有一個排他鎖由執(zhí)行器的線程管理，一個事務在開始運行之前要獲得所要訪問的所有分區(qū)的鎖。當事務請求到達時，DBMS為其分配一個時間戳，然后將其添加到其目標分區(qū)的所有鎖獲取隊列中。如果事務具有隊列中最早的時間戳，則授予它對該分區(qū)的訪問權限（Lock）。

3. MANY-CORE DBMS TEST-BED

使用Graphite來模擬一個可以擴展到1024 core CPU，DBMS開發(fā)了一個內存OLTP engine。定制DBMS 可以排除變量只有并發(fā)控制一個平靜，第二是使用現(xiàn)有的DBMS會很慢（模擬器的運算很慢？）

3.1 Simulator and Target Architecture

Graphite是一個用于大規(guī)模多core系統(tǒng)的CPU模擬器，為架構中每一個core創(chuàng)建一個單獨的線程來運行l(wèi)inux process。每個線程被attached to一個模擬的內核線程，然后可以將其映射到不同物理主機上的不同進程上。只執(zhí)行應用程序不會模擬操作系統(tǒng)，在本文中部署Graphite到一個22節(jié)點的集群中，每個node有雙插槽(double-socket)Intel Xeon E5-2670和64GB DRAM。

Target architecture是tiled分層多核CPU，平鋪式芯片多處理器，使用高帶寬、二維網(wǎng)格片上網(wǎng)絡相互連接，每跳需要兩個周期。使用共享的L2-cache configuration。

3.2 DBMS

事務運行時的數(shù)據(jù)：throughput、latency and abort rates.其他六種度量

• useful work：事務執(zhí)行和操作元組的時間
• ABORT：事務回滾所做的所有更改的開銷
• TS ALLOCATION:對于需要時間戳的并發(fā)控制協(xié)議，系統(tǒng)從centralized allocator獲取時間戳的時間
• INDEX：事務在hash index上花費的時間
• WAIT：事務必須等待的總時間，2PL，T/O
• MANGAER：除了等待時間，事務在lock管理器、時間戳管理器的中花費的時間。

3.2 Workloads

TCSB+TPC-C

3.3 Simulator vs. Real Hardware

為了證明Graphite的效果和真實硬件的效果差不多，在現(xiàn)有硬件上部署DBMS，執(zhí)行了一個讀密集型YCSB，使用相同數(shù)量的core在graphite上執(zhí)行相同的負載。所有并發(fā)方案在graphite和真是硬件上表現(xiàn)出相同的性能變化趨勢，MVCC T/O OCC之間的相對性能差異有不同，MVCC訪問內存更多在tw0-socket system中代價更高，而graphite建模是single CPU socket，沒有inter-socket的代價.32核的時候TO和WAIT_DIE性能下降，主要因為在分配時間戳的時候需要進行跨核通訊。

4. DESIGN CHOICES & OPTIMIZATIONS

主要挑戰(zhàn)之一就是：設計一個擴展性很好的DBMS以及并發(fā)控制方案，主要需要消除共享數(shù)據(jù)結構，設計經(jīng)典版本的并發(fā)控制方案的分布式版本。還確定了2PL / T/O 算法的基本瓶頸，并展示了硬件支持來解決該問題。

4.1 General Optimizations

對所有并發(fā)控制方案做的對DBMS的優(yōu)化

• Memory Allocation

  malloc，DBMS花費大量時間來等待內存分配，即使對于讀也有復制Records，并為訪問跟蹤數(shù)據(jù)結構創(chuàng)建內部元數(shù)據(jù)句柄，TCmalloc jemalooc效果都不好，自己重寫了malloc，每個線程都被分配了自己的內存池，本文的allocator會根據(jù)工作負載自動調整池的大小。

• Lock Table

  鎖表是dbms中的另一個關鍵爭用點，沒有使用centralized lock table 或者 timestamp manager而是實現(xiàn)了一個元組粒度的加鎖。提高了可伸縮性，但增加了內存開銷

• Mutexes

  互斥鎖，由互斥鎖保護的中心臨界區(qū)將限制任何系統(tǒng)的可伸縮性。因此，避免在關鍵路徑上使用互斥鎖是很重要的。對于2PL，保護集中式死鎖檢測器的互斥鎖是主要瓶頸，而對于T/O算法，用于分配唯一時間戳的互斥鎖是主要瓶頸。

4.2 Scalable Two-Phase Locking

• Deadlock Detection

  死鎖檢測，死鎖檢測是一個瓶頸，多個線程競爭更新等待圖（centralized），通過跨核劃分數(shù)據(jù)結構并且讓死鎖檢測器完全無鎖來解決。(沒看懂

• Lock Thrashing

  鎖抖動，由于鎖抖動，DL_DETECT還是不能擴展，當事務在提交之前保持其鎖，阻塞所有其他試圖獲取這些鎖的并發(fā)事務時，就會發(fā)生這種情況。具體的，在寫密集型中按照事務的主鍵順序來獲得鎖，就不需要進行死鎖檢測了，來觀察鎖抖動，隨著寫事務比例增加，競爭增加，在核數(shù)增多的情況下，不能夠線性擴展，所以說明鎖方法本事就是一個瓶頸，限制了在多核高爭用場景下的可伸縮性。

  

• Waiting vs. Aborting

  通過在某些時間點終止事務來減少活動事務數(shù)，來解決DL_DETECTION抖動問題，設置一個超時閾值timeout threshold，重啟等待鎖時間超過閾值的事務，如果threshold =0 ，就是No-Wait，在64核CPU上使用不同的超時閾值運行具有高爭用的相同YCSB工作負載。我們測量了DL_DETECTscheme在0-100 ms之間掃描超時的DBMS中的吞吐量和中斷率，如果超時時間較短，則中止率較高，從而減少了正在運行的事務數(shù)量并緩解了抖動問題。使用更長的超時可以降低中止率，但代價是更多的抖動。在本文中，我們將超時閾值設置為100μs來評估dl_detect。

  

4.3 Scalable Timestamp Ordering

• Timestamp Allocation

  根據(jù)分配的時間戳對事務進行排序決策，保證時間戳unique，navie的方法是對allocator的臨界區(qū)加mutex鎖，但是verybad 性能。另一個方法是使用atomic addition operation來推進全局邏輯時間戳，需要的指令更少因此比mutex鎖臨界區(qū)的時間更短。對千核cpu來說還是不夠的，討論三種timestamp allocation方案，(1) atomic addition with batching 帶批處理的原子加法, (2) CPU clocks, and (3) hardware counters.

  批處理的原子加法：DBMS使用相同的原子指令來分配時間戳，但是時間戳管理器為每個請求批量返回多個時間戳。

  clock-based allocation：每個工作線程從其本地核心讀取邏輯時鐘，然后將其與其線程id連接起來。只要所有時鐘都是同步的，這就提供了良好的可伸縮性。在分布式系統(tǒng)中，同步是通過軟件協(xié)議或外部時鐘來完成的。然而，在多核CPU上，這會帶來很大的開銷，因此需要硬件支持。截至2014年7月，只有英特爾cpu支持跨核同步時鐘。

  使用高效內置硬件計數(shù)器，計數(shù)器物理上位于CPU的中心，這樣到每個內核的平均距離就最小化了。目前沒有現(xiàn)有的CPU支持此操作，本文在Graphite上實現(xiàn)了一個計數(shù)器，通過on-chip network來發(fā)送時間戳請求，以便在單個周期內自動增加時間戳請求。

  為了確定一下每種方法分配時間戳的最大速率，進行了micro-benchmark，基于互斥鎖效率最低，再就是原子加法，由于write back和每個timestamp cache line last copy invalid，需要在芯片上進行一次往返通信，對1024core 來說需要100個周期，所以1GHz下最大吞吐量是1000 million Ts/s。Hardware基于硬件的解決方案能夠隨著核心數(shù)量的增加而擴展，由于使用基于硬件計數(shù)器的方法增加時間戳只需要一個周期，因此該方法可以實現(xiàn)1 bilion ts/s的最大吞吐量,性能增益來自于通過遠程執(zhí)行加法操作來消除coherence traffic淺談多核系統(tǒng)的緩存一致性協(xié)議與非均一緩存訪問 - 知乎 (zhihu.com)基于時鐘的方法具有理想的(即線性)擴展，因為這種解決方案是完全分散的。

  

  還測試了DBMS中的不同分配方案在實際工作負載下的表現(xiàn)。No Contention情況下結果7.a = 6，首先，DBMS 使用批處理原子加法方法的吞吐量要差得多。這是因為當事務由于沖突而重新啟動時，它會在同一個工作線程中重新啟動，并在最后一批中分配下一個時間戳。但是這個新的時間戳也將小于導致中止的其他事務的時間戳，因此它將不斷重新啟動，直到線程獲取新批次。非批處理的atomic addition和clock、硬件計數(shù)器方法表現(xiàn)得一樣好， 本文使用atomic addition without batching來分配時間戳，因為其他的方式需要特定的硬件支持，并不一定適用于所有cpus

  

• Distributed Validation

  原始的OCC存在一個critical section來比較當前事務的讀集和之前事務的寫集是否有沖突，雖然很短，但是任何mutex-protected 臨界區(qū)都會損害可擴展性。using per-tuple validation，類似于HekatonHigh-performance concurrency control mechanisms for main-memory databases

• Local Partitions

  優(yōu)化了原始的 H-SORE 協(xié)議以利用共享內存：我們允許多分區(qū)事務直接訪問遠程分區(qū)上的元組，而不是發(fā)送由遠程分區(qū)的工作線程執(zhí)行的查詢請求。這樣可以實現(xiàn)比使用進程內通信更快的更簡單的實現(xiàn)。使用這種方法，數(shù)據(jù)不需要進行物理分區(qū)，因為片上通信延遲很低。所有線程都可以訪問只讀表，而不需要進行復制，從而減少了內存占用。使用上述相同的時間戳分配優(yōu)化來避免強制等待時間

5 EXPERIMENTAL ANALYSIS

兩組實驗(1) scalability：固定workload參數(shù)，增加core 到1024看性能。(2) sensitivity evaluations.改變單個工作負載參數(shù)(例如，事務訪問傾斜)。 即可擴展性和靈敏度測試。

5.1 Read-Only Workload

在一個完全可擴展的DBMS中，吞吐量應該隨著核心數(shù)量的增加而線性增加，但是T/O時間戳分配變成瓶頸，OCC遇到瓶頸的時間更早，因為它需要為每個事務分配兩次時間戳(即，在事務開始時和驗證階段之前)。無論內核數(shù)量多少，OCC和TIMESTAMP的性能都明顯比其他算法差。這些算法浪費循環(huán)，因為它們復制元組來執(zhí)行讀操作，而其他算法則直接讀取元組。

5.2 Write-Intensive Workload

寫密集型負載，中等程度競爭結果如下:

• no_wait和WAIT_DIE是唯一可以擴展到512核以上的2PL方案。NO_WAIT優(yōu)于WAIT_DIE。
• NO_WAIT是最具可伸縮性的，消除了等待
• no_wait和WAIT_DIE都有很高的事務中止率，但是重新啟動一個中止的事務的開銷很低。undo事務所需的時間略少于重新執(zhí)行事務查詢所需的時間，但是如果undo涉及到多個表、索引和物化視圖的改變，實際代價更高。

在更高爭用場景下

• 幾乎所有算法都無法擴展到64 core+
• NO_WAIT最初的性能優(yōu)于所有其他，但隨后屈服于鎖抖動
• OCC在1024核時性能最好。這是因為盡管在驗證階段有大量事務發(fā)生沖突并且必須中止，但總是允許提交一個事務。

為了更好地理解隨著爭用增加，每種方案何時開始出現(xiàn)問題，我們將內核數(shù)量固定為64，并對傾斜參數(shù)(theta)進行敏感性分析。

• 當theta值小于0.6時，爭用對性能的影響很小。
• 對于更高的設置，吞吐量會突然下降，使得所有算法都無法擴展，并且當值大于0.8時接近于零。

5.3 Working Set Size

事務訪問的元組數(shù)量是影響可伸縮性的另一個因素。當事務的工作集很大時，并發(fā)事務訪問相同數(shù)據(jù)的可能性就會增加。對于2PL算法，這增加了事務持有鎖的時間長度。然而，對于T/O，較長的事務可能會減少時間戳分配爭用。在寫密集型YCSB工作負載中改變每個事務訪問的元組數(shù)量。因為短事務導致更高的吞吐量，所以我們測量每秒訪問元組的數(shù)量，而不是完成的事務。我們使用中等傾斜設置(theta=0.6)并將核心計數(shù)固定為512。

• 短事務的時候：DL_DETECT和NO_WAIT的性能最好，因為死鎖很少，中止的數(shù)量也很低。但是，隨著事務工作集大小的增加，由于抖動的開銷，DL_DETECT的性能會下降。
• 對于T/O算法和WAIT_DIE，當事務較短時吞吐量較低，因為DBMS將大部分時間用于分配時間戳。但是隨著事務變長，時間戳分配成本被平攤。
• OCC的性能最差，因為它為每個事務分配的時間戳數(shù)量是其他方案的兩倍。
• 基于T/O的算法比DL_DETECT更能容忍爭用。

5.4 Read/Write Mixture

在這個實驗中，我們在64核配置上使用YCSB，并改變每個事務執(zhí)行的讀查詢的百分比。每個事務使用高傾斜設置(theta=0.8)執(zhí)行16個查詢。

• 在100%讀取時,TIMESTAMP和OCC表現(xiàn)不佳，因為它們復制元組以供讀取。
• 當有少量寫事務時，MVCC表現(xiàn)出最好的性能。這也是支持跨多個版本的非阻塞讀取最有效的一個例子;讀查詢根據(jù)時間戳訪問元組的正確版本，不需要等待寫事務。
• 這是與TIMESTAMP的一個關鍵區(qū)別，在TIMESTAMP中，延遲到達的查詢被拒絕，它們的事務被中止。

5.5 Database Partitioning

DBMS將數(shù)據(jù)庫劃分為不相交的子集以增加可擴展性.通過大多數(shù)事務只需要訪問單個分區(qū)上的數(shù)據(jù)這樣的保證來進行分區(qū)，可以提高數(shù)據(jù)庫的性能。

H-STORE的鎖是粗粒度的，當工作負載包含多分區(qū)事務時，H-STORE不能很好地工作。每個事務訪問多少分區(qū)也很重要;例如，即使有少量的多分區(qū)事務訪問所有分區(qū)，H-STORE的性能仍然很差。先在理想條件下比較H-store和其他六種方案，然后用多分區(qū)事務來測試它的性能。

假設DBMS在運行時開始之前知道將每個事務分配到哪個分區(qū)，在第一個實驗中，我們執(zhí)行了一個僅由單分區(qū)事務組成的工作負載。圖14的結果表明，HSTORE在高達800核的情況下優(yōu)于所有其他方案。H-Store取決于時間戳的分配和調度，因此在較高核數(shù)下性能下降。

改變工作負載中多分區(qū)事務的百分比，將DBMS部署在64核CPU上。圖15a中的結果說明了H-STORE方案的兩個重要方面。首先，無論工作負載是否包含修改數(shù)據(jù)庫的事務，性能都沒有差異;這是因為H-STORE鎖的方案。其次，DBMS的吞吐量隨著工作負載中多分區(qū)事務數(shù)量的增加而降低，因為它們減少了系統(tǒng)中的并行性。圖15b：由于降低了并行性和增加了跨核心通信，DBMS不能擴展訪問四個或更多分區(qū)的事務。

5.6 TPC-C

TPC-C中的事務比YCSB中的事務更復雜，代表了一大類OLTP應用程序。例如，它們以讀-修改-寫訪問模式訪問多個表，一些查詢的輸出用作同一事務中后續(xù)查詢的輸入。TPC-C事務也可能因為程序邏輯中的某些條件而中止，而不是僅僅因為DBMS檢測到?jīng)_突。

50% Neworder 50% Payment

TPC-C數(shù)據(jù)庫的大小通常由倉庫的數(shù)量來衡量，遵循TPC-C規(guī)范，其中約10%的NewOrder事務和約15%的payment事務訪問“遠程”倉庫。對于基于分區(qū)的方案，如H-STORE，每個分區(qū)由單個倉庫的所有數(shù)據(jù)組成。這意味著遠程倉庫事務將訪問多個分區(qū)。

首先在一個4倉庫數(shù)據(jù)庫上執(zhí)行TPC-C工作負載，每個倉庫有100MB數(shù)據(jù)(總共0.4GB)。這允許我們在工作線程多于倉庫時評估算法。然后，我們在1024倉庫數(shù)據(jù)庫上再次執(zhí)行相同的工作負載。由于在Graphite simulator中運行的內存限制，我們將這個數(shù)據(jù)庫的大小減少到每個倉庫26MB的數(shù)據(jù)(總共26GB)。這不會影響我們的測量，因為每個事務訪問的元組數(shù)量與數(shù)據(jù)庫大小無關。

• 5.6.1 4 Warehouses

  當倉庫數(shù)量少于core數(shù)量時，所有方案都難以擴展。使用h - store時，由于它的分區(qū)方案，DBMS無法利用額外的核;額外的工作線程基本上是空閑的。

  對圖16 c:對NewOrder大概能擴展到64核，TIMESTAMP、MVCC和OCC由于高中止率而具有較差的可伸縮性。由于抖動和死鎖，DL_DETECT不能擴展。

  對圖16 b: 擴展很差，因為Payment事務需要更新倉庫的一個單獨的字段W_YTD，需要1. 加排他鎖 或者2.prewrite。如果線程的數(shù)量大于倉庫的數(shù)量，那么更新倉庫表就會成為瓶頸。

  這兩個事務的主要問題是更新WAREHOUSE表時的爭用。每個Payment事務更新其相應的倉庫條目，每個neworder將讀取它。2PL-based算法中這些讀和寫操作相互阻礙。兩種基于T/O的算法，TIMESTAMP和MVCC，優(yōu)于其他方案，因為它們的寫操作不會被讀阻塞。這消除了2PL中的鎖阻塞問題。因此，NewOrder事務可以與Payment事務并行執(zhí)行

• 5.6.2 1024 Warehouses

  使用1024個倉庫，最多1024個內核。No scheme is able to Scale。原因各不相同

  對于幾乎所有的方案，主要的瓶頸是維護locks and latches的開銷，即使沒有爭用也會發(fā)生。

  對于2PL模式，每次訪問都會在DBMS中創(chuàng)建一個共享鎖條目。有大量并發(fā)事務時，鎖元數(shù)據(jù)會變得很大，因此需要更長的時間來更新它們。OCC在事務運行時不使用這種鎖，但是他在驗證階段使用latches來獲取tuple進行控制。雖然MVCC也沒有鎖，但是每個讀請求都會生成一個新的歷史記錄，這會增加內存流量。同時注意到，所有這些在技術上都是不必要的工作，因為ITEM表從未被修改過。

  對圖17-b: 當倉庫的數(shù)量等于或大于工作線程的數(shù)量時，Payment事務中的瓶頸被消除了，這幾乎提高了所有方案的性能。但是對于T/O方案，在較大的核數(shù)下吞吐量會變得太高，因此它們會受到時間戳分配的抑制。因此，它們無法達到高于~ 1000萬txn/s的速率。H-STORE總體上表現(xiàn)最好，因為它能夠利用分區(qū)，即使工作負載中有~ 12%的多分區(qū)事務。這證實了先前的研究結果，即當包含多分區(qū)事務的工作負載少于20%時，h - store優(yōu)于其他方法。但是，在1024核時，它受到DBMS的時間戳分配的限制。

6. DISCUSSION

討論分析前幾節(jié)的結果，提出避免多核dbms出現(xiàn)這些可伸縮性問題的解決方案。

6.1 DBMS Bottlenecks

評估表明，由于不同的原因和條件，所有七種并發(fā)控制方案都無法擴展到大量的內核，確定了可伸縮性的幾個瓶頸:(1)鎖抖動，(2)搶占式中止，(3)死鎖，(4)時間戳分配，以及(5)內存到內存復制。

• 抖動會發(fā)生在任何基于等待的算法中，如第4.2節(jié)所討論的，通過主動中止來減輕抖動。這導致中止和性能之間的權衡。一般來說，對于高爭用工作負載，非等待死鎖預防方案(NO_WAIT)比死鎖檢測(DL_DETECT)執(zhí)行得好得多。
• 雖然沒有一種并發(fā)控制方案適用于所有場景，但是在不同場景下都能找到一個效果不錯的方案。因此，可以將兩個或多個算法類組合到一個DBMS中，并根據(jù)工作負載在它們之間進行切換。例如，DBMS可以對競爭較少的工作負載使用dl_detect，但當事務由于抖動而花費太長時間才能完成時，則切換到NO_WAIT或基于T/的算法。還可以采用混合方法，例如MySQL的DL_DETECT + MVCC方案，其中只讀事務使用多版本控制，而所有其他事務使用2PL。
• 需要新硬件來克服這些瓶頸。當吞吐量很高時，所有的T/O方案都會遇到時間戳分配瓶頸，因為當內核數(shù)量很大時，使用原子加法方法會導致工作線程在芯片上發(fā)送許多消息來修改時間戳。
• 內存問題：緩解這個問題的一種方法是在CPU上添加硬件加速器，以便在后臺進行內存復制。這將消除通過CPU的管道加載所有數(shù)據(jù)的需要。本文認為，未來的cpu將需要切換到分散或分層內存控制器，以提供更快的內存分配。

6.2 Multi-core vs. Multi-node Systems

多節(jié)點，也就是分布式，存在一個瓶頸：分布式事務，因為網(wǎng)絡上節(jié)點之間的通信很慢，這種協(xié)議的協(xié)調開銷抑制了分布式dbms的可伸縮性。相比之下，共享內存環(huán)境中線程之間的通信要快得多。這意味著除了最大的OLTP應用程序外，單個具有大量DRAM的多核節(jié)點可能在所有應用程序中都優(yōu)于分布式DBMS。

還有一種可能的架構，shared-nothing 在多個節(jié)點之間，然后單個芯片內多線程共享內存。高性能，需要分層并發(fā)控制。

7. RELATED WORK

8. FUTURE WORK

本文主要是揭示了并發(fā)控制算法的瓶頸，這些瓶頸會隨著內核數(shù)量的增加而限制它們的可伸縮性。是算法固有的瓶頸，無法盡在軟件算法層面克服，需要軟硬件協(xié)同、新硬件。并發(fā)控制只是DBMS影響可伸縮性的幾個方面之一。要構建一個真正可伸縮的DBMS，還需要研究其他組件。計劃研究日志記錄和索引實現(xiàn)，然后分析針對這些組件的可能的優(yōu)化。還將擴展我們的工作，包括具有多個多核CPU的多套接字系統(tǒng)multisocket systems with more than one many-core CPU。

10. CONCLUSION

pluggable architecture支持七種并發(fā)控制方案。發(fā)現(xiàn)基于2pl的方案擅長處理在key-value工作負載中常見的具有低爭用的短事務。而基于T/ o的算法則擅長處理在復雜OLTP工作負載中更常見的較長事務的較高爭用。文章來源地址http://www.zghlxwxcb.cn/news/detail-716102.html

到了這里，關于【論文閱讀】An Evaluation of Concurrency Control with One Thousand Cores的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！