Upgrade to Pro — share decks privately, control downloads, hide ads and more …

Notes on Eventual Consistency

Sponsored · Ship Features Fearlessly Turn features on and off without deploys. Used by thousands of Ruby developers. →
UENISHI Kota
December 11, 2014

Notes on Eventual Consistency

結果整合性などの復習

UENISHI Kota

December 11, 2014

Transcript

32 slides
  1. ࣗݾ঺հ • @kuenishi • Github, Twitter, etc • ෼ࢄγεςϜྺ6೥ •

    Bashoδϟύϯͷํ͔Βདྷ·ͨ͠ • Riak CSͷ։ൃ • ͦͷଞ೔ຊͷ͜ͱ • msgpack-erlang ϝϯςφ
  2. CAP Theorem • Consistent: ෳ਺ͷAtomic Objectʹର͢Δ ࿈ଓͨ͠ૢ࡞ (w1, w3, w4,

    ….) ͕શͯಉҰ Ͱ͋Δ͜ͱ (linearizable) • Available: Atomic Objectʹૢ࡞ w1, w2, …Λ࣮ߦͯ͠Ϩεϙϯε͕ಘΒΕΔ͜ͱ • Partition Tolerant: ૹͬͨϝοηʔδ͕૕ ࣦͯ͠΋ਖ਼͍͠ʢatomicʣͳϨεϙϯε͕ ಘΒΕΔ͜ͱ G1 G2 write read Gilbert and Lynch, Brewer’s Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services
  3. ͳͥڧ੔߹ੑͷ࣮ݱ͕೉͍͠ͷ͔ • ଟ਺ܾͱ͔ atomic broadcast Λ࢖͏ͱͯ͠΋ύ ϑΥʔϚϯεͷϖφϧςΟ͕͋Δ • asynchrony +

    partial failureͷ೉͠͞ • ࢮ׆؂ࢹ is hard => Downtime • ӡ༻ੑ • ੾Γସ͑ɺ੾Γ໭͠ɺ༳Ε·͢༳Ε·͢
  4. Read Repair v2 v2 get(“conferences/thoughtworks”) Get Handler (FSM) client Riak

    Coordinating node Cluster 6 7 8 9 10 11 12 13 14 15 16 R=2 v1 v2 v2 v1 v2 v1 v1 v2 v2
  5. Active Anti Entropy • APࢦ޲ͷDBͷσʔλྼԽΛ๷͙ ͨΊͷόοΫάϥ΢ϯυॲཧ • Merkle-TreeΛ࢖ͬͯύʔςΟγϣ ϯຖͷʮνΣοΫαϜʯΛܭࢉ •

    ࠩ෼Λݟ͚ͭͨΒͦ͜ΛRead Repair͢Δ hash(vnode=0, pid=0) hash(vnode=1, pid=0) hash(vnode=2, pid=0)
  6. CRDT • ॱ൪͕ೖΕସΘͬͯ΋݁Ռ͕มΘΒͳ͍ܕ • update(w1, update(w2, Data0) = update(w2, update(w1,

    Data0) = Data w1 w1 w1 w2 w2 w2 Actor 0 Actor 1 Actor 2 w1(w2(Data0)) => Data w1(w2(Data0)) => Data w2(w1(Data0)) => Data
  7. CRDT: PN-Counter • merge • {a: {1,-1}, b: {1,0}, c:

    {2,0}} • {a: {0,0}, b: {2, 0}, c: {0, -2}} • => {a: {1,-1}, b:{2,0}, c:{2,-2}} => 2 • update • a͕ {increment, 3} Λड͚෇͚Δͱ • {a: {4,-1}, b: {1,0}, c: {2,0}}
  8. CRDT: OR-Sets • merge • {a:{“foo”:true}, b:{“bar”:false}} • + {a:{“foo”:true},

    b:{“foo”:false, “bar”:false}} • => {a:{“foo”:true}, b:{“foo”:false, “bar”:true}} • => [“bar”] • update • add: {a:{}} => +”foo” => {a:{“foo”:false}} • remove: {a: {“foo”:false}} => {a: {“foo”:true}}

More Decks by UENISHI Kota

Other Decks in Technology