riak_kv

n this, the number of siblings an object can have on disk, assuming all merge operations happen at the client, is potentially unbounded if you never ever read, and only ever write. When implemented on the server, we can ensure that we perform this merge operation during both the read and write cycle, keeping the sibling count down to one and reducing the amount of state we need to ship to the client. * In addition, we use the coordinating node (really, a combination of virtual node and partition index) of the write as the "participant" or "actor" for the operation. This is not to be confused with actor model based languages. This allows us to have better control over actor growth; when dealing with clients all writing to CRDTs, every single particpant needs to have a unique actor id. Recall, that most of the CRDTs track actor counts, for instance the G-Counter which is structurally equivalent to a vector clock, although semantically different. This introduces a problem of garbage collection. Interval tree clocks, is one such solution for addressing the problem, but can not be used as the basis for some CRDTs. [4] * Finally, there is work underway in making state-based CRDTs more efficient through "delta-CRDTs" [5], which allow for a more efficient optimistic and anti-entropy repair mechanism. While the most notable resource for exploring CRDTs continues to be the comprehensive report by Shapiro, et al, [6] in practice many of the data structures outlined here have unbounded growth in garbage (specifically referring to items such as the OR set, which tracks an object for every operation performed). Therefore, we rely on some of the more optimized representations which don’t accumulate garbage. [7] In addition, the conflict-free, composable, replicated map structure, which is provided by Riak 2.0 was specifically invented by Basho, and it is the first of its kind. [8] It took many hours and iterations on QuickCheck models to ensure that, given somewhat arbitrary composition, that merge operations happened correctly. This is why there has been interest in exploring alternative ways of checking or building these models. [9] By storing these CRDTs at the server-side, we also are able to provide a operation-based interface for interacting with these objects from all of our clients, and leave the complexity of implementing the CRDTs out of the client. This additionally allows for our search offering, Yokozuna, to be able to index these data types and provide query over their values. [1] https://github.com/basho/riak_kv/pull/746 [2] https://github.com/basho/riak_core/pull/463 [3] http://basho.com/counters-in-riak-1-4/ [4] http://gsd.di.uminho.pt/members/cbm/ps/itc2008.pdf [5] https://twitter.com/xmal/status/467331615535149059 [6] http://hal.inria.fr/inria-00555588 [7] http://arxiv.org/abs/1210.3368 [8] http://dl.acm.org/citation.cfm?id=2596633 [9] http://arxiv.org/abs/1406.4291 * Edited to fix citation formatting.