Documentation/public-inbox-v2-format.pod

   1 % public-inbox developer manual
   2
   3 =head1 NAME
   4
   5 public-inbox v2 repository description
   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 are NOT recommended for indexing of
 117 large mail archives; but are fine for backup and usable for
 118 small instances.
 119
 120 Our use of the L</OVERVIEW DB> requires Xapian document IDs to
 121 remain stable.  Using L<public-inbox-compact(1)> and
 122 L<public-inbox-xcpdb(1)> wrappers are recommended over tools
 123 provided by Xapian.
 124
 125 =head2 OVERVIEW DB
 126
 127 Towards the end of v2 development, it became apparent Xapian did
 128 not perform well for sorting large result sets used to generate
 129 the landing page in the PSGI UI (/$INBOX/) or many queries used
 130 by the NNTP server.  Thus, SQLite was employed and the Xapian
 131 "skeleton" DB was renamed to the "overview" DB (after the NNTP
 132 OVER/XOVER commands).
 133
 134 The overview DB maintains all the header information necessary
 135 to implement the NNTP OVER/XOVER commands and non-search
 136 endpoints of of the PSGI UI.
 137
 138 Xapian has become completely optional for v2 (as it is for v1), but
 139 SQLite remains required for v2.  SQLite turns out to be powerful
 140 enough to maintain overview information.  Most of the PSGI and all
 141 of the NNTP functionality is possible with only SQLite in addition
 142 to git.
 143
 144 The overview DB was an instrumental piece in maintaining near
 145 constant-time read performance on a dataset 2-3 times larger
 146 than LKML history as of 2018.
 147
 148 =head3 GHOST MESSAGES
 149
 150 The overview DB also includes references to "ghost" messages,
 151 or messages which have replies but have not been seen by us.
 152 Thus it is expected to have more rows than the "msgmap" DB
 153 described below.
 154
 155 =head2 msgmap.sqlite3
 156
 157 The SQLite msgmap DB is unchanged from v1, but it is now at the
 158 top-level of the directory.
 159
 160 =head1 OBJECT IDENTIFIERS
 161
 162 There are three distinct type of identifiers.  content_id is the
 163 new one for v2 and should make message removal and deduplication
 164 easier.  object_id and Message-ID are already known.
 165
 166 =over
 167
 168 =item object_id
 169
 170 The blob identifier git uses (currently SHA-1).  No need to
 171 publicly expose this outside of normal git ops (cloning) and
 172 there's no need to make this searchable.  As with v1 of
 173 public-inbox, this is stored as part of the Xapian document so
 174 expensive name lookups can be avoided for document retrieval.
 175
 176 =item Message-ID
 177
 178 The email header; duplicates allowed for archival purposes.
 179 This remains a searchable field in Xapian.  Note: it's possible
 180 for emails to have multiple Message-ID headers (and L<git-send-email(1)>
 181 had that bug for a bit); so we take all of them into account.
 182 In case of conflicts detected by content_id below, we generate a new
 183 Message-ID based on content_id; if the generated Message-ID still
 184 conflicts, a random one is generated.
 185
 186 =item content_id
 187
 188 A hash of relevant headers and raw body content for
 189 purging of unwanted content.  This is not stored anywhere,
 190 but always calculated on-the-fly.
 191
 192 For now, the relevant headers are:
 193
 194         Subject, From, Date, References, In-Reply-To, To, Cc
 195
 196 Received, List-Id, and similar headers are NOT part of content_id as
 197 they differ across lists and we will want removal to be able to cross
 198 lists.
 199
 200 The textual parts of the body are decoded, CRLF normalized to
 201 LF, and trailing whitespace stripped.  Notably, hashing the
 202 raw body risks being broken by list signatures; but we can use
 203 filters (e.g. PublicInbox::Filter::Vger) to clean the body for
 204 imports.
 205
 206 content_id is SHA-256 for now; but can be changed at any time
 207 without making DB changes.
 208
 209 =back
 210
 211 =head1 LOCKING
 212
 213 L<flock(2)> locking exclusively locks the empty inbox.lock file
 214 for all non-atomic operations.
 215
 216 =head1 HEADERS
 217
 218 Same handling as with v1, except the Message-ID header will
 219 be generated if not provided or conflicting.  "Bytes", "Lines"
 220 and "Content-Length" headers are stripped and not allowed, they
 221 can interfere with further processing.
 222
 223 The "Status" mbox header is also stripped as that header makes
 224 no sense in a public archive.
 225
 226 =head1 THANKS
 227
 228 Thanks to the Linux Foundation for sponsoring the development
 229 and testing of the v2 repository format.
 230
 231 =head1 COPYRIGHT
 232
 233 Copyright 2018-2020 all contributors L<mailto:meta@public-inbox.org>
 234
 235 License: AGPL-3.0+ L<http://www.gnu.org/licenses/agpl-3.0.txt>
 236
 237 =head1 SEE ALSO
 238
 239 L<gitrepository-layout(5)>, L<public-inbox-v1-format(5)>