1 % public-inbox developer manual
5 public-inbox-v2-format - structure of public inbox v2 archives
9 The v2 format is designed primarily to address several
10 scalability problems of the original format described at
11 L<public-inbox-v1-format(5)>. It also handles messages with
16 The key change in v2 is the inbox is no longer a bare git
17 repository, but a directory with two or more git repositories.
18 v2 divides git repositories by time "epochs" and Xapian
19 databases for parallelism by "shards".
21 =head2 INBOX OVERVIEW AND DEFINITIONS
23 $EPOCH - Integer starting with 0 based on time
24 $SCHEMA_VERSION - DB schema version (for Xapian)
25 $SHARD - Integer starting with 0 based on parallelism
27 foo/ # "foo" is the name of the inbox
28 - inbox.lock # lock file to protect global state
29 - git/$EPOCH.git # normal git repositories
30 - all.git # empty, alternates to $EPOCH.git
31 - xap$SCHEMA_VERSION/$SHARD # per-shard Xapian DB
32 - xap$SCHEMA_VERSION/over.sqlite3 # OVER-view DB for NNTP, threading
33 - msgmap.sqlite3 # same the v1 msgmap
35 For blob lookups, the reader only needs to open the "all.git"
36 repository with $GIT_DIR/objects/info/alternates which references
37 every $EPOCH.git repo.
39 Individual $EPOCH.git repos DO NOT use alternates themselves as
40 git currently limits recursion of alternates nesting depth to 5.
44 One of the inherent scalability problems with git itself is the
45 full history of a project must be stored and carried around to
46 all clients. To address this problem, the v2 format uses
47 multiple git repositories, stored as time-based "epochs".
49 We currently divide epochs into roughly one gigabyte segments;
50 but this size can be configurable (if needed) in the future.
52 A pleasant side-effect of this design is the git packs of older
53 epochs are stable, allowing them to be cloned without requiring
54 expensive pack generation. This also allows clients to clone
55 only the epochs they are interested in to save bandwidth and
58 To minimize changes to existing v1-based code and simplify our
59 code, we use the "alternates" mechanism described in
60 L<gitrepository-layout(5)> to link all the epoch repositories
61 with a single read-only "all.git" endpoint.
63 Processes retrieve blobs via the "all.git" repository, while
64 writers write blobs directly to epochs.
66 =head2 GIT TREE LAYOUT
68 One key problem specific to v1 was large trees were frequently a
69 performance problem as name lookups are expensive and there were
70 limited deltafication opportunities with unpredictable file
71 names. As a result, all Xapian-enabled installations retrieve
72 blob object_ids directly in v1, bypassing tree lookups.
74 While dividing git repositories into epochs caps the growth of
75 trees, worst-case tree size was still unnecessary overhead and
78 So in contrast to the big trees of v1, the v2 git tree contains
79 only a single file at the top-level of the tree, either 'm' (for
80 'mail' or 'message') or 'd' (for deleted). A tree does not have
81 'm' and 'd' at the same time.
83 Mail is still stored in blobs (instead of inline with the commit
84 object) as we still need a stable reference in the indices in
85 case commit history is rewritten to comply with legal
88 After-the-fact invocations of L<public-inbox-index> will ignore
89 messages written to 'd' after they are written to 'm'.
91 Deltafication is not significantly improved over v1, but overall
92 storage for trees is made as as small as possible. Initial
93 statistics and benchmarks showing the benefits of this approach
96 L<https://public-inbox.org/meta/20180209205140.GA11047@dcvr/>
100 Another second scalability problem in v1 was the inability to
101 utilize multiple CPU cores for Xapian indexing. This is
102 addressed by using shards in Xapian to perform import
103 indexing in parallel.
105 As with git alternates, Xapian natively supports a read-only
106 interface which transparently abstracts away the knowledge of
107 multiple shards. This allows us to simplify our read-only
110 The performance of the storage device is now the bottleneck on
111 larger multi-core systems. In our experience, performance is
112 improved with high-quality and high-quantity solid-state storage.
113 Issuing TRIM commands with L<fstrim(8)> was necessary to maintain
114 consistent performance while developing this feature.
116 Rotational storage devices perform significantly worse than
117 solid state storage for indexing of large mail archives; but are
118 fine for backup and usable for small instances.
120 As of public-inbox 1.6.0, the C<publicInbox.indexSequentialShard>
121 option of L<public-inbox-index(1)> may be used with a high shard
122 count to ensure individual shards fit into page cache when the entire
125 Our use of the L</OVERVIEW DB> requires Xapian document IDs to
126 remain stable. Using L<public-inbox-compact(1)> and
127 L<public-inbox-xcpdb(1)> wrappers are recommended over tools
132 Towards the end of v2 development, it became apparent Xapian did
133 not perform well for sorting large result sets used to generate
134 the landing page in the PSGI UI (/$INBOX/) or many queries used
135 by the NNTP server. Thus, SQLite was employed and the Xapian
136 "skeleton" DB was renamed to the "overview" DB (after the NNTP
137 OVER/XOVER commands).
139 The overview DB maintains all the header information necessary
140 to implement the NNTP OVER/XOVER commands and non-search
141 endpoints of the PSGI UI.
143 Xapian has become completely optional for v2 (as it is for v1), but
144 SQLite remains required for v2. SQLite turns out to be powerful
145 enough to maintain overview information. Most of the PSGI and all
146 of the NNTP functionality is possible with only SQLite in addition
149 The overview DB was an instrumental piece in maintaining near
150 constant-time read performance on a dataset 2-3 times larger
151 than LKML history as of 2018.
153 =head3 GHOST MESSAGES
155 The overview DB also includes references to "ghost" messages,
156 or messages which have replies but have not been seen by us.
157 Thus it is expected to have more rows than the "msgmap" DB
160 =head2 msgmap.sqlite3
162 The SQLite msgmap DB is unchanged from v1, but it is now at the
163 top-level of the directory.
165 =head1 OBJECT IDENTIFIERS
167 There are three distinct type of identifiers. content_hash is the
168 new one for v2 and should make message removal and deduplication
169 easier. object_id and Message-ID are already known.
175 The blob identifier git uses (currently SHA-1). No need to
176 publicly expose this outside of normal git ops (cloning) and
177 there's no need to make this searchable. As with v1 of
178 public-inbox, this is stored as part of the Xapian document so
179 expensive name lookups can be avoided for document retrieval.
183 The email header; duplicates allowed for archival purposes.
184 This remains a searchable field in Xapian. Note: it's possible
185 for emails to have multiple Message-ID headers (and L<git-send-email(1)>
186 had that bug for a bit); so we take all of them into account.
187 In case of conflicts detected by content_hash below, we generate a new
188 Message-ID based on content_hash; if the generated Message-ID still
189 conflicts, a random one is generated.
193 A hash of relevant headers and raw body content for
194 purging of unwanted content. This is not stored anywhere,
195 but always calculated on-the-fly.
197 For now, the relevant headers are:
199 Subject, From, Date, References, In-Reply-To, To, Cc
201 Received, List-Id, and similar headers are NOT part of content_hash as
202 they differ across lists and we will want removal to be able to cross
205 The textual parts of the body are decoded, CRLF normalized to
206 LF, and trailing whitespace stripped. Notably, hashing the
207 raw body risks being broken by list signatures; but we can use
208 filters (e.g. PublicInbox::Filter::Vger) to clean the body for
211 content_hash is SHA-256 for now; but can be changed at any time
212 without making DB changes.
218 L<flock(2)> locking exclusively locks the empty inbox.lock file
219 for all non-atomic operations.
223 Same handling as with v1, except the Message-ID header will
224 be generated if not provided or conflicting. "Bytes", "Lines"
225 and "Content-Length" headers are stripped and not allowed, they
226 can interfere with further processing.
228 The "Status" mbox header is also stripped as that header makes
229 no sense in a public archive.
233 Thanks to the Linux Foundation for sponsoring the development
234 and testing of the v2 format.
238 Copyright 2018-2021 all contributors L<mailto:meta@public-inbox.org>
240 License: AGPL-3.0+ L<http://www.gnu.org/licenses/agpl-3.0.txt>
244 L<gitrepository-layout(5)>, L<public-inbox-v1-format(5)>