VoltDB內存數據庫設計與實現

介紹

  • 支持SQL的內存數據庫。

整體架構

  • VoltDB借鑒NoSQL架構,每個host都是同等的。通過Zookeeper維護cluster。
  • 在此先隻考慮單機版本。

線程模型

  • Volt-Server-Network-N為網絡接收Client請求線程,默認為core/4。
  • NTPServiceThread-Priority-N可能為回調線程,構造Client請求回包?
  • NTPServiceThread-N為執行SQL解析與可執行計劃構建的線程,存在多個。
  • SP-N-Site為處理SP的Site線程,可通過siteperhost=N配置,執行此Site對應的Partition的PlanFragment,通常有 [事務初始化,事務處理,消息回包] 流程。
  • MP-Site為Write-MP事務流程控制的線程,隻有1個,partitionId是16383。用於將MP事務拆解為多個SP事務,控制事務流程狀態。
  • MpInitiator-deliver線程為MpScheduler從MpInitiatorMailbox接收來自其他Site/NTPServiceThread的消息,聚合處理並通知MpSite的線程。
  • MpInitiator-send線程為接收從MpInitiatorMailbox傳來的消息並多播給其他Site的線程。
  • Ro-MP-Site-Pool為Read-MP事務流程控制線程池MpRoSitePool。

請求處理模型

  • SP處理流程是通過“事件驅動”的方式實現,基於消息通信。把一個SP事務的串行流程拆解為多個細粒度的消息處理事件,異步執行,提高細粒度事件執行的並發度,以及增加代碼復用。(可用協程)。
  • MP處理過程中,可能涉及到RoMpSite/MpSite與其他Site多輪交互的邏輯,采用多線程執行模型。單個MP事務控制邏輯保留在RoMpSite/MpSite線程內,其他消息接收與發送邏輯拆分到MpInitiator-deliver線程與MpInitiator-send線程中。由於Write-MP事務同一時間段內隻有1個執行,但Read-MP事務可能同時有多個,消息接收發送邏輯拆到其他線程,有利於充分復用。

消息通信

  • SpScheduler擁有TransactionTaskQueue(包含taskQueue與backlog)。MpScheduler擁有MpTransactionTaskQueue。
  • 事務任務是TransactionTask,消息包裝成SiteTasker。
  • Site間通過Mailbox傳遞消息Message。Message會包裝成SiteTasker投遞到TransactionTaskQueue內。同時Site由於異步操作,自身也會將下一步操作包裝成Task重新投入TransactionTaskQueue內。Site從TransactionTaskQueue.take()取出task來執行。
  • HostMessenger.send(destHSIds, VoltMessage)多播消息發送到多個destHSIds。destHSId如果是LocalHostId,則調用MpInitiatorMailbox/InitiatorMailbox/LocalMailbox.deliver將消息發送到目的Site/MpSite;若是RemoteHostId,則調用網絡發送。
  • InitiatorMailbox.deliver(VoltMessage) 發送消息到SpScheduler的taskQueue。
  • InitiatorMailbox.send(destHSIds, VoltMessage)通過HostMessenger.send多播消息。
  • MpInitiatorMailbox.deliver(VoltMessage) 發送消息到MpInitiatorMailbox的taskQueue(LinkedBlockingQueue)。後續由MpInitiator-deliver線程(MpInitiatorMailbox.m_taskThread)中的通過taskQueue接收該消息並處理。
  • MpInitiatorMailbox.send(destHSIds, VoltMessage)發送消息給sendQueue(LinkedBlockingQueue)。然後MpInitiator-send線程(MpInitiatorMailbox.m_sendThread)從sendQueue接收消息,然後調用HostMessenger.send()進行多播消息給其他Site。

Transaction

  • SP在單個Partition內順序執行,MP執行為2pc方式。事務順序通過TransactionTaskQueue保證。
  • MpScheduler使用MpTransactionTaskQueue接收MP,內有1個backlog事務隊列,所有到來MP事務都尾添加到backlog隊列內。從backlog隊列取事務時,Write-MP與Read-MP事務處理互斥。Write-MP事務同一時段隻有一個執行,Read-MP事務同一時段可有RoMpSitePool並發執行多個。
  • SpScheduler使用TransactionTaskQueue接收SP/Partitial-MP。
  • TransactionTaskQueue內含2個隊列,就緒執行隊列taskQueue(SiteTaskerQueue)與等待隊列backlog(Deque<TransactionTask>)。taskQueue內任務會被Site接下來執行,執行過程中新來的TransactionTask尾添加到backlog,同時正在執行的MP也在backlog頭(因為MP完整事務可能有多個Partital-MP將被Site執行)。
  • TransactionTask通過offer(task)投入,其他SiteTasker(比如消息)直接尾添加到taskQueue內。offer()時,若當前backlog為空,即在空閑狀態或隻有SP在執行,task若是MP則尾添加到backlog,若是SP則直接尾添加到taskQueue;若backlog非空即表示當前有MP事務在執行,task若是SP則尾添加到backlog,MP則尾添加到taskQueue。對於SP事務,最終調用taskQueueOffer()直接尾添加到taskQueue。對於MP事務,最終調用coordinatedTaskQueueOffer(),這裡有同步Write-MP操作(避免隻有部分任務執行)。每個Site有自己的Scoreboard跟蹤當前要執行的MP任務,同時有全局的s_stashedMpWrites跟蹤所有Site的Scoreboard。MP任務先被stash到各個Site的Scoreboard內,並將score++。當最後一個LastSite檢測到score==SiteCount(即所有Site加入MP完成),LastSite會通過s_stashedMpWrites.releaseStashedTxns()將所有Site.Scoreboard內MP尾添加到taskQueue去執行。TransactionTaskQueue在當前事務執行結束時,通過flush()將backlog中所有task重新offer()。
  • MpTransactionTaskQueue(繼承自TransactionTaskQueue)。含有1個taskQueue、1個backlog、MpRoSitePool、以及currentWrites/currentReads(Map)跟蹤當前執行MP。offer(task)時,所有MP都先尾添加到backlog。然後從backlog頭取出task,若是連續的Read-MP,則交由MpRoSitePool執行。若是Write-MP,則隻有當前沒有MP時才加入到taskQueue執行,否則留在backlog內。可看出Write-MP與Read-MP處理是互斥。MpTransactionTaskQueue在當前事務結束時,調用flush()重新offer()。

Catalog

  • Catalog為樹形結構,類似/cluster/databases/database/table/columns。可通過catalog commands來描述,形如 [add ref collection name, set ref fieldname value, ref = path | guid]。其中$PREV指上1個路徑減少每行大小。
  • 每個子節點類型為CatalogType,包含path、children、fields等。 Statement/PlanFragment/Cluster/Database/Table/Column/Index等都繼承自CatalogType。

SQL Parse

  • 使用embedded-memory-mode HSQLDB將SQL語句解析為xml格式。

QueryPlan

  • 左為SP,右為MP。翻譯成可執行計劃時已經知道是否是SP還是MP事務。
  • SP事務的可執行計劃隻有“ONE”部分,沒有“ALL”部分。
  • MP事務的可執行計劃有“ONE”與“ALL”2個部分。
  • MP事務可看成是Map-Reduce任務。“ALL”部分即為Map任務,對應於每個Partition上Partitial-MP事務操作。“ONE”即為Reduce任務,對應於aggregate操作。
  • CompiledPlan是由PlanNode組成的樹結構,PlanNode包含ChildrenPlanNodes與InlinePlanNodes。

Storage

    SP時序圖

    • 1個典型的SP有在Site中執行時,主要有3步驟:[handleIv2InitiateTaskMessage, SpProcedureTask.run, handleIv2InitiateResponseMessage],其中SpProcedureTask.run會調用ExecutionEngine操作數據。
    • 存儲過程與AdHoc都是1種SpProcedureTask。
    • Site在handleIv2InitiateTaskMessage時記錄command-log記錄TransactionTask。
    • SP開始時要setUndoToken(),事務完成要releaseUndoToken()/undoUndoToken()。

    MP時序圖

    • MP可看成2pc模式。Prepare即是Map-Reduce過程,Map為執行FragmentTask,Reduce為BorrowTask(MpSite借給某個Site來做),最後commit。註意MpSite發送完commit消息後即完成MP,不會接收Site commit完成確認的回包。Map-Reduce過程在MP內可能有多次,隻有收到commit消息才代表MP事務結束。
    • 每個FragmentTask,BorrowTask可看成1個SP執行過程,期間都會setUndoToken(),但隻有收到commit消息才releaseUndoToken()/undoUndoToken()。
    • MpSite在handleIv2InitiateTaskMessage時記錄command-log。其餘Site在handleFragmentTaskMessage記錄command-log。

    參考

    赞(0)