跳到主要内容

Viewstamped Replication

Full Title​

Viewstamped Replication: A New Primary Copy Method to Support Highly-Available Distributed Systems

Motivation

提出一個high performance的replication 演算法。

Characteristics​

  • leader based (只有primary 可以處理請求)
  • 盡量不使用permanent storage (狀態靠整個cluster來存，只要majority有記住狀態，就recoverable)
  • 用viewstamp來當logcial clock，搭配leader based，所以可以做到total order

terminology​

  1. primary: primary負責處理請求。
  2. cohort: 又稱為backup負責做replication。
  3. view: 所有在同一個group的node形成一個view，view裡面有primary和cohort。

Running Transactions​

Cohort Data Structure​

每個cohort會保存自身以下的變數:

  • status: active、view_manager或是underling
  • gstate: <uid: int, base: T, lockers: {lock-info}>
  • cur_viewed: 目前的 view id
  • cur_view: 目前的view
  • history: 目前經歷過的 viewstamps (viewstamp = <id: view_id, ts: int>)

Primary buffer​

Primary會keep一個buffer，buffer類似FIFO的queue，event進到buffer裡面就會同步給其他backup，只要有majority (包含primary)同步到，就可以保證這個event不會在view change的時候lost。

Processing at the Active Primary of a Client​

starting​

產生 transaction id和一個空的pset(pset裡面存的是)。

Making a remote call​

  1. Client查一下cache server的資訊，如果不對就更新cache。然後send request到primary，
  2. Client如果收到reply message，把reply message放到pset。
  3. 如果沒得到reply message，就abort transaction。
  4. 如果reply message內容是view changed，client primary就嘗試更新cache，如果真的落後太多就abort transaction。

Coordinator for two-phase commit​

  1. coordinator 送 prepare message到其他的participants，裡面有transaction id 和pset。
  2. 如果所有的participants都agree commit，就釋放locks並且put <"commiting", plist, aid> record到buffer，並且取得新的viewstamp，然後等到viewstamp同步到participants，就做commit(過程類似前面)。
  3. 如果沒有得到回應就更新cache和重試，如果失敗太多次或是view落後太多就abort transaction。

Processing at the Active Primary of a Server​

Processing a call​

  1. 如果送過來request的view id比現在的view id 還前面，就拒絕請求並且回復目前的view id和view。
  2. 產生一個empty pset，然後跑RPC相對應的邏輯。
  3. 當RPC流程結束，放一筆<"completed-call", object-list, aid>記錄到buffer，object-list包含RPC用到的object和lock type，並且回覆pset和viewstamp給client。

Processing a Prepare Message​

  1. 如果送過來的message可以處理，處理到此message的viewstamp，然後release local locks並回覆prepared，如果此request是read only會順便新增一筆<"commited", aid> record到buffer。
  2. 如果message不能處理，就拒絕request並abort transaction，並增加一筆<"abort", aid> record到buffer。

Processing a Commit Message​

  1. Release local locks並且更新資料和版本，然後新增一筆<"commited", aid> record到buffer。

Processing an Abort Message​

  1. Discard locks和version，然後新增一筆<"aborted", aid> record到buffer。

Queries​

Cohort可以去詢問其他Cohort當下的狀況，如果被詢問的Cohort知道答案就回答，增快整體的performance。

View Change​

State of a Cohort​

image info

View Change Algorithm​

image info