3 ms·

> I'm curious to know what the actual data structure is. This tweet from Rich provides the missing puzzle pieces: "The log is not a btree - used for durabilit

> I'm curious to know what the actual data structure is. This tweet from Rich provides the missing puzzle pieces: "The log is not a btree - used for durability, not query. Separate indexes combine memory with batch-updated storage." https://twitter.com/richhickey/status/420910382538948608 https://twitter.com/richhickey/status/420910382538948608 Restating in my own words: The transaction log is essentially just a stream of asserts and retracts with metadata. That's used for durability first and echoed to clients/peers and the indexing engine. The indexing engine asynchronously batch updates indexes (which probably are b-trees, but have no need to be streaming append-only style in this context). The peers query a joined dataset of the latest consistent indexes plus the set of unindexed transactions. > As append-only B tree is persistent. You're right, it can be. However, the popular append-only b-tree systems (such as CouchDB) are actually append-only B+-tree systems. That "+" means the leaves of the tree are intrusively linked together, and so are not persistent. You can not "fork" such trees cheaply. > losing information is a specific feature that was added to git http://blog.datomic.com/2013/05/excision.html http://blog.datomic.com/2013/05/excision.html

taeric 12y ago
This doesn't really answer any missing piece. The contention is precisely what is used for query. Specifically, "how long before a write/assert is able to be queried?" Otherwise, it might as well not have happened. Right? Going further, you want fast queries on recent data. At this point, structures that build updateable indexes as fast as possible are going to be preferred. And you are likely looking at some form of b-tree for this. (Not necessarily, true. But likely.) Excision is neat, but not necessarily the same thing. In git, if I do a shallow copy, I do not know that it was shallow. It literally gives me wrong information on who authored parts of code at this point. And again, the point there is that it is a pragmatic feature, not necessarily a technical/ideal one.
- Tuna-Fish 12y ago
  > Specifically, "how long before a write/assert is able to be queried?" Otherwise, it might as well not have happened. Right? Immediately. The approach used is to have a separate "long-term" data structure and a smaller short term one. The long-term structure is only batch updated periodically, while the short-term logs changes since last batch. Every access queries both.
  - taeric 12y ago
    So now we are back to "what is the data structure?" Or is it non-indexed and therefore has slower queries? Because that appears to be what is implied. And this doesn't even get in to the questions such as at what point is a record eligible to be in my query. When I ran my query, or when I iterated to where that record would be? Is this controllable? And seriously, just answering "immediately" is very close to saying "by magic." Too close, for this old timer's preference. I have a ton of respect for the stack. More so for those making it.
    - t__crayford 12y ago
      It's a B-tree alike, with a fixed depth of 3, built on top of cached (at the query layer), immutable storage. There's a "atom" stored in consistent storage (and in memory on all processes), with a UUID pointer to the immutable tree. The root of the immutable tree contains pointers to "directories", which are the second layer. The third layer contains the actual data, in chunks of ~1k facts per segment. All of the immutable tree is stored in riak/dynamo/cassandra/postgres or whatever (it's just binary blob storage by k/v, so it's pretty easy to implement). There are several indexes that are in different orders, all of them covering indexes. The transaction log also goes into a tree, but that tree is structured rather differently (for performance reasons). For example, it maintains a "linked-list" (in storage!) of the latest N transactions, which it then rolls up into one tree node once that list gets to a certain size. The missing part about how transactions are available "immediately" (which is a word that doesn't make sense for a distributed database ;), is that the transactor (which is a separate process/system from those that answer questions), streams new transactions (as they happen) to the query boxes (known as "peers"). A peer is just your usual client process: for example your Java frontend webserver process (at this time only JVM clients are properly supported in this model) Indexing is done in the background every ~33mb of transaction data (in the transactor) (and it allows that to build up during new indexing jobs, applying back pressure if it gets too much in memory data). Indexing isn't append only at all - it creates a new tree (that very often shares a lot of data with the old tree, however). To answer queries, the "peers" merge the new transactions they've received (that are in memory), with the durable index. That's how new transactions get seen quickly - the peers have recent data in memory, and other data in long term durable storage. Transactions are visible as soon as the transactor's streaming sends them to peers. There is also a mechanism to say "wait until this transaction has arrived at this peer" before querying. Because the data in the indexes is immutable, it's trivial to cache in the client processes. Many smaller databases can fit entirely in memory, in which case querying only hits main memory, not the network on the peer process, which makes them (potentially) many orders of magnitude faster than querying a traditional RDBMS).
hyc_symas 12y ago
The defining characteristic of a B+tree is that interior nodes only store keys, not values. The "+" does not mean that leaves are linked together - they may be but that's not a requirement. LMDB is a B+tree but it doesn't link leaf pages together. http://en.wikipedia.org/wiki/B-tree http://en.wikipedia.org/wiki/B-tree

taeric 12y ago

This doesn't really answer any missing piece. The contention is precisely what is used for query. Specifically, "how long before a write/assert is able to be queried?" Otherwise, it might as well not have happened. Right? Going further, you want fast queries on recent data. At this point, structures that build updateable indexes as fast as possible are going to be preferred. And you are likely looking at some form of b-tree for this. (Not necessarily, true. But likely.) Excision is neat, but not necessarily the same thing. In git, if I do a shallow copy, I do not know that it was shallow. It literally gives me wrong information on who authored parts of code at this point. And again, the point there is that it is a pragmatic feature, not necessarily a technical/ideal one.

Tuna-Fish 12y ago
> Specifically, "how long before a write/assert is able to be queried?" Otherwise, it might as well not have happened. Right? Immediately. The approach used is to have a separate "long-term" data structure and a smaller short term one. The long-term structure is only batch updated periodically, while the short-term logs changes since last batch. Every access queries both.
- taeric 12y ago
  So now we are back to "what is the data structure?" Or is it non-indexed and therefore has slower queries? Because that appears to be what is implied. And this doesn't even get in to the questions such as at what point is a record eligible to be in my query. When I ran my query, or when I iterated to where that record would be? Is this controllable? And seriously, just answering "immediately" is very close to saying "by magic." Too close, for this old timer's preference. I have a ton of respect for the stack. More so for those making it.
  - t__crayford 12y ago
    It's a B-tree alike, with a fixed depth of 3, built on top of cached (at the query layer), immutable storage. There's a "atom" stored in consistent storage (and in memory on all processes), with a UUID pointer to the immutable tree. The root of the immutable tree contains pointers to "directories", which are the second layer. The third layer contains the actual data, in chunks of ~1k facts per segment. All of the immutable tree is stored in riak/dynamo/cassandra/postgres or whatever (it's just binary blob storage by k/v, so it's pretty easy to implement). There are several indexes that are in different orders, all of them covering indexes. The transaction log also goes into a tree, but that tree is structured rather differently (for performance reasons). For example, it maintains a "linked-list" (in storage!) of the latest N transactions, which it then rolls up into one tree node once that list gets to a certain size. The missing part about how transactions are available "immediately" (which is a word that doesn't make sense for a distributed database ;), is that the transactor (which is a separate process/system from those that answer questions), streams new transactions (as they happen) to the query boxes (known as "peers"). A peer is just your usual client process: for example your Java frontend webserver process (at this time only JVM clients are properly supported in this model) Indexing is done in the background every ~33mb of transaction data (in the transactor) (and it allows that to build up during new indexing jobs, applying back pressure if it gets too much in memory data). Indexing isn't append only at all - it creates a new tree (that very often shares a lot of data with the old tree, however). To answer queries, the "peers" merge the new transactions they've received (that are in memory), with the durable index. That's how new transactions get seen quickly - the peers have recent data in memory, and other data in long term durable storage. Transactions are visible as soon as the transactor's streaming sends them to peers. There is also a mechanism to say "wait until this transaction has arrived at this peer" before querying. Because the data in the indexes is immutable, it's trivial to cache in the client processes. Many smaller databases can fit entirely in memory, in which case querying only hits main memory, not the network on the peer process, which makes them (potentially) many orders of magnitude faster than querying a traditional RDBMS).

hyc_symas 12y ago

The defining characteristic of a B+tree is that interior nodes only store keys, not values. The "+" does not mean that leaves are linked together - they may be but that's not a requirement. LMDB is a B+tree but it doesn't link leaf pages together. http://en.wikipedia.org/wiki/B-tree http://en.wikipedia.org/wiki/B-tree