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.
added
removed
subversion/libsvn_fs_x/TODO
