This disclosure describes the application of LSM trees as a primitive data structure to provide a file-like Application Programming Interface (API). The LSM tree data structure is used to implement an object store. Namespace features, such as support for directories, can be layered on top of objects to form a hierarchy of object stores, with a root object store connected to an arbitrary number of child object stores that store user directories and files. Since the tree stores deltas on objects, it can contain multiple entries per object ID. However, within a given layer of the tree, there can be at most one entry for a given key within the object. The filesystem achieves performance by writing mutations to a fast in-memory layer, which is flushed at appropriate times to minimize latency caused by disk write operations. Moreover, the use of a journal can help minimize data loss from unflushed write operations in the event of sudden loss of power.
Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 License.
Suter, Chris and Sullivan, James, "Filesystem API based on Log Structured Merge (LSM) Trees", Technical Disclosure Commons, (November 01, 2021)