跳到主要内容

Conflict-free Replicated Data Types - An Overview

TL;DR​

  • 主要for weak consistency (eventual consistent)
  • 必須要保證invariant 被滿足
  • 通常要求exactly-once，不然就是CRTD本身要idempotent

Semantics​

  1. 必須定義happens-before
  2. 某些semantic 會用到 total order (ex: Last Wrtite Win, LWW)

Counter​

icr或dec的順序不會造成結果差異，所以可以不用考慮，但如果要支援write，有兩種semantics可以考慮：

  • icr和dec必須happens-afterwrite才計算
  • icr和dec跟write concurrent就計算

Set​

主要有三種semantics:

  • Add-wins
  • Remove-wins
  • Last-writer-wins (LWW)

List / Sequence​

支援的操作是insert(i, v)和pop(i)，因為執行的順序會影響結果，所以需要total order。

Map​

不考慮nested，只需要考慮單純的put(k,v)換rmv(k)的話，semantics類似set。

如果考慮nested的情況，有以下幾種semantics:

  • Remove-as-recursive-reset: 把rmv(k)視為把k的data reset為zero value，缺點是不容易知道原本就是空值，或是removed。
  • Remove-wins
  • Update-wins

要注意的事情​

  • Large object可以考慮分解成較小的object，然後用reference來組合

System Devloper 要注意的事情​

  • State-based 或是 Operation-based (operation要不要aggregated)