TODO (see also DONE section below) ================================== Internal API cleanup -------------------- During refactoring, some functions had to be declared in header files to make them available to other fsfs code. We need to revisit those function definitions to turn them into a proper API that may be useful to other code (such as fsfs tools). Checksum all metadata elements ------------------------------ All elements of an FS-X repository shall be guarded by checksums. That includes indexes, noderevs etc. Larger data structures, such as index files, should have checksummed sub-elements such that corrupted parts may be identified and potentially repaired / circumvented in a meaningful way. Those checksums may be quite simple such as Adler32 because that meta- data can be cross-verified with other parts as well and acts only as a fallback to narrow down the affected parts. 'svnadmin verify' shall check consistency based on those checksums. Port existing FSFS tools ------------------------ fsfs-stats, fsfsverify.py and possibly others should have equivalents in the FS-X world. Optimize data ordering during pack ---------------------------------- I/O optimized copy algorithms are yet to be implemented. The current code is relatively slow as it performs quasi-random I/O on the input stream. TxDelta v2 ---------- Version 1 of txdelta turns out to be limited in its effectiveness for larger files when data gets inserted or removed. For typical office documents (zip files), deltification often becomes ineffective. Version 2 shall introduce the following changes: - increase the delta window from 100kB to 1MB - use a sliding window instead of a fixed-sized one - use a slightly more efficient instruction encoding When introducing it, we will make it an option at the txdelta interfaces (e.g. a format number). The version will be indicated in the 'SVN\x1' / 'SVN\x2' stream header. While at it, (try to) fix the layering violations where those prefixes are being read or written. Large file storage ------------------ Even most source code repositories contain large, hard to compress, hard to deltify binaries. Reconstructing their content becomes very I/O intense and it "dilutes" the data in our pack files. The latter makes e.g. caching, prefetching and packing less efficient. Once a representation exceeds a certain configured threshold (16M default), the fulltext of that item will be stored in a separate file. This will be marked in the representation_t by an extra flag and future reps will not be deltified against it. From that location, the data can be forwarded directly via SendFile and the fulltext caches will not be used for it. Note that by making the decision contingent upon the size of the deltified and packed representation, all large data that benefit from these (i.e. have smaller increments) will still be stored within the rev and pack files. If a future representation is smaller than the threshold, it may be /* danielsh: so if we have a file which is 20MB over many revisions, it'll be stored in fulltext every single time unless the configured threshold is changed? Wondering if that's the best solution... */ Sorted binary directory representations --------------------------------------- Lookup of entries in a directory is a frequent operation when following cached paths. The represents directories as arrays sorted by entry name to allow for binary search during that lookup. However, all external representation uses hashes and the conversion is expensive. FS-X shall store directory representations sorted by element names and all use that array representation internally wherever appropriate. This will minimize the conversion overhead for long directories, especially during transaction building. Moreover, switch from the key/value representation to a slightly tighter and easier to process binary representation (validity is already guaranteed by checksums). Star-Deltification ------------------ Current implementation is incomplete. TODO: actually support & use base representations, optimize instruction table. Combine this with Txdelta 2 such that the corresponding windows from all representations get stored in a common star-delta container. Multiple pack stages -------------------- FSFS only knows one packing level - the shard. For repositories with a large number of revisions, it may be more efficient to start with small packs (10-ish) and later pack them into larger and larger ones. Open less files when opening a repository ----------------------------------------- Opening a repository reads numerous files in db/ (besides several more in ../conf): uuid, current, format, fs-type, fsfs.conf, min-unpacked-rev, ... Combine most of them into one or two files (eg uuid|format(|fs-type?), current|min-unpacked-revprop). Sharded transaction directories ------------------------------- Transaction directories contain 3 OS files per FS file modified in the transaction. That doesn't scale well; find something better. DONE ==== Turn into separate FS --------------------- Make FS-X a separate file system alongside BDB and FSFS. Rip out all FSFS compatibility code. Logical addressing ------------------ To allow for moving data structures around within the repository, we must replace the current absolute addressing using file offsets with a logical one. All references will no take the form of (revision, index) pairs and a replacement to the format 6 manifest files will map that to actual file offsets. Having the need to map revision-local offsets to pack-file global offsets today already gives us some localized address mapping code that simply needs to be replaced. Optimize data ordering during pack ---------------------------------- Replace today's simple concatenating shard packing process with a one placing fragments (representations and noderevs) from various revisions close to each other if they are likely needed to serve in the same request. We will optimize on a per-shard basis. The general strategy is * place all change lists at the beginning of the pack file - strict revision order - place newest ones first * place all file properties reps next - place newer reps first * place all directory properties next - place newer reps first * place all root nodes and root directories - ordered newest rev -> oldest rev - place rep delta chains 'en block' - place root node in front of rep, if that rep has not already been placed as part of a rep delta chain * place remaining content as follows: - place node rev directly in front of their reps (where they have one) - start with the latest root directory not placed, yet - recurse to sub-folders first with, sorted by name - per folder, place files in naming order - place rep deltification chains in deltification order (new->old) * no fragments should be left but if they are, put them at the end Index pack files ---------------- In addition to the manifest we need for the (revision, index) -> offset mapping, we also introduce an offset -> (revision, index, type) index file. This will allow us to parse any data in a pack file without walking the DAG top down. Data prefetch ------------- This builds on the previous. The idea is that whenever a cache lookup fails, we will not just read the single missing fragment but parse all data within the APR file buffer and put that into the cache. For maximum efficiency, we will align the data blocks being read to multiples of the block size and allow that buffer size to be configured (where supported by APR). The default block size will be raised to 64kB. Extend 'svnadmin verify' ------------------------ Format 7 provides many extra chances to verify contents plus contains extra indexes that must be consistent with the pack / rev files. We must extend the tests to cover all that. Containers ---------- Extend the index format support containers, i.e. map a logical item index to (file offset, sub-index) pairs. The whole container will be read and cached and the specific item later accessed from the whole structure. Use these containers for reps, noderevs and changes. Provide specific data container types for each of these item types and different item types cannot be put into the same container. Containers are binaries, i.e. there is no textual representations of their contents. This allows for significant space savings on disk due to deltification amongst e.g. revprops. More importantly, it reduces the size of the runtime data structures within the cache *and* reduces the number of cache entries (the cache is can't handle items < 500 bytes very well). Packed change lists ------------------- Change lists tend to be large, in some cases >20% of the repo. Due to the new ordering of pack data, the change lists can be the largest part of data to read for svn log. Use our standard compression method to save 70 .. 80% of the disk space. Packing will only be applied to binary representations of change lists to keep the number of possible combinations low. Star-Deltification ------------------ Most node contents are smaller than 500k, i.e. less than Txdelta 2 window. Those contents shall be aggregated into star-delta containers upon pack. This will save significant amounts of disk space, particularly in case of heavy branching. Also, the data extraction is independent of the number of deltas, i.e. delta chain length) within the same container. Support for arbitrary chars in path names ----------------------------------------- FSFS's textual item representations breaks when path names contain newlines. FS-X revisions shall escape all control chars (e.g. < 0x20) in path names when using them in textual item representations.