# Overview As part of https://gitlab.com/groups/gitlab-org/-/epics/8903, we're moving to use Raft instead of our custom replication algorithm. Raft is based on a replicated write-ahead log. As one of the first steps towards the new architecture, we must implement write-ahead logging in Gitaly. This should be done independently from the rest of the changes and Raft. This allows us to verify the flow early and measure its performance impact. Writes that perform no user visible changes do not need to go through the write-ahead log. This includes background operations such as Git's pruning, repacking and others. These are local to a given replica and do not need to be replicated for correctness. Writes that can lead to user visible changes need to go through write-ahead log to be properly replicated later by Raft. These include: 1. Reference changes by: 1. Git pushes, hooked via [`proc-receive` hook](https://git-scm.com/docs/githooks#proc-receive). 2. Non-push reference updates, mostly made via the [Updater](https://gitlab.com/gitlab-org/gitaly/-/blob/4c15523cf680c107c5aa2b8268674cd0345a6b78/internal/git/updateref/updateref.go#L27). 3. Git fetches, as used for [repository mirroring](https://gitlab.com/gitlab-org/gitaly/-/blob/4c15523cf680c107c5aa2b8268674cd0345a6b78/internal/gitaly/service/repository/fetch_remote.go#L22). This needs a workaround as we don't have a way to takeover the reference updates made when fetching. 2. `info/attributes` changes. These can affect how files are treated by git. 3. `.git/config` changes. We don't change config files anymore, other than [setting the `gitlab.full_path` key](https://gitlab.com/gitlab-org/gitaly/-/blob/4c15523cf680c107c5aa2b8268674cd0345a6b78/internal/gitaly/service/repository/fullpath.go#L17). 4. Custom hooks, as they can affect how writes are processed. Each of these cases need to be modified to make their changes through the write-ahead log instead of directly applying them to the repository. Each repository has its own write-ahead log. A repository has a log worker goroutine reading the write-ahead log and applying it to the repository. The log worker is spawned if there is no existing log worker for a repository when a new writes are coming in. A log worker is also spawned for a repository if the write-ahead log contains entries when the Gitaly starts up. The log worker shuts down when there are no more log entries to process. A separate worker disjoint from the request context ensures the log gets fully applied regardless whether the original writer is waiting for the result. Before reference changes can be appended to the write-ahead log, the changes must be verified to apply to the repository. This can be done by looking through the write-ahead log to see what changes we've already accepted, and ensuring the old references match the changes that are about to be applied. The references that have no changes queued in the write-ahead log must be verified against the references in the repository. This ensures all logged writes will apply to the repository and the log application will not fail. As the reference verification needs to be synchronized with the log application, it's performed also by the log worker. The RPCs do not directly append to the write-ahead log. The log worker has a work queue, where the proposed log entries can be queued. The worker takes proposed log entries from the queue and verifies them. Verification failures are communicated to the goroutine that queued the work. If the verification passes, it's acknowledged to the goroutine that queued the work once the log entry has been appended to the write-ahead log. A write is considered committed when it has been appended to the write-ahead log. Log entries are persisted to the disk immediately. If writer times out while its proposal is waiting in the work queue, the write is dropped from the queue. Reads must wait until all writes that were committed when the read operation began to be applied to the repository. This ensures reads see their own writes. The write-ahead logs need to be persisted on the disk. This supports crash recovery as partially applied writes can be performed to finish by reapplying the write from the log. This is also necessary for replicating the logs using Raft as the writes need to survive past restarts. The logs can be stored in a key-value database local to each storage, such as [BadgerDB](https://github.com/dgraph-io/badger). Git may prune objects that are reachable only from references in the write-ahead log. To prevent that, internal references need to be created to hold on to the objects while the reference updates are waiting in the write-ahead log to be applied. This can be done by creating references in `refs/log/<log-index>/*` that point to the new OIDs of the references. This namespace is internal and should be hidden from other readers. As the internal references are created prior to the log entry, it could be that the internal references manage to be created but persisting the log entry fails. This would leave stale internal references in the repository. To avoid this, a record needs to be created prior to creating the internal references. This can then be used to identify repositories which need cleaning up after a shutdown. The internal references can be dropped once their log record is removed. This needs to also happen in two stages. The log record can be removed but a record needs to be left in place to record that the internal references still need to be cleaned up. This ensures there is a record always for the internal references so their removal is guaranteed when the log entry is removed. Repository deletions also go in the write-ahead log. It results in the repository being tombstoned once the deletion log entry is appended to the log, all writes in the work queue will fail with an appropriate `not found` error. Once the tombstone log entry is applied, a tombstone record is created for the repository in the key-value store. Once there are no requests accessing the repository that began before the tombstone was committed, the repository is deleted from the disk and the tombstone record is removed afterwards. Repository creations could work for now as they already work by creating them in a temporary directory first and then moving them to their place. Throughout the implementation, we want to ensure we gather enough metrics to evaluate the performance. We'll likely want to gather metrics at least on: 1. Total work queue depth - This helps identify when writes are getting piled up while waiting for the log worker to accept them. 2. Total number of entries in the write-ahead log - This helps identify the number of writes waiting to be applied. 3. Total number of log workers - This tells us the number of repositories being actively written to. This gives us a proxy number of unquiesced Raft groups we'd have later on. 4. Metrics on time spent waiting in work queue and for the write to be ultimately applied. - These give us a better idea in general on the impact of the write-ahead logging. # Problems The write-ahead logging supports only a single writer into a given repository. This makes the zero downtime upgrades as they are done today unfeasible. In the current approach using [tableflip](https://github.com/cloudflare/tableflip), the new process takes over a socket and may concurrently write into a repository with the old process. This would mean there are two processes using the same database. In the target architecture, zero downtime upgrades would be supported by retrying requests with another replica. There's also a plan to support draining a Gitaly node, which would allow for zero downtime upgrades even with replication factor of one by moving the repositories to another node prior to taking the node down. Deploying these changes as is could negatively impact zero downtime upgrades. How to manage this? Users who have strict requirements on availability are likely using Gitaly Cluster already. Given that, we could implement the features needed in Praefect to support zero-downtime upgrades without tableflip. # Status ## 2023-10-26 Further status updates are given in https://gitlab.com/groups/gitlab-org/-/epics/8903+. The projects are closely related so the updates will be centralized in the parent epic. ## 2023-05-21 The core write-ahead log implementation is in a good enough shape where we can begin integrating it into Gitaly for testing. We've opened https://gitlab.com/groups/gitlab-org/-/epics/10625+ to track the integration effort where we'll later open issues to track integration work for each RPC in Gitaly. Concurrently with the integration effort, there's still work to do on the core implementation at https://gitlab.com/groups/gitlab-org/-/epics/8911+. There is still required functionality missing such pruning old data and support for object pools. While we haven't performed any benchmarks yet, we anticipate that there will need to be further work, some upstream, to get the performance on an acceptable level. The work so far has focused on getting to a functional implementation. ## 2023-04-25 WAL work stays on track. The pre-requisites for write-ahead logging objects has been merged, so the https://gitlab.com/gitlab-org/gitaly/-/merge_requests/5638+ is now in review. With that in place, all writes into the repositories are logged. In addition, https://gitlab.com/gitlab-org/gitaly/-/issues/5050+ and https://gitlab.com/gitlab-org/gitaly/-/issues/5049+ are in development. With those in place, all writes are logged. Work is continuing on https://gitlab.com/gitlab-org/gitaly/-/merge_requests/5520+ and https://gitlab.com/gitlab-org/gitaly/-/merge_requests/5600+. ## 2023-04-18 WAL work stays on track. [Pre-requisites](https://gitlab.com/gitlab-org/gitaly/-/merge_requests/5619) for [logging objects](https://gitlab.com/gitlab-org/gitaly/-/merge_requests/5638) are in review. There's on-going [discussion](https://gitlab.com/groups/gitlab-org/-/epics/10328) on how to handle zero down time upgrades with WAL. The current solution relies on multiple processes, which is difficult for the WAL implementation as it would require synchronizing multiple processes. ## 2023-04-11 WAL work is on track with mostly the same topics still being worked on. Including pack-files in the log is done with pre-requisites in review. ## 2023-04-06 WAL work is on track. Two main topics needed until it is functionally complete: - Pack files are soon going through the log. That’s the final write type we are missing currently. - Log pruning still needs synchronization with readers. After these two, we should be in a position to start integration work. Main issues we still have to tackle before production: - Object pool design and their interaction with the WAL is still open in: https://gitlab.com/gitlab-org/gitlab/-/merge_requests/116275 - Performance is likely not good enough and will need further work. - Some upstream work in Git to make writes loggable - WAL’s interaction with zero down time upgrades: https://gitlab.com/gitlab-org/gitaly/-/issues/4934 ## 2023-03-29 Work continues on track with the focus on the same topics as last update. Some open MRs: - https://gitlab.com/gitlab-org/gitaly/-/issues/4792+ has some open MRs pending review: - https://gitlab.com/gitlab-org/gitaly/-/merge_requests/5577+ - The test suite has grown quite unwieldy through various iterations. This refactors the tests so we have a better base to continue on. - https://gitlab.com/gitlab-org/gitaly/-/merge_requests/5579+ - The transactions are not currently guaranteed to read all data committed prior to beginning. This MR synchronizes the reads with the log application and ensures all committed writes have been applied and available for reading prior to subsequent transaction beginning. - https://gitlab.com/gitlab-org/gitaly/-/merge_requests/5584+ - This enables snapshot reads of WALed custom hooks which enables consistent reads for backups. - https://gitlab.com/gitlab-org/gitaly/-/issues/4736+ - https://gitlab.com/gitlab-org/gitaly/-/merge_requests/5520 allows for synchronizing housekeeping with the log application to prevent lock conflicts related issues. ## 2023-03-20 We're working on the core WAL implementation itself. As it nears completion, we'll take on more integration related topics. The WAL currently supports: - Reference updates - Default branch updates - Recovering from crashes to a consistent state by reapplying interrupted writes. - Writes are synchronized by serializing them - Log pruning is partially supported From the core implementation, we're missing: - Writing custom hooks through the log - Logging pack files on writes - Synchronization of reads, ie. reads don't begin before all committed data being available. - Pruning all logged data, needs to by synchronized with reads to prevent pruning data needed by older transaction snapshots Work currently underway: - https://gitlab.com/gitlab-org/gitaly/-/issues/4737+ - This will add support for custom hooks which is one of the unsupported write types. - https://gitlab.com/gitlab-org/gitaly/-/issues/4736+ - Stale lock files after crashes can currently prevent recovery until housekeeping cleans the locks up. This enables immediate recovery post crash by removing the stale locks. - https://gitlab.com/gitlab-org/gitaly/-/issues/4792+ - This covers read side synchronization by ensuring all committed writes are in the repository ready for reading. This will also enable synchronizing log pruning with reads, which is necessary for prevent older versions from getting pruned while they are still in the snapshot of a transaction. - https://gitlab.com/gitlab-org/gitaly/-/issues/4516+ - Each repository has it's own WAL and will have a single goroutine synchronizing and writing to the repository. This implements a higher level component that routes writes and reads to these goroutines, and manages their lifecycle to prevent keeping excessive numbers of goroutines running. Challenges: - Object pool and their interaction with the WAL is not designed yet. - Current approach to zero downtime upgrades is not compatible with the WAL implementation: https://gitlab.com/gitlab-org/gitaly/-/issues/4934 - https://gitlab.com/gitlab-org/gitaly/-/issues/3780 has been identified to require upstream changes in Git, which can take a few months.