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

A New Concept of Consistency in Distributed Dat...

UENISHI Kota
November 28, 2013

A New Concept of Consistency in Distributed Database and Implementation in Riak

Web+DB forum 技術報告 by Basho

UENISHI Kota

November 28, 2013
Tweet

More Decks by UENISHI Kota

Other Decks in Technology

Transcript

  1. Consistent Hashing • 160-bit Ωʔۭؒ • ۭؒΛ౳෼͢Δ • ύʔςΟγϣϯ͸ϊʔ υ͕ݸผ؅ཧ

    • ϨϓϦΧ͸Nݸͷύʔ ςΟγϣϯʹίϐʔ͞ ΕΔ OPEF OPEF OPEF OPEF hash(“meetups/spamham”) N=3
  2. ౴͑: CRDT •ʮෳ੡ՄೳͳՄ׵σʔλܕʯ •Conflict-Free Replicated Data Types •Commutative Replicated Data

    Types •… •(Going to be included in Riak 2.0) ஫) CRDTͷ࡞ऀ͸Logical Monotinicy ͱ͍͏ݴ༿͸࢖͍ͬͯͳ͍
  3. 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}}
  4. 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}}
  5. Ϣʔεέʔε •ΫϦοΫ਺ͷΧ΢ϯτ (G-counter) • riak-server/types/counters/buckets/likes/datatypes/basho.com -d 1 •γϣοϐϯάΧʔτ (OR-sets) •ϩάΠϯϢʔβʔ਺

    (PN-counter) •͜ΕΒͷ૊Έ߹Θͤ (map & LWW-register, boolean) •{ name : “basho.com”, likes: 20000, users: 3000, links: [ “basho.co.jp”, “basho.co.uk” ], cool: true }