WIP: Add disk based cache.

[ChillFish8]

Description

Closes #1761

This PR adds the start of a disk-based LRU cache. And has the following structure and behaviour:

• The core disk handling is detached from the main LRU logic, via the Store<D> struct.
• The LRU logic is largely copied over from the memory implementation but with some adjustments made to the eviction behaviour (notably the LRU state is reset to its original state if it turns out we don't want to evict any files. )
• Files are checked when the cache is opened and their checksums checked.
• The maximum number of file descriptors can be adjusted, the higher the number the more open files will be kept in an LRU cache rather than having to open and close different files when a request comes in.

Durability

Durability is a best-effort type system, focussing more on a reactive system than the pre-active system. I.e. The store will attempt to write all the data and flush it to the disk. However, it does not employ something like a write-ahead log to guarantee that the file will be saved correctly to the disk in the event of a sudden shutdown/power outage. Instead, the following solution is employed to prevent a corrupted state:

• File access (read, write) is logged to a file using fixed-length rows as part of a background writer thread, so as to not negatively affect performance too much.
• The log will batch sudden influxes of events up, write the changes to disk, and then flush afterwards. Waiting for the next event(s).
• The log itself is effectively an array of 'slots' where each slot contains the metadata for a single file (slot_checksum, file_key, file_checksum, file_length).
• These slots by themselves are small enough to where the OS should be able to write the data atomically to disk anyway, however, in the case a partial write does occur due to a power outage or the likes. The system walks through the log, checking each 'slots' checksum. If the checksums do not align, the slot is marked as 'free' so that it can be overwritten in future. Only the files that have correct checksums and are not marked as empty are added to the list of valid files. The cache will then purge any files which are not marked as valid or have invalid checksums, thus preventing any leaking of files or invalid states from being left over.

Current Limitations

• Unix only support.
• LRU wrapper is not currently tested within quickwit itself.
• FileKeys are currently only calculated as the crc32 hash of the file path -> this could lead to conflicts which we don't want, and this probably wants to change. (In prototyping I use a metro or city hash rather than crc32)
• Writing slices to a given file can potentially cause some less than ideal behaviour if you then attempt to read a slice of a file which hasn't necessarily been written to entirely as the OS will pad the file with intermediate 0s should the write range lie outside of the file length. TL;DR:
  • Writing files using write_all, or writing incrementally without exceeding the current file_length 👍
  • Writing files using write_range starting from a random point of the file and then reading a range from the start 👎

How was this PR tested?

Due to the WIP nature of this PR testing is limited to unit testing. Which in itself is slightly WIP still.

Testing covers:

• FileBackedDirectory handling of data.
• Access log standard functionality, durability and corruption recovery.

[CLAassistant]

All committers have signed the CLA.

[fulmicoton]

Cool work! I like the idea of the access log with fixed-size entries and a freelist. It is not-so-common solution and I think this is a good fit here.

A markdown document in the directory describing the overall logic would be really useful. Right now I had to look at the implementation to understand the logic.

Something describing roughly

• the read path
• the write path
• file cleanup
• what happens if there is a collision.

would have been helpful.