In the fall of 2019, a long-awaited event occurred in the Cloud team at Mail.ru for iOS. The primary database for persistent application state storage became a rather exotic choice for the mobile world. (LMDB). Below, you will find a detailed overview presented in four parts. First, we will discuss the reasons for such an unusual and difficult choice. Then we will examine the three foundations of the LMDB architecture: memory-mapped files, B+-tree, and the copy-on-write approach for implementing transactionality and multi-versioning. Finally, we will delve into the practical part. It will cover how to design and implement a schema with multiple tables on top of the low-level key-value API, including indexing.
Content
3.1.
3.2.
3.3.
4.1.
4.2.
4.3.
1. Motivation for Implementation
Once, around 2015, we became concerned about monitoring how often our application's interface lagged. We embarked on this not without reason. Complaints had increased that the application would sometimes stop responding to user actions: buttons would not press, lists would not scroll, etc. I was at AvitoTech, so here I will just provide the order of magnitude.
The results of the measurements were a cold shower for us. It turned out that the problems caused by lags were far more numerous than any others. Before realizing this fact, our main technical quality indicator was crash-free performance, but after, our focus to freeze-free.
Having built and conducted and analysis of their causes, it became clear who the main enemy was — the heavy business logic running in the main application thread. The natural reaction to this disorder was a strong desire to distribute it across worker threads. To systematically solve this problem, we resorted to a multi-threaded architecture based on lightweight actors. I dedicated on the collective Twitter and In the context of the current narrative, I would like to emphasize those aspects of the solution that influenced the choice of database.
The actor model of organizing the system suggests that multithreading becomes its second essence. Objects in this model tend to cross thread boundaries. They do this not occasionally or in some places, but practically all the time and everywhere.
The database is one of the cornerstones of the presented scheme. Its primary task is to implement the macro pattern . If in the enterprise world it is used to organize data synchronization between services, in the case of an actor architecture — it is for data between threads. Thus, we needed a database whose operation in a multithreaded environment presents no even minimal challenges. In particular, this means that the objects obtained from it should be at least thread-safe, and ideally immutable. As is known, the latter can be simultaneously used from multiple threads without resorting to any locks, which positively affects performance.
The second significant factor that influenced the choice of database was our cloud API. It was inspired by the synchronization approach adopted in git. Like it, we aimed at , which seems quite appropriate for cloud clients. It was assumed that they would only download the full state of the cloud once, and then synchronization in the overwhelming majority of cases would occur through the application of changes. Unfortunately, this capability is still only in the theoretical zone, and in practice, clients have yet to learn to work with patches. There are several objective reasons for this, which, to avoid prolonging the introduction, we will leave aside. At present, however, the more significant interest lies in the instructive outcome of the lesson about what happens when the API says 'A,' but its consumer does not say 'B.'
So, if you imagine git, which, when executing the pull command, instead of applying patches to a local snapshot, compares its complete state with the server's complete state, you will have a fairly accurate idea of how synchronization occurs in cloud clients. It’s not hard to guess that to accomplish this, you need to allocate two DOM trees in memory with metadata about all server and local files. This means that if a user stores 500 thousand files in the cloud, synchronizing them requires recreating and destroying two trees with 1 million nodes. And each node is an aggregate containing a graph of sub-objects. In this light, the profiling results were expected. It turned out that even without accounting for the merge algorithms, the procedure of creating and subsequently destroying a huge number of small objects is already quite costly. The situation is exacerbated by the fact that the basic synchronization operation is included in a large number of user scenarios. As a result, we fix the second important criterion in choosing a database — the ability to implement CRUD operations without dynamic allocation of objects.
Other requirements are more traditional, and the complete list looks as follows.
- Thread safety.
- Multiprocessing. This is driven by the desire to use the same database instance for synchronizing the state not only between threads but also between the main application and iOS extensions.
- The ability to represent stored entities as immutable objects.
- No dynamic allocations within CRUD operations.
- Support for the basic properties of transactions : atomicity, consistency, isolation, and durability.
- Speed in the most popular cases.
A good choice with such a set of requirements was and remains SQLite. However, in the course of exploring alternatives, I came across a book Under her leadership, a benchmark was created comparing the speed of different databases in real cloud scenarios. The result exceeded the wildest expectations. In the most popular cases—retrieving a cursor on a sorted list of all files and a sorted list of all files for a given directory—LMDB proved to be 10 times faster than SQLite. The choice became obvious.
2. Positioning of LMDB
LMDB is a very small library (only 10K lines) that implements the foundational layer of databases—storage.
The presented diagram shows that comparing LMDB with SQLite, which also implements higher levels, is essentially no more accurate than comparing SQLite with Core Data. To fairly compare as equal competitors, one should reference similar storage engines—BerkeleyDB, LevelDB, Sophia, RocksDB, etc. There are even developments where LMDB acts as a storage engine component for SQLite. The first such experiment was conducted in 2012. the author of LMDB . were so intriguing that his initiative was picked up by OSS enthusiasts and continued in the form of In January 2020, the author of this project, Den Shearer, it at LinuxConfAu.
LMDB primarily finds its application as an engine for application databases. The library owes its existence to the developers of , who were quite dissatisfied with BerkeleyDB as a basis for their project. Building upon the modest library , Howard Chu was able to create one of the most popular alternatives today. He dedicated a very impressive talk to this history and the internal structure of LMDB. A good example of conquering storage was shared by Leonid Yuryev (aka ) from Positive Technologies in his talk at Highload 2015 . In it, he discusses LMDB in the context of a similar task of implementing ReOpenLDAP, and LevelDB was subjected to comparative criticism. As a result of the implementation, Positive Technologies even developed an actively evolving fork with very appealing features, optimizations, and .
LMDB is often used as a storage as is. For example, the Mozilla Firefox browser it for a number of needs, and starting from version 9, Xcode it over SQLite for storing indexes.
The engine has made its mark in the world of mobile development. Its usage can be in the iOS client for Telegram. LinkedIn has gone even further, selecting LMDB as the default storage for its homegrown data caching framework, Rocket Data, which was in its article in 2016.
LMDB is successfully fighting for a place in the sun in the niche left by BerkeleyDB after its transition under Oracle’s control. The library is favored for its speed and reliability, even compared to similar solutions. As they say, there are no free lunches, and it is essential to emphasize the trade-off that one will encounter when choosing between LMDB and SQLite. The diagram above clearly illustrates how increased speed is achieved. First, we do not incur costs for additional layers of abstraction over the disk storage. Obviously, in a good architecture, it is still necessary, and they will inevitably appear in the application code, however, they will be much thinner. They will lack features that are not needed by a specific application, such as support for SQL queries. Secondly, there is an opportunity to optimally implement the mapping of application operations to queries to the disk storage. While SQLite based on the average needs of a typical application, you as an application developer are well aware of the primary workload scenarios. A more efficient solution will come at an increased cost for both the initial development of the solution and its subsequent support.
3. The Three Pillars of LMDB
Looking at LMDB from a bird's eye view, it's time to dive deeper. The following three sections will address the main pillars upon which the storage architecture rests:
- Memory-mapped files as a mechanism for working with the disk and synchronizing internal data structures.
- B+-tree as the organization of the stored data structure.
- Copy-on-write as an approach to ensure ACID properties of transactions and multi-versioning.
3.1. Pillar #1. Memory-mapped files
The files displayed in memory are such an important architectural element that they even appear in the name of the storage. Issues of caching and synchronization of access to the stored information are entirely delegated to the operating system. LMDB does not contain any caches within itself. This is a conscious decision by the author, as reading data directly from the mapped files allows for cutting many corners in the engine implementation. Below is a far from complete list of some of them.
- Maintaining data consistency in the storage when accessed by several processes becomes the responsibility of the operating system. In the next section, this mechanism is explored in detail with illustrations.
- The absence of caches completely frees LMDB from the overhead associated with dynamic allocations. Reading data in practice involves merely setting a pointer to the correct address in virtual memory and nothing more. It sounds like a fantasy, but in the storage source code, all calls to salloc are concentrated in the storage configuration function.
- The lack of caches also means the absence of locks associated with synchronizing access to them. Readers, of which an arbitrary number can exist simultaneously, do not encounter a single mutex on their path to the data. As a result, the read speed has perfect linear scalability with the number of CPUs. In LMDB, only modifying operations are subject to synchronization. At any given moment, there can only be one writer.
- A minimum of caching and synchronization logic frees the code from extremely complex types of errors associated with operation in a multithreaded environment. At the Usenix OSDI 2014 conference, there were two interesting database studies: and . From them, one can gather information about both the unprecedented reliability of LMDB and the practically flawless implementation of ACID properties of transactions that surpasses them in SQLite.
- The minimalism of LMDB allows the machine representation of its code to be entirely placed in the CPU's L1 cache, resulting in remarkable speed characteristics.
Unfortunately, memory-mapped files in iOS are not as straightforward as one might wish. To discuss the associated disadvantages more consciously, we need to recall the general principles of how this mechanism is implemented in operating systems.
Overview of Memory-Mapped Files
The operating system associates an entity called a process with each executable application. Each process is allocated a continuous block of addresses where it places everything necessary for its operation. The lowest addresses contain sections with code and hardcoded data and resources. Above that is the growing block of dynamic address space, commonly known as the heap. It contains addresses for entities that appear during program execution. At the top is the area of memory used by the application stack, which grows and shrinks, meaning its size also has a dynamic nature. To prevent the stack and heap from colliding and interfering with each other, they are separated across different ends of the address space. Between the two dynamic sections at the top and bottom, there is a gap. The operating system uses addresses in this middle section to associate various entities with the process. In particular, it can match a continuous range of addresses with a file on the disk. Such a file is called a memory-mapped file.
The address space allocated to a process is enormous. Theoretically, the number of addresses is limited only by the size of the pointer, which is determined by the system's bitness. If physical memory were directly mapped 1-to-1 to it, the very first process would consume all the RAM, making multitasking impossible.
However, from experience, we know that modern operating systems can simultaneously execute as many processes as needed. This is possible because they only allocate a lot of memory to processes on paper, while in reality, they load into the main physical memory only that part that is currently required. Therefore, the memory associated with the process is called virtual.
The operating system organizes virtual and physical memory in the form of pages of a specific size. Once a certain page of virtual memory is requested, the operating system loads it into physical memory and establishes a correspondence between them in a special table. If there are no free slots, one of the previously loaded pages is copied to disk, and the requested one takes its place. This process, which we will return to shortly, is called swapping. The illustration below depicts the described process. Here, page A with address 0 has been loaded and placed on the main memory page with address 4. This fact is reflected in the correspondence table in cell number 0.
The history with memory-mapped files is exactly the same. Logically, they are supposedly placed continuously and entirely in the virtual address space. However, they enter physical memory page by page and only on demand. Modifications to such pages are synchronized with the file on disk. Thus, file I/O can be performed simply by working with bytes in memory—the changes will be automatically transferred by the operating system kernel to the original file.
The image below demonstrates how LMDB synchronizes its state when working with a database from different processes. By mapping the virtual memory of different processes to the same file, we effectively require the operating system to transitively synchronize certain blocks of their address spaces, which is what LMDB observes.
An important nuance is that LMDB by default modifies the data file through the system call mechanism write, while the file itself is mapped in read-only mode. This approach has two important consequences.
The first consequence is common to all operating systems. It involves adding protection against unintentional damage to the database by incorrect code. As is known, executable instructions in a process are free to access data from anywhere in its address space. At the same time, as we just recalled, mapping a file in read-write mode means that any instruction can additionally modify it. If it does this by mistake, for example, trying to overwrite an array element at a non-existent index, it could accidentally change the file mapped to that address, leading to database corruption. However, if the file is mapped in read-only mode, attempting to modify the corresponding address space will result in a program crash with a signal. SIGSEGV, and the file will remain intact.
The second consequence is specific to iOS. Neither the author nor any other sources explicitly mention it, but without it, LMDB would be unsuitable for use in this mobile operating system. The next section is dedicated to its discussion.
Characteristics of memory-mapped files in iOS
In 2018 at WWDC, there was a remarkable presentation . It explains that in iOS, all pages located in physical memory fall into one of three types: dirty, compressed, and clean.
Clean memory refers to the set of pages that can be safely evicted from physical memory. The data in them can be reloaded from their original sources as needed. Read-only memory-mapped files fall into this category. iOS is not afraid to evict mapped file pages from memory at any time, as they are guaranteed to be synchronized with the file on disk.
Dirty memory includes all modified pages, regardless of where they were originally located. In particular, memory-mapped files modified by writing to their associated virtual memory will also be classified this way. When opening LMDB with the flag MDB_WRITEMAP, after making changes to it, this can be personally confirmed.
Once an application starts to consume too much physical memory, iOS subject its dirty pages to compression. The total memory occupied by dirty and compressed pages constitutes the application's so-called memory footprint. When this reaches a certain threshold, the system daemon OOM killer comes into play and forcibly terminates the process. This is a particularity of iOS compared to desktop operating systems. Unlike them, iOS does not allow reducing the memory footprint by swapping pages from physical memory to disk. The reasons for this remain speculative. Perhaps the intensive procedure of moving pages to and from disk is too energy-consuming for mobile devices, or iOS is conserving the resource used to rewrite cells on SSDs, or maybe the designers were not satisfied with the overall system performance where everything is constantly swapped. Regardless, the fact remains.
The good news, as previously mentioned, is that LMDB does not use the mmap mechanism for updating files by default. This means that the mapped data is classified by iOS as clean memory and does not contribute to the memory footprint. This can be verified using an Xcode tool called VM Tracker. The screenshot below shows the state of the virtual memory of the iOS Cloud application during operation. At startup, it was initialized with 2 LMDB instances. The first was allowed to map its file into 1GiB of virtual memory, while the second was allocated 512MiB. Although both storage instances occupy a certain amount of resident memory, neither contributes to the dirty size.
And now for the bad news. Due to the swapping mechanism in 64-bit desktop operating systems, each process can occupy as much virtual address space as the free space on the hard drive allows for its potential swap. The replacement of swapping with compression in iOS radically reduces the theoretical maximum. Now all living processes must fit into main (i.e., RAM) memory, and anything that cannot fit is subject to forced termination. This is mentioned in the previously cited text. , and in Consequently, iOS rigidly limits the amount of memory available for allocation through mmap. Here is You can examine the empirical limits of memory volumes that can be allocated on different devices using this system call. The latest iOS smartphone models offer 2 gigabytes, while the top versions of the iPad have 4 gigabytes. In practice, of course, you have to focus on the lowest supported device models, where the situation is quite grim. Worse still, when looking at the application's memory state in VM Tracker, you may find that LMDB is far from the only contender for memory-mapped storage. Significant portions are consumed by system allocators, resource files, image processing frameworks, and other smaller predators.
Based on the experiments conducted in the Cloud, we arrived at the following compromise values for allocated LMDB memory: 384 megabytes for 32-bit devices and 768 megabytes for 64-bit devices. After this volume has been used up, any modifying operations start to return the code MDB_MAP_FULL. We observe such errors in our monitoring, but they are infrequent enough to be disregarded at this stage.
An unexpected cause of excessive memory consumption by the storage may be long-lived transactions. To understand how these two phenomena are related, we will consider the remaining two pillars of LMDB.
3.2. Pillar #2. B+-Tree
To simulate tables on top of a key-value storage, the following operations must be present in its API:
- Inserting a new element.
- Searching for an element with a specified key.
- Deleting an element.
- Iterating over key ranges in sorted order.
The simplest data structure that can easily implement all four operations is a binary search tree. Each node represents a key, dividing the entire subset of child keys into two subtrees. The left subtree contains keys that are smaller than the parent, while the right contains those that are larger. An ordered set of keys is achieved through one of the classic tree traversal methods.
Binary trees have two fundamental drawbacks that prevent them from being effective as disk data structures. Firstly, their degree of balance is unpredictable. There is a significant risk of ending up with trees where the height of different branches can vary greatly, which significantly worsens the algorithmic complexity of searching compared to expected values. Secondly, the abundance of cross-references between nodes deprives binary trees of locality in memory. Close nodes (in terms of connections) can be located on completely different pages in virtual memory. Consequently, even for a simple traversal of several adjacent nodes in the tree, it may require visiting a comparable number of pages. This poses a problem even when discussing the effectiveness of binary trees as in-memory data structures, as the constant rotation of pages in the CPU cache is an expensive endeavor. When it comes to frequently fetching pages related to nodes from disk, the situation becomes quite dire. .
B-trees, being an evolution of binary trees, address the issues mentioned in the previous paragraph. Firstly, they are self-balancing. Secondly, each of their nodes splits a set of child keys not into 2, but into M ordered subsets, where M can be quite large, on the order of several hundreds, or even thousands.
As a result:
- Each node contains a large number of already ordered keys, and the trees end up being very shallow.
- The tree acquires the property of locality in memory, as closely valued keys naturally tend to be located next to each other on the same or adjacent nodes.
- The number of intermediary nodes decreases when descending through the tree during search operations.
- The number of read target nodes decreases during range queries, as each of them already contains a large number of ordered keys.
In LMDB, one of the variations of B-tree known as B+-tree is used for data storage. The diagram above shows three types of nodes that can be present within it:
- At the top lies the root. It materializes nothing but the concept of a database within the storage. Within a single instance of LMDB, several databases can be created that share a mapped virtual address space. Each of these begins with its own root.
- At the very bottom level are the leaves. They alone contain the key-value pairs stored in the database. This is the distinctive feature of B+-trees. While a regular B-tree stores value parts in nodes at all levels, the B+-variation only does so at the bottom level. Having established this fact, we will further refer to the subtype of the tree used in LMDB simply as a B-tree.
- Between the root and the leaves, there are 0 or more technical levels with navigation nodes. Their task is to divide the sorted set of keys among the leaves.
Physically, nodes are memory blocks of a predefined length. Their size is a multiple of the memory page size in the operating system, which we discussed earlier. Below is the structure of a node. The header contains metadata, the most obvious being a checksum for our example. Next comes information about the offsets where data cells are located. The data can either be keys if we are dealing with navigation nodes, or complete key-value pairs in the case of leaves. More details about the structure of pages can be found in the work .
Having understood the internal contents of the node-pages, we will represent the B-tree of LMDB simplistically in the following way.
Pages with nodes are sequentially located on the disk. Pages with higher numbers are closer to the end of the file. The so-called meta page contains information about the offsets where the roots of all trees can be found. Upon opening an LMDB file, it scans the file page by page from end to beginning in search of a valid meta page and through it finds existing databases.
Now that we have an understanding of the logical and physical structure of data organization, we can move on to the discussion of the third pillar of LMDB. It is through this that all modifications to the storage occur transactionally and isolated from one another, endowing the database with multi-versioning property.
3.3. Pillar No. 3. Copy-on-write
Certain operations with B-trees involve making a whole series of changes to its nodes. One example is adding a new key to a node that has already reached maximum capacity. In this case, it is necessary to first split the node into two, and secondly, add a reference to the newly branched child node in its parent. This procedure is potentially very risky. If, for any reason (crash, power failure, etc.), only part of the changes from the series occur, the tree will remain in an inconsistent state.
One traditional solution for ensuring database resilience against failures is to add an additional disk data structure next to the B-tree — a transaction log, also known as a write-ahead log (WAL). It is a file that strictly records the intended operation at the end before modifying the B-tree itself. Thus, if data corruption is detected during self-diagnosis, the database consults the log to restore its integrity.
LMDB chose a different approach as a mechanism for ensuring resilience against failures called copy-on-write. Its essence is that instead of updating data on the existing page, it first completely copies it and makes all modifications in the copy.
Furthermore, in order for the updated data to be available, the reference to the now relevant node must be changed in its parent node. Since this also requires modification, it is also copied beforehand. The process continues recursively up to the root. The data on the meta-page is changed last.
If an unexpected termination of the process occurs during the update procedure, either a new meta-page will not be created, or it will not be written to disk until completion, and its checksum will be incorrect. In either case, new pages will be unreachable, while the old ones remain unaffected. This eliminates the need for LMDB to maintain a write-ahead log for data consistency. The de-facto data storage structure on disk described above simultaneously takes on this function. The absence of an explicit transaction log is one of the features of LMDB that ensures high read speeds.
The resulting structure called an append-only B-tree naturally provides transaction isolation and multi-versioning. In LMDB, each open transaction is associated with the current root of the tree. As long as the transaction is not completed, the pages linked to it will never be changed or reused for new versions of data. Thus, one can continue to work indefinitely with the exact set of data that was valid at the time of opening the transaction, even if the storage continues to be actively updated. This is the essence of multi-versioning, making LMDB an ideal data source for all of us who love. UICollectionViewBy opening a transaction, there is no need to increase the application's memory footprint by hastily loading relevant data into some in-memory structure, fearing to be left with nothing. This feature significantly distinguishes LMDB from SQLite, which cannot boast such complete isolation. If you open two transactions in the latter and delete a certain record within one of them, that same record will already be unavailable in the remaining second transaction.
The flip side of the coin is the potentially significantly higher consumption of virtual memory. The slide shows what the database structure will look like if it is modified simultaneously with 3 open read transactions looking at different versions of the database. Since LMDB cannot reuse nodes reachable from roots associated with active transactions, the storage has no choice but to place another fourth root in memory and once again clone the modifiable pages underneath it.
It is worth recalling the section on memory-mapped files. Although additional virtual memory consumption shouldn't be a major concern since it doesn't contribute to the application's memory footprint, it has been noted that iOS is quite stingy with allocation, and we can't just provide LMDB a region of 1 terabyte as we could on a server or desktop without considering this issue. If possible, we should try to keep the lifetime of transactions as short as possible.
4. Designing a Data Schema on Top of Key-Value API
We will start examining the API by looking at the basic abstractions provided by LMDB: environment and databases, keys and values, transactions and cursors.
Note on code listings
All functions in the public LMDB API return their results as error codes, but for brevity, error checks are omitted in all subsequent listings. In practice, we actually used our own C++ wrapper , where errors materialize as C++ exceptions.
As the fastest way to integrate LMDB into a project for iOS or macOS, I suggest my CocoaPod .
4.1. Basic Abstractions
Environment
Structure MDB_env is the storage for the internal state of LMDB. The family of functions prefixed with mdb_env allows you to configure some of its properties. In the simplest case, the engine initialization looks as follows.
mdb_env_create(env);
mdb_env_set_map_size(*env, 1024 * 1024 * 512);
mdb_env_open(*env, path.UTF8String, MDB_NOTLS, 0664);In the Mail.ru Cloud application, we only changed the default values for two parameters.
The first aspect is the size of the virtual address space that the storage file maps to. Unfortunately, even on the same device, specific values can vary significantly from one run to another. To account for this iOS nuance, the maximum storage size is dynamically determined. Starting from a certain value, it is continually halved until the function mdb_env_open returns a result different from ENOMEM. In theory, there is an opposite approach — to initially allocate the engine a minimal amount of memory and then, upon encountering errors, increase it. However, this path is much more challenging. The reason is that the memory reallocation procedure (remap) with the function MDB_MAP_FULLmdb_env_set_map_size invalidates all entities (cursors, transactions, keys, and values) previously obtained from the engine. Taking this turn of events into account in the code will significantly complicate it. If, however, virtual memory is crucial for you, this could be a reason to look at a fork that has advanced significantly, which among its declared features includes "automatic on-the-fly database size adjustment." The second parameter, whose default value did not suit us, regulates thread safety mechanics. Unfortunately, at least in iOS 10, there are issues with support for thread local storage. For this reason, the storage is opened in the example above with the flag
MDB_NOTLS . Additionally, it was necessary tofork , to remove variables with this attribute from it. The database represents a separate instance of the B-tree we discussed earlier. Its opening occurs within a transaction, which may initially seem a bit odd.
Databases
MDB_txn *txn; MDB_dbi dbi; mdb_txn_begin(env, NULL, MDB_RDONLY, &txn); mdb_dbi_open(txn, NULL, MDB_CREATE, &dbi); mdb_txn_abort(txn);
Indeed, a transaction in LMDB is an entity of the storage, not of a specific database. This concept allows for atomic operations on entities that reside in different databases. Theoretically, this opens up the possibility of modeling tables as separate databases, but I chose a different approach, which I describe in detail below.Keys and values
MDB_val
Structure MDB_value Models the concept of both keys and values. The storage has no notion of their semantics. To it, one is just an array of bytes of a given size. The maximum size of a key is 512 bytes.
typedef struct MDB_val {
size_t mv_size;
void *mv_data;
} MDB_val;Using a comparator, the storage organizes keys in ascending order. If you do not replace it with your own, the default one will be used, which sorts them byte by byte in lexicographic order.
Transactions
The transaction mechanism is described in detail in , so here I will briefly reiterate their key properties:
- Support for all fundamental properties : atomicity, consistency, isolation, and durability. I must note that there is a bug related to durability on macOS and iOS, which has been fixed in MDBX. More details can be found in their .
- The approach to multithreading is described by the "single writer / multiple readers" scheme. Writers block each other, but do not block readers. Readers do not block either writers or each other.
- Support for nested transactions.
- Support for multiversioning.
Multiversioning in LMDB is so good that I want to demonstrate it in action. The code below shows that each transaction works with the version of the database that was current at the time it was opened, being completely isolated from all subsequent changes. The initialization of the storage and the addition of a test record are nothing interesting, so those rituals are left under a spoiler.
Adding a test record
MDB_env *env;
MDB_dbi dbi;
MDB_txn *txn;
mdb_env_create(&env);
mdb_env_open(env, ".\/testdb", MDB_NOTLS, 0664);
mdb_txn_begin(env, NULL, 0, &txn);
mdb_dbi_open(txn, NULL, 0, &dbi);
mdb_txn_abort(txn);
char k = 'k';
MDB_val key;
key.mv_size = sizeof(k);
key.mv_data = (void *)&k;
int v = 997;
MDB_val value;
value.mv_size = sizeof(v);
value.mv_data = (void *)&v;
mdb_txn_begin(env, NULL, 0, &txn);
mdb_put(txn, dbi, &key, &value, MDB_NOOVERWRITE);
mdb_txn_commit(txn);MDB_txn *txn1, *txn2, *txn3;
MDB_val val;
// Opening 2 transactions, each of which looks at
// the version of the database with one record.
mdb_txn_begin(env, NULL, 0, &txn1); // read-write
mdb_txn_begin(env, NULL, MDB_RDONLY, &txn2); // read-only
// In the first transaction, we remove the existing record from the database.
mdb_del(txn1, dbi, &key, NULL);
// Committing the deletion.
mdb_txn_commit(txn1);
// Opening a third transaction that looks at
// the current version of the database where the record no longer exists.
mdb_txn_begin(env, NULL, MDB_RDONLY, &txn3);
// Ensuring that the record with the searched key no longer exists.
assert(mdb_get(txn3, dbi, &key, &val) == MDB_NOTFOUND);
// Ending the transaction.
mdb_txn_abort(txn3);
// Ensuring that, within the second transaction opened at the time
// the record existed in the database, it can still be found by key.
assert(mdb_get(txn2, dbi, &key, &val) == MDB_SUCCESS);
// Checking that the data received by key is not just any garbage, but valid data.
assert(*(int *)val.mv_data == 997);
// Ending the transaction working with an outdated, but consistent database.
mdb_txn_abort(txn2);I optionally recommend trying to pull off the same trick with SQLite and see what happens.
Multi-versioning brings very nice perks to the life of an iOS developer. This property allows for easy and seamless regulation of the data source's update speed for UI forms, based on user experience considerations. For example, let’s take a feature of the Mail.ru Cloud application that automatically loads content from the system media gallery. With a good connection, the client can upload several photos to the server per second. If we update UICollectionView the media content in the user's cloud after each upload, we can forget about 60 fps and smooth scrolling during this process. To prevent frequent screen updates, it's necessary to limit the data change rate at the core. UICollectionViewDataSource.
If the database does not support multiversioning and only allows working with the current active state, then to create a stable snapshot of the data over time, it is necessary to copy it either into some in-memory data structure or to a temporary table. Both approaches are costly. In the case of an in-memory store, we incur both memory costs from storing constructed objects and time costs associated with excessive ORM transformations. As for the temporary table, it is an even more expensive option, making sense only in non-trivial cases.
LMDB's multiversioning elegantly solves the problem of maintaining a stable data source. It's just a matter of opening a transaction and voilà — as long as we don't complete it, our dataset is guaranteed to be fixed. The logic of its update speed is now entirely in the hands of the presentation layer, with no significant resource overhead.
Cursors
Cursors provide a mechanism for ordered iteration over key-value pairs by traversing a B-tree. Without them, it would be impossible to effectively model the tables in the database, which we are now moving on to.
4.2. Table Modeling
The property of key ordering allows us to construct a high-level abstraction such as a table on top of basic abstractions. Let's consider this process using the example of the main table of a cloud client, which caches information about all the user's files and folders.
Table Schema
One of the common scenarios for which the structure of the table with a folder tree must be tailored is extracting all elements located within a given directory. A good data organization model for efficient queries of this kind is . To implement it on top of a key-value store, it is necessary to sort the keys of files and folders in such a way that they are grouped based on their parent directory. Additionally, to display the contents of the directory in a user-friendly Windows format (folders first, followed by files, both sorted alphabetically), corresponding additional fields must be included in the key.
The image below shows how the representation of keys in the form of a byte array can look based on the given task. It starts with the bytes containing the parent directory ID (red), followed by the type (green), and finally the name (blue). When sorted using LMDB's default comparator in lexicographical order, they are arranged as required. Sequentially iterating through the keys with the same red prefix gives us the associated values in the order they should be displayed in the user interface (to the right), without any need for additional post-processing.
Serialization of keys and values
Many methods for serializing objects have been invented. Since we had no requirement other than speed, we chose the fastest one available for ourselves — a memory dump of the space occupied by an instance of the C language structure. Thus, a directory element's key can be modeled with the following structure NodeKey.
typedef struct NodeKey {
EntityId parentId;
uint8_t type;
uint8_t nameBuffer[256];
} NodeKey;To save NodeKey in storage, you need to position the pointer to the data at the beginning address of the structure, and calculate its size using the function MDB_value sizeof MDB_val serialize(NodeKey * const key) { return MDB_val { .mv_size = sizeof(NodeKey), .mv_data = (void *)key }; }.
In the first chapter on the criteria for selecting a database, I mentioned minimizing dynamic allocations as an important selection factor for CRUD operations. The code of the functionserialize shows how, in the case of LMDB, they can be completely avoided when inserting new records into the database. The incoming byte array from the server is first transformed into stack structures, and then they are trivially dumped into storage. Given that LMDB also has no dynamic allocations, a fantastic situation by iOS standards can be achieved — utilizing only stack memory for data handling all the way from the network to the disk! Sorting keys with a binary comparator
Sorting keys with a binary comparator
The order of keys is determined by a special function known as a comparator. Since the engine has no knowledge of the semantics of the bytes it contains, the default comparator has no choice but to sort the keys in lexicographic order, resorting to byte-by-byte comparison. Using it for sorting structures is akin to shaving with a cleaver. Nevertheless, I find this method acceptable in simple cases. An alternative is described a bit further below, but here I will note a couple of pitfalls scattered along this path.
The first thing to remember is the representation of primitive data types in memory. On all Apple devices, integer variables are stored in the . This means that the least significant byte will be on the left, and sorting integers using their byte-by-byte comparison will not work. For example, attempting to do this with a set of numbers from 0 to 511 will lead to the following result.
// value (hex dump)
000 (0000)
256 (0001)
001 (0100)
257 (0101)
...
254 (fe00)
510 (fe01)
255 (ff00)
511 (ff01)To solve this problem, integers must be stored in the key in a format suitable for byte-by-byte comparators. The necessary conversion can be accomplished with functions from the hton* family (in particular, htons for the two-byte numbers from the example).
The representation format of strings in programming is, as we know, a whole . If the semantics of strings and the encoding used for their representation in memory imply that a symbol can occupy more than one byte, it is better to abandon the idea of using the default comparator right away.
The second thing to keep in mind is the of the structure's fields by the compiler. Due to this, bytes with garbage values can form in memory between fields, which, of course, breaks byte-wise sorting. To eliminate garbage, you need to either declare fields in a strictly defined order, keeping in mind the alignment rules, or use the packed.
attribute in the structure declaration. Sorting keys with an external comparator
The logic of comparing keys may be too complex for a binary comparator. One of many reasons is the presence of technical fields within structures. I will illustrate their emergence using the already familiar key for an element of the directory.
typedef struct NodeKey {
EntityId parentId;
uint8_t type;
uint8_t nameBuffer[256];
} NodeKey;Despite its simplicity, it consumes too much memory in the vast majority of cases. The buffer for the name occupies 256 bytes, although file and folder names rarely exceed 20-30 characters on average.
One of the standard techniques for optimizing record size consists of "trimming" it to the actual size. Its essence is that the contents of all variable-length fields are stored at the end of the structure, while their lengths are stored in separate variables. In accordance with this approach, the key NodeKey is transformed as follows.
typedef struct NodeKey {
EntityId parentId;
uint8_t type;
uint8_t nameLength;
uint8_t nameBuffer[256];
} NodeKey;Then, during serialization, the size of the data is specified not MDB_val serialize(NodeKey * const key) { return MDB_val { .mv_size = sizeof(NodeKey), .mv_data = (void *)key }; } for the entire structure, but for the size of all fixed-length fields plus the size of the actually used part of the buffer.
MDB_val serialize(NodeKey * const key) {
return MDB_val {
.mv_size = offsetof(NodeKey, nameBuffer) + key->nameLength,
.mv_data = (void *)key
};
}As a result of the refactoring, we achieved significant savings in space occupied by the keys. However, due to the technical field nameLength, the default binary comparator is no longer suitable for comparing keys. If we do not replace it with our own, the length of the name will be a more prioritized factor for sorting than the name itself.
LMDB allows each database to specify its key comparison function. This is done using the function mdb_set_compare strictly before opening. For obvious reasons, it cannot be changed throughout the lifetime of the database. The comparator receives two keys in binary format as input, and returns the result of the comparison: less (-1), greater (1), or equal (0). The pseudocode for NodeKey looks like this.
int compare(MDB_val * const a, MDB_val * const b) {
NodeKey * const aKey = (NodeKey * const)a->mv_data;
NodeKey * const bKey = (NodeKey * const)b->mv_data;
return // ...
}As long as all keys in the database are of the same type, unconditional casting of their byte representation to the application key structure type is legitimate. There is one nuance, but it will be addressed shortly in the subsection "Reading Records."
Serialization of values
The keys of the stored LMDB records work extremely intensively. Their comparison occurs during any application operation, and the speed of the comparator affects the performance of the entire solution. In an ideal world, the default binary comparator should suffice for comparing keys, but if you have to use your own, the key deserialization procedure should be as fast as possible.
The value part of the record is not particularly interesting to the database. Its conversion from byte representation to an object occurs only when it is needed by the application code, for example, for display on the screen. Since this happens relatively rarely, the speed requirements for this procedure are not as critical, allowing us much more freedom to prioritize convenience in its implementation. For instance, to serialize metadata about files that have not yet been loaded, we use NSKeyedArchiver.
NSData *data = serialize(object);
MDB_val value = {
.mv_size = data.length,
.mv_data = (void *)data.bytes
};However, there are cases when performance does matter. For instance, when storing metadata about the file structure of a user cloud, we use the same memory dump of objects. The highlight of the task of forming their serialized representation is the fact that directory elements are modeled by a hierarchy of classes.
To implement this in C, specific fields of the subclasses are allocated in separate structures, and their connection to the base is established through a union type field. The current content of the union is defined via a technical attribute called type.
typedef struct NodeValue {
EntityId localId;
EntityType type;
union {
FileInfo file;
DirectoryInfo directory;
} info;
uint8_t nameLength;
uint8_t nameBuffer[256];
} NodeValue;Adding and updating records
Serialized key and value can be added to the storage. This is done using the function mdb_put.
// key и value имеют тип MDB_val
mdb_put(..., &key, &value, MDB_NOOVERWRITE);At the configuration stage, the storage can be allowed or prohibited from holding multiple records with the same key. If key duplication is not allowed, when inserting a record, it can be specified whether updating an existing record is permissible or not. If overwriting can only happen due to a code error, it can be mitigated by setting a flag. NOOVERWRITE.
Reading records
The function designed for reading records in LMDB is mdb_get. If the key-value pair has been previously presented with dumped structures, this procedure looks as follows.
NodeValue * const readNode(..., NodeKey * const key) {
MDB_val rawKey = serialize(key);
MDB_val rawValue;
mdb_get(..., &rawKey, &rawValue);
return (NodeValue * const)rawValue.mv_data;
}The presented listing demonstrates how serialization through dumped structures allows avoiding dynamic allocations not only during writing but also when reading data. The pointer obtained from the function mdb_get points exactly to the address in virtual memory where the database stores the byte representation of the object. In fact, this results in a sort of ORM, providing very high data reading speeds almost for free. Despite the elegance of this approach, several associated features must be kept in mind.
- For readonly transactions, the pointer to the structure-value will remain valid only until the transaction is closed. As previously noted, the B-tree pages where the object resides, due to the copy-on-write principle, remain unchanged as long as at least one transaction references them. However, as soon as the last related transaction concludes, the pages may be reused for new data. If it is necessary for objects to survive their originating transaction, they still must be copied.
- For readwrite transactions, the pointer to the obtained structure-value will be valid only until the first modifying operation (writing or deleting data).
- Despite the fact that the structure
NodeValueis not full but trimmed (see the section 'Sorting keys with an external comparator'), the fields can be accessed through the pointer. The main thing is not to dereference it! - Under no circumstances should the structure be modified through the obtained pointer. All changes must be made only through the method
mdb_put. However, no matter how much you want to do this, it won't work, as the memory area where this structure resides is mapped in readonly mode. - Remapping the file into the address space of the process, for example, to increase the maximum storage size using the function
invalidates all entities (cursors, transactions, keys, and values) previously obtained from the engine. Taking this turn of events into account in the code will significantly complicate it. If, however, virtual memory is crucial for you, this could be a reason to look at a fork that has advanced significantly,completely invalidates all transactions and associated entities in general, and pointers to read objects in particular.
Finally, there's one more feature that is so insidious that revealing its essence doesn't fit simply into another point. In the chapter on the B-tree, I presented a diagram of how its pages are organized in memory. From it, it follows that the address of the beginning of the buffer with serialized data can be completely arbitrary. Because of this, the pointer to it, obtained in the structure MDB_value and cast to a pointer to the structure, becomes misaligned in the general case. At the same time, the architectures of some chips (in the case of iOS this is armv7) require that the address of any data is a multiple of the machine word size or, in other words, the system’s bitness (for armv7 — this is 32 bits). In other words, operations like *(int *foo)0x800002 are treated as a crash and lead to a verdict of EXC_ARM_DA_ALIGN. You can avoid such a sad fate in two ways.
The first involves pre-copying the data into a properly aligned structure. For instance, in a custom comparator, this would look like the following.
int compare(MDB_val * const a, MDB_val * const b) {
NodeKey aKey, bKey;
memcpy(&aKey, a->mv_data, a->mv_size);
memcpy(&bKey, b->mv_data, b->mv_size);
return // ...
}An alternative path is to inform the compiler in advance that structures with keys and values may be unaligned by using the attribute aligned(1). On ARM, the same effect can be achieved with the packed attribute. Given that it also contributes to optimizing the space taken by the structure, I find this approach preferable, although it leads to higher costs of data access operations.
typedef struct __attribute__((packed)) NodeKey {
uint8_t parentId;
uint8_t type;
uint8_t nameLength;
uint8_t nameBuffer[256];
} NodeKey;Range queries
To iterate over a group of records in LMDB, a cursor abstraction is provided. We will look at how to work with it using the example of the previously familiar user cloud metadata table.
When displaying the list of files in a directory, it is necessary to find all the keys associated with its child files and folders. In the previous sections, we sorted the keys NodeKey in such a way that they are primarily ordered by the identifier of the parent directory. Therefore, technically, the task of obtaining the contents of a folder reduces to setting the cursor at the upper boundary of the group of keys with a given prefix and then iterating to the lower boundary.
The upper boundary can be found "brute force" through sequential search. For this, the cursor is set at the beginning of the entire list of keys in the database and is then incremented until it is underneath the key with the identifier of the parent directory. This approach has two obvious disadvantages:
- Linear search complexity, although it is known that in trees in general and in B-trees in particular, it can be done in logarithmic time.
- It unnecessarily loads all pages preceding the sought one from the file into main memory, which is extremely costly.
Fortunately, the LMDB API provides an efficient way for initial cursor positioning. To do this, a key must be formed whose value is guaranteed to be less than or equal to the key at the upper boundary of the interval. For example, regarding the list in the image above, we can create such a key where the field parentId is equal to 2, and all others are filled with zeros. Such a partially filled key is supplied to the function mdb_cursor_get with the operation specified as MDB_SET_RANGE.
NodeKey upperBoundSearchKey = {
.parentId = 2,
.type = 0,
.nameLength = 0
};
MDB_val value, key = serialize(upperBoundSearchKey);
MDB_cursor *cursor;
mdb_cursor_open(..., &cursor);
mdb_cursor_get(cursor, &key, &value, MDB_SET_RANGE);If the upper boundary of the group of keys is found, we then iterate over it until we either encounter a key with a different parentIdor the keys run out altogether.
do {
rc = mdb_cursor_get(cursor, &key, &value, MDB_NEXT);
// processing...
} while (MDB_NOTFOUND != rc && // check end of table
IsTargetKey(key)); // check end of keys groupWhat's nice is that during iteration using mdb_cursor_get, we receive not only the key but also the value. If the selection criteria need to check fields from the value part of the record, they are quite accessible without any additional effort.
4.3. Modeling Relationships Between Tables
At this point, we have managed to consider all aspects of designing and working with a single-table database. It can be said that a table is a collection of sorted records consisting of homogeneous key-value pairs. If we represent the key as a rectangle and the associated value as a parallelepiped, we will obtain a visual scheme of the database.
However, in real life, it is rarely possible to get by with such little effort. Often, a database requires having several tables, and second, to perform queries in an order different from the primary key. This last section is dedicated to the issues of creating and linking them together.
Index Tables
In the cloud application, there is a section called 'Gallery'. It displays media content from the entire cloud, sorted by date. For optimal implementation of such queries, it is necessary to create another table with a new type of keys alongside the main table. It will contain a field with the file creation date, which will serve as the primary sorting criterion. Since the new keys reference the same data as the keys in the main table, they are called index keys. In the picture below, they are highlighted in orange.
To separate the keys of different tables within a single database, an additional technical field tableId has been added to all of them. By making it the highest priority for sorting, we will achieve grouping of keys first by tables, and then within tables according to their own rules.
An index key refers to the same data as the primary key. The straightforward implementation of this property by associating it with a copy of the value part of the primary key is suboptimal from several points of view:
- From the perspective of space occupied, given that metadata can be quite rich.
- From the point of view of performance, as updating the metadata will require rewriting two keys.
- From a code support perspective, as soon as we forget to update the data for one of the keys, we end up with a hard-to-trace bug of data inconsistency in the storage.
Next, let's look at how to eliminate these shortcomings.
Organizing relationships between tables
The pattern well suited for linking the index table with the main one is ‘key as value’. As the name suggests, the value part of the index record is a copy of the primary key’s value. This approach mitigates all the aforementioned shortcomings related to storing a copy of the value part of the primary record. The only drawback is that to get a value by the index key, two database queries are needed instead of one. The resulting database schema looks as follows.
Another pattern for organizing relationships between tables is ‘redundant key’. Its essence lies in adding additional attributes to the key that are not intended for sorting, but for reconstructing the related key. In the Mail.ru Cloud application, there are real examples of its use, but to avoid delving deeply into the context of specific iOS frameworks, I will provide a fictional, yet more understandable example.
In cloud mobile clients, there is a page that displays all files and folders to which the user has granted access to other people. Since there are relatively few such files, while there is a lot of specific information related to their public nature (who has access, with what rights, etc.), it would be impractical to weight the value part of the record in the main table with it. However, if one wants to display such files offline, it still needs to be stored somewhere. A natural solution is to create a separate table for it. In the diagram below, its key has the prefix ‘P’, and the placeholder ‘propname’ can be replaced with a more specific value, ‘public info’.
All unique metadata, for which a new table was created, is placed in the value part of the record. At the same time, we do not want to duplicate the data about files and folders that are already stored in the main table. Instead, redundant data in the form of 'node ID' and 'timestamp' fields are added to the key 'P'. Thanks to them, we can construct an index key that allows us to retrieve the primary key, which finally lets us access the node's metadata.
Conclusion
We evaluate the results of implementing LMDB positively. After its introduction, the number of application freezes decreased by 30%.
The results of the work done have resonated beyond the iOS team. Currently, one of the main sections 'Files' in the Android app has also switched to using LMDB, and other parts are on the way. The C language, in which the key-value storage is implemented, has been a great help to initially create a cross-platform application wrapper around it in C++. A code generator was used for seamless integration of the resulting C++ library with platform code in Objective-C and Kotlin. from Dropbox, but that's a completely different story.
Source: habr.com
