Posts

Separation of concerns: Buffered file IO with OCaml

This piece of code  adds write buffering for append operations on a file, and read buffering to attempt to make repeated preads quicker. Ultimately the implementation supports (buffered) pread, pwrite and (buffered) append. I'm posting it here because I thought it nicely demonstrated separation of concerns: first we build a file which maintains its own length in memory (V2); then we add the write buffer (V3); then finally we add the read buffer (V4). Each implementation builds on the previous. But each level is reasonably self-contained and addresses the single feature at that level. Previously I tried to do this by implementing everything in a single level, but the code was considerably more complex and harder to follow. 

The Economics of Writing (Good) Code Documentation

TL;DR: Writing documentation can be beneficial even for a lone programmer writing code that will never be read by anyone else; however, the benefits, when other programmers are involved, are cumulative and potentially huge in terms of time saved (of those programmers) when trying to grok the existing codebase.  It is well known that programmers in general hate to write documentation. There are lots of reasons for this. For example, in the heat of writing code, the programmer simply cannot envisage what it would be like for someone else to come along in a couple of years and try to understand the code from scratch... And anyway, what does the programmer owe to that future person? (The programmer will likely have moved on by that point...) etc. etc. So, poor documentation (or lack of documentation altogether) is a problem that stems from the programmer, and probably left unfixed by the managers of the programmer, right up the chain of responsibility. This post isn't an attempt to add

How to safely append to a file? (Can we?)

[NOTE: this post was inspired by looking at the mirage/index code and trying to understand the properties that code provides in a crash scenario] In systems with reasonable claims to robustness in the event of system crash, the issue arises that we want to write to a file in an "atomic" way. Let's simplify by considering appending data to a file. Let's also assume that the filesystem performs blk-sized blk-aligned writes atomically (but multiple such writes may be reordered). Simplify further by assuming we only want to append a single block of data to a file at a position that is a multiple of the block size. What can go wrong?  The problem is that there are many moving parts, each of which can result in incorrectness. Here are some possibilities: We append a new block at the end of the file (at a position that is a multiple of the blk size). This should be atomic. Has the FS (filesystem) freelist correctly recorded that the block is now in use? Has the FS updated th

kv-hash, a new key-value store

At OCamlLabs/Tarides, I have been working on kv-hash ( https://github.com/tomjridge/kv-hash ), a replacement for irmin/index ( https://github.com/mirage/index ) The original index code implements a key-value store. New key-values are written first to a log, and then when the log is large it is merged into the main data store, and a new log is started. The performance is good initially, but deteriorates over time (essentially because the entire store needs to be written whenever the log is merged into the store).  kv-hash is an alternative, where the performance remains constant over time, and where the merge duration in particular is fast and constant. In our tests, this avoids various issues with off-the-shelf solutions such as LMDB, RocksDB, SQLite etc. LMDB is great, providing the active set of keys fits in memory; if it doesn't, the use of an mmap means that performance degrades quite significantly RocksDB has amazing write performance, but the relatively poor read performance

A new OCaml library: kv-lite, a Key Value store implemented on SQLite

I wrote a thin wrapper round SQLite to implement a simple Key Value store interface. The github repository is  https://github.com/tomjridge/kv-lite The bindings use Lwt for concurrency.  Performance is reasonably good: a batch set of 100k operations completes in about 1.5s. This is not as quick as mini-btree, but SQLite is probably doing a bit more here, and the layers of wrapping probably add some overhead too.

Updates to mini-btree library

Image
The mini-btree library is here:  https://github.com/tomjridge/mini-btree Recently I made some changes. Now, mmap is used throughout, and there is no use of the Lwt monad. So, the interface is somewhat simpler, and the performance is slightly improved (although the performance was already fairly good, we can now achieve about 1M inserts per second).  This work was done while employed by OCamlLabs, so many thanks to them. This library may in the future form part of the irmin/irmin-pack/index library used by Tezos.

New minimal B-tree implementation

Image
 In the last couple of days I wrote a minimal B-tree implementation (based on previous work, of course). The link is here:  https://github.com/tomjridge/mini-btree This B-tree is resistant to write reordering, that is, the block device can reorder writes, and crash, and the B-tree will still function correctly (although obviously some recent operations may not have flushed fully to disk unless you managed a sync before the crash).