2 TODO (see also DONE section below)
3 ==================================
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).
14 Checksum all metadata elements
15 ------------------------------
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
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.
27 'svnadmin verify' shall check consistency based on those checksums.
30 Port existing FSFS tools
31 ------------------------
33 fsfs-stats, fsfsverify.py and possibly others should have equivalents
37 Optimize data ordering during pack
38 ----------------------------------
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
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.
52 Version 2 shall introduce the following changes:
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
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.
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.
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.
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
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... */
88 Sorted binary directory representations
89 ---------------------------------------
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.
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.
101 Moreover, switch from the key/value representation to a slightly tighter
102 and easier to process binary representation (validity is already guaranteed
109 Current implementation is incomplete. TODO: actually support & use base
110 representations, optimize instruction table.
112 Combine this with Txdelta 2 such that the corresponding windows from
113 all representations get stored in a common star-delta container.
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.
124 Open less files when opening a repository
125 -----------------------------------------
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, ...
130 Combine most of them into one or two files (eg uuid|format(|fs-type?),
131 current|min-unpacked-revprop).
134 Sharded transaction directories
135 -------------------------------
137 Transaction directories contain 3 OS files per FS file modified in the
138 transaction. That doesn't scale well; find something better.
144 Turn into separate FS
145 ---------------------
147 Make FS-X a separate file system alongside BDB and FSFS. Rip out all
148 FSFS compatibility code.
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
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.
165 Optimize data ordering during pack
166 ----------------------------------
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.
172 We will optimize on a per-shard basis. The general strategy is
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
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
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.
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.
216 Extend 'svnadmin verify'
217 ------------------------
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.
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.
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.
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).
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.
250 Packing will only be applied to binary representations of change lists
251 to keep the number of possible combinations low.
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.
264 Support for arbitrary chars in path names
265 -----------------------------------------
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.