= RIP-0003: Storage Layout @fintohaps :rip: 0003 :status: Final :type: Standard :created-at: 2022-10-27 :updated-at: 2022-10-27 :copyright: CC0-1.0 include::_metadata.adoc[] :toc: The storage layer is a crucial component of the Radicle network, and it is designed with a local-first approach. This means that it can accommodate not only the local operator’s view of a repository, but also the views of peers in whom the operator is interested. These views, also known as _forks_ or _source trees_, play a key role in enabling collaboration and version control within the network. == Overview In a peer-to-peer network, there is no centralized server or repository for users to submit their changes. Additionally, the absence of a consensus mechanism at the protocol level means that the sequence of operations cannot be guaranteed. To tackle these issues, Radicle implements a partitioned approach in which each user maintains their own local "`fork`" of a repository, as well as any other forks they have an interest in. These forks are then shared among users across the network. This method not only enhances the user experience by allowing offline work but also eliminates the need for a server to process data. Each repository fork has a single owner and writer, and users are only permitted to make changes to their respective forks. The storage layer must also be designed for efficient replication of data between peers. For this reason, Git is used as the underlying protocol and database, as it maps nicely to the type of data exchanged on the Radicle network, and is flexible enough for our use case. In addition, Git has been optimized for speed and disk space, and will automatically de-duplicate repository data and fetch missing objects from peersfootnote:[https://git-scm.com/book/en/v2/Git-Internals-Transfer-Protocols]. With the above in mind, this document proposes a storage layer that meets the following requirements: [arabic] . The storage layer is capable of maintaining a local copy of the working dataset. . The storage layer can store any number of repositories. . For each repository, it can represent multiple views, or _forks_, of the repository. . The storage layer can natively interoperate with Git. There are two aspects to consider for Git interoperability: [arabic] . Repository replication between peers. . Associating a _working_ repository or "`copy`" with a _stored_ repository. In the next sections we will cover how the above works with the storage layout. == Layout The storage layout must support multiple repositories and multiple peers per repository. Each stored repository is a _bare_ Git repositoryfootnote:[https://git-scm.com/docs/git-init#Documentation/git-init.txt—bare]. To ensure uniqueness and easy identification of repositories, a stable and globally unique identifier, known as the Repository ID (RID), is assigned to each stored repository. The RID for each repository is established according to the guidelines provided in RIP#2’s section _The Repository Identifier_, and is represented as `++<++rid++>++` in diagrams found in this document. Since our underlying storage uses Git, we represent the storage layout as a file tree on the file-system, with `++<++storage++>++` representing the storage root, or top-level directory under which all repositories are stored on a user’s device. Though this storage tree is browsable by the user with standard file system commands, it is not meant to be interacted with directly by users, for risk of corrupting the data. Additionally, Git is free to pack the objects, which means they may not always appear as individual files. .... # Storage root containing all local repositories ├── # Some repository, e.g. a project, as a bare git repository │ └── refs # All Git references under this project ├── │ └── refs ├── │ └── refs └── ... .... Basic overview of the storage layout with multiple repositories For every repository, each peer associated with that repository must have a separate, logical Git source tree – which contains all the usual reference namespaces, i.e. `heads`, `tags`, and `notes`. This _logical repository_ is what we call _fork_ or _view_, and allows peers to maintain different sets of changes for the same physical repository. .... └─ # The "physical" Git repository └─ refs └─ namespaces # All forks are stored under this namespace ├─ # One peer's fork is stored here │ └─ refs ├─ # Another peer's fork is stored here │ └─ refs └─ # Etc. └─ refs .... Storage partitioning by Node ID or `++<++nid++>++` To have this separation, instead of having each peer stored in a separate Git repository with a separate object database (ODB), the `gitnamespaces`footnote:[https://git-scm.com/docs/gitnamespaces] feature is used. For each peer, including the local peer, their unique identifier is used as the namespace within each repository to separate Git objects. The identifier used is described in _Peer Identity_ in RIP#2, and is usually known as the _Node Identifier_ (NID): ____ In Heartwood, peers are simply identified by their public key. This key is an Ed25519 key that is encoded as a DID using the `did:key` method. DIDs are used for interoperability with other systems as well as allowing for other types of identifiers in the future. ____ Thus, each peer can have its own namespace for references, while sharing the objects with other peers via a shared ODB. This ensures only one copy of each object is stored across all repository forks. The storage uses the encoded public key portion of the `did:key` string as the namespace path, denoted as `++<++nid++>++` or _Node ID_ going forward. This means that a peer’s references will be scoped by their Node ID via the path prefix `refs/namespaces/++<++nid++>++`. We demonstrate this organisation below in more detail: .... # Storage root containing all local repositories ├─ # Storage for first repository │ └─ refs # All Git references locally stored │ └─ namespaces # All peer source trees or "forks" │ ├─ # First node's source tree │ │ └─ refs # First node's Git references │ │ ├─ heads # First node's branches │ │ │ └─ master # First node's master branch │ │ ├─ tags # First node's tags │ │ │ ... │ │ └─ rad │ │ └─ id # First node's version of the repository identity document │ │ │ └─ # Second node's source tree │ ├─ refs # Second node's references │ └─ ... ├─ # Storage for second repository │ ... └─ # etc. ... .... Note that top-level references may still exist, i.e. `++<++rid++>++/refs/++{++heads,tags}`. The top-level namespace must be reserved for canonical references – references that are agreed upon collaboratively, as published and stable. They do not belong to any one peer and thus may be different on each device. How canonical references are decided and written is left for a future RIP. .... └─ └─ refs ├─ HEAD # Canonical head reference ├─ heads # Canonical branches │ └─ master # Canonical master branch ├─ tags │ └─ v1.0.0 # Canonical v1.0.0 release tag ├─ rad │ └─ id # Canonical identity reference └─ namespaces # All peer source trees ├─ # First node's source tree └─ # Second node's source tree ... .... Example of canonical references under a repository == Replication Repository replication involves retrieving data from a remote peer. As the storage consists of Git repositories, data can be transferred remotely using the Git protocolsfootnote:[https://git-scm.com/book/en/v2/Git-on-the-Server-The-Protocols] and appropriate refspecsfootnote:[https://git-scm.com/book/en/v2/Git-Internals-The-Refspec]. However, this document does not cover the protocol used or how to verify fetched data, as those topics are beyond its scope. They may be discussed in a separate document. That being said, we designed the storage layout such that it’s easy to transfer data between repositories over the network, using an unmodified Git protocol. Using refspecs, it’s possible to transfer only the objects we’re interested in, for example we can fetch only a certain peer’s fork and not another. == Working Copy A working copy is a local copy of a repository, which corresponds to a repository in storage. The operator can make changes to the source code in the working copy. This is similar to how one would use `git clone` to obtain a copy of an upstream repository, such as one hosted on GitHub or GitLab. Once the changes have been made in the working copy, they can be pushed upstream. With Radicle, changes are fetched and pushed between the _working_ copy and the _stored_ copy within the local storage. The connection between the working copy and the storage is maintained through a set of Git remotesfootnote:[https://git-scm.com/book/en/v2/Git-Basics-Working-with-Remotes], where each remote represents a single remote peer or _namespace_ for that repository and is associated with a Node ID. The name of each remote, defined by the operator or application, can be customized to suit their preferences. For instance, the operator may use the Node ID of the peer, `origin`, `rad`, a nickname, or any other desired name. By convention, we use the `rad` remote for the local peer’s remote, such that a user may push changes to his or her own fork with `git push rad`. The URL of each Git remote must resolve the local storage’s repository corresponding to the working copy. As such, the URL serves as a mapping between the working copy and the stored copy. == URL The URL scheme for a given Radicle remote is of the form: .... rad://[/] .... * The `rad://` scheme is used for Radicle repositories, and identifies a project on the network. By using this scheme with Git, the user instructs Git to invoke the `git-remote-rad` executable during `git push` or `git fetch`, which allows the user to interact with the network through the storage layer. This will be covered in more detail in the _Remote Helper_ section. * The `++<++rid++>++` component is the repository identifier to be found in storage. * The `++<++nid++>++` component is the Node ID which the `--namespace` option will be set to. If `++<++nid++>++` is not specified, Git will interact with the repository’s _canonical references_. Here’s an example URL for repository `z42hL2jL4XNk6K8oHQaSWfMgCL7ji` and peer `z6MknSLrJoTcukLrE435hVNQT4JUhbvWLX4kUzqkEStBU8Vi`: .... rad://z42hL2jL4XNk6K8oHQaSWfMgCL7ji/z6MknSLrJoTcukLrE435hVNQT4JUhbvWLX4kUzqkEStBU8Vi .... Here’s a URL for the same repository’s canonical references: .... rad://z42hL2jL4XNk6K8oHQaSWfMgCL7ji .... == Refspecs Since Git namespaces are used, the `fetch` refspecfootnote:[https://git-scm.com/book/en/v2/Git-Internals-The-Refspec] may be: .... +refs/heads/*:refs/remotes//* .... The operator may also want to scope tags to particular remotes. This can be achieved by using the `tagOpt` of a remote and adding another fetch refspec. .... fetch = +refs/tags/*:refs/remotes//tags/* tagOpt = --no-tags .... When using these refspecs with `git fetch` or `git push`, it is necessary to specify the namespace that is being used for the operation. This can be achieved using `git --namespace=++<++nid++>++` or `GIT++_++NAMESPACE=++<++nid++>++ git`. Unfortunately, this is somewhat cumbersome for the user and does not prevent pushing to namespaces belonging to a non-local peer. This is remedied in link:#remote-helper[Remote Helper]. == Example Here’s an example remote configuration based on the above specifications: .... [remote "rad"] url = rad://z42hL2jL4XNk6K8oHQaSWfMgCL7ji/z6MknSLrJoTcukLrE435hVNQT4JUhbvWLX4kUzqkEStBU8Vi fetch = +refs/heads/*:refs/remotes/rad/* .... To support fetching canonical references while pushing to the local peer’s namespace, a configuration like the following can be used: .... [remote "rad"] url = rad://z42hL2jL4XNk6K8oHQaSWfMgCL7ji pushurl = rad://z42hL2jL4XNk6K8oHQaSWfMgCL7ji/z6MknSLrJoTcukLrE435hVNQT4JUhbvWLX4kUzqkEStBU8Vi fetch = +refs/heads/*:refs/remotes/rad/* .... In the above configuration, `git pull rad` would pull the canonical references while `git push rad` would push to the local user’s namespace. For a more thorough example, see the link:#appendix[Appendix]. == Remote Helper The remote helper is what allows Git to interpret URLs with the `rad://` scheme. As mentioned in the link:#working-copy[Working Copy] section, there is currently no way to configure a Git remote to be aware of additional logic, such as the appropriate `refs/namespaces` to use (to avoid having to use `--namespace`) or to prevent pushing to other peers’ namespaces. To address these requirements, a `git-remote-rad` helper binary can be introduced to supply the necessary namespace and enforce the correct use of peer namespaces. `git-remote-rad` is a gitremote-helperfootnote:[https://git-scm.com/docs/gitremote-helpers] binary. When Git encounters a URL that uses the `rad` transport protocol, it delegates the call to `git-remote-rad`, which should be found in the operator’s path, during a `fetch` or `push` operation. === Authorization With the remote helper installed, `git push` can automatically set `GIT++_++NAMESPACE` to the Node ID of the current user after verifying that it matches the one specified in the URL, and reject pushes to other Node IDs. When fetching, the remote helper can set `GIT++_++NAMESPACE` to whatever Node ID is specified in the URL, as no authorization is required to fetch. == Future Work You may have noticed that in this link:#layout[layout] the top-level namespace is left for canonical references. The definition and verification of canonicity is left for a future RIP. == Appendix == Alternative Designs An alternative design for organizing peer source trees is to use the `remotes` namespaces, i.e. `refs/remotes/++<++nid++>++`. This particular namespace is deemed special by `git` and its tooling. A "`remote`" reference is one that corresponds to a remote location. The remote location and how to fetch/push from/to is configured using `git remote`footnote:[https://git-scm.com/docs/git-remote]. When `git fetch` is used for that remote, it will place the references under `refs/remotes`footnote:[https://git-scm.com/book/en/v2/Git-Internals-Git-References]. === Associating a Working Copy Continuing along this line of enquiry, we look at how this storage will link to a working copy – our personal directory for editing the code. As we previously said, we will want to setup a remote in the working copy. This will look like the following: .... [remote "alice"] url = file:///path/to/storage fetch = +refs/remotes/alice/heads/*:refs/remotes/alice/* .... This will do what you expect when running: .... $ git fetch alice .... However, you may be surprised that when running: .... $ git fetch alice master fatal: couldn't find remote ref master .... It will not result in fetching the latest changes from `master`. In fact, it will say no reference exists. To get the exact `master` we are looking for we must run: .... $ git fetch alice refs/remotes/alice/heads/master .... To explain, `git` tends to work under a DWIM (Do What I Mean) principle. The `master` in `git fetch alice master` is ambiguous, in general. It could be `refs/heads/master`, `refs/remotes/origin/master`, `refs/remotes/alice/heads/master`, etc. `git` will assume that what you meant was `refs/heads/master` and will look for this on the remote end, but of course it does not exist. This problem is only compounded with `refs/tags`footnote:[https://git-scm.com/book/en/v2/Git-Internals-Git-References], where pushing a tag to a remote will always DWIM and target the `refs/tags` namespace – unless otherwise specified. Thus, we see that this design is not adequate. == Worked Example To begin we want to set up three git repositories: `storage`, `project`, and `fork`. The `storage` repository will act like the Radicle storage, while `project` and `fork` are working copies that will be linked to `storage` via their remote entries. .... # Storage setup $ mkdir storage $ cd storage $ git init --bare # Project setup $ mkdir project $ cd project $ git init # Fork setup $ mkdir fork $ cd fork $ git init .... === Pushing Changes Our first action will be to make changes in `project` and push them to `storage`. In order for us to do that we need to create a remote in `project`, create a commit, and push it to `storage`. .... # Add remote: "alice" will be used instead of a Node ID $ cd project $ git remote add alice file:///home/user/radicle/storage # Add a commit $ touch README.md && git add README.md && git commit -am "Add README" $ git --namespace=alice push alice master .... `git` will then print out that it pushed a new branch and we can confirm by inspecting the `refs` in `storage`. .... # Inspect refs $ cd storage $ tree refs refs ├── heads ├── namespaces │   └── alice │   └── refs │   └── heads │   └── master └── tags .... === Fetching Changes Our next action will be to fetch the changes from `alice` in the `fork` repository. To do this, we must add a remote – like before – and run a `git fetch`. .... # Add remote; alice will mimic the public key hash $ cd fork $ git remote add alice file:///home/user/radicle/storage # Fetch the changes $ git --namespace=alice fetch alice .... This will fetch the `heads` from `alice` and put them under the remote `alice`. We can confirm this by inspecting the `refs` in `fork`. .... # Inspect refs $ tree .git/refs .git/refs ├── heads ├── remotes │   └── alice │   └── master └── tags .... === Different Peers To imitate the reality that there will be a namespace per peer, we add a new remote for `fork`. We can then make changes to `alice/master` and publish it under the `bob` namespace. .... # Add bob remote $ git remote add bob file:///home/user/radicle/storage $ git merge bob/master $ echo "Hello, Radicle" >> README.md $ git commit -am "Hello, Radicle" $ git --namespace=bob push bob master .... Again, we can confirm this did what we wanted in `storage`. .... # Inspect storage refs cd storage tree refs refs ├── heads ├── namespaces │   ├── alice │   │   └── refs │   │   └── heads │   │   └── master │   └── bob │   └── refs │   └── heads │   └── master └── tags .... === Non-global Tags Often we find that pushing tags pollutes the `refs/tags` namespace since they do not get placed under `remotes` when fetching. With the use of the `gitnamespaces` feature we avoid this. .... $ cd fork $ git tag v1.0.0 $ git push v1.0.0 # Inspect storage refs refs ├── heads ├── namespaces │   ├── alice │   │   └── refs │   │   └── heads │   │   └── master │   └── bob │   └── refs │   ├── heads │   │   └── master │   └── tags │   └── v1.0.0 └── tags .... This shows that namespaces are superior in organising references correctly for each given peer. == Credits * Kim Altintop, for shining the light on the lesser known `gitnamespaces`footnote:[https://git-scm.com/docs/gitnamespaces] feature while developing `radicle-link`. * Alex Good, for attempting to implement a feature dubbed "`ref rewriting`" to solve the remotes problem, before realising that using `gitnamespaces`footnote:[https://git-scm.com/docs/gitnamespaces] could be a better option. == Copyright This document is licensed under the Creative Commons CC0 1.0 Universal license.