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

Opaque No More: Riak's New Data Types

Opaque No More: Riak's New Data Types

Since the beginning, Riak has been a plain-Jane key-value store that pretty much didn't care what you stored in it.

That changed for the first time in Riak 1.4, when we introduced a new convergent data type, the counter, exposing operations other than just "set" and "get".

We're going even further for Riak 2.0 by adding more convergent datatypes, a whole new API for accessing them from client applications, and garbage collection to keep them tight and small.

Sean Cribbs

October 22, 2013
Tweet

More Decks by Sean Cribbs

Other Decks in Programming

Transcript

  1. “You’ve got to give the people what they want.” Ben

    Folds, “Rock Star” Photo by BERKLEE COLLEGE OF MUSIC
  2. Counters increment Actor who receives operation adds to its count

    (same for decrements) [ Actor → (Increments, Decrements) ]
  3. ORSWOT add Increment Version Vector Merge updated Dot with the

    Element’s Dots Version Vector ⊠ [ Element → [ Dot ] ]
  4. Merging ORSWOTs Element in both: merge dots Element differs: Drop

    if Dots dominated by other Version Vector Keep otherwise Merge Version Vector Version Vector ⊠ [ Element → [ Dot ] ]
  5. ORSWOTs Size: O(Actors + Elements) About 165× SMALLER! 3> orset_bm:start(10000,

    riak_dt_orset). Results are {99,3464858} in 9051.647 ok 4> orset_bm:start(10000, riak_dt_orswot). Results are {99,21005} in 7206.505 ok 5> 3464858 / 21005. 164.95396334206143
  6. Maps update Apply type-specific update to ValueCRDT Increment Version Vector

    Insert Dot into value’s Dot list Version Vector ⊠ [ (Name, ValueType) → ([Dot], ValueCRDT) ]
  7. Maps add Like update, but insert the “bottom” / empty

    value if not present Version Vector ⊠ [ (Name, ValueType) → ([Dot], ValueCRDT) ]
  8. Maps remove Like ORSWOT remove, drop the key-value pair Version

    Vector ⊠ [ (Name, ValueType) → ([Dot], ValueCRDT) ]
  9. Maps merge Field in both: Merge Dots, merge Values Field

    in only one: Drop when dominated by other Version Vector Keep otherwise
  10. Lazy Consensus (Epoch, GLBSet, CommittedSet, GLB) 1a. Increment Epoch (one

    replica) 1b. Compute intersection into GLB, add self to GLBSet 2. When all are present in GLBSet, add self to CommittedSet 3. When all are present in CommittedSet, everyone collects
  11. Lazy Consensus Problems: - Have to keep GC info until

    committed (grows!) - Who should the participants be?
  12. Client API Requires a Bucket Type with ‘datatype’ = map

    | set | counter ‘allow_mult’=true Manual right now, will be easier soon.
  13. Client Operations %% Fetch {ok, DataType} = riakc_pb_socket:fetch_type(Pid, {Type, Bucket},

    Key). %% Update riakc_pb_socket:update_type(Pid, {Type, Bucket}, Key, Op). %% Modify riakc_pb_socket:modify_type(Pid, Fun, {Type, Bucket}, Key, Options).
  14. Client CRDT Behavior -callback new() -> datatype(). -callback new(Value::term(), context())

    -> datatype(). -callback value(datatype()) -> term(). -callback dirty_value(datatype()) -> term(). -callback to_op(datatype()) -> update(term()). -callback is_type(datatype()) -> boolean(). -callback type() -> typename().
  15. Client Counters %% Create one Counter = riakc_counter:new(), %% Increment

    / Decrement Counter1 = riakc_counter:increment(Counter), Counter2 = riakc_counter:decrement(5, Counter), %% Values 0 = riakc_counter:value(Counter2), %% Immutable -4 = riakc_counter:dirty_value(Counter2), %% Extract op Op = riakc_counter:to_op(Counter2).
  16. Client Sets %% Create Set = riakc_set:new(), %% Add /

    remove Set1 = riakc_set:add_element(<<"sean">>, Set), Set2 = riakc_set:del_element(<<"russell">>, Set1), %% Values [] = riakc_set:value(Set2), [<<"sean">>] = riakc_set:dirty_value(Set2), %% Extract op Op = riakc_set:to_op(Set2).
  17. Client Maps %% Create Map = riakc_map:new(), %% Add /

    remove fields Map1 = riakc_map:add({<<"emails">>, set}, Map), Map2 = riakc_map:erase({<<"id">>, register}, Map1), %% Update fields Map3 = riakc_map:update({<<"confirmed">>, flag}, fun riakc_flag:enable/1, Map2), %% Values [] = riakc_map:value(Map3), [{{<<"confirmed">>, flag}, true}, {{<<"emails">>, set}, []}] = riakc_map:dirty_value(Map3).
  18. The Context If you’re going to remove, fetch first to

    get the context - Empty fallbacks - Missing elements to be removed Additions/modifications don’t need context!
  19. SyncFree INRIA, Universidade Nova de Lisboa, Université Catholique de Louvain,

    Koç Üniversitesi, Technische Universität Kaiserslautern, Basho, Rovio, Trifork European FP7 project 609551 SyncFree http://syncfree.lip6.fr/ (2013-2016)