| This file describes the design, data model, and storage formats of FSFS |
| index data. |
| |
| |
| Design |
| ====== |
| |
| Each pack and each rev file using logical addressing contains exactly |
| two index sections. One, the log-to-phys index, maps the (rev, item_index) |
| pairs to absolute file offsets. The other, phys-to-log, is a reverse |
| index that gives basic information on any file location. This is enough |
| to read and cache any data without traversing DAGs. |
| |
| Rev and pack files are immutable, so the same is true for index data. |
| During a transaction or while packing a file, a proto index file gets |
| written (actually, one log-to-phys and one phys-to-log). They use a |
| simpler, less compact format with fixed record lengths. A proto index |
| basically aggregates all the information that must later be transformed |
| into the final index. |
| |
| |
| General design concerns |
| ----------------------- |
| |
| In Subversion, there is no limit to the size of a revision; even practical |
| limits are in the order of millions of changes at least. Index data for |
| these would be multiple megabytes in size with pack file indexes possibly |
| approaching 1 GB. To ensure we still get roughly O(1) access time, we |
| need a hierarchical data structure. |
| |
| Therefore, the indexes will start with a header containing an array of |
| references to sub-sections or pages. The length of these pages varies |
| but is limited to a size configurable in fsfs.conf. |
| |
| Finally, it is assumed that whole pages can be cached efficiently and |
| with a high cache hit rate. So, although a page may have a thousand or |
| more entries, the access time is still amortized O(1) in many scenarios. |
| |
| |
| Items and item types |
| -------------------- |
| |
| The index implementation treats item_index and item type as simple ints, |
| except for SVN_FS_FS__ITEM_INDEX_UNUSED and SVN_FS_FS__ITEM_TYPE_UNUSED. |
| Since they have been defined as 0, the code may test for "used" etc. |
| by simply comparing with 0. |
| |
| See section "addressing modes" in structure to a list of item types |
| and pre-defined item_index values. |
| |
| |
| Encoding |
| -------- |
| |
| The final index data format is tuned for space and decoding efficiency. |
| Indexes are stored as a sequence of variable integers. The encoding is |
| as follows: |
| |
| * Unsigned integers are stored in little endian order with a variable |
| length 7b/8b encoding. If most significant bit a byte has been set, |
| the next byte has also belongs to the same value. |
| |
| 0x00 .. 0x7f -> 0x00 .. 0x7f ( 7 bits stored in 8 bits) |
| 0x80 .. 0xff -> 0x80 0x01 .. 0xff 0x01 (14 bits stored in 16 bits) |
| 0x100 .. 0x3fff -> 0x80 0x02 .. 0xff 0x7f (14 bits stored in 16 bits) |
| 0x100000000 -> 0x80 0x80 0x80 0x80 0x10 (35 bits stored in 40 bits) |
| |
| Technically, we can represent integers of arbitrary lengths. Currently, |
| we only generate and parse up to 64 bits. |
| |
| * Signed integers are mapped onto the unsigned value space as follows: |
| |
| x >= 0 -> 2 * x |
| x < 0 -> -2 * x - 1 |
| |
| Again, we can represent arbitrary length numbers that way but the code |
| is currently restricted to 64 bits. |
| |
| Most data is unsigned by nature but will be stored differentially using |
| signed integers. |
| |
| |
| Encoding in proto-index files |
| ----------------------------- |
| |
| These have a much simpler encoding. Throughout the files, all records have |
| the same length (but different between L2P and P2L). All records contain |
| unsigned 64 bit integers only, stored in little endian byte order. |
| |
| |
| Log-to-phys index |
| ================= |
| |
| This index has to map (rev, item_index) -> offset. It assumes that the |
| item_index values per revision are dense and start at 0. There may be |
| unused item_index values, though; the data structure simply gets less |
| space-efficient when the more sparse the value space gets. |
| |
| |
| Index data model |
| ---------------- |
| |
| hierarchy: |
| |
| header -> per-revision info -> page -> offset |
| |
| There is one entry per revision in the header. Per revision there are |
| one or more pages (exclusive to that revision) containing up to a known, |
| fixed limit of entries (= page size). The total access path is: |
| |
| pages = header->pages[revision]; |
| offsets = page = pages[item_index / page_size]; |
| offset = offsets[item_index % page_size]; |
| |
| Different log-to-phys indexes in the same repository may have different |
| page sizes but within any given index, the page size is the same and |
| immutable. |
| |
| header: |
| |
| <first revision> ... first revision covered by this index |
| <revision count> ... number of revision covered by this index |
| <page size> ... maximum number of entries per page |
| <page table index> ... array, for each revision containing the index in |
| <page table> of the first page that belongs to |
| this revision. This has <revision count>+1 |
| entries to terminate the last revision. |
| <page table> ... array of page headers. It has |
| <page table index>[<revision count>] entries. |
| |
| page table: |
| |
| <offset> ... absolute position of the page contents within the |
| index |
| <entry count> ... number of offset entries in the page. |
| Must match <header>.<page size> unless this is |
| the last page for the respective revision. |
| <size> ... length in bytes of the on-disk page description. |
| Note that this is redundant with the <offset>. |
| |
| page: |
| |
| <entry count> ... number of offset entries in the page. |
| Must match <header>.<page size> unless this is |
| the last page for the respective revision. |
| Redundant with <page table>.<entry count> |
| <offsets> ... array of absolute file positions within the rev / |
| pack file. This has <entry count> entries. |
| |
| |
| Index on-disk format |
| -------------------- |
| |
| index := "L2P-INDEX\n" header revisions pages offsets |
| |
| header := u(<header>.<first revision>) \ |
| u(<header>.<page size>) \ |
| u(<header>.<revision count>) \ |
| u(s(<header>.<page table>)) |
| |
| revisions := u( <header>.<page table index>[k+1] |
| - <header>.<page table index>[k]), |
| for k in 0 .. <header>.<revision count>-1 |
| |
| pages := u(<header>.<page table>[k].<size>) \ |
| u(<header>.<page table>[k].<entry count>), |
| for k in 0 .. s(<header>.<page table>)-1 |
| |
| offsets := page(k), |
| for k in 0 .. s(<header>.<page table>)-1 |
| |
| page(k) := i(<header>.<page table>[k].<offsets>[0]) \ |
| i( <header>.<page table>[k].<offsets>[l] \ |
| - <header>.<page table>[k].<offsets>[l - 1]), |
| for l in 1 .. s(<header>.<page table>[k].<entry count>)-1 |
| |
| u(x) ... unsigned int x in 7b/8b encoding |
| i(x) ... signed int x in 7b/8b encoding |
| s(x) ... number of entries in array x |
| |
| |
| Proto index file format |
| ----------------------- |
| |
| The index will be created from a "revision-less" proto index file |
| containing (<offset><item_index>) pairs only. |
| |
| All mappings belonging to the same revision must be written in one go but |
| there is no restriction on the order of those entries. To signify that |
| a new revision begins, a (0, 0) mapping must be written. A (0, 0) entry |
| at the beginning of the file is optional and will be ignored. |
| |
| <bof> /* begin of proto index file for revision r and following */ |
| (0, 0) /* mark start of revision r, optional for first rev */ |
| (off, item)* /* zero or more mappings in random order */ |
| (0, 0) /* mark start of revision r + 1 */ |
| (off, item)* /* zero or more mappings in random order */ |
| (0, 0) /* mark start of revision r + 2 */ |
| (off, item)* /* zero or more mappings in random order */ |
| ... |
| <eof> /* end of file. */ |
| |
| All entries are pairs of 64 bit unsigned integers in little endian order. |
| |
| |
| Phys-to-log index |
| ================= |
| |
| This index has to map offset -> (rev, item_index, type, len, checksum). |
| |
| |
| Index data model |
| ---------------- |
| |
| hierarchy: |
| |
| header -> page -> item info |
| |
| Logically, the index splits up index rev / pack file into pages of a |
| fixed size. That page size may differ from the FS's block size. The |
| index will describe each rev / pack file page with one index page. |
| |
| page = header->pages[offset % page_size]; |
| item info = binary_search(page.data, offset) |
| |
| Note that the current implementation will not return any data if the |
| offset is does not match any actual item start. To simplify the lookup, |
| the last index page will have an "unused item" entry for the section |
| behind EOF. Holes aren't allowed as well, i.e. every byte of the rev / |
| pack is expected to be covered by the index. |
| |
| Also, there may be items stretching across page borders or even over |
| multiple pages. The data model solves this issue by storing the item |
| descriptions as a "primary array" and then representing the pages as |
| ranges within that array. Thus multiple pages may reference the same |
| item description. |
| |
| header: |
| |
| <first revision> ... first revision covered by this index |
| <file size> ... size of the rev / pack file in bytes |
| <page size> ... number of bytes in the rev / pack file covered by |
| each index page |
| <page count> ... number of pages |
| <offsets> ... array of page offsets, i.e. locations the page |
| data within the index. |
| This array has <page count> + 1 entries. |
| |
| page: |
| |
| <entries> ... array of item descriptions, ordered by offset. |
| First and last entry may cross page boundaries. |
| |
| entry: |
| |
| <offset> ... absolute position in the pack / rev file |
| <size> ... on-disk size of the item in the pack / rev file |
| <type> ... item type |
| <FNV checksum> ... modified 32 bit FNV-1a checksum of that section |
| of the pack / rev file (see below). 0 for empty |
| or zero-length items |
| <revision> ... revision that this item belongs to |
| <item_index> ... item_index within that revision |
| |
| |
| Index on-disk format |
| -------------------- |
| |
| index := "P2L-INDEX\n" header pages items |
| |
| header := u(<header>.<first revision>) \ |
| u(<header>.<file size>) \ |
| u(<header>.<page size>) \ |
| u(<header>.<page count>) |
| |
| pages := u(<header>.<offsets>[k+1] - <header>.<offsets>[k]), |
| for k in 0 .. <header>.<page count> -1 |
| |
| items := u(<items in page k>[0].<offset>) \ |
| u(<items in page k>[l].<size>) \ |
| i(c(<items in page k>[l]) - c(<items of page k>[l-1])) \ |
| i( <items in page k>[l].<revision> |
| - <items in page k>[l-1].<revision>), \ |
| u(FNV checksum) |
| for l in 0 .. s(<items in page k>)-1, |
| for k in 0 .. <header>.<page count>-1 |
| |
| u(x) ... unsigned int x in 7b/8b encoding |
| i(x) ... signed int x in 7b/8b encoding |
| s(x) ... number of entries in collection x |
| c(x) ... compound function := x.<item_index> * 8 + x.<type> |
| |
| Access to negative indexes gives a 0 value. |
| |
| <Items in page k> are in strict ascending offset order. Items that |
| started after the begin of a given page and overlap with the next page |
| will not be stored in the start page. The runtime representation will |
| duplicate items overlapping page boundaries; the on-disk representation |
| will not. Thus, pages inside large items will have zero entries on disk. |
| |
| |
| Proto index file format |
| ----------------------- |
| |
| The index will be created from a proto index file containing simple |
| instances of svn_fs_fs__p2l_entry_t with the following element order: |
| |
| item offset as uint64 |
| item size as uint64 |
| item type as uint64 |
| modified FNV1a checksum as uint64 |
| revision as uint64, with SVN_INVALID_REVNUM mapped to 0 |
| and revisions >= 0 stored as rev+1 |
| item index as uint64 |
| |
| All values are stored in little endian order. |
| |
| Page table and header information, except start revision and page size, |
| can easily be derived from that information. |
| |
| All entries must be written in strict offset order. Overlapping entries |
| are not allowed; zero-length items are. |
| |
| In transactions, the final revision number may not be known when writing |
| the proto index file (e.g. while still writing the proto rev file). Items |
| with revision set to SVN_INVALID_REVNUM will therefore be automatically |
| updated when creating the final index. This is possible in conjunction |
| with rev files but not for pack files. |
| |
| |
| FNV checksum |
| ------------ |
| |
| FNV-1a can be found here: http://www.isthe.com/chongo/tech/comp/fnv/ |
| For performance reasons we use a modified version: |
| |
| * split the input byte stream [b0 .. bN] into 4 sub-streams of equal |
| length and up to 3 remnants: |
| |
| [b0 b4 b8 ..], [b1 b5 b9 ..], [b2 b6 b10 ..], [b3 b7 b11 ..], [remnant] |
| |
| * calculate 32 bit FNV-1a checksums for the 4 substreams: |
| |
| h0 = fnv_1a([b0 b4 b8 ..]), ..., h3 = fnv_1a([b3 b7 b11 ..]) |
| |
| * concatenate the big endian representation of these checksums (4 bytes |
| each) plus the remnant of the original stream into a 16 to 19 byte long |
| intermediate: |
| |
| [i0 .. iK] = [big-endian(h0) ... big-endian(h3) remnant ], 16 <= K+1 <= 19 |
| |
| * fold the variable-length intermediate into a compact 32 bit checksum: |
| |
| FNV checksum = fnv_1a([i0 .. iK]) |
