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