diff options
Diffstat (limited to 'doc')
| -rw-r--r-- | doc/concepts/garbage.md | 110 | ||||
| -rw-r--r-- | doc/future-designs/large-blobs.md | 115 |
2 files changed, 110 insertions, 115 deletions
diff --git a/doc/concepts/garbage.md b/doc/concepts/garbage.md index 69594b1c..cca3f0f7 100644 --- a/doc/concepts/garbage.md +++ b/doc/concepts/garbage.md @@ -84,3 +84,113 @@ starve local garbage collection. Moreover, it should be noted that the actual removal of no-longer-needed files from the file system happens without any lock being held. Hence the disturbance of builds caused by garbage collection is small. + +Compactification as part of garbage collection +---------------------------------------------- + +When building locally, all intermediate artifacts end up in the +local CAS. Depending on the nature of the artifacts built, this +can include large ones (like disk images) that only differ in small +parts from the ones created in previous builds for a code base +with only small changes. In this way, the disk can fill up quite +quickly. Reclaiming this disk space by the described generation +rotation would limit how far the cache reaches back. Therefore, +large blobs are split in a content-defined way; when storing the +chunks the large blobs are composed of, duplicate blobs have to be +stored only once. + +### Large-objects CAS + +Large objects are stored in a separated from of CAS, +called large-objects CAS. It follows +the same generation regime as the regular CAS; more precisely, +next to the `casf`, `casx`, and `cast` two additional +entries are generated, `cas-large-f` and `cas-large-t`, where the +latter is only available in native mode (i.e., when trees are hashed +differently than blobs). + +The entries in the large-objects CAS are keyed by hash of the +large object and the value of an entry is the concatenation of the +hashes of the chunks the large object is composed of. An entry in +a large-object CAS promises +- that the chunks the large object is composed of are in the main + CAS, more precisely `casf` in the same generation, +- the concatenation of the specified chunks indeed gives the + requested object, +- if the object is a tree, the parts are also in the same generation, + in main or larger-object CAS, and +- the object is strictly larger than the maximal size a chunk + obtained by splitting can have. + +Here, the last promise avoids that chunks of a large object later +can be replaced by a large-object entry themselves. + +### Using objects from the large-objects CAS + +Whenever an object is not found in the main CAS, the large-objects +CAS is inspected. If found there, then, in this order, +- if the entry is not already in the youngest generation, the chunks + are promoted to the youngest generation, +- the object itself is spliced on disk in a temproary file, +- if the object is a tree, the parts are promoted to the youngest + generation (only necessary if the large-object entry was not + found in the youngest generation anyway), +- the large object is added to the respective main CAS, and finally +- the large-objects entry is added to the youngest generation (if + not already there). + +The promoting of the chunks ensures that they are already present +in the youngest generation at almost no storage cost, as promoting +is implemented using hard links. Therefore, the overhead of a later +splitting of that blob is minimal. + +### Blob splitting uses large-objects CAS as cache + +When `just execute` is asked to split an object, first the +large-objects CAS is inspected. If the entry is present in the +youngest generation, the answer is directly served from there; +if found in an older generation, it is served from there after +appropriate promotion (chunks; parts of the tree, if the object to +split was a tree; large-objects entry) to the youngest generation. + +When `just execute` actually performs a split and the object that +was to be splitted was larger than the maximal size of a chunk, +after having added the chunks to the main CAS, it will also write +a corresponding entry to the large-objects CAS. In this way, +subsequent requests for the same object can be served from there +without having to inspect the object again. + +Similarly, if a blob is split in order to be transferred to an +endpoint that supports blob-splicing, a corresponding entry is +added to the large-objects CAS (provided the original blob was +larger than the maximal size of a chunk, but we will transfer by +blob splice only for those objects anyway). + +### Compactification of a CAS generation + +During garbage collection, while already holding the exclusive +garbage-collection lock, the following compactification steps are +performed on the youngest generation before doing the generation +rotation. +- For every entry in the large-objects CAS the corresponding entries + in the main CAS are removed (for an entry in `cas-large-f` the + entries in both, `casf` and `casx` are removed, as files and + executable files are both hashed the same way, as blobs). +- For every entry in the main CAS that is larger than the + compactification threshold, the object is split, the chunks are + added to the main CAS, the list of chunks the object is composed + of is added to the large-objects CAS, and finally the object is + removed from the main CAS. +It should be noted that these steps do not modify the objects +that can be obtained from that CAS generation. In particular, all +invariants are kept. + +As compactification threshold we chose a fixed value larger than +the maximal size a chunk obtained from splitting can have. More +precisely, we take the maximal value where we still can transfer +a blob via `grpc` without having to use the streaming interface, +i.e, we chose 2MB. In this way, we already have correct blobs split +for transfer to an end point that supports blob splicing. + +The compactification step will also be carried out if the `--no-rotate` +option is given to `gc`. diff --git a/doc/future-designs/large-blobs.md b/doc/future-designs/large-blobs.md deleted file mode 100644 index 5c94f23b..00000000 --- a/doc/future-designs/large-blobs.md +++ /dev/null @@ -1,115 +0,0 @@ -# Handling of large blobs - -## Current situation and shortcomings - -When building locally, all intermediate artifacts end up in the -local CAS. Depending on the nature of the artifacts built, this -can include large ones (like disk images) that only differ in small -parts from the ones created in previous builds for a code base -with only small changes. In this way, the disk can fill up quite -quickly. Of course, space can always be reclaimed by `just gc`, -but that would limit how far the cache reaches back. - -## Proposed changes - -We propose to use the same solution that is already used for reducing -traffic when downloading large final artifacts for installing; there, -large blobs are split in a content-defined way and only chunks not -already known have to be transferred. Similarly, when storing the -chunks the large blobs are composed of, duplicate blobs have to be -stored only once. - -### New store: large-objects CAS - -A new form of CAS is added, called large-objects CAS. It follows -the same generation regime as the regular CAS; more precisely, -next to the already existing `casf`, `casx`, and `cast` two new -entries are generated, `cas-large-f` and `cas-large-t`, where the -latter is only available in native mode (i.e., when trees are hashed -differently than blobs). - -The entries in the large-objects CAS are keyed by hash of the -large object and the value of an entry is the concatenation of the -hashes of the chunks the large object is composed of. An entry in -a large-object CAS promises -- that the chunks the large object is composed of are in the main - CAS, more precisely `casf` in the same generation, -- the concatenation of the specified chunks indeed gives the - requested object, -- if the object is a tree, the parts are also in the same generation, - in main or larger-object CAS, and -- the object is strictly larger than the maximal size a chunk - obtained by splitting can have. - -Here, the last promise avoids that chunks of a large object later -can be replaced by a large-object entry themselves. - -### Using objects from the large-objects CAS - -Whenever an object is not found in the main CAS, the large-objects -CAS is inspected. If found there, then, in this order, -- if the entry is not already in the youngest generation, the chunks - are promoted to the youngest generation, -- the object itself is spliced on disk in a temproary file, -- if the object is a tree, the parts are promoted to the youngest - generation (only necessary if the large-object entry was not - found in the youngest generation anyway), -- the large object is added to the respective main CAS, and finally -- the large-objects entry is added to the youngest generation (if - not already there). - -The promoting of the chunks ensures that they are already present -in the youngest generation at almost no storage cost, as promoting -is implemented using hard links. Therefore, the overhead of a later -splitting of that blob is minimal. - -### Blob splitting uses large-objects CAS as cache - -When `just execute` is asked to split an object, first the -large-objects CAS is inspected. If the entry is present in the -youngest generation, the answer is directly served from there; -if found in an older generation, it is served from there after -appropriate promotion (chunks; parts of the tree, if the object to -split was a tree; large-objects entry) to the youngest generation. - -When `just execute` actually performs a split and the object that -was to be splitted was larger than the maximal size of a chunk, -after having added the chunks to the main CAS, it will also write -a corresponding entry to the large-objects CAS. In this way, -subsequent requests for the same object can be served from there -without having to inspect the object again. - -Similarly, if a blob is split in order to be transferred to an -endpoint that supports blob-splicing, a corresponding entry is -added to the large-objects CAS (provided the original blob was -larger than the maximal size of a chunk, but we will transfer by -blob splice only for those objects anyway). - -### Compactification of a CAS generation - -During garbage collection, while already holding the exclusive -garbage-collection lock, the following compactification steps are -performed on the youngest generation before doing the generation -rotation. -- For every entry in the large-objects CAS the corresponding entries - in the main CAS are removed (for an entry in `cas-large-f` the - entries in both, `casf` and `casx` are removed, as files and - executable files are both hashed the same way, as blobs). -- For every entry in the main CAS that is larger than the - compactification threshold, the object is split, the chunks are - added to the main CAS, the list of chunks the object is composed - of is added to the large-objects CAS, and finally the object is - removed from the main CAS. -It should be noted that these steps do not modify the objects -that can be obtained from that CAS generation. In particular, all -invariants are kept. - -As compactification threshold we chose a fixed value larger than -the maximal size a chunk obtained from splitting can have. More -precisely, we take the maximal value where we still can transfer -a blob via `grpc` without having to use the streaming interface, -i.e, we chose 2MB. In this way, we already have correct blobs split -for transfer to an end point that supports blob splicing. - -The compactification step will also be carried out if the `--no-rotate` -option is given to `gc`. |