Another predictably slow week chewing away on Acid bugs, although one evening in a sudden flash of violent vimmery I managed to finish three pretty complicated changes:
Previously all acid.Collection methods were hard wired to handle every possible configuration: non-batch collections without indices, non-batch collections with indices, batch collections without indices, and batch collections with indices. The result was an insane hodge-podge that was pretty impossible to test.
Now the class has been split up into backing Strategy classes, initially with just two available: BasicStrategy and BatchStrategy. BasicStrategy does little but proxy all Collection methods straight through to the storage engine, after encoding any keys, so “Collection.get((1,2,3))” is equivalent to “Engine.get(keylib.Key(1, 2, 3).to_raw(prefix))”.
On the other hand, BatchStrategy contains all the nasty batch splitting logic for handling mutations, and implements get() using a range query with the lower bound set to the requested key. While an efficient operation with py-lmdb, it seems not all ordered engines are so effective at range queries, for example an LSM tree needs an N-way merge of all live segments. So now if batch compression isn’t needed, BasicStrategy can be swapped in to make more efficient use of this style of engine.
The collection’s strategy name may now be persisted in the store’s metadata, which will eventually provide forward compatibility with future library versions, should the default strategy be changed or improved somehow.
A final interesting side effect is that it might eventually be possible, or even useful, to add a strategy that supports hashed storage engines. Obviously range queries would not be possible, but there may be great value in supporting e.g. a hashed engine for a Collection’s primary storage, with indices stored in a second, ordered engine. Clearly consistency would be difficult to guarantee there, but nonetheless it seems an interesting use case.
Strategies might also make a nice boundary for later swapping out the key encoding. I will probably never have a need for this, however it is a very desirable feature for providing exact behavioural emulation of other storage systems. Of particular interest is Google App Engine, right now the key encoding’s sort order doesn’t quite match App Engine’s, but in future this could be made configurable.
Yet another possibility is implementing a custom strategy to allow a gradual migration to Acid using an existing database. In this scenario, acid.Store could be instantiated with some prefix= set to avoid new collections from conflicting with existing keys in the store, and one magic Collection could be instantiated with a custom strategy that, say, took simple string keys, and ignored the store/collection’s prefix.
Storage engine events
Another blocker to cleaning up the Collection implementation was storage engine events: these are simply neat logical callbacks that happen at useful times to allow code to respond to mutations usefully.
With a solid set of events, many interesting primitives can be built on top of collections, without having to be hard-wired directly into the Collection logic. Now there is after_create, after_delete, and after_replace, which are sufficient at least to implement indexing. I also went ahead and added transaction-level on_commit, after_commit and after_abort.
This sounds like a relatively simple change but actually the design is fraught with treachery, since supporting events like on_create and suchlike would require any network-backed storage engine to at least make multiple round trips on the network, doubling the latency of every operation. For example, there is no way to provide on_create without first asking the networked engine if the record exists.
While waiting for the engine’s response, a race ensues between Collection.put() finally writing the new record, and another network client getting there first. Even if the race is detected, the event has already been fired and we can’t somehow magically undo the effect of any on_create listeners.
Instead events like after_create can be implemented using a standard compare-and-swap-like operation, which should require only a single network roundtrip. More ramblings about that here.
During put() or delete(), depending on which event listeners are registered, the Collection class may make use of either the Strategy’s put() or replace() method, or its delete() or pop() method. “Replace” simply means “put record and return previous”, while “Pop” means “delete record and return previous”.
If no event listeners are subscribed the simpler put()/delete() operations will be used, which better optimizes the operation for write-optimized engines, such as LevelDB (in LevelDB, a write generally requires only a log file append and an insertion into an in-memory skip list, whereas a read is always a far more complicated operation).
Now that nice events exist, all the indexing logic has been pushed into acid.Index class. Part of this involved flattening the index/collection namespace, partially to avoid needing a collection to know which indices exist for it, but also to allow a not-yet-decided mechanism to reinstantiate all Python-level objects using only metadata provided by the store (which itself will eventually be necessary to support safe/transactional schema updates).
The new layout is cool in a bunch more interesting ways: for example, it would be trivial to implement some kind of acid.CrossIndex, which would provide a single enumeration of index entries that spanned multiple underlying Collections. Another possibility is implementing aggregate functions, although I need to think a lot more about that design before writing any code.
Reviewing this post, it’s kinda shocking that last December I thought the library was bloated when it reached 500 lines of code (currently it is 2000, excluding the C extension). It’s really amazing how much functionality can be packed into a tiny space using Python, but even back then, the result was totally unsuited to use in a real world application: it couldn’t be tested or extended, and it was very much write-only code.
Comments on a postcard to @edeadlk