diff options
Diffstat (limited to 'doc/architecture/blueprints/object_pools/index.md')
| -rw-r--r-- | doc/architecture/blueprints/object_pools/index.md | 495 |
1 files changed, 495 insertions, 0 deletions
diff --git a/doc/architecture/blueprints/object_pools/index.md b/doc/architecture/blueprints/object_pools/index.md new file mode 100644 index 00000000000..3f3a0341e4a --- /dev/null +++ b/doc/architecture/blueprints/object_pools/index.md @@ -0,0 +1,495 @@ +--- +status: proposed +creation-date: "2023-03-30" +authors: [ "@pks-gitlab" ] +coach: [ ] +approvers: [ ] +owning-stage: "~devops::systems" +participating-stages: [ "~devops::create" ] +--- + +# Iterate on the design of object pools + +## Summary + +Forking repositories is at the heart of many modern workflows for projects +hosted in GitLab. As most of the objects between a fork and its upstream project +will typically be the same, this opens up potential for optimizations: + +- Creating forks can theoretically be lightning fast if we reuse much of the + parts of the upstream repository. + +- We can save on storage space by deduplicating objects which are shared. + +This architecture is currently implemented with object pools which hold objects +of the primary repository. But the design of object pools has organically grown +and is nowadays showing its limits. + +This blueprint explores how we can iterate on the design of object pools to fix +long standing issues with it. Furthermore, the intent is to arrive at a design +that lets us iterate more readily on the exact implementation details of object +pools. + +## Motivation + +The current design of object pools is showing problems with scalability in +various different ways. For a large part the problems come from the fact that +object pools have organically grown and that we learned as we went by. + +It is proving hard to fix the overall design of object pools because there is no +clear ownership. While Gitaly provides the low-level building blocks to make +them work, it does not have enough control over them to be able to iterate on +their implementation details. + +There are thus two major goals: taking ownership of object pools so that it +becomes easier to iterate on the design, and fixing scalability issues once we +can iterate. + +### Lifecycle ownership + +While Gitaly provides the interfaces to manage object pools, the actual life +cycle of them is controlled by the client. A typical lifecycle of an object pool +looks as following: + +1. An object pool is created via `CreateObjectPool()`. The caller provides the + path where the object pool shall be created as well as the origin repository + from which the repository shall be created. + +1. The origin repository needs to be linked to the object pool explicitly by + calling `LinkRepositoryToObjectPool()`. + +1. The object pool needs to be regularly updated via `FetchIntoObjectPool()` + that fetches all changes from the primary pool member into the object pool. + +1. To create forks, the client needs to call `CreateFork()` followed by + `LinkRepositoryToObjectPool()`. + +1. Repositories of forks are unlinked by calling `DisconnectGitAlternates()`. + This will reduplicate objects. + +1. The object pool is deleted via `DeleteObjectPool()`. + +This lifecycle is complex and leaks a lot of implementation details to the +caller. This was originally done in part to give the Rails side control and +management over Git object visibility. GitLab project visibility rules are +complex and not a Gitaly concern. By exposing these details Rails can control +when pool membership links are created and broken. It is not clear at the +current point in time how the complete system works and its limits are not +explicitly documented. + +In addition to the complexity of the lifecycle we also have multiple sources of +truth for pool membership. Gitaly never tracks the set of members of a pool +repository but can only tell for a specific repository that it is part of said +pool. Consequently, Rails is forced to maintain this information in a database, +but it is hard to maintain that information without becoming stale. + +### Repository maintenance + +Related to the lifecycle ownership issues is the issue of repository +maintenance. As mentioned, keeping an object pool up to date requires regular +calls to `FetchIntoObjectPool()`. This is leaking implementation details to the +client, but was done to give the client control over syncing the primary +repository with its object pool. With this control, private repositories can be +prevented from syncing and consquently leaking objects to other repositories in +the fork network. + +We have had good success with moving repository maintenance into Gitaly so that +clients do not need to know about on-disk details. Ideally, we would do the same +for repositories that are the primary member of an object pool: if we optimize +its on-disk state, we will also automatically update the object pool. + +There are two issues that keep us from doing so: + +- Gitaly does not know about the relationship between an object pool and its + members. + +- Updating object pools is expensive. + +By making Gitaly the single source of truth for object pool memberships we would +be in a position to fix both issues. + +### Fast forking + +In the current implementation, Rails first invokes `CreateFork()` which results +in a complete `git-clone(1)` being performed to generate the fork repository. +This is followed by `LinkRepositoryToObjectPool()` to link the fork with the +object pool. It is not until housekeeping is performed on the fork repository +that objects are deduplicated. This is not only leaking implementation details +to clients, but it also keeps us from reaping the full potential benefit of +object pools. + +In particular, creating forks is a lot slower than it could be since a clone is +always performed before linking. If the steps of creating the fork and linking +the fork to the pool repository were unified, the initial clone could be +avoided. + +### Clustered object pools + +Gitaly Cluster and object pools development overlapped. Consequently they are +known to not work well together. Praefect does neither ensure that repositories +with object pools have their object pools present on all nodes, nor does it +ensure that object pools are in a known state. If at all, object pools only work +by chance. + +The current state has led to cases where object pools were missing or had +different contents per node. This can result in inconsistently observed state in +object pool members and writes that depend on the object pool's contents to +fail. + +One way object pools might be handled for clustered Gitaly could be to have the +pool repositories duplicated on nodes that contain repositories dependent on +them. This would allow members of a fork network to exist of different nodes. To +make this work, repository replciation would have to be aware of object pools +and know when it needs to duplicate them onto a particular node. + +## Requirements + +There are a set of requirements and invariants that must be given for any +particular solution. + +### Private upstream repositories should not leak objects to forks + +When a project has a visibility setting that is not public, the objects in the +repository should not be fetched into an object pool. An object pool should only +ever contain objects from the upstream repository that were at one point public. +This prevents private upstream repositories from having objects leaked to forks +through a shared object pool. + +### Forks cannot sneak objects into upstream projects + +It should not be possible to make objects uploaded in a fork repository +accessible in the upstream repository via a shared object pool. Otherwise +potentially unauthorized users would be able to "sneak in" objects into +repositories by simply forking them. + +Despite leading to confusion, this could also serve as a mechanism to corrupt +upstream repositories by introducing objects that are known to be broken. + +### Object pool lifetime exceeds upstream repository lifetime + +If the upstream repository gets deleted, its object pool should remain in place +to provide continued deduplication of shared objects between the other +repositories in the fork network. Thus it can be said that the lifetime of the +object pool is longer than the lifetime of the upstream repository. An object +pool should only be deleted if there are no longer any repositories referencing +it. + +### Object lifetime + +By deduplicating objects in a fork network, repositories become dependent on the +object pool. Missing objects in the pooled repository could lead to corruption +of repositories in the fork network. Therefore, objects in the pooled repository +must continue to exist as long as there are repositories referencing them. + +Without a mechanism to accurately determine if a pooled object is referenenced +by one of more repositories, all objects in the pooled repository must remain. +Only when there are no repositories referencing the object pool can the pooled +repository, and therfore all its objects, be removed. + +### Object sharing + +An object that is deduplicated will become accessible from all forks of a +particular repository, even if it has never been reachable in any of the forks. +The consequence is that any write to an object pool immediately influences all +of its members. + +We need to be mindful of this property when repositories connected to an object +pool are replicated. As the user-observable state should be the same on all +replicas, we need to ensure that both the repository and its object pool are +consistent across the different nodes. + +## Proposal + +In the current design, management of object pools mostly happens on the client +side as they need to manage their complete lifecyclethem. This requires Rails to +store the object pool relationships in the Rails database, perform fine-grained +management of every single step of an object pool's life, and perform periodic +Sidekiq jobs to enforce state by calling idempotent Gitaly RPCs. This design +significantly increases complexity of an already-complex mechanism. + +Instead of handling the full lifecycle of object pools on the client-side, this +document proposes to instead encapsulate the object pool lifecycle management +inside of Gitaly. Instead of performing low-level actions to maintain object +pools, clients would only need to tell Gitaly about updated relationships +between a repository and its object pool. + +This brings us multiple advantages: + +- The inherent complexity of the lifecycle management is encapsulated in a + single place, namely Gitaly. + +- Gitaly is in a better position to iterate on the low-level technical design of + object pools in case we find a better solution compared to "alternates" in the + future. + +- We can ensure better interplay between Gitaly Cluster, object pools and + repository housekeeping. + +- Gitaly becomes the single source of truth for object pool relationships and + can thus start to manage it better. + +Overall, the goal is to raise the abstraction level so that clients need to +worry less about the technical details while Gitaly is in a better position to +iterate on them. + +### Move lifecycle management of pools into Gitaly + +The lifecycle management of object pools is leaking too many details to the +client, and by doing so makes parts things both hard to understand and +inefficient. + +The current solution relies on a set of fine-grained RPCs that manage the +relationship between repositories and their object pools. Instead, we are aiming +for a simplified approach that only exposes the high-level concept of forks to +the client. This will happen in the form of three RPCs: + +- `ForkRepository()` will create a fork of a given repository. If the upstream + repository does not yet have an object pool, Gitaly will create it. It will + then create the new repository and automatically link it to the object pool. + The upstream repository will be recorded as primary member of the object pool, + the fork will be recorded as a secondary member of the object pool. + +- `UnforkRepository()` will remove a repository from the object pool it is + connected to. This will stop deduplication of objects. For the primary object + pool member this also means that Gitaly will stop pulling new objects into the + object pool. + +- `GetObjectPool()` returns the object pool for a given repository. The pool + description will contain information about the pool's primary object pool + member as well as all secondary object pool members. + +Furthermore, the following changes will be implemented: + +- `RemoveRepository()` will remove the repository from its object pool. If it + was the last object pool member, the pool will be removed. + +- `OptimizeRepository()`, when executed on the primary object pool member, will + also update and optimize the object pool. + +- `ReplicateRepository()` needs to be aware of object pools and replicate them + correctly. Repositories shall be linked to and unlink from object pools as + required. While this is a step towards fixing the Praefect world, which may + seem redundant given that we plan to deprecate Praefect anyway, this RPC call + is also used for other use cases like repository rebalancing. + +With these changes, Gitaly will have much tighter control over the lifecycle of +object pools. Furthermore, as it starts to track the membership of repositories +in object pools it can become the single source of truth for fork networks. + +### Fix inefficient maintenance of object pools + +In order to update object pools, Gitaly performs a fetch of new objects from the +primary object pool member into the object pool. This fetch is inefficient as it +needs to needlessly negotiate objects that are new in the primary object pool +member. But given that objects are deduplicated already in the primary object +pool member it means that it should only have objects in its object database +that do not yet exist in the object pool. Consequently, we should be able to +skip the negotiation completely and instead link all objects into the object +pool that exist in the source repository. + +In the current design, these objects are kept alive by creating references to +the just-fetched objects. If the fetch deleted references or force-updated any +references, then it may happen that previously-referenced objects become +unreferenced. Gitaly thus creates keep-around references so that they cannot +ever be deleted. Furthermore, those references are required in order to properly +replicate object pools as the replication is reference-based. + +These two things can be solved in different ways: + +- We can set the `preciousObjects` repository extension. This will instruct all + versions of Git which understand this extension to never delete any objects + even if `git-prune(1)` or similar commands were executed. Versions of Git that + do not understand this extension would refuse to work in this repository. + +- Instead of replicating object pools via `git-fetch(1)`, we can instead + replicate them by sending over all objects part of the object database. + +Taken together this means that we can stop writing references in object pools +altogether. This leads to efficient updates of object pools by simply linking +all new objects into place, and it fixes issues we have seen with unbounded +growth of references in object pools. + +## Design and implementation details + +<!-- + +This section intentionally left blank. I first want to reach consensus on the +bigger picture I'm proposing in this blueprint before I iterate and fill in the +lower-level design and implementation details. + +--> + +## Problems with the design + +As mentioned before, object pools are not a perfect solution. This section goes +over the most important issues. + +### Complexity of lifecycle management + +Even though the lifecycle of object pools becomes easier to handle once it is +fully owned by Gitaly, it is still complex and needs to be considered in many +ways. Handling object pools in combination with their repositories is not an +atomic operation as any action by necessity spans over at least two different +resources. + +### Performance issues + +As object pools deduplicate objects, the end result is that object pool members +never have the full closure of objects in a single packfile. This is not +typically an issue for the primary object pool member, which by definition +cannot diverge from the object pool's contents. But secondary object pool +members can and often will diverge from the original contents of the upstream +repository. + +This leads to two different sets of reachable objects in secondary object pool +members. Unfortunately, due to limitations in Git itself, this precludes the use +of a subset of optimizations: + +- Packfiles cannot be reused as efficiently when serving fetches to serve + already-deltified objects. This requires Git to recompute deltas on the fly + for object pool members which have diverged from object pools. + +- Packfile bitmaps can only exist in object pools as it is not possible nor + easily feasible for these bitmaps to cover multiple object databases. This + requires Git to traverse larger parts of the object graph for many operations + and especially when serving fetches. + +### Dependent writes across repositories + +The design of object pools introduces significant complexity into the Raft world +where we use a write-ahead log for all changes to repositories. In the ideal +case, a Raft-based design would only need to care about the write-ahead log of a +single repository when considering requests. But with object pools, we are +forced to consider both reads and writes for a pooled repository to be dependent +on all writes in its object pool having been applied. + +## Alternative Solutions + +The proposed solution is not obviously the best choice as it has issues both +with complexity (management of the lifecycle) and performance (inefficiently +served fetches for pool members). + +This section explores alternatives to object pools and why they have not been +chosen as the new target architecture. + +### Stop using object pools altogether + +An obvious way to avoid all of the complexity is to stop using object pools +altogether. While it is charming from an engineering point of view as we can +significantly simplify the architecture, it is not a viable approach from the +product perspective as it would mean that we cannot support efficient forking +workflows. + +### Primary repository as object pool + +Instead of creating an explicit object pool repository, we could just use the +upstream repository as an alternate object database of all forks. This avoids a +lot of complexity around managing the lifetime of the object pool, at least +superficially. Furthermore, it circumvents the issue of how to update object +pools as it will always match the contents of the upstream repository. + +It has a number of downsides though: + +- Normal repositories can now have different states, where some of the + repositories are allowed to prune objects and others aren't. This introduces a + source of uncertainty and makes it easy to accidentally delete objects in a + normal repository and thus corrupt its forks. + +- When upstream repositories go private we must stop updating objects which are + supposed to be deduplicated across members of the fork network. This means + that we would ultimately still be forced to create object pools once this + happens in order to freeze the set of deduplicated objects at the point in + time where the repository goes private. + +- Deleting repositories becomes more complex as we need to take into account + whether a repository is linked to by forks. + +### Reference namespaces + +With `gitnamespaces(7)`, Git provides a mechanism to partition references into +different sets of namespaces. This allows us to serve all forks from a single +repository that contains all objects. + +One neat property is that we have the global view of objects referenced by all +forks together in a single object database. We can thus easily perform shared +housekeeping across all forks at once, including deletion of objects that are +not used by any of the forks anymore. Regarding objects, this is likely to be +the most efficient solution we could potentially aim for. + +There are again some downsides though: + +- Calculating usage quotas must by necessity use actual reachability of objects + into account, which is expensive to compute. This is not a showstopper, but + something to keep in mind. + +- One stated requirement is that it must not be possible to make objects + reachable in other repositories from forks. This property could theoretically + be enforced by only allowing access to reachable objects. That way an object + can only be accessed through virtual repository if the object is reachable from + its references. Reachability checks are too compute heavy for this to be practical. + +- Even though references are partitioned, large fork networks would still easily + end up with multiple millions of references. It is unclear what the impact on + performance would be. + +- The blast radius for any repository-level attacks significantly increases as + you would not only impact your own repository, but also all forks. + +- Custom hooks would have to be isolated for each of the virtual repositories. + Since the execution of Git hooks is controled it should be possible to handle + this for each of the namespaces. + +### Filesystem-based deduplication + +The idea of deduplicating objects on the filesystem level was floating around at +several points in time. While it would be nice if we could shift the burden of +this to another component, it is likely not easy to implement due to the nature +of how Git works. + +The most important contributing factor to repository sizes are Git objects. +While it would be possible to store the objects in their loose representation +and thus deduplicate on that level, this is infeasible: + +- Git would not be able to deltify objects, which is an extremely important + mechanism to reduce on-disk size. It is unlikely that the size reduction + caused by deduplication would outweigh the size reduction gained from the + deltification mechanism. + +- Loose objects are significantly less efficient when accessing the repository. + +- Serving fetches requires us to send a packfile to the client. Usually, Git is + able to reuse large parts of already-existing packfiles, which significantly + reduces the computational overhead. + +Deduplicating on the loose-object level is thus infeasible. + +The other unit that one could try to deduplicate is packfiles. But packfiles are +not deterministically generated by Git and will furthermore be different once +repositories start to diverge from each other. So packfiles are not a natural +fit for filesystem-level deduplication either. + +An alternative could be to use hard links of packfiles across repositories. This +would cause us to duplicate storage space whenever any repository decides to +perform a repack of objects and would thus be unpredictable and hard to manage. + +### Custom object backend + +In theory, it would be possible to implement a custom object backend that allows +us to store objects in such a way that we can deduplicate them across forks. +There are several technical hurdles though that keep us from doing so without +significant upstream investments: + +- Git is not currently designed to have different backends for objects. Accesses + to files part of the object database are littered across the code base with no + abstraction level. This is in contrast to the reference database, which has at + least some level of abstraction. + +- Implementing a custom object backend would likely necessitate a fork of the + Git project. Even if we had the resources to do so, it would introduce a major + risk factor due to potential incompatibilities with upstream changes. It would + become impossible to use vanilla Git, which is often a requirement that exists + in the context of Linux distributions that package GitLab. + +Both the initial and the operational risk of ongoing maintenance are too high to +really justify this approach for now. We might revisit this approach in the +future. |