Diamond: Automating data management and storage for wide-area, reactive applications Zhang et al., OSDI 2016
Diamond tackles the end-to-end problem of building reactive applications, defined here as those that update end-user visible state without requiring any explicit user action:
… today’s popular applications are reactive: they provide users with the illusion of continuous synchronization across their device without requiring them to explicitly save, reload, and exchange shared data.
Such applications have widely distributed processes sharing data across mobile devices, desktops, and cloud services. They make concurrent updates, may stop or fail at any time, and can be connected by slow or unreliable links. Distributed storage systems on their own don’t provide a complete solution since programmers still need to synchronize updates between application processes and distributed storage.
I didn’t see it in the related work section, but for me SwiftCloud is another very interesting system that extends transactions all the way to the application / mobile client (although it doesn’t emphasize the reactive nature in the same way as Diamond).
Diamond aims to simplify development of such applications by combining a client-side library of reactive data types with a CRDT-aware data structure server (cf. Riak), push notifications, and client-side transaction support.
- A reactive data map (rmap) primitive lets applications create reactive data types and map them into the Diamond data management service
- Reactive transactions automatically (re-)execute in response to shared data updates (push notifications)
- A data-type aware form of optimistic concurrency control (DOCC) leverages the semantics of the supported data types to better cope with wide-area latencies (e.g., by concurrently committing transactions executing commutative operations).
In case you were under any illusion that building such end-to-end reactive applications while maintaining safety was easy, §2 in a paper does a good job of explaining otherwise. I’m going to jump straight to the description of Diamond itself.
System and data model
Diamond processes run on client device and on cloud servers. Every process is linked with a client-side library libdiamond, which provides access to the shared Diamond cloud. Front-end servers are scalable stateless nodes providing clients with access to Diamond’s back-end storage, saving them from having to authenticate with or track the partitioning scheme of the back-end servers. Back-end storage servers themselves use Viewstamped Replication for fault tolerance.
Diamond supports reactive data types for fine-grained synchronization, efficient concurrency control, and persistence. As with popular data structure stores such as Redis and Riak, we found that simple data types are general enough to support a wide range of application and provide the necessary semantics to enable commutativity and avoid false sharing…. In addition to primitive data types, Diamond support simple Conflict-Free Replicated Data Types (CRDTs) and collection types with efficient type-specific interfaces.
A Diamond instance provides a set of tables, where a table is simply a key -> data type map. Diamond maps its data types into application memory space through an operation called rmap. “Applications call rmap with an application variable and a key to the Diamond record, giving them control over what data in their address space is shared and how it is organized.”
Transaction model and implementation
Diamond supports both traditional style (application initiated) read-write transactions, and reactive transactions. A reactive transaction is essentially a state-change callback that runs inside a transaction and is triggered by a push notification from the Diamond ‘cloud.’ Reactive transaction may read, but not write, reactive data items.
Reactive transactions help application processes automatically propagate changes made to reactive data types. Each time a read-write transaction modifies an rmapped variable in a reactive transaction’s read set, the reactive transaction re-executes, propagating changes to derived local variables. As a result, reactive transactions provide a “live” view that gives the illusion of reactivity while maintaining an imperative programming style comfortable to application programmers. Further, because they read a consistent snapshot of rmapped data, reactive transactions avoid application-level bugs common to reactive programming models [48].
Diamond’s transaction protocol is similar to Spanner’s, but uses DOCC instead of a locking mechanism, and commit timestamps from a timestamp service rather than TrueTime.
When a read-write transaction commits, one or more reactive transactions may need to be executed:
- The leader in the partition sends a publish request with the transaction’s commit timestamp to each front-end subscribed to the related record
- For each publish, the front-end server looks up the reactive transactions that have the updated record in their read sets and checks if the commit timestamp is bigger than the last notification sent to that client.
- If so, the front-end server sends a notify request to the client with the commit timestamp and the reactive transaction id
- The client logs the notification on receipt, updates its latest known timestamp, and re-executes the reactive transaction at the commit timestamp.
How does the front-end server know which reactive transactions will have the updated record in their read-set? When a reactive transaction is first registered by a client, libdiamond executes it immediately with the most recent data and records the reads that the transaction makes. This also means that push notifications can be made efficient as they can contain the data the reactive transaction is most likely to request.
The discussion affords the fact that the read-set of a reactive transaction may change over time. If a reactive transaction doesn’t have all of the data it wants to read pushed to it, it can always fetch it (and the read set will be updated for future go-rounds). What’s not clear is how the front-end server would know to notify a client at all for some data that changes but the client has never requested before. My best guess is that it’s up to the client to make sure it reads everything it might want to be notified about on that first run after registration.
Reactive transactions in Diamond are similar to database triggers, events, and materialized views. They differ from these mechanisms because they modify local application state and execute application code rather than database queries that update storage state. Diamond’s design draws on Thialfi; however, Thialfi cannot efficiently support data push notifications without insight into the application’s access patterns.
The Data-type (specific) Optimistic Concurrency Control mechanism (DOCC) uses fine-grained concurrency control based on the semantics of the different reactive data types. For example, allowing concurrent updates to different list elements. There’s an (implicit) assumption baked in here though that there are no integrity constraints that need to be maintained across such elements. DOCC also makes use of CRDT properties when these types are used.
The Diamond guarantee (100% satisfaction or your money back 😉 )
The Diamond guarantee is described as “ACID+R” and promises:
- Atomicity – all or no updates to shared records in a r/w transaction succeed
- Consistency – accesses in all transactions reflect a consistent view of shared records [Strongly consistent??]
- Isolation – accesses in all transactions reflect a global ordering of committed read-write transactions
- Durability – updates to shared records in commited r/w transactions are never lost
- Reactivity – accesses to modified records in registered reactive transactions will eventually re-execute.
Diamond supports configurable isolation levels:
Evaluation
The team compared non-Diamond and Diamond-based versions of a number of reactive applications including ‘the 100 game,’ a chat room, a multiplayer scrabble game, and a twitter-clone.
In addition to simplifying the design and programming of reactive apps, we found that Diamond facilitates the creation of general-purpose reactive libraries. As one example, Diamond transactions naturally lend themselves to managing UI elements. For instance, a check box usually maps a Boolean, re-draws a UI element in a reactive transaction, and writes to the Boolean in a read-write transaction when the user checks/unchecks the box.
General findings when rewriting reactive apps to use Diamond include an elimination of bugs, and reduction in code size by around 30%. Performance evaluations show a low overhead in read-committed mode, through to a throughput reduction of about 50% when using strict serializability.
