NEWS for larch ============== These are the release notes for larch, a Python implementation of a copy-on-write B-tree, designed by Ohad Rodeh. Version 1.20151025 ------------------ * Test suite improvement: fsck tests by Antoine Brenner. * Debian packaging improvements. Version 1.20131130 ------------------ * Serious bug fixed: the "KeyError" crash for reference counts. This was false memory use optimisation, which triggered a rare bug in related code. Repeatable test case by Rob Kendrick, and helpful analysis by Itamar Turing-Trauring. * Serious bug fixed: another "node missing" bug. This crash was caused by a bug that overwrote on-disk reference count groups with zeroes. Repeatable test case by Rob Kendrick. * Fixes to fsck from Antoine Brenner. Version 1.20130808 ------------------ * Bug fix in how Larch handles partly-comitted B-tree journals in read-only mode. Previously, this would result in a crash if, say, a node had been removed, but the B-tree metadata hadn't been committed. Recipe for reproducing bug found by Damien Couroussé. Version 1.20130316 ------------------ * Fsck now check for missing nodes, and optionally fixes them by deleting references to them. * Node numbers are now reported in hexadecimal, to make it easier to find on disk. Patch by Damien Couroussé. * The `speed-test` script now works again. The initialiser API for `NodeStore` and `NodeStoreMemory` now have a new first argument, `allow_writes`, to make them compatible with the `NodeStoreDisk` initialiser. Patch by Antoine Brenner. * Improved error messages for nodes that seem to be missing. Version 1.20121216 ------------------ * Make fsck progress reporting be a bit more fine grained. Version 1.20121006 ------------------ * Critical bug fix: an indentation problem in the Python code was fixed. A line was intended wrong, resulting it to not be included in the right block, and therefore not having access to the variable created in that block. * Bug fix: The Debian packaging was missing a build dependency on cmdtest. Version 1.20120527, released 2012-05-27 --------------------------------------- * New version scheme. Thank you, Joey Hess. * The on-disk data structures and file formats are now declared frozen. An automatic test has been added to verify that things do not break. Version 0.31, released 2012-05-08 --------------------------------- * Optimize journal use to have fewer round-trips. This matters when the journal is stored on a high-latency storage, such as an SFTP server. * Now handles better missing key or node sizes in the metadata. * All exceptions thrown by larch are now subclasses of `larch.Error`. * The on-disk format is now frozen. Version 0.30, released 2012-04-29 --------------------------------- * `NodeStoreDisk` is now explicitly in read-only or read-write mode. In read-only mode it does not replay or rollback to the journal, or care about any changes made there. Version 0.29, released 2012-04-15 --------------------------------- * Larch now uses the `larch.FormatProblem´ exception when an on-disk node store is missing a format version, or has the wrong version. This helps Obnam print a better error message. Version 0.28, released 2012-03-25 --------------------------------- * Changes to on-disk storage are now done via a journal data structure to protect against corruption from crashing. Previously, if a program using Larch crashed during an unfortunate moment, the on-disk state would not be consistent: some nodes might have been removed, for example, but other nodes or the list of root nodes still referred to them. This is now fixed. The on-disk data format version has not changed: the on-disk format is compatible with old versions of larch, as long as there are no uncommitted changes from a new version. The API has changed, however, and it is now necessary for Larch users to call the `Forest.commit` method to force changes to be stored on disk. Failure to do so will cause changes to be lost, and many annoyed bug reports. Version 0.27, released 2012-02-18 --------------------------------- * Merged in some fsck `WorkItem` changes from Obnam, so that Obnam can share the code. Version 0.26, released 2011-12-18 --------------------------------- * `open_forest` now works even if the requested node size is different from the node size used with an existing tree. The requested size is just ignored, rather than causing an error. This is useful for, say, Obnam, when the user decides to change the node size setting, or when Obnam's default node size for a tree grows. This way, things work. Version 0.25, released 2011-10-02 --------------------------------- * `fsck` can now optionally attempt to fix B-trees with missing nodes. The index nodes referring to the missing nodes get adjusted to drop the reference. Version 0.24, released 2011-09-17 --------------------------------- * Debian packaging install the fsck-larch manual page. Version 0.23, released 2011-08-19 --------------------------------- * The default size of the LRU cache used by NodeStoreDisk is not 500 instead of 100. This provides much better performance with large trees: 37% vs 99% cache hit rates with speed-test for 100k keys. * The `BTree.lookup_range` method now returns a list, not a generator. It turned out to be very surprising to return a generator, especially with the documentation saying a list was returned. (Thanks, Jo Shields, for the bug report.) Version 0.22, released 2011-08-03 --------------------------------- * The library now declares which on-disk format it supports, so that B-trees stored with an incompatible format can be detected. * `fsck-larch` now has a `--trace` option, and the library has a bit more tracing statements. Version 0.21, released 2011-08-02 --------------------------------- * Better error messages from `fsck-larch`. * Bug fix: `fsck-larch` no longer reports as missing nodes that aren't in use by all B-trees in a forest. * `fsck-larch` now has a manual page. * More `tracing.trace` statements to make it easier to track when nodes are created and destroyed. * B-tree nodes are now stored in a more efficient way on disk (several levels of directories, not just one). This is a compatibility breaker: old B-trees aren't readable with new larch, and B-trees created with the new larch aren't readable by old larch. * A couple of memory leaks fixed: both were caches that grew effectively without bounds. * Least-Recently-Used caches now log their hit/miss statistics explicitly. Previous this was done in the `__del__` method, but those did not get called deterministically, so the logging did not always happen. Version 0.20, released 2011-07-20 --------------------------------- * `pydoc larch` should now work better. * Changes to larch benchmarking scripts (to make them use cliapp). * `fsck-larch` improvements: - now uses cliapp, for better usability - now automatically detects a forest's key and node sizes, so the user no longer needs to give them manually. - some more checks - installed as part of the Debian package * API documentation with Sphinx. As part of that, the API was cleaned up a bit with regards to public and private methods (the latter being prefixed by underscores now). * The separate LRU cache implementation is now included in larch, to avoid yet another dependency, and to avoid polluting PyPI. * Various speedups. * `BTree.count_range` method added, for speed. * Library version number is now `larch.__version__` instead of `larch.version`, to follow Python conventions. Version 0.19, released 2011-03-21 --------------------------------- * The `NodeStoreDisk` class now uses a separate VFS class for I/O, rather than methods in `NodeStoreDisk` itself, and requiring subclassing with method overrides. A separate VFS class is clearer and simpler to use. As a bonus, the API is now compatible with the Obnam VFS API. * Forest metadata now includes key and node sizes, and there's a factory function that checks that the sizes given to it match the existing ones. This should reduce potential errors. * Renamed from btree to larch, to avoid name clashes with other projects. Version 0.18, released 2011-02-18 --------------------------------- * Fix memory leak. Version 0.17, released 2011-02-13 --------------------------------- * Use the python-tracing library to add logging of node creation and removal and other operations. The library makes it possible for the user to enable and disable logging for specific code modules, and defaults to being disabled, so that the logging will not affect normal execution speed. * `codec-speed` now reports MiB/s, instead of seconds, giving an easy way to compare encoding and decoding speeds with, say, hard disk or network speeds. * B-tree now again modifies nodes, and does so by first removing them from the node store's upload queue. This returns the library back to useful speeds. Version 0.16.2, released 2011-01-07 --------------------------------- * Really fix problems with nodes growing too big while in the upload queue. The previous fixes meant well, but didn't really do the trick. Now we stop modifying nodes at all while in the upload queue, which is good for several reasons. Performance in this release degrades a lot, until there is time to optimize the code. However, correctness is more important than performance. Version 0.16.1, released 2011-01-07 --------------------------------- * Bug fix: Remove temporary node used while splitting a leaf node that has grown too large. * Bug fix: Since we do, in fact, modify nodes in-place when they are not shared between trees, it was possible for a node to be put into the node store upload queue, and later modified. This is not a problem as such, but when inserting a value into a leaf node, we modify it in place making it too large, and then create one or two new nodes. If the too-large node was at the beginning of the upload queue, creating the new node might push it out, resulting in a bug. We fix this by moving the too-large node to the end of the queue, ensuring it will not be pushed out. A cleaner solution would be to not modify the node if it will grow too big, but that change will need to wait for a later date. * BTree now checks that nodes are not too big when they are put into the node store. The node store already did the checking, but only at the point where it was ready to write the node to disk, and that meant the problem was caught at a time that was hard to debug. * BTree now sets an explicit maximum size of the values inserted into the tree: slightly less than half the size of a node. This is necessary for leaf node splitting to work correctly without requiring more than more than two nodes to hold everything. Version 0.16, released 2011-01-07 --------------------------------- * The code to split over-full leaf nodes into two is fixed. Before version 0.14 we had a problem where one of the two halves might still be too big. The code in 0.14 fixed that, but introduced a new problem where one of the new nodes would be very small. Now they should be just right. No, I have not read Goldilocks recently, why do you ask? Version 0.15, released 2011-01-02 --------------------------------- * This version replaces all use of my custom `bsearch` function with the `bisect` module in the Python standard library. This speeds up all operations, some more than others. In-memory benchmarks with ´speed-test` sped up from about 20% for `remove_range` up to 240% for `lookup`. No other changes, but I felt this warranted a release on its own. Version 0.14, released 2010-12-29 --------------------------------- This version seems to work well enough for Obnam to do backups of real systems. It is, however, not as fast as one would wish. Bug fixes: * When a tree was made shallower after a remove operation, the code used to assume the direct children of the root node would not be shared with other trees. This is obviously a wrong assumptions. I must have been distracted by XKCD when writing the code. * A bug in cloning (shadowing) nodes when doing copy-on-write was fixed. The code now increment the reference counts of an index node's children correctly. * The cached encoded size of nodes now gets cleared by `remove_index_range`. * Leaf nodes are now split based on size, not key count. Key counts are OK for index nodes, whose values are all of the same size. However, leaf node values may vary wildly. Sometimes it happens that after splitting, one of the halves is still too large. * `Forest.remove_tree` now actually removes the unshared nodes of the tree that is removed. * `BTree.remove_range` was quite fast, but not always correct. The code was just tricky enough that I was unable to find the actual fault, so I rewrote the method in a simplistic, but slow way. A speed improvement for this needs to happen in a future version. Speed improvements: * When a node is cloned, its previously computed size is now remembered. Since the clone is identical to the original node, except for the id, the size will be the same. New features and stuff: * fsck-btree: a rudimentary checker of the B-tree data structures. This will undoubtedly be improved in the future, but even the simple checking it does now has already helped when debugging things. * Some parts of the code that used to be excluded from test coverage now has tests. Now 19 statements remain that are excluded from coverage. * Some other code prettification has happened, including some docstring improvements. * `BTRee.remove_range` and `lookup_range` now check that their arguments are of the correct size of keys for that tree. * `Node` got a new method, `find_pairs`. * `BTree.dump`, which is useful for debugging, is now nicer to use. * `NodeStoreDisk` no longer forces the use of `fsync` when it writes files. It is not btree's responsibility to decide that on behalf of all users. Those who want it can subclass and override the method. * `RefcountStore` and `UploadQueue` are their own modules, and have much better test coverage now. `UploadQueue` got rewritten in terms of `LRUCache`. * New `BTree.range_is_empty` method, for those (few) cases where one just needs to know if there are any keys, and where getting all keys with `lookup_range` would be slow. * `BTree.lookup_range` is now a generator, which should reduce memory consumption and thus speed things up in cases where a very large number of keys are about to be returned. Removed stuff: * The NodeStore API no longer wants a `listdir` method. It has been removed from NodeStoreDisk. * `RefcountStore` no longer logs statistics. They did not seem to be useful. * `IndexNode` no longer explicitly checks the types of its arguments. This was wasting CPU cycles, and it did not once find an actual bug. Version 0.13, released 2010-07-13 --------------------------------- * Speed-related improvement: The size of NodeStoreDisk's LRU cache for nodes is now user-settable. Version 0.12, released 2010-07-11 --------------------------------- * Some speed optimizations. * The BTree objects no longer have a root_id attribute. Instead, use BTree.root.id (if BTree.root is not None). Version 0.11, released 2010-07-05 --------------------------------- * Now includes a small example program, written for the Wellington Python User Group meeting where the first talk about this library was given. * `NodeStoreDisk` stores nodes in a simple directory hierarchy, instead of a flat one, to better handle very large trees. * `NodeStoreDisk` now has a much larger default upload queue size (now 1024, was 64), to better handle large trees. * `speed-test` now also tests `remove` and `remove_range` methods. Further, it reports both CPU and wall clock timings, and has been refactored a bit. Results for `lookup_range` are no longer comparable with old versions, since the measured scenario has changed. * `remove_range` has been rewritten and is now much faster. Version 0.10, released 2010-06-29 --------------------------------- * Storage of node reference counts is now more efficient. * NodeStoreDisk stores reference counts and nodes in files in a subdirectory of the directory root, which is an incompatible change, so trees made by earlier versions can't be used anymore. (That's what you get for using alpha level code. Obviously, once btree is declared to be ready for production, the on-disk data structures will be supported in future versions.) * Nodes that exist in only one tree are modified in place, rather than via copy-on-write. This is impure, but brings a big speed boost. * New test script: insert-remove-test. "make check" automatically runs it. * Many optimizations to NodeCodec and elsewhere, by Richard Braakman. Version 0.9, released 2010-05-26 -------------------------------- * Several speed optimizations. * One of this requires a Least-Recently-Used cache, which is provided by my python-lru package. That is now a dependency. * NodeStoreDisk now has an upload queue. This is so that when a node gets immediately overwritten, it can be removed from the queue, i.e., removed before it gets encoded and written at all. This provides quite significant speedups. * A bug fix for reference counting of index node is fixed. This allows the speedups from the upload queue to actually occur. * On-disk node encodings have changed. Anything written by previous versions is now unusable.