Debian Codegraph @

maxmind-db/MaxMind-DB-spec.md

raw
1 ---
2 layout: default
3 title: MaxMind DB File Format Specification
4 version: v2.0
5 ---
6 # MaxMind DB File Format Specification
7
8 ## Description
9
10 The MaxMind DB file format is a database format that maps IPv4 and IPv6
11 addresses to data records using an efficient binary search tree.
12
13 ## Version
14
15 This spec documents **version 2.0** of the MaxMind DB binary format.
16
17 The version number consists of separate major and minor version numbers. It
18 should not be considered a decimal number. In other words, version 2.10 comes
19 after version 2.9.
20
21 Code which is capable of reading a given major version of the format should
22 not be broken by minor version changes to the format.
23
24 ## Overview
25
26 The binary database is split into three parts:
27
28 1. The binary search tree. Each level of the tree corresponds to a single bit
29 in the 128 bit representation of an IPv6 address.
30 2. The data section. These are the values returned to the client for a
31 specific IP address, e.g. "US", "New York", or a more complex map type made up
32 of multiple fields.
33 3. Database metadata. Information about the database itself.
34
35 ## Database Metadata
36
37 This portion of the database is stored at the end of the file. It is
38 documented first because understanding some of the metadata is key to
39 understanding how the other sections work.
40
41 This section can be found by looking for a binary sequence matching
42 "\xab\xcd\xefMaxMind.com". The *last* occurrence of this string in the file
43 marks the end of the data section and the beginning of the metadata. Since we
44 allow for arbitrary binary data in the data section, some other piece of data
45 could contain these values. This is why you need to find the last occurrence
46 of this sequence.
47
48 The maximum allowable size for the metadata section, including the marker that
49 starts the metadata, is 128KiB.
50
51 The metadata is stored as a map data structure. This structure is described
52 later in the spec. Changing a key's data type or removing a key would
53 constitute a major version change for this spec.
54
55 Except where otherwise specified, each key listed is required for the database
56 to be considered valid.
57
58 Adding a key constitutes a minor version change. Removing a key or changing
59 its type constitutes a major version change.
60
61 The list of known keys for the current version of the format is as follows:
62
63 ### node\_count
64
65 This is an unsigned 32-bit integer indicating the number of nodes in the
66 search tree.
67
68 ### record\_size
69
70 This is an unsigned 16-bit integer. It indicates the number of bits in a
71 record in the search tree. Note that each node consists of *two* records.
72
73 ### ip\_version
74
75 This is an unsigned 16-bit integer which is always 4 or 6. It indicates
76 whether the database contains IPv4 or IPv6 address data.
77
78 ### database\_type
79
80 This is a string that indicates the structure of each data record associated
81 with an IP address. The actual definition of these structures is left up to
82 the database creator.
83
84 Names starting with "GeoIP" are reserved for use by MaxMind (and "GeoIP" is a
85 trademark anyway).
86
87 ### languages
88
89 An array of strings, each of which is a locale code. A given record may
90 contain data items that have been localized to some or all of these
91 locales. Records should not contain localized data for locales not included in
92 this array.
93
94 This is an optional key, as this may not be relevant for all types of data.
95
96 ### binary\_format\_major\_version
97
98 This is an unsigned 16-bit integer indicating the major version number for the
99 database's binary format.
100
101 ### binary\_format\_minor\_version
102
103 This is an unsigned 16-bit integer indicating the minor version number for the
104 database's binary format.
105
106 ### build\_epoch
107
108 This is an unsigned 64-bit integer that contains the database build timestamp
109 as a Unix epoch value.
110
111 ### description
112
113 This key will always point to a map. The keys of that map will be language
114 codes, and the values will be a description in that language as a UTF-8
115 string.
116
117 The codes may include additional information such as script or country
118 identifiers, like "zh-TW" or "mn-Cyrl-MN". The additional identifiers will be
119 separated by a dash character ("-").
120
121 This key is optional. However, creators of databases are strongly
122 encouraged to include a description in at least one language.
123
124 ### Calculating the Search Tree Section Size
125
126 The formula for calculating the search tree section size *in bytes* is as
127 follows:
128
129 ( ( $record_size * 2 ) / 8 ) * $number_of_nodes
130
131 The end of the search tree marks the beginning of the data section.
132
133 ## Binary Search Tree Section
134
135 The database file starts with a binary search tree. The number of nodes in the
136 tree is dependent on how many unique netblocks are needed for the particular
137 database. For example, the city database needs many more small netblocks than
138 the country database.
139
140 The top most node is always located at the beginning of the search tree
141 section's address space. The top node is node 0.
142
143 Each node consists of two records, each of which is a pointer to an address in
144 the file.
145
146 The pointers can point to one of three things. First, it may point to another
147 node in the search tree address space. These pointers are followed as part of
148 the IP address search algorithm, described below.
149
150 The pointer can point to a value equal to `$number_of_nodes`. If this is the
151 case, it means that the IP address we are searching for is not in the
152 database.
153
154 Finally, it may point to an address in the data section. This is the data
155 relevant to the given netblock.
156
157 ### Node Layout
158
159 Each node in the search tree consists of two records, each of which is a
160 pointer. The record size varies by database, but inside a single database node
161 records are always the same size. A record may be anywhere from 24 to 128 bits
162 long, depending on the number of nodes in the tree. These pointers are
163 stored in big-endian format (most significant byte first).
164
165 Here are some examples of how the records are laid out in a node for 24, 28,
166 and 32 bit records. Larger record sizes follow this same pattern.
167
168 #### 24 bits (small database), one node is 6 bytes
169
170 | <------------- node --------------->|
171 | 23 .. 0 | 23 .. 0 |
172
173 #### 28 bits (medium database), one node is 7 bytes
174
175 | <------------- node --------------->|
176 | 23 .. 0 | 27..24 | 27..24 | 23 .. 0 |
177
178 Note 4 bits of each pointer are combined into the middle byte. For both
179 records, they are prepended and end up in the most significant position.
180
181 #### 32 bits (large database), one node is 8 bytes
182
183 | <------------- node --------------->|
184 | 31 .. 0 | 31 .. 0 |
185
186 ### Search Lookup Algorithm
187
188 The first step is to convert the IP address to its big-endian binary
189 representation. For an IPv4 address, this becomes 32 bits. For IPv6 you get
190 128 bits.
191
192 The leftmost bit corresponds to the first node in the search tree. For each
193 bit, a value of 0 means we choose the left record in a node, and a value of 1
194 means we choose the right record.
195
196 The record value is always interpreted as an unsigned integer. The maximum
197 size of the integer is dependent on the number of bits in a record (24, 28, or
198 32).
199
200 If the record value is a number that is less than the *number of nodes* (not
201 in bytes, but the actual node count) in the search tree (this is stored in the
202 database metadata), then the value is a node number. In this case, we find
203 that node in the search tree and repeat the lookup algorithm from there.
204
205 If the record value is equal to the number of nodes, that means that we do not
206 have any data for the IP address, and the search ends here.
207
208 If the record value is *greater* than the number of nodes in the search tree,
209 then it is an actual pointer value pointing into the data section. The value
210 of the pointer is relative to the start of the data section, *not* the
211 start of the file.
212
213 In order to determine where in the data section we should start looking, we use
214 the following formula:
215
216 $data_section_offset = ( $record_value - $node_count ) - 16
217
218 The 16 is the size of the data section separator. We subtract it because we
219 want to permit pointing to the first byte of the data section. Recall that
220 the record value cannot equal the node count as that means there is no
221 data. Instead, we choose to start values that go to the data section at
222 `$node_count + 16`. (This has the side effect that record values
223 `$node_count + 1` through `$node_count + 15` inclusive are not valid).
224
225 This is best demonstrated by an example:
226
227 Let's assume we have a 24-bit tree with 1,000 nodes. Each node contains 48
228 bits, or 6 bytes. The size of the tree is 6,000 bytes.
229
230 When a record in the tree contains a number that is less than 1,000, this
231 is a *node number*, and we look up that node. If a record contains a value
232 greater than or equal to 1,016, we know that it is a data section value. We
233 subtract the node count (1,000) and then subtract 16 for the data section
234 separator, giving us the number 0, the first byte of the data section.
235
236 If a record contained the value 6,000, this formula would give us an offset of
237 4,984 into the data section.
238
239 In order to determine where in the file this offset really points to, we also
240 need to know where the data section starts. This can be calculated by
241 determining the size of the search tree in bytes and then adding an additional
242 16 bytes for the data section separator:
243
244 $offset_in_file = $data_section_offset
245 + $search_tree_size_in_bytes
246 + 16
247
248 Since we subtract and then add 16, the final formula to determine the
249 offset in the file can be simplified to:
250
251 $offset_in_file = ( $record_value - $node_count )
252 + $search_tree_size_in_bytes
253
254 ### IPv4 addresses in an IPv6 tree
255
256 When storing IPv4 addresses in an IPv6 tree, they are stored as-is, so they
257 occupy the first 32-bits of the address space (from 0 to 2**32 - 1).
258
259 Creators of databases should decide on a strategy for handling the various
260 mappings between IPv4 and IPv6.
261
262 The strategy that MaxMind uses for its GeoIP databases is to include a pointer
263 from the `::ffff:0:0/96` subnet to the root node of the IPv4 address space in
264 the tree. This accounts for the
265 [IPv4-mapped IPv6 address](http://en.wikipedia.org/wiki/IPv6#IPv4-mapped_IPv6_addresses).
266
267 MaxMind also includes a pointer from the `2002::/16` subnet to the root node
268 of the IPv4 address space in the tree. This accounts for the
269 [6to4 mapping](http://en.wikipedia.org/wiki/6to4) subnet.
270
271 Database creators are encouraged to document whether they are doing something
272 similar for their databases.
273
274 The Teredo subnet cannot be accounted for in the tree. Instead, code that
275 searches the tree can offer to decode the IPv4 portion of a Teredo address and
276 look that up.
277
278 ## Data Section Separator
279
280 There are 16 bytes of NULLs in between the search tree and the data
281 section. This separator exists in order to make it possible for a verification
282 tool to distinguish between the two sections.
283
284 This separator is not considered part of the data section itself. In other
285 words, the data section starts at `$size_of_search_tree + 16` bytes in the
286 file.
287
288 ## Output Data Section
289
290 Each output data field has an associated type, and that type is encoded as a
291 number that begins the data field. Some types are variable length. In those
292 cases, the type indicator is also followed by a length. The data payload
293 always comes at the end of the field.
294
295 All binary data is stored in big-endian format.
296
297 Note that the *interpretation* of a given data type's meaning is decided by
298 higher-level APIs, not by the binary format itself.
299
300 ### pointer - 1
301
302 A pointer to another part of the data section's address space. The pointer
303 will point to the beginning of a field. It is illegal for a pointer to point
304 to another pointer.
305
306 Pointer values start from the beginning of the data section, *not* the
307 beginning of the file.
308
309 ### UTF-8 string - 2
310
311 A variable length byte sequence that contains valid utf8. If the length is
312 zero then this is an empty string.
313
314 ### double - 3
315
316 This is stored as an IEEE-754 double (binary64) in big-endian format. The
317 length of a double is always 8 bytes.
318
319 ### bytes - 4
320
321 A variable length byte sequence containing any sort of binary data. If the
322 length is zero then this a zero-length byte sequence.
323
324 This is not currently used but may be used in the future to embed non-text
325 data (images, etc.).
326
327 ### integer formats
328
329 Integers are stored in variable length binary fields.
330
331 We support 16-bit, 32-bit, 64-bit, and 128-bit unsigned integers. We also
332 support 32-bit signed integers.
333
334 A 128-bit integer can use up to 16 bytes, but may use fewer. Similarly, a
335 32-bit integer may use from 0-4 bytes. The number of bytes used is determined
336 by the length specifier in the control byte. See below for details.
337
338 A length of zero always indicates the number 0.
339
340 When storing a signed integer, the left-most bit is the sign. A 1 is negative
341 and a 0 is positive.
342
343 The type numbers for our integer types are:
344
345 * unsigned 16-bit int - 5
346 * unsigned 32-bit int - 6
347 * signed 32-bit int - 8
348 * unsigned 64-bit int - 9
349 * unsigned 128-bit int - 10
350
351 The unsigned 32-bit and 128-bit types may be used to store IPv4 and IPv6
352 addresses, respectively.
353
354 The signed 32-bit integers are stored using the 2's complement representation.
355
356 ### map - 7
357
358 A map data type contains a set of key/value pairs. Unlike other data types,
359 the length information for maps indicates how many key/value pairs it
360 contains, not its length in bytes. This size can be zero.
361
362 See below for the algorithm used to determine the number of pairs in the
363 hash. This algorithm is also used to determine the length of a field's
364 payload.
365
366 ### array - 11
367
368 An array type contains a set of ordered values. The length information for
369 arrays indicates how many values it contains, not its length in bytes. This
370 size can be zero.
371
372 This type uses the same algorithm as maps for determining the length of a
373 field's payload.
374
375 ### data cache container - 12
376
377 This is a special data type that marks a container used to cache repeated
378 data. For example, instead of repeating the string "United States" over and
379 over in the database, we store it in the cache container and use pointers
380 *into* this container instead.
381
382 Nothing in the database will ever contain a pointer to this field
383 itself. Instead, various fields will point into the container.
384
385 The primary reason for making this a separate data type versus simply inlining
386 the cached data is so that a database dumper tool can skip this cache when
387 dumping the data section. The cache contents will end up being dumped as
388 pointers into it are followed.
389
390 ### end marker - 13
391
392 The end marker marks the end of the data section. It is not strictly
393 necessary, but including this marker allows a data section deserializer to
394 process a stream of input, rather than having to find the end of the section
395 before beginning the deserialization.
396
397 This data type is not followed by a payload, and its size is always zero.
398
399 ### boolean - 14
400
401 A true or false value. The length information for a boolean type will always
402 be 0 or 1, indicating the value. There is no payload for this field.
403
404 ### float - 15
405
406 This is stored as an IEEE-754 float (binary32) in big-endian format. The
407 length of a float is always 4 bytes.
408
409 This type is provided primarily for completeness. Because of the way floating
410 point numbers are stored, this type can easily lose precision when serialized
411 and then deserialized. If this is an issue for you, consider using a double
412 instead.
413
414 ### Data Field Format
415
416 Each field starts with a control byte. This control byte provides information
417 about the field's data type and payload size.
418
419 The first three bits of the control byte tell you what type the field is. If
420 these bits are all 0, then this is an "extended" type, which means that the
421 *next* byte contains the actual type. Otherwise, the first three bits will
422 contain a number from 1 to 7, the actual type for the field.
423
424 We've tried to assign the most commonly used types as numbers 1-7 as an
425 optimization.
426
427 With an extended type, the type number in the second byte is the number
428 minus 7. In other words, an array (type 11) will be stored with a 0 for the
429 type in the first byte and a 4 in the second.
430
431 Here is an example of how the control byte may combine with the next byte to
432 tell us the type:
433
434 001XXXXX pointer
435 010XXXXX UTF-8 string
436 110XXXXX unsigned 32-bit int (ASCII)
437 000XXXXX 00000011 unsigned 128-bit int (binary)
438 000XXXXX 00000100 array
439 000XXXXX 00000110 end marker
440
441 #### Payload Size
442
443 The next five bits in the control byte tell you how long the data field's
444 payload is, except for maps and pointers. Maps and pointers use this size
445 information a bit differently. See below.
446
447 If the five bits are smaller than 29, then those bits are the payload size in
448 bytes. For example:
449
450 01000010 UTF-8 string - 2 bytes long
451 01011100 UTF-8 string - 28 bytes long
452 11000001 unsigned 32-bit int - 1 byte long
453 00000011 00000011 unsigned 128-bit int - 3 bytes long
454
455 If the five bits are equal to 29, 30, or 31, then use the following algorithm
456 to calculate the payload size.
457
458 If the value is 29, then the size is 29 + *the next byte after the type
459 specifying bytes as an unsigned integer*.
460
461 If the value is 30, then the size is 285 + *the next two bytes after the type
462 specifying bytes as a single unsigned integer*.
463
464 If the value is 31, then the size is 65,821 + *the next three bytes after the
465 type specifying bytes as a single unsigned integer*.
466
467 Some examples:
468
469 01011101 00110011 UTF-8 string - 80 bytes long
470
471 In this case, the last five bits of the control byte equal 29. We treat the
472 next byte as an unsigned integer. The next byte is 51, so the total size is
473 (29 + 51) = 80.
474
475 01011110 00110011 00110011 UTF-8 string - 13,392 bytes long
476
477 The last five bits of the control byte equal 30. We treat the next two bytes
478 as a single unsigned integer. The next two bytes equal 13,107, so the total
479 size is (285 + 13,107) = 13,392.
480
481 01011111 00110011 00110011 00110011 UTF-8 string - 3,421,264 bytes long
482
483 The last five bits of the control byte equal 31. We treat the next three bytes
484 as a single unsigned integer. The next three bytes equal 3,355,443, so the
485 total size is (65,821 + 3,355,443) = 3,421,264.
486
487 This means that the maximum payload size for a single field is 16,843,036
488 bytes.
489
490 The binary number types always have a known size, but for consistency's sake,
491 the control byte will always specify the correct size for these types.
492
493 #### Maps
494
495 Maps use the size in the control byte (and any following bytes) to indicate
496 the number of key/value pairs in the map, not the size of the payload in
497 bytes.
498
499 This means that the maximum number of pairs for a single map is 16,843,036.
500
501 Maps are laid out with each key followed by its value, followed by the next
502 pair, etc.
503
504 The keys are **always** UTF-8 strings. The values may be any data type,
505 including maps or pointers.
506
507 Once we know the number of pairs, we can look at each pair in turn to
508 determine the size of the key and the key name, as well as the value's type
509 and payload.
510
511 #### Pointers
512
513 Pointers use the last five bits in the control byte to calculate the pointer
514 value.
515
516 To calculate the pointer value, we start by subdividing the five bits into two
517 groups. The first two bits indicate the size, and the next three bits are part
518 of the value, so we end up with a control byte breaking down like this:
519 001SSVVV.
520
521 The size can be 0, 1, 2, or 3.
522
523 If the size is 0, the pointer is built by appending the next byte to the last
524 three bits to produce an 11-bit value.
525
526 If the size is 1, the pointer is built by appending the next two bytes to the
527 last three bits to produce a 19-bit value + 2048.
528
529 If the size is 2, the pointer is built by appending the next three bytes to the
530 last three bits to produce a 27-bit value + 526336.
531
532 Finally, if the size is 3, the pointer's value is contained in the next four
533 bytes as a 32-bit value. In this case, the last three bits of the control byte
534 are ignored.
535
536 This means that we are limited to 4GB of address space for pointers, so the
537 data section size for the database is limited to 4GB.
538
539 ## Reference Implementations
540
541 ### Writer
542
543 * [Perl](https://github.com/maxmind/MaxMind-DB-Writer-perl)
544
545 ### Reader
546
547 * [C](https://github.com/maxmind/libmaxminddb)
548 * [C#](https://github.com/maxmind/MaxMind-DB-Reader-dotnet)
549 * [Java](https://github.com/maxmind/MaxMind-DB-Reader-java)
550 * [Perl](https://github.com/maxmind/MaxMind-DB-Reader-perl)
551 * [PHP](https://github.com/maxmind/MaxMind-DB-Reader-php)
552 * [Python](https://github.com/maxmind/MaxMind-DB-Reader-python)
553 * [Ruby](https://github.com/maxmind/MaxMind-DB-Reader-ruby)
554
555 ## Authors
556
557 This specification was created by the following authors:
558
559 * Greg Oschwald \<[email protected]\>
560 * Dave Rolsky \<[email protected]\>
561 * Boris Zentner \<[email protected]\>
562
563 ## License
564
565 This work is licensed under the Creative Commons Attribution-ShareAlike 3.0
566 Unported License. To view a copy of this license, visit
567 [http://creativecommons.org/licenses/by-sa/3.0/](http://creativecommons.org/licenses/by-sa/3.0/)
568 or send a letter to Creative Commons, 444 Castro Street, Suite 900, Mountain
569 View, California, 94041, USA
570