22

✏️ Editing: storage.txt

Storage system notes
--------------------

extstore.h defines the API.

extstore_write() is a synchronous call which memcpy's the input buffer into a
write buffer for an active page. A failure is not usually a hard failure, but
indicates caller can try again another time. IE: it might be busy freeing
pages or assigning new ones.

As of this writing the write() implementation doesn't have an internal loop,
so it can give spurious failures (good for testing integration)

extstore_read() is an asynchronous call which takes a stack of IO objects and
adds it to the end of a queue. It then signals the IO thread to run. Once an
IO stack is submitted the caller must not touch the submitted objects anymore
(they are relinked internally).

extstore_delete() is a synchronous call which informs the storage engine an
item has been removed from that page. It's important to call this as items are
actively deleted or passively reaped due to TTL expiration. This allows the
engine to intelligently reclaim pages.

The IO threads execute each object in turn (or in bulk of running in the
future libaio mode).

Callbacks are issued from the IO threads. It's thus important to keep
processing to a minimum. Callbacks may be issued out of order, and it is the
caller's responsibility to know when its stack has been fully processed so it
may reclaim the memory.

With DIRECT_IO support, buffers submitted for read/write will need to be
aligned with posix_memalign() or similar.

Buckets
-------

During extstore_init(), a number of active buckets is specified. Pages are
handled overall as a global pool, but writes can be redirected to specific
active pages.

This allows a lot of flexibility, ie:

1) an idea of "high TTL" and "low TTL" being two buckets. TTL < 86400
goes into bucket 0, rest into bucket 1. Co-locating low TTL items means
those pages can reach zero objects and free up more easily.

2) Extended: "low TTL" is one bucket, and then one bucket per slab class.
If TTL's are low, mixed sized objects can go together as they are likely to
expire before cycling out of flash (depending on workload, of course).
For higher TTL items, pages are stored on chunk barriers. This means less
space is wasted as items should fit nearly exactly into write buffers and
pages. It also means you can blindly read items back if the system wants to
free a page and we can indicate to the caller somehow which pages are up for
probation. ie; issue a read against page 3 version 1 for byte range 0->1MB,
then chunk and look up objects. Then read next 1MB chunk/etc. If there's
anything we want to keep, pull it back into RAM before pages is freed.

Pages are assigned into buckets on demand, so if you make 30 but use 1 there
will only be a single active page with write buffers.

Memcached integration
---------------------

With the POC: items.c's lru_maintainer_thread calls writes to storage if all
memory has been allocated out to slab classes, and there is less than an
amount of memory free. Original objects are swapped with items marked with
ITEM_HDR flag. an ITEM_HDR contains copies of the original key and most of the
header data. The ITEM_data() section of an ITEM_HDR object contains (item_hdr
*), which describes enough information to retrieve the original object from
storage.

To get best performance is important that reads can be deeply pipelined.
As much processing as possible is done ahead of time, IO's are submitted, and
once IO's are done processing a minimal amount of code is executed before
transmit() is possible. This should amortize the amount of latency incurred by
hopping threads and waiting on IO.

Recaching
---------

If a header is hit twice overall, and the second time within ~60s of the first
time, it will have a chance of getting recached. "recache_rate" is a simple
"counter % rate == 0" check. Setting to 1000 means one out of every 1000
instances of an item being hit twice within ~60s it will be recached into
memory. Very hot items will get pulled out of storage relatively quickly.

Compaction
----------

A target fragmentation limit is set: "0.9", meaning "run compactions if pages
exist which have less than 90% of their bytes used".

This value is slewed based on the number of free pages in the system, and
activates when half of the pages used. The percentage of free pages is
multiplied against the target fragmentation limit, ie:
limit of 0.9: 50% of pages free -> 0.9 * 0.5 -> 0.45%. If a page is 64
megabytes, pages with less than 28.8 megabytes used would be targeted for
compaction. If 0 pges are free, anything less than 90% used is targeted, which
means it has to rewrite 10 pages to free one page.

In memcached's integration, a second bucket is used for objects rewritten via
the compactor. Potentially objects around long enough to get compacted might
continue to stick around, so co-locating them could reduce fragmentation work.

If an exclusive lock is made on a valid object header, the flash locations are
rewritten directly in the object. As of this writing, if an object header is
busy for some reason, the write is dropped (COW needs to be implemented). This
is an unlikely scenario however.

Objects are read back along the boundaries of a write buffer. If an 8 meg
write buffer is used, 8 megs are read back at once and iterated for objects.

This needs a fair amount of tuning, possibly more throttling. It will still
evict pages if the compactor gets behind.

TODO
----

Sharing my broad TODO items into here. While doing the work they get split up
more into local notes. Adding this so others can follow along:

(a bunch of the TODO has been completed and removed)
- O_DIRECT support
- libaio support (requires O_DIRECT)
- JBOD support (not in first pass)
  - 1-2 active pages per device. potentially dedicated IO threads per device.
    with a RAID setup you risk any individual disk doing a GC pause stalling
    all writes. could also simply rotate devices on a per-bucket basis.

on memcached end:
- O_DIRECT support; mostly memalign pages, but also making chunks grow
  aligned to sector sizes once they are >= a single sector.
- specify storage size by MB/G/T/etc instead of page count

MR SKB