whio  whio_vlbm

ACHTUNG: AS OF 20110523, THIS PAGE IS NOW MAINTAINED IN THE NEW WIKI: http://whiki.wanderinghorse.net/wikis/whio/?page=whio_vlbm


Header: <wh/whio/whio_vlbm.h>

VLBM is a "Variable-Length Block Manager," with a single goal in life: provide management of atomic logical data blocks of varying sizes. This is in principal similar to what whio_udb and whio_epfs do, except that those deal with blocks of identical sizes. VLBM is intended to be a component in a database-like API which stores individual record values in their own data blocks, each sized to fit that data. This component takes over the de/re/allocation of the storage blocks. For example, VLBM handles the underlying block management for the whio_ht hashtable.

VLBM is fundamentally very similar to a memory allocator, doling out storage blocks to the caller. The primary difference is that it allocates storage space from a whio_dev object instead of directly from system memory. The "data area" of an allocated block is abstractly the same as a malloc()ed memory block, and can be read and written using several different approaches:

  • Copy the bits to/from a memory buffer (has linear memory costs).
  • Read/write using whio_stream or whio_dev objects as either the destination or source (constant memory costs).
  • Read/write using a user-supplied callback function as the destination or source (constant memory costs).

The first option is the simplest, and is suitable for small data sets or where the memory costs of keeping records in RAM are irrelevant. The latter two options make it possible to stream arbitrarily large blocks with constant memory costs (independent of the final size of the in-block data). The callback approach allows one to use custom streams for fetching/writing the block data.

VLBM itself uses very little memory - essentially only the whio_dev provided by the client (i.e. the underlying storage) and one internally-used whio_dev "subdevice" object. Simple use cases need less than 500 bytes of dynamically allocated memory.

A VLBM is created by "formatting" a whio_dev object, which writes the internal bookkeeping data to the device. After that, the device can be used to allocate blocks. The VLBM-internal data are encoded in a platform-neutral manner, and will work across different computing environments (e.g. 32- vs. 64-bit, or big- vs. little-endian).

When VLBM allocates a block for the caller, it gives the caller a ID back, and that ID is used to later reference the block. Just like a memory allocator, if you forget the ID of a block then it gets "orphaned", which is just like a memory leak but it leaks storage space instead of RAM. Such leaked storage stays leaked as long as the VLBM container storage is kept intact. If it is re-initialized then the orphaned blocks (along with any non-orphaned blocks) are reaped and their storage made available for re-allocation.

Unlike a memory allocator, the VLBM marshalls access to the data via its own API, as opposed to direct memory access, and will not allow a client to overwrite/overread a block's boundaries.

VLBM currently has no way to shrink its size. When blocks are deallocated, they are added to a "free-list" and will be re-used for future allocations (provided they are big enough). However, it is currently not possible to actually shrink the size of the underlying database. Even if we could do it, we shouldn't because clients are responsible for storing the IDs somewhere (if needed), and shrinking the VLBM might require moving blocks around (which changes their IDs, since a block's ID is actually its offset within the parent storage). Just an idea: we could provide an approach which takes a callback from the client, and that callback would be called to tell the client the new and old block ID when a block gets moved. In any case, this feature is very low-priority.