MongoDB Internals, Part 1

Intro

The more you work on practical issues, the further you go from the basics. Of course, a good computer science course can teach algorithms, data structures and software development principles, but most of the time we work on a high level without needing to go down to the fundamentals.

Working with databases, we, as application developers, usually need to effectively use a query language, design good data models, optimize indexes and so on. You do not need to know how it all works under the hood. Or do you? Anyway, curiosity is a strong motivation.

Now, it's obvious that a DBMS must include a storage engine, i.e. a mechanism to, you know, store data. Martin Kleppmann's legendary book shows a good example of what we can call a minimal database: it's a bash script that can save data and retrieve it.

And this is where the corny revelation hit me: in databases, everything is a file! We can find so many ways to optimize our storage, the fanciest tools to operate it, the most beautiful query language. But at the end of the day, it's gonna be some bytes stored on persistent storage.

And this means that, to understand how exactly a real-life, production-ready database stores data, we can just find these files, read them and try to interpret them. That's where we can start our journey.

Goals

What are we looking for? I want to track what happens when we run a query in MongoDB. Like, having the complete picture of how we get a record stored somewhere on disk when running db.collection.find({}).

Why MongoDB? Well, that's my main working database for now, so the reason is pretty selfish - just want to understand the tool I work with every day more deeply.

We're going to dig until we find a particular document inside MongoDB files, and later also will try to understand how the query finds it.

Facts

What we already know from the documentation and articles:

• MongoDB is a document-oriented database.
• It uses a storage engine named WiredTiger (awesome name!). It used to have its own storage engine, but it was deprecated and now WiredTiger is the king.
• By default WiredTiger uses B-trees as its underlying storage structure.

Given that, we might configure our Mongo lab for experimenting.

Getting hands dirty

Set up

I'm a Windows user (guilty, just a habit of an old .Net coder), so I'm going to use Docker Desktop + WSL2 to run an instance of MongoDB on my laptop.

In our Docker image we will install MongoDB 7, a standalone WiredTiger instance, and a set of tools for debugging. Of course, WiredTiger installation is not required for running MongoDB, but we need it for our investigation.

The complete lab setup is available on GitHub:

• Dockerfile — MongoDB + WiredTiger build
• docker-compose.yml — container configuration
• init.js — test database initialization
• init.sh — MongoDB startup script
• decode-bson.py — small BSON decoding helper

Now we are ready to run it:
docker-compose up

MongoDB research

Let's go inside our container:
docker exec -it mongo-lab /bin/bash

First, we are going to check what MongoDB can tell us about the storage without any additional tools.

We are running a mongosh:
mongosh

and switch to our database:
use exampleDb

In init.js we initialized users collection with 3 records, and we created the email index in this collection. Let's check:

exampleDb> db.users.find()
[
  {
    _id: ObjectId('6836a11b9a95b3d064c59f35'),
    name: 'Alice',
    email: '[e-mail]',
    age: 25
  },
  {
    _id: ObjectId('6836a11b9a95b3d064c59f36'),
    name: 'Bob',
    email: '[e-mail]',
    age: 31
  },
  {
    _id: ObjectId('6836a11b9a95b3d064c59f37'),
    name: 'Charlie',
    email: '[e-mail]',
    age: 28
  }
]

exampleDb> db.users.getIndexes()
[
  { v: 2, key: { _id: 1 }, name: '_id_' },
  { v: 2, key: { email: 1 }, name: 'email_1' }
]

Ok, looks good.
As the next step we can try to find the name of files that store the structures that represent our data. Let's run this command:
db.users.stats({ indexDetails: true })

The output is big but the important places for our goals are uri fields:

{
  ok: 1,
  capped: false,
  wiredTiger: {
    uri: 'statistics:table:collection-7-374368253173125407',
    ...
  },
  indexDetails: {
    _id_: {
      uri: 'statistics:table:index-8-374368253173125407',
      ...
    },
    email_1: {
      uri: 'statistics:table:index-11-374368253173125407',
      ...
    }
  },
  sharded: false,
  size: 228,
  count: 3,
  numOrphanDocs: 0,
  storageSize: 36864,
  totalIndexSize: 57344,
  totalSize: 94208,
  indexSizes: { _id_: 36864, email_1: 20480 },
  avgObjSize: 76,
  ns: 'exampleDb.users',
  nindexes: 2,
  scaleFactor: 1
}

Good, now we can leave mongosh (with exit command) and staying in the container, check /data/db folder as we specified it as --dbpath argument for mondog in init.sh.

> cd /data/db
> ls -lh
total 476K
-rw------- 1 root root   50 Aug 11 13:22 WiredTiger
-rw------- 1 root root   21 Aug 11 13:22 WiredTiger.lock
-rw------- 1 root root 1.5K Sep  6 00:14 WiredTiger.turtle
-rw------- 1 root root  76K Sep  6 00:14 WiredTiger.wt
-rw------- 1 root root 4.0K Aug 24 11:49 WiredTigerHS.wt
-rw------- 1 root root  36K Aug 24 11:49 _mdb_catalog.wt
-rw------- 1 root root  20K Aug 24 11:49 collection-0-374368253173125407.wt
-rw------- 1 root root  36K Aug 24 11:50 collection-2-374368253173125407.wt
-rw------- 1 root root  36K Sep  6 00:07 collection-4-374368253173125407.wt
-rw------- 1 root root  36K Aug 24 11:50 collection-7-374368253173125407.wt
drwx------ 1 root root 4.0K Sep  6 00:14 diagnostic.data
-rw------- 1 root root  20K Aug 24 11:49 index-1-374368253173125407.wt
-rw------- 1 root root  20K Sep  6 00:01 index-11-374368253173125407.wt
-rw------- 1 root root  36K Aug 24 11:50 index-3-374368253173125407.wt
-rw------- 1 root root  24K Sep  5 23:57 index-5-374368253173125407.wt
-rw------- 1 root root  36K Sep  6 00:07 index-6-374368253173125407.wt
-rw------- 1 root root  36K Sep  6 00:01 index-8-374368253173125407.wt
drwx------ 1 root root 4.0K Aug 24 11:50 journal
-rw------- 1 root root    2 Aug 24 11:49 mongod.lock
-rw------- 1 root root  36K Sep  5 23:58 sizeStorer.wt
-rw------- 1 root root  114 Aug 11 13:22 storage.bson

We can see that there are files with the names matching with uri fields in the MongoDB stats:

collection-7-374368253173125407.wt
index-8-374368253173125407.wt
index-11-374368253173125407.wt

If we try to read it with some simple approach, like, literally using cat or something similar, we won't be able to understand it. There are metadata and a lot of binary symbols. So we need tools that will help us with that.

Data storage internals

From the WiredTiger docs, "The wt tool is a command-line utility that provides access to various pieces of the WiredTiger functionality."

We will use it to inspect the files that we found in the previous steps.

The commands that can help us are:

• dump - exports data in text format. Might be useful for reading the file content.
• verify - checks the structural integrity. It can also show information about the tree structure, including page addresses.

The options that we are going to use:

• -r - opens a database in the read-only mode. Since we copied our data files from the working directory, we can skip it. But just in case, let's keep it.
• -h - home directory (where our data files are).
• -C - configuration. In our case we need to specify the snappy compressor that was used to store the data, so we need to use it to read the data.
• -d - specifies what exactly we want to display: for example, -d dump_tree_shape will demonstrate the B-tree structure.
• -x - dumps data in hexadecimal form.

Let's start with inspecting a tree structure in the _id index file:

wt -r \
  -h /data/db-copy \
  -C "extensions=(/opt/wiredtiger/build/ext/compressors/snappy/libwiredtiger_snappy.so)" \
  verify -d dump_tree_shape \
  file:index-8-374368253173125407.wt

0  INTERNAL  type: WT_PAGE_ROW_LEAF  entries: 1  mem_footprint: 460
0.0  LEAF  type: UNKNOWN  keys: 3  keys_size: 18  values_size: 6  total_size: 72  mem_footprint: 328
0  =  children: 1  keys: 3  keys_size: 18  values_size: 6  total_size: 72

Looks as expected: we have 3 keys in the leaf, representing 3 documents in the users collection. The index is a B-tree, as we mentioned earlier, in MongoDB/WiredTiger - so that's how we see it here. INTERNAL, in our tiny tree, is a non-leaf root node with a single leaf child containing three keys.

Now, what if we try to run verify -d dump_tree_shape against the collection data file?

wt -r \
  -h /data/db-copy \
  -C "extensions=(/opt/wiredtiger/build/ext/compressors/snappy/libwiredtiger_snappy.so)" \
  verify -d dump_tree_shape \
  file:collection-7-374368253173125407.wt

0  INTERNAL  type: WT_PAGE_ROW_LEAF  entries: 1  mem_footprint: 460
0.0  LEAF  type: UNKNOWN  keys: 3  keys_size: 3  values_size: 228  total_size: 280  mem_footprint: 536
0  =  children: 1  keys: 3  keys_size: 3  values_size: 228  total_size: 280

And this is interesting: looks like not only the indexes, but also collection data itself is stored as a B-tree in WiredTiger!

Being already excited about this finding, we need to go further trying to understand what exactly is stored in the leafs of these trees. The next command will dump the _id index file's content as text:

wt -r \
  -h /data/db-copy \
  -C "extensions=(/opt/wiredtiger/build/ext/compressors/snappy/libwiredtiger_snappy.so)" \
  dump -x file:index-8-374368253173125407.wt

WiredTiger Dump (WiredTiger Version 12.0.0)
Format=hex
Header
file:index-8-374368253173125407.wt
...
**skipping some metadata here**
...
Data
646836a11b9a95b3d064c59f3504
0008
646836a11b9a95b3d064c59f3604
0010
646836a11b9a95b3d064c59f3704
0018

We can see that the index file stores pairs:

• 646836a11b9a95b3d064c59f3504 -> 0008
• 646836a11b9a95b3d064c59f3604 -> 0010
• 646836a11b9a95b3d064c59f3704 -> 0018

And, as we can see, the key here contains the _id value encoded in MongoDB's KeyString format. But wait, our _id values are: 6836a11b9a95b3d064c59f35 (Alice), 6836a11b9a95b3d064c59f36 (Bob), and 6836a11b9a95b3d064c59f37 (Charlie).
Why do we store, for example, 6836a11b9a95b3d064c59f35 as 646836a11b9a95b3d064c59f3504?
This is actually a KeyString format - a serialization format for BSON.

As explained in the docs:

• the first byte represents the type: 64,
• then we see our 12 bytes ObjectId: 6836a11b9a95b3d064c59f35,
• and 04 is an end byte in KeyString.

Let's check in the source code what 64 hex (or 100 in decimal) type is:

const uint8_t kOID = 100;

Ok, it's OID, i.e. the KeyString type corresponding to BSON ObjectId. Now we see that the key this index is just _id with some small tech additions.

But what is the value here? These 0008, 0010, 0018 values? Based on the common sense, they might represent something that will help to find a record in the collection data file. I mean, this is what indexes are for.

RecordId

Let's jump forward a bit and look at the docs again: here's the interesting paragraph about RecordId, a unique identifier of a record. The catch phrase for us there is:

Note that changing record ids can be very expensive, as indexes map to the RecordId.

So, now we can assume that 0008, 0010, 0018 values are RecordIds of our documents.

Let's check it with a help of mongosh's command showRecordId():

exampleDb> db.users.find().showRecordId()
[
  {
    _id: ObjectId('6836a11b9a95b3d064c59f35'),
    name: 'Alice',
    email: '[e-mail]',
    age: 25,
    '$recordId': Long('1')
  },
  {
    _id: ObjectId('6836a11b9a95b3d064c59f36'),
    name: 'Bob',
    email: '[e-mail]',
    age: 31,
    '$recordId': Long('2')
  },
  {
    _id: ObjectId('6836a11b9a95b3d064c59f37'),
    name: 'Charlie',
    email: '[e-mail]',
    age: 28,
    '$recordId': Long('3')
  }
]

Doesn't look the same as what we found in the index... But let's try to dump the data from the collection file:

wt -r \
  -h /data/db-copy \
  -C "extensions=(/opt/wiredtiger/build/ext/compressors/snappy/libwiredtiger_snappy.so)" \
  dump -x file:collection-7-374368253173125407.wt

WiredTiger Dump (WiredTiger Version 12.0.0)
Format=hex
...
Data
81
4c000000075f6964006836a11b9a95b3d064c59f35026e616d650006000000416c6963650002656d61696c0012000000616c696365406578616d706c652e636f6d0010616765001900000000
82
48000000075f6964006836a11b9a95b3d064c59f36026e616d650004000000426f620002656d61696c0010000000626f62406578616d706c652e636f6d0010616765001f00000000
83
50000000075f6964006836a11b9a95b3d064c59f37026e616d650008000000436861726c69650002656d61696c0014000000636861726c6965406578616d706c652e636f6d0010616765001c00000000

Keys here are represented as 81, 82, 83.
Let's decipher the values to make sure that these are our users documents. For this, I've created a small Python script that uses a BSON decoder from pymongo, a MongoDB driver for Python. It was copied into the Docker container so we can run it from the inside:

./decode-bson.py

#!/usr/bin/env python3

import sys
from bson import BSON
from pprint import pprint


def main():
    if len(sys.argv) != 2:
        print(f"Usage: {sys.argv[0]} HEX_STRING")
        sys.exit(1)

    try:
        data = bytes.fromhex(sys.argv[1])
        document = BSON(data).decode()
        pprint(document, sort_dicts=False)
    except ValueError as e:
        print(f"Invalid hex string: {e}", file=sys.stderr)
        sys.exit(1)
    except Exception as e:
        print(f"Failed to decode BSON: {e}", file=sys.stderr)
        sys.exit(1)


if __name__ == "__main__":
    main()

Now run it:

> decode-bson '4c000000075f6964006836a11b9a95b3d064c59f35026e616d650006000000416c6963650002656d61696c0012000000616c696365406578616d706c652e636f6d0010616765001900000000'

{'_id': ObjectId('6836a11b9a95b3d064c59f35'),
 'name': 'Alice',
 'email': '[e-mail]',
 'age': 25}

Good, BSON decoder helped us to see that this is 'Alice' user.

Let's try to track down what we already found:

1. We want to find Alice in the users collection. Assume that we know the _id, because we're researching how a document is found using this index. Running the following query in Mongo shell:

db.users.find({ _id: ObjectId('6836a11b9a95b3d064c59f35') })

1. The B-tree traversal starts in the index file and finds the key-value pair:
   6836a11b9a95b3d064c59f35 -> 0008. 0008 appears to be an encoded representation of Alice's RecordId.

2. Then, B-tree search is starting in the collection data file. Here comes the obscure part: I expected that the key that we are looking for is 0008. But it's plain to see that the key in the data is represented as 81.
   And, what makes things even less clear, when we ran showRecordId() command the RecordId for Alice was 1.

The question is, how 0008 did become 81, and then 1?

We do not know it yet. But I can refer to Akira Kurogane's article WiredTiger File Forensics Part 3: Viewing all the MongoDB Data. Akira observed the mathematical dependencies between these values, like:

0008₈ = 1000₂

1000₂ >> 3 = 1₂ = 1₈

80₈ + 1₈ = 81₈

And that explains how we can link 0008 with 81, and with 1.
This was found experimentally, but why and how does it work this way? This is the good topic for the next chapter: we will try to investigate the WiredTiger source code (maybe even debug it step by step) to understand these conversions.