The Architecture of Datomic
Datomic is a new database designed as a composition of simple services. It strives to strike a balance between the capabilities of the traditional RDBMS and the elastic scalability of the new generation of redundant distributed storage systems.
Datomic seeks to accomplish the following goals:
- Provide for a sound information model, eschewing update-in-place
- Leverage redundant, scalable storage systems
- Provide ACID transactions and consistency
- Enable declarative data programming in applications
Any database system needs to have a point of view about the data model it supports. Traditional RDBMS support the relational model combined with some sort of world-update semantic. On the opposite end of the spectrum, some of the new NoSQL systems know little or nothing of the information they contain, simply storing blobs at keys, with eventual consistency. Datomic considers a database to be an information system, where information is a set of facts, and facts are things that have happened. Since one can't change the past, this implies that the database accumulates facts, rather than updates places, and that while the past may be forgotten, it is immutable. Thus if someone 'changes' their address, Datomic stores the fact that they have a new address without replacing the old fact (it has simply been retracted as of this point in time). This immutability leads to many important architectural benefits and opportunities.
Many great strides have been made in defining highly available, redundant, distributed and scalable storage systems, such as Amazon's Dynamo. In moving away from a monolithic design, Datomic seeks to support these systems directly, offering users their choice of storage system, location, cost and scalability characteristics.
ACID transactions are quite important to many business processes. While much has been made of the difficulty of scaling ACID, as we'll see, Datomic separates transactions from read/query, and in doing so maximizes the throughput of the transactional component. That said, there is a definite tradeoff here, one that Datomic makes in favor of ACID transactions instead of unlimited write scalability, and targets domains where that tradeoff is appropriate. Consistency is a greatly simplifying characteristic of systems, leading to more robust solutions, and shouldn't be discarded without good reason. (There are, sometimes, good reasons, but make sure they apply to you!).
Traditional RDBMS provide powerful logical, declarative and set-oriented language for manipulating data. Unfortunately, that power is trapped in servers, and once the data reaches the application, too often vanishes in a sea of nested for loops and imperative manipulation. Datomic provides what is fundamentally a distributed index, and allows the declarative query component to reside in the application server tier. This query engine can manipulate both Datomic-hosted data and in-memory data sources, providing for a consistent, high-level approach.
There are many concepts that pervade the Datomic architecture, among them:
Simplicity and composition. The system should comprise a set of services each of which does one thing well, and knows little or nothing about the others. Where well-regarded, simple components already exist in a particular domain, such as storage or caching, they should be integrable.
Scalability and elasticity of storage and query. If you need more storage or query capability, you should be able to dynamically add machines, and if less, remove them, without preconfiguration.
Location flexibility. The components should not care where the other components reside.
Pervasive immutability. Programming using update-in-place is an idea whose time has passed. Most programming should be done with immutable values. In Datomic, even the database itself can be treated as a value.
Data as interface. The system should be programmable. In order to be so, the primary interfaces should be data-driven, not syntax-laden strings. In Datomic, schema, transactions, queries and query results are all defined in terms of ordinary data structures such as lists and maps.
Datomic comprises the following services:
- Transaction coordination and notification
- Application data model and query
The capabilities required of storage are minimal - primarily storage of small (< 64k) blobs. Storage is used by the system much in the same way a file system might be used by a traditional database - for log and index segments. These segments are immutable. In addition, a small set of keys are used as references to the log and index roots. These are the only mutable use of storage, and require the storage system to provide consistent write/read, and, at present, conditional or versioned put.
All additions of information to the database take the form of submissions of novelty to the transaction coordinator. The coordinator serializes all transactions, and ensures ACID semantics, placing the new information in log segments in storage. Upon durable storage, the coordinator notifies the transaction submitter and any connected parties of the new information resulting from the transaction.
The second use of storage, the index, is actually several sets of the database data, sorted in various orders, represented as trees of segments. Periodically, the indexing service incorporates new information from the logs in storage into these sorted sets. Since the index segments are immutable, the indexing process always creates a new index tree, that tree sharing structure with the prior index tree as much as possible.
Datomic presents to the application server tier a view of the database as if it was a value in memory. This database value provides a view of the database as a graph of entities and their attributes. In addition, the database object provides direct iterable access to the indexes themselves. Finally, the database value can serve as an argument to a declarative query. In order to present what appears to be a 'current' view of the database, the database object must merge the most recent index with an in-memory index of the novelty that has occurred since the last durable index was produced.
Datomic also provides to the application server an embedded query engine which can operate upon the database values, as well as in-memory collections.
Caching is fully integrated into the Datomic model. Unlike the typical scenario, where caching is an application-level problem, used to cache query results in an effort to ease the load on servers, Datomic manages caches itself, and caches the index segments themselves, in order to bring them into memory from storage, or into the application process. This ability to cache 'under' the queries derives from the fact that index segments are immutable, and query is distributed.
The logical model maps in a straightforward way to the physical model, with independent subsystems for most services.
- Storage services
Perhaps surprisingly, Datomic is not in the business of disks. Instead, it integrates with a wide variety of storage servers and systems, as long as they satisfy the minimal requirements mentioned previously. Examples of supported storages are:
- In-process memory (no storage). Datomic can run completely in memory, in-process, which is great for development and testing.
- SQL. Any JDBC-compliant SQL database can serve as storage.
- Key/value stores. Next-generation distributed, redundant key/value stores such as Amazon's DynamoDB are a great fit for Datomic.
- Memory grids. Distributed data grids such as Infinispan can be used when redundant memory is sufficiently durable.
The result of this 'servicification' of storage is a tremendous amount of flexibility. Note also that in many cases (e.g. SQL and Infinispan), Datomic need not have a dedicated storage resource. You can have Datomic use an existing SQL server by simply adding a single table. When used with a highly-scalable storage such as DynamoDB, Datomic acquires the same elastic read scalability. This is another benefit of the component-based architecture - read and write scaling become orthogonal decisions, with different tradeoffs.
Datomic encapsulates the differences between storages, and operates identically on all of them. You can move a system from one storage to another by a simple export/import to/from an S3 bucket or local directory, and change your app from one storage to another with a few property file changes and a different URI.
- the Transactor
The transactor is a process dedicated to transaction coordination. It accepts persistent connections from application server peers. Over these connections it accepts transactions, serializes them, commits log segments to storage, and broadcasts novelty to all connected peers. Currently, indexing also runs as a background process on the transactor. The transactor can be made highly available by running a second transactor as a standby. Since storage is shared truth, no dedicated connections are required between the active transactor and the standby. The transactor does not have any storage of its own, and does not service any read or query load. Thus, there is far less contention for it vs a monolithic model. That said, Datomic is not the right choice when you require unlimited write scalability.
- the Peer library
The database value code, connectivity code, memory index and query engine are provided in a JVM library called the 'peer' library, since application servers running this library are fully empowered equals. This library presents a Java API suitable for use by Java, Clojure, Scala, JRuby, Groovy and all other JVM languages. Each peer has direct (read-only) access to storage. The peer also contains the top-level cache of index segments, in which the segments have been fully expanded into JVM objects.
Programming at the peer level feels categorically different from client-server database programming. While peers are not full replicas, they quickly cache their working sets, and the database feels like an object in memory. This is not a veneer, as is provided by an ORM. Furthermore, query is local. Thus, rather than queries running within the context of a database, databases become arguments to queries. Queries can take more than one database, and/or a combination of database and ordinary collections.
Datomic comes with a Datalog query engine. Datalog is an easy-to-learn, pattern oriented query language well suited to Datomic's data model and programmatic collections. It is set-oriented and relational, like SQL. There is a sense in which even the query engine is orthogonal though, as the direct index access provided supports the use of other query languages. For instance, Clojure users are able to use Clojure's Prolog-like core.logic library to query Datomic as well.
All of this application interaction happens through a data-driven API with an extremely small surface area.
Datomic can automatically utilize a memcache cluster as second-tier cache between the in-process peer cache and storage. As described above, this is a cache 'under' query, of index segments. Because they are immutable, and are the source of answers, rather than specific answers, there is tremendous leverage in caching index segments, with none of the normal complexity of caching, i.e. cache coherence, invalidation etc. The transactor can be configured to prefill memcache as it writes to storage, so even the first reads will result in cache hits. This can add a level of scalability and performance not otherwise present in the base storage (e.g. if it is a single-instance SQL server). As with storage, Datomic doesn't need a dedicated memcache cluster. It uses UUID-based keys that will not conflict with other use of the same cache.
The REST API and clients
Datomic comes with a REST component that turns a process running the peer library into an HTTP service supporting the Datomic API. This can be used for non-JVM languages, or for lighter-weight clients that don't need the full in-process capabilities of the peer. The REST service is completely discoverable and self-describing via the text/html media type. Applications will generally request the application/edn media type, which supports data transmission in the edn format.
Clients of the REST API lose very few of the benefits of sharing the process with the database cache, and otherwise retain the important characteristics of the model - programming with data, queries can cross data sources, or incorporate program data, and independent queries can act upon the same basis, without any transaction, due to the fact that particular database values can have permalinks.
Clients pass and receive the exact same data structures as do peer API callers, with an isomorphic interface. This says less about the REST API than it does about the peer API - programming with data is a good idea, on the wire or off.
I hope this has given you a feel for the nature of Datomic's architecture and some of its details. If nothing else, it provides many examples of the architectural value of immutability. Databases as compositions of services, such as Datomic, are likely to become more common as we move away from the limitations of monolithic architectures while trying to retain their capabilities, and reach for new ones.
There are many more aspects of Datomic, including the information model, the reification of process, the database as a value, the query model and time model, all of which are synergistic with the architecture. You can learn more from the Datomic documentation.
About the Author
Rich Hickey, the author of Clojure and designer of Datomic, is a software developer with over 25 years of experience in various domains. Rich has worked on scheduling systems, broadcast automation, audio analysis and fingerprinting, database design, yield management, exit poll systems, and machine listening, in a variety of languages.
Confused about Storage and Add only philosohy
Delivering Performance Under Schedule and Resource Pressure: Lessons Learned at Google and Microsoft
Ivan Filho Mar 06, 2014