Documentation/public-inbox-v2-format.pod

   1 % public-inbox developer manual
   2
   3 =head1 NAME
   4
   5 public-inbox-v2-format - structure of public inbox v2 archives
   6
   7 =head1 DESCRIPTION
   8
   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
  12 Message-IDs.
  13
  14 =head1 INBOX LAYOUT
  15
  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".
  20
  21 =head2 INBOX OVERVIEW AND DEFINITIONS
  22
  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
  26
  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
  34
  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.
  38
  39 Individual $EPOCH.git repos DO NOT use alternates themselves as
  40 git currently limits recursion of alternates nesting depth to 5.
  41
  42 =head2 GIT EPOCHS
  43
  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".
  48
  49 We currently divide epochs into roughly one gigabyte segments;
  50 but this size can be configurable (if needed) in the future.
  51
  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
  56 storage.
  57
  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.
  62
  63 Processes retrieve blobs via the "all.git" repository, while
  64 writers write blobs directly to epochs.
  65
  66 =head2 GIT TREE LAYOUT
  67
  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.
  73
  74 While dividing git repositories into epochs caps the growth of
  75 trees, worst-case tree size was still unnecessary overhead and
  76 worth eliminating.
  77
  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.
  82
  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
  86 requirements.
  87
  88 After-the-fact invocations of L<public-inbox-index> will ignore
  89 messages written to 'd' after they are written to 'm'.
  90
  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
  94 are documented at:
  95
  96 L<https://public-inbox.org/meta/20180209205140.GA11047@dcvr/>
  97
  98 =head2 XAPIAN SHARDS
  99
 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.
 104
 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
 108 code paths.
 109
 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.
 115
 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.
 119
 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
 123 Xapian DB cannot.
 124
 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
 128 provided by Xapian.
 129
 130 =head2 OVERVIEW DB
 131
 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).
 138
 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.
 142
 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
 147 to git.
 148
 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.
 152
 153 =head3 GHOST MESSAGES
 154
 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
 158 described below.
 159
 160 =head2 msgmap.sqlite3
 161
 162 The SQLite msgmap DB is unchanged from v1, but it is now at the
 163 top-level of the directory.
 164
 165 =head1 OBJECT IDENTIFIERS
 166
 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.
 170
 171 =over
 172
 173 =item object_id
 174
 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.
 180
 181 =item Message-ID
 182
 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.
 190
 191 =item content_hash
 192
 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.
 196
 197 For now, the relevant headers are:
 198
 199         Subject, From, Date, References, In-Reply-To, To, Cc
 200
 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
 203 lists.
 204
 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
 209 imports.
 210
 211 content_hash is SHA-256 for now; but can be changed at any time
 212 without making DB changes.
 213
 214 =back
 215
 216 =head1 LOCKING
 217
 218 L<flock(2)> locking exclusively locks the empty inbox.lock file
 219 for all non-atomic operations.
 220
 221 =head1 HEADERS
 222
 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.
 227
 228 The "Status" mbox header is also stripped as that header makes
 229 no sense in a public archive.
 230
 231 =head1 THANKS
 232
 233 Thanks to the Linux Foundation for sponsoring the development
 234 and testing of the v2 format.
 235
 236 =head1 COPYRIGHT
 237
 238 Copyright 2018-2021 all contributors L<mailto:meta@public-inbox.org>
 239
 240 License: AGPL-3.0+ L<http://www.gnu.org/licenses/agpl-3.0.txt>
 241
 242 =head1 SEE ALSO
 243
 244 L<gitrepository-layout(5)>, L<public-inbox-v1-format(5)>