contrib/subversion/subversion/libsvn_fs_x/TODO

   1
   2 TODO (see also DONE section below)
   3 ==================================
   4
   5 Internal API cleanup
   6 --------------------
   7
   8 During refactoring, some functions had to be declared in header files
   9 to make them available to other fsfs code.  We need to revisit those
  10 function definitions to turn them into a proper API that may be useful
  11 to other code (such as fsfs tools).
  12
  13
  14 Checksum all metadata elements
  15 ------------------------------
  16
  17 All elements of an FS-X repository shall be guarded by checksums. That
  18 includes indexes, noderevs etc.  Larger data structures, such as index
  19 files, should have checksummed sub-elements such that corrupted parts
  20 may be identified and potentially repaired / circumvented in a meaningful
  21 way.
  22
  23 Those checksums may be quite simple such as Adler32 because that meta-
  24 data can be cross-verified with other parts as well and acts only as a
  25 fallback to narrow down the affected parts.
  26
  27 'svnadmin verify' shall check consistency based on those checksums.
  28
  29
  30 Port existing FSFS tools
  31 ------------------------
  32
  33 fsfs-stats, fsfsverify.py and possibly others should have equivalents
  34 in the FS-X world.
  35
  36
  37 Optimize data ordering during pack
  38 ----------------------------------
  39
  40 I/O optimized copy algorithms are yet to be implemented.  The current
  41 code is relatively slow as it performs quasi-random I/O on the
  42 input stream.
  43
  44
  45 TxDelta v2
  46 ----------
  47
  48 Version 1 of txdelta turns out to be limited in its effectiveness for
  49 larger files when data gets inserted or removed.  For typical office
  50 documents (zip files), deltification often becomes ineffective.
  51
  52 Version 2 shall introduce the following changes:
  53
  54 - increase the delta window from 100kB to 1MB
  55 - use a sliding window instead of a fixed-sized one
  56 - use a slightly more efficient instruction encoding
  57
  58 When introducing it,  we will make it an option at the txdelta interfaces
  59 (e.g. a format number).  The version will be indicated in the 'SVN\x1' /
  60 'SVN\x2' stream header.  While at it, (try to) fix the layering violations
  61 where those prefixes are being read or written.
  62
  63
  64 Large file storage
  65 ------------------
  66
  67 Even most source code repositories contain large, hard to compress,
  68 hard to deltify binaries.  Reconstructing their content becomes very I/O
  69 intense and it "dilutes" the data in our pack files.  The latter makes
  70 e.g. caching, prefetching and packing less efficient.
  71
  72 Once a representation exceeds a certain configured threshold (16M default),
  73 the fulltext of that item will be stored in a separate file.  This will
  74 be marked in the representation_t by an extra flag and future reps will
  75 not be deltified against it.  From that location, the data can be forwarded
  76 directly via SendFile and the fulltext caches will not be used for it.
  77
  78 Note that by making the decision contingent upon the size of the deltified
  79 and packed representation,  all large data that benefit from these (i.e.
  80 have smaller increments) will still be stored within the rev and pack files.
  81 If a future representation is smaller than the threshold, it may be
  82
  83 /* danielsh: so if we have a file which is 20MB over many revisions, it'll
  84 be stored in fulltext every single time unless the configured threshold is
  85 changed?  Wondering if that's the best solution... */
  86
  87
  88 Sorted binary directory representations
  89 ---------------------------------------
  90
  91 Lookup of entries in a directory is a frequent operation when following
  92 cached paths.  The represents directories as arrays sorted by entry name
  93 to allow for binary search during that lookup.  However, all external
  94 representation uses hashes and the conversion is expensive.
  95
  96 FS-X shall store directory representations sorted by element names and
  97 all use that array representation internally wherever appropriate.  This
  98 will minimize the conversion overhead for long directories, especially
  99 during transaction building.
 100
 101 Moreover, switch from the key/value representation to a slightly tighter
 102 and easier to process binary representation (validity is already guaranteed
 103 by checksums).
 104
 105
 106 Star-Deltification
 107 ------------------
 108
 109 Current implementation is incomplete. TODO: actually support & use base
 110 representations, optimize instruction table.
 111
 112 Combine this with Txdelta 2 such that the corresponding windows from
 113 all representations get stored in a common star-delta container.
 114
 115
 116 Multiple pack stages
 117 --------------------
 118
 119 FSFS only knows one packing level - the shard.  For repositories with
 120 a large number of revisions, it may be more efficient to start with small
 121 packs (10-ish) and later pack them into larger and larger ones.
 122
 123
 124 Open less files when opening a repository
 125 -----------------------------------------
 126
 127 Opening a repository reads numerous files in db/ (besides several more in
 128 ../conf): uuid, current, format, fs-type, fsfs.conf, min-unpacked-rev, ...
 129
 130 Combine most of them into one or two files (eg uuid|format(|fs-type?),
 131 current|min-unpacked-revprop).
 132
 133
 134 Sharded transaction directories
 135 -------------------------------
 136
 137 Transaction directories contain 3 OS files per FS file modified in the
 138 transaction.  That doesn't scale well; find something better.
 139
 140
 141 DONE
 142 ====
 143
 144 Turn into separate FS
 145 ---------------------
 146
 147 Make FS-X a separate file system alongside BDB and FSFS.  Rip out all
 148 FSFS compatibility code.
 149
 150
 151 Logical addressing
 152 ------------------
 153
 154 To allow for moving data structures around within the repository, we must
 155 replace the current absolute addressing using file offsets with a logical
 156 one.  All references will no take the form of (revision, index) pairs and
 157 a replacement to the format 6 manifest files will map that to actual file
 158 offsets.
 159
 160 Having the need to map revision-local offsets to pack-file global offsets
 161 today already gives us some localized address mapping code that simply
 162 needs to be replaced.
 163
 164
 165 Optimize data ordering during pack
 166 ----------------------------------
 167
 168 Replace today's simple concatenating shard packing process with a one
 169 placing fragments (representations and noderevs) from various revisions
 170 close to each other if they are likely needed to serve in the same request.
 171
 172 We will optimize on a per-shard basis.  The general strategy is
 173
 174 * place all change lists at the beginning of the pack file
 175   - strict revision order
 176   - place newest ones first
 177 * place all file properties reps next
 178   - place newer reps first
 179 * place all directory properties next
 180   - place newer reps first
 181 * place all root nodes and root directories
 182   - ordered newest rev -> oldest rev
 183   - place rep delta chains 'en block'
 184   - place root node in front of rep, if that rep has not already
 185     been placed as part of a rep delta chain
 186 * place remaining content as follows:
 187   - place node rev directly in front of their reps (where they have one)
 188   - start with the latest root directory not placed, yet
 189   - recurse to sub-folders first with, sorted by name
 190   - per folder, place files in naming order
 191   - place rep deltification chains in deltification order (new->old)
 192 * no fragments should be left but if they are, put them at the end
 193
 194
 195 Index pack files
 196 ----------------
 197
 198 In addition to the manifest we need for the (revision, index) -> offset
 199 mapping, we also introduce an offset -> (revision, index, type) index
 200 file.  This will allow us to parse any data in a pack file without walking
 201 the DAG top down.
 202
 203
 204 Data prefetch
 205 -------------
 206
 207 This builds on the previous.  The idea is that whenever a cache lookup
 208 fails,  we will not just read the single missing fragment but parse all
 209 data within the APR file buffer and put that into the cache.
 210
 211 For maximum efficiency,  we will align the data blocks being read to
 212 multiples of the block size and allow that buffer size to be configured
 213 (where supported by APR).  The default block size will be raised to 64kB.
 214
 215
 216 Extend 'svnadmin verify'
 217 ------------------------
 218
 219 Format 7 provides many extra chances to verify contents plus contains
 220 extra indexes that must be consistent with the pack / rev files.  We
 221 must extend the tests to cover all that.
 222
 223
 224 Containers
 225 ----------
 226
 227 Extend the index format support containers, i.e. map a logical item index
 228 to (file offset, sub-index) pairs.  The whole container will be read and
 229 cached and the specific item later accessed from the whole structure.
 230
 231 Use these containers for reps, noderevs and changes.  Provide specific
 232 data container types for each of these item types and different item
 233 types cannot be put into the same container.  Containers are binaries,
 234 i.e. there is no textual representations of their contents.
 235
 236 This allows for significant space savings on disk due to deltification
 237 amongst e.g. revprops.  More importantly, it reduces the size of the
 238 runtime data structures within the cache *and* reduces the number of
 239 cache entries (the cache is can't handle items < 500 bytes very well).
 240
 241
 242 Packed change lists
 243 -------------------
 244
 245 Change lists tend to be large, in some cases >20% of the repo.  Due to the
 246 new ordering of pack data,  the change lists can be the largest part of
 247 data to read for svn log.  Use our standard compression method to save
 248 70 .. 80% of the disk space.
 249
 250 Packing will only be applied to binary representations of change lists
 251 to keep the number of possible combinations low.
 252
 253
 254 Star-Deltification
 255 ------------------
 256
 257 Most node contents are smaller than 500k, i.e. less than Txdelta 2 window.
 258 Those contents shall be aggregated into star-delta containers upon pack.
 259 This will save significant amounts of disk space, particularly in case
 260 of heavy branching.  Also, the data extraction is independent of the
 261 number of deltas, i.e. delta chain length) within the same container.
 262
 263
 264 Support for arbitrary chars in path names
 265 -----------------------------------------
 266
 267 FSFS's textual item representations breaks when path names contain
 268 newlines.  FS-X revisions shall escape all control chars (e.g. < 0x20)
 269 in path names when using them in textual item representations.
 270