skip to content

Binary Encoding Format

A BSON document is a length prefix followed by typed elements, each with a type byte and a C-string key. Those prefixes let a reader skip a subdocument without parsing it, the point of the layout.

on this pageshow

explore

questions

5

How is a BSON document laid out in bytes, from its length prefix to its final byte?

level: juniorimportance: must knowfreq 35%

answer

  1. three parts, then recursion
  2. what the first four bytes count
  3. type byte, name, value
  4. empty document is five bytes

basics

~20 s

A BSON document is a little-endian int32 total length, then elements, then a 0x00 byte; the length counts its own four bytes and that byte. Each element is a type byte, a NUL-terminated name and a value.

solid answer

~40 s

A BSON document follows the grammar `document ::= int32 e_list unsigned_byte(0)`. The `int32` is little-endian and holds the total number of bytes in the document, including its own four and the trailing `0x00`, so an empty document is exactly 5 bytes: `05 00 00 00 00`. The `e_list` is a run of elements, and each element is one type byte, an `e_name` (a `cstring`: key bytes ended by NUL), and a value whose form the type byte decides. An embedded document or array value is a complete document again, with its own length and terminator. The layout exists for traversal: a reader learns a document's declared size from four bytes and can jump past a nested document without parsing it.

code

plaintext · 3 lines
plaintext
05 00 00 00 00

0D 00 00 00 03 78 00 05 00 00 00 00 00

go deeper

for a junior

Recall the three parts in order: total length, elements, trailing zero byte. Then give an element's three parts, and say the empty document is five bytes.

for a middle

Explain that the prefix includes itself and the terminator, that it is little-endian, and that nested values repeat the whole structure. Being able to recount a small example is what separates you here.

for a senior

Separate what the format says from what a product imposes, such as the maximum document size, and treat the prefix as a declared value that a reader must check against the bytes it actually holds.

for a principal

Connect the layout to its design goal: traversal was bought with per-document and per-key overhead. A lead should know that cost is structural, so it cannot be tuned away by configuration.

## What a BSON document is BSON is a binary format that stores zero or more **ordered key/value pairs** as one entity called a **document**. Its specification (version 1.1, published at bsonspec.org) is written as a grammar, and every multi-byte number in that grammar is **little-endian**, lowest byte first. Condensed, the top of the grammar reads: ```plaintext document ::= int32 e_list unsigned_byte(0) e_list ::= element e_list | "" element ::= type byte, e_name, value for that type e_name ::= cstring cstring ::= bytes without 0x00, then 0x00 ``` ## The three parts of a document 1. **The length.** A four-byte `int32` holding the total number of bytes that make up the document. The total includes the four bytes of the length itself and the trailing byte. 2. **The element list, `e_list`.** Zero or more elements, one after another, with no separators and no count. 3. **The terminator.** A single `0x00` byte. The source of MongoDB's own BSON code and the bsonspec FAQ call it EOO, for end of object. The terminator works because the reader meets it at an element boundary, where a type byte is expected, and the grammar gives no element type the code `0x00`. Zero bytes inside a value are never examined as type bytes, because the reader has already jumped over the value. ## Inside one element Every element has the same three-part shape: - **Type byte.** One byte naming the value's type, for example `0x10` for a 32-bit integer. - **`e_name`.** The key, stored as a `cstring`: its bytes, then a NUL. There is no separate key length. - **Value.** Whatever the type byte says comes next. Some types have a fixed width, some carry their own length, and some have no value bytes at all. | Type byte | Type | Value bytes | |---|---|---| | `0x10` | `int32` | 4 | | `0x01` | `double` | 8 | | `0x08` | boolean | 1 | | `0x0A` | null | 0 | | `0x02` | string | `int32`, UTF-8 bytes, NUL | | `0x03` | embedded document | one complete document | | `0x04` | array | one complete document with keys `"0"`, `"1"`, and so on | ## A worked example The bsonspec FAQ's first example is `{"hello": "world"}`: ```plaintext offset bytes meaning 0x00 16 00 00 00 document length: 22 0x04 02 type: string 0x05 68 65 6C 6C 6F 00 e_name "hello" and its NUL 0x0B 06 00 00 00 string length: 6 0x0F 77 6F 72 6C 64 00 "world" and its NUL 0x15 00 document terminator ``` Recount it: 4 for the document length, 1 for the type byte, 6 for the name, 4 for the string length, 6 for the string, 1 for the terminator. That is 22, or `0x16`, the value in the first four bytes. Note that the string's length, 6, does not count its own four bytes, unlike the document's. ## Nesting is the same grammar again An embedded document is not a special case. Its value is a whole `document`, with its own length at the front and its own terminator at the back, so a parent's length counts every byte of its children. An array uses the same body under a different type byte. This recursion is the point of the layout: because each nested value declares its size up front, a reader that does not want it can jump over it. ## Boundaries, and who sets them - **Smallest document: exactly 5 bytes.** The BSON corpus test vectors list a declared length of 4 or 1 as a decode error, even when followed by `0x00`. - **Largest the prefix can say: 2,147,483,647 bytes.** The field is a signed `int32`, and the specification states no lower cap. - **The maximum BSON document size of 16 mebibytes is MongoDB's rule, not the format's.** MongoDB 9.0 measures it on the same total the prefix records, and a document of exactly 16,777,216 bytes is still within it. ## Common misreadings - The prefix counts **bytes**, never fields. To count fields a reader walks the element list. - The value of the prefix is a **declared** size. It is cheap to read, and a reader still has to check it against the bytes. - Keys are not length-prefixed, though string values are. The two use different encodings of text. The bsonspec home page names the design goals as lightweight, traversable and efficient, and the length prefix serves the second of those.

  • Does a BSON document's length prefix tell you how many fields the document has?
    No. The int32 counts bytes, not elements, and BSON stores no field count anywhere. A document with one large string can be longer than one with ten small integers. To count fields, a reader walks the element list until it reaches the terminator.
  • How can a single 0x00 byte end a BSON document when zero bytes are common inside values?
    A reader only tests for it at an element boundary, where a type byte is due, and no element type uses code 0x00. Zero bytes inside an int32 or a string are consumed as part of the value's width, so they are never read as a possible terminator.
  • Is the 16 mebibyte maximum document size part of the BSON format?
    No. The BSON grammar only says the length is an int32, which can express up to 2,147,483,647 bytes. The 16 mebibyte maximum is a limit MongoDB sets, documented for 9.0. Blaming the format for it names the wrong owner.

  • The length prefix counts only the bytes after itself.
  • The length prefix holds the number of fields in the document.
  • A BSON key carries its own int32 length, as a string value does.
  • An empty BSON document takes no bytes, or only the four-byte length.
  • Integers in BSON are big-endian, in network byte order.
  • The BSON format itself limits every document to 16 MB.

Assumes MongoDB 9.0 for the 16 mebibyte maximum document size; the byte layout itself is BSON 1.1 and carries no product version.

open as a page

How does a BSON reader skip a field it does not want, and what must it still walk?

level: middleimportance: must knowfreq 32%

basics

~20 s

A BSON reader reads an element's type byte, scans its name to the NUL, then jumps the value using a fixed width or its int32 length. With no field index, it still visits every earlier sibling.

open as a page

How does BSON store the array in {"a": 1, "b": [true]}, with 1 as an int32, and how many bytes does the document take?

level: middleimportance: should knowfreq 25%

basics

~20 s

BSON stores [true] as an embedded document with key "0" under type byte 0x04, taking 9 bytes. With 1 as an int32, the whole document {"a": 1, "b": [true]} is 24 bytes, so its length prefix is 0x18.

open as a page

Why can a BSON string value hold a NUL byte when a BSON key cannot?

level: middleimportance: should knowfreq 20%

basics

~20 s

A BSON key is a cstring with no length field, so its first NUL is its end and its bytes cannot contain one. A string value carries an int32 length, so NUL bytes inside it are just data.

open as a page

A hand-written BSON encoder grows a string inside a subdocument in an existing buffer, and readers now reject or truncate the document: what did it forget, and what do length prefixes cost a writer?

level: seniorimportance: should knowfreq 22%

basics

~20 s

Growing a nested BSON value changes the string's int32, every enclosing document's int32 and the offset of all later bytes. A writer must also patch or precompute each length, since BSON has no padding to grow into.

open as a page