lxpz

Exists, already linked in another comment : https://github.com/deuxfleurs-org/garage

I'd much rather have a system that doesn't try to solve human conflict by algorithms. Blockchains do this: you write code, the code becomes the law, and then there is no recourse when things go wrong. I deeply believe that we should rather focus on developping our interpersonnal communication skills and building social structures that empower us to do things together by trusting eachother and taking care together of the group. Algorithms are just tools, and we don't want them interfering in our relationships; in particular in the case of blockchains, the promise of trustlessness is absolutely opposite to this ideal.

No, we are simply using synapse-s3-storage-provider: https://github.com/matrix-org/synapse-s3-storage-provider

Garage is designed for self-hosting by collectives of system administrators, what we could call "inter-hosting". Basically you ask your friends to put a server box at their home and achieve redundancy that way.

True; we don't solve this. If there is a fault and data is stored only on node A and not nodes B and C, the view might be inconsistent until the next repair procedure is run (which happens on each read operation if an inconsistency is detected, and also regularly on the whole dataset using an anti-entropy procedure). However if that happens, the client that sends an update will not have received an OK response, so it will know that its update is in an indeterminate state. The only guarantee that Garage gives you is that if you have an OK, the update will be visible in all subsequent reads (read-after-write consistency).

You are absolutely correct concerning the trust model of Garage: any administrator of one node is an administrator of the entire cluster, and can manipulate data arbitrarily in the system.

From an ideological perspective, we are strongly attached to the building of tight-knit communities in which strong trust bonds can emerge, as it gives us more meaning than living in an individualized society where all exchanges between individuals are mediated by a market, or worse, by blockchain technology. This means that trusting several system's administrator makes sense to us.

Note that in the case of cooperatives such as CHATONS, most users are non-technical and have to trust their sysadmin anyways; here, they just have to trust several sysadmins instead of just one. We know that several hosting cooperatives of the CHATONS network are thinking like us and are interested in setting up systems such as Garage that work under this assumption.

In the meantime, we also do perfectly recognize the possibility of a variety of attack scenarios against which we want to consider practical defenses, such as the following:

1/ An honest-but-curious system administrator or an intruder in the network that wants to read user's private data, or equivalently, a police raid where server software is embarked for inspection by state services;

2/ A malicious administrator or an intruder that wants to manipulate the users by introducing fake data;

3/ A malicious administrator or an intruder that simply wants to wreak havoc by deleting everything.

Point 1 is the biggest risk in my eyes. Several solutions can be built to add an encryption layer over S3 for different usage scenarios. For instance for storing personnal files, Rclone can be used to add simple file encryption to an S3 bucket and can also be mounted directly via FUSE, allowing us to access Garage as an end-to-end encrypted network drive. For backups, programs like Restic and Borg allow us to upload our backups encrypted into Garage.

Point 2 can be at least partially solved by adding signatures and verification in the encryption layer which is handled on the client (I don't know for sure if Rclone, Restic and Borg are doing this).

Point 3 is harder and probably requires adaptation on the side of Garage to be solved, for instance by adding a restriction on which nodes are allowed to propagate updates in the network and thus establishing a hierarchy between two categories of nodes: those that implement the S3 gateway and thus have full power in the network, and those that are only responsible for storing data given by the gateway but cannot originate modifications themselves (under the assumption that modifications must be accompanied by a digital signature and that only gateway nodes have the private keys to generate such signatures). Then we could separate gateway nodes according to the different buckets in which they can write for better separation of concernts. However, as long as we are trying to implement the S3 protocol I think we are stuck with some imperfect solution like this, because S3 itself does not implement using public-key cryptography to attest operations sent by the users.

It is perfectly true that solutions that are explicitely designed to handle these threats (such as TAHOE-LAFS) would provide better guarantees in a system that is maybe more consistent as a whole. However we are also trying to juggle these security constraints with deployment contraints such as keeping compatibility with standard protocols such as S3 (and soon also IMAP for mailbox storage), which restricts us in the design choices we make.

Just to clarify, the fact that any node can tamper with any of the data in the cluster is not strictly linked to the fact that we use CRDTs internally. It is true that CRDTs make it more difficult, but we do believe that there are solutions to this and we intend to implement at least some of them in our next project that involves mailbox storage.

License-wise, Garage is AGPLv3 like many similar software projects such as MinIO and MongoDB. We are not lawyers, but in the spirit, this should not preclude from using it in commercial software as long as it is not modified. In the case where you are modifying it, like e.g. adding a nice administration GUI, we kindly ask that you publish your modifications as open source so that we can incorporate them back in the main product if we want.

Very interesting, thanks for sharing.

Exposing Prometheus metrics is an ongoing work which we haven't had much time to advance yet. For now we can check on replication progress or overall cluster health by inspecting Garage's state from the command line.

I also had some things to answer to that comment which I'll put back here for the record.

> I have been building distributed systems for 20 years, and they are not more reliable. They are probabilistically more likely to fail.

It depends on what kind of faults you want to protect against. In our case, we are hosting servers at home, meaning that any one of them could be disconnected at any time due to a power outage, a fiber being cut off, or any number of reasons. We are also running old hardware where individual machines are more likely to fail. We also do not run clusters composed of very large numbers of machines, meaning that the number of simultaneous failures that can be expected actually remains quite low. This means that the choices made by Garage's architecture make sense for us.

But maybe your point was about the distinction between distributed systems and high availability, in which case I agree. Several of us have studied distributed systems in the academic setting, and in our vocabulary, distributed systems almost by definition includes crash-tolerance and thus making systems HA. I understand that in the engineering community the vocabulary might be different and we might orient our communication more towards presenting Garage as HA thanks to your insight, as it is one of our core, defining features.

> However, this isn't it. This is distributed S3 with CRDTs. Still too application-specific, because every app that wants to use it has to be integrated with S3. They could have just downloaded something like Riak and added an S3 API around it.

Garage is almost that, except that we didn't download Riak but made our own CRDT-based distributed storage system. It's actually not the most complex part at all, and most of the developpement time was spent on S3 compatibility. Rewriting the storage layer means that we have better integration between components, as everything is built in Rust and heavily depends on the type system to ensure things work well together. In the future, we plan to reuse the storage layer we built for Garage for other projects, in particular to build an e-mail storage server.

Yes, in which case you just make your cluster bigger or delete some data. Seems like a reasonable compromise to me.

Garage has advanced functionnality to control how much data is stored on each node, and is also very flexible with respect to adding or removing nodes, making all of this very easy to do.

Thanks!

I'll give a bit more details about CRDTs, then.

The thing is, if you don't have CRDT, the only way to replicate things over nodes in such a way that they end up in consistent states, is to have a way of ordering operations so that all nodes apply them in the same order, which is costly.

Let me give you a small example. Suppose we have a very simple key-value storage, and that two clients are writing different values at the same time on the same key. The first one will invoke write(k, v1), and the second one will invoke write(k, v2), where v1 and v2 are different values.

If all nodes receive the two write operation but don't have a way to know which one came first, some will receive v1 before v2, and end up with value v2 as the last written values, and other nodes will receive v2 before v1 meaning the will keep v1 as the definitive value. The system is now in an inconsistent state.

There are several ways to avoid this.

The first one is Raft consensus: all write operations will go through a specific node of the system, the leader, which is responsible for putting them in order and informing everyone of the order it selected for the operations. This adds a cost of talking to the leader at each operation, as well as a cost of simply selecting which node is the leader node.

CRDT are another way to ensure that we have a consistent result after applying the two writes, not by having a leader that puts everything in a certain order, but by embedding certain metadata with the write operation itself, which is enough to disambiguate between the two writes in a consistent fashion.

In our example, now, the node that does write(k, v1) will for instance generate a timestamp ts1 that corresponded to the (approximate) time at which v1 was written, and it will also generate a UUID id1. Similarly, the nodes that does write(k, v2) will generate ts2 and id2. Now when they send their new values to other nodes in the network, they will send along their values of ts1, id1, ts2 and id2. Nodes now know enough to always deterministcally select either v1 or v2, consistently everywhere: if ts1 > ts2 or ts1 = ts2 and id1 > id2, then v1 is selected, otherwise v2 is selected (we suppose that id1 = id2 has a negligible probability of happening). In terms of message round-trips between nodes, we see that with this new method, nodes simply communicate once with all other nodes in the network, which is much faster than having to pass through a leader.

Here the example uses timestamps as a way to disambiguate between v1 and v2, but CRDTs are more general and other ways of handling concurrent updates can be devised. The core property is that concurrent operations are combined a-posteriori using a deterministic rule once they reach the storage nodes, and not a-priori by putting them in a certain order.

Raft consensus apparently needs more round-trips than that (maybe two round-trips to another node per write?), as evidenced by this benchmark we made against Minio:

https://garagehq.deuxfleurs.fr/documentation/design/benchmar...

Yes we do round-trips to other nodes, but we do much fewer of them to ensure the same level of consistency.

This is to be expected from a distributed system's theory perspective, as consensus (or total order) is a much harder problem to solve than what we are doing.

We haven't (yet) gone into dissecating the Raft protocol or Minio's implementation to figure out why exactly it is much slower, but the benchmark I linked above is already strong enough evidence for us.

Thanks for the feedback! We will definitely be adjusting our pitch in further iterations.

Sure!

CRDTs are often presented as a way of building asynchronous replication system with eventual consistency. This means that when modifying a CRDT object, you just update your local copy, and then synchronize in background with other nodes.

However this is not the only way of using CRDTs. At there core, CRDTs are a way to resolve conflicts between different versions of an object without coordination: when all of the different states of the object that exist in the network become known to a node, it applies a local procedure known as a merge that produces a deterministic outcome: all nodes do this, and once they have all done it, they are all in the same state. In that way, nodes do not need to coordinate before-hand when doing modifictations, in the sense where they do not need to run a two-phase commit protocol that ensures that operations are applied one after the other in a specific order that is replicated identically at all nodes. (This is the problem of consensus which is theoretically much harder to solve from a distributed system's theory perspective, as well as from an implementation perspective).

In Garage, we have a bit of a special way of using CRDTs. To simplify a bit, each file stored in Garage is a CRDT that is replicated on three known nodes (deterministically decided). While these three nodes could synchronize in the background when an update is made, this would mean two things that we don't want: 1/ when a write is made, it would be written only on one node, so if that node crashes before it had a chance to synchronize with other nodes, data would be lost; 2/ reading from a node wouldn't necessarily ensure that you have the last version of the data, therefore the system is not read-after-write consistent. To fix this, we add a simple synchronization system based on read/write quorums to our CRDT system. More precisely, when updating a CRDT, we wait for the value to be known to at least two of the three responsible nodes before returning OK, which allows us to tolerate one node failure while always ensuring durability of stored data. Further when performing a read, we ask for their current state of the CRDT to at least two of the three nodes: this ensures that at least one of the two will know about the last version that was written (due to the intersection of the quorums being non-empty), making the system read-after-write consistent. These are basically the same principles that are applied in CRDT databases such as Riak.

We ensure the CRDT is synced with at least two nodes in different geographical areas before returning an OK status to a write operation. We are using CRDTs not so much for their asynchronous replication properties (what is usually touted as eventual consistency), but more as a way to avoid conflicts between concurrent operations so that we don't need a consensus algorithm like Raft. By combining this with the quorum system (two writes out of three need to be successfull before returning ok), we ensure durability of written data but without having to pay the synchronization penalty of Raft.

> Raft is for synchronized writes. It's slow in the case of a single-write being slow because you have to wait for an "ok" from replicas, which is a good thing (compared to async-replication in, say, cassandra/dynamodb). Keep in mind that s3 also moved to synced replication. This is fixed by having more parallelism.

We have synchronous writes without Raft, meaning we are both much faster and still strongly consistent (in the sense of read-after-write consistency, not linearizability). This is all thanks to CRDTs.

We don't currently have a comparison with SeaweedFS. For the record, we have been developping Garage for almost two years now, and we hadn't heard of SeaweedFS at the time we started.

To me, the two key differentiators of Garage over its competitors are as follows:

- Garage contains an evolved metadata system that is based on CRDTs and consistent hashing inspired by Dynamo, solidly grounded in distributed system's theory. This allows us to be very efficient as we don't use Raft or other consensus algorithms between nodes, and we also do not rely on an external service for metadata storage (Postgres, Cassandra, whatever) meaning we don't pay an additionnal communication penalty.

- Garage was designed from the start to be multi-datacenter aware, again helped by insights from distributed system's theory. In practice we explicitly chose against implementing erasure coding, instead we spread three full copies of data over different zones so that overall availability is maintained with no degradation in performance when one full zone goes down, and data locality is preserved at all locations for faster access (in the case of a system with three zones, our ideal deployment scenario).

For people interested in digging in, we have an interesting benchmark here showing how it significantly outperforms Minio in the geo-distributed setting: https://garagehq.deuxfleurs.fr/documentation/design/benchmar...

We also made a presentation at FOSDEM'22, the video should be out soon.

It's "closure" in the mathematical sense, not in the functionnal programming sense. It would have been clearer with the full term: "transitive closure" instead of just "closure".

This should be integrated with Cargo to reduce the size of the target directories which are becoming ridiculously large.

Thank you for stating this. I absolutely agree with you, and this is what we are trying to do with the Deuxfleurs collective which is also getting funded by the EU to work on our project Garage [0, 1]. We are working on making self-hosting easier, and also more reliable, by exploiting geographical redundancy [2]. We will use the grant money mostly to develop Garage, our self-hosted data server (an object store implementing the S3 protocol, and soon also an email inbox server with IMAP access). We are also working on automating opening ports on your router to get around NAT (with our project DiploNAT [3]), and on facilitating distributed deployments with the Nomad orchestrator. Our vision is to help technical users set up local self-hosting collectives by setting up servers at three or four geographical locations for redundancy, which can then be used by their friends, neighbors, etc. We are of course very keen on deploying federated protocols such as Matrix to link all of these communities together.

[0] https://garagehq.deuxfleurs.fr

[1] https://git.deuxfleurs.fr/Deuxfleurs/infrastructure

[2] https://git.deuxfleurs.fr/Deuxfleurs/garage/src/branch/main/...

[3] https://git.deuxfleurs.fr/Deuxfleurs/diplonat

Not linking our main website because it's in French.

Hey, thanks for sharing your perspective. I'm sorry you interpreted my comment in that way, I did not mean to say that TeXmacs had shortcomings in the way it imports LaTeX, in fact I do believe it does its best given the constraints it faces, but as you justly said the task is impossible in the general case given LaTeX's Turing completeness. To be clear the problem is not TeXmacs, but the fact that in a team most people work in LaTeX and having to constantly convert from one another would be impractical. In particular I rely heavily on git to manage document history and to view diffs from my co-authors, and having to manage a document that exists in two languages simultaneously would add significant complexity to a workflow that I'm already barely able to make my co-authors follow. This would be of course significantly simplificated if import followed by export (and the reverse) was the identity function, which would technically allow TeXmacs to directly edit LaTeX documents without having to rewrite them entirely, but I don't believe that to be the case and again I don't see how it could be possible.

To answer your other comment, this paper of mine https://arxiv.org/abs/2102.04063 has many problems when importing in TeXmacs: the title is not aligned correctly, the algorithms are messed up, the figures don't have the correct sizes, and one of the figures which is exported from Inkscape is not even imported at all. There are also a bunch of macros that are shown as raw visible commands in TeXmacs and I don't know what to do with those (but that's certainly something I could learn to manage). Again not blaming you or the particular TeXmacs devs working on import, this situation is a fatality of how LaTeX works.

I've successfully used TeXmacs to take more than 100 pages of notes live during a math class. The keyboard shortcuts used to build math formulas are extremely effective and quite easy to learn. I still use it from time to time when I need to write a quick draft of some idea with formulas, or as a wysiwig editor for non-technical text documents. Unfortunately it is not compatible with LaTeX in both directions (export works, import is only partially supported), which means I'm unable to use it when collaborating with other researchers that are used to LaTeX. I'll be happy when LaTeX dies the horrible death it deserves and a better structured document format like TeXmacs emerges as a new consensus, but sadly I don't see that happenning in the forseeable future.

Algorithms that tolerate Byzantine failures generally require t<n/3, i.e. at least 4 nodes to tolerate 1 byzantine fault. This is in fact required for primitives as simple as reliable broadcast. Systems that use leader election such as Raft are not Byzantine tolerant. They tolerate t<n/2, meaning that 3 nodes does indeed buy tolerance to 1 crash, but it doesn't support anything else than crashes.

I'm not the best qualified to answer this question as I do spend a lot of time reading about programming languages in general, and even though I was able to grasp Rust's async/await very fast, I probably owe it to previous knowledge of a relatively large variety of programming paradigms. I'll thus rely on other commenters that seem to agree that it's really not as hard as you would expect. In particular Rust helps a lot in making sure you don't make too many mistakes so I'd wager that learning to do correct async/await in Rust is probably easier than in, say, Javascript.

The advantage of async tasks for structured concurrency lies in task cancellation, which is intrinsically linked to the notion of "task ownership". If you are using an OS thread to offload some task, and then realize that you don't need that task's result anymore, your safest bet is to let the thread run until the end and then discard the results it produces. Other options include adding custom cancellation logic to the thread and remembering to call it at the appropriate time. Nobody checks that you are doing this correctly, which means you may leak resources such as the thread's memory or a TCP connection. On the other hand when using async/await in Rust, the fact of owning a future (i.e. owning the promise that will return you the value when it's done) implies ownership of the task's resources, such as memory, file descriptors, or TCP connections. Dropping the future before it completes means that the task will stop and all resources will be freed/closed immediately, and this is checked statically by the compiler.

That .NET syntax using Task.WhenAll seems quite bad, which might be part of the reason why not many people bother (disclaimer: I don't do C# or ASP.NET). In Rust it would be:

    let p, c, m = join!(
        GetUserPermission(username),
        GetServerConfig(),
        GetMessageOftheDay()
    );

(you don't even have to write await when using the join macro)

With such simple syntax available it seems obvious to me that one would want to use it as often as possible, and it's also much simpler (and probably cheaper) than dispatching those three tasks to a thread pool.

Sorry, yes this is not from the mouth of the author, however he seemed to agree with the premise that async/await is unergonomical and that performance is its only reason to exist, which I am trying to dispute (at least in the context of how Rust does it, which is much better than the JS version for instance)

> People often see that there's some theoretical benefit of async and then they accept far less ergonomic coding styles and the additional bug classes that only happen on async due to accidental blocking etc... despite the fact that when you consider a real-world deployed application, those "benefits" become indistinguishable from noise. However, due to the additional bug classes and worse ergonomics, there is now less energy for actually optimizing the business logic, which is where all of the cycles and resource use are anyway, so in-practice async implementations tend to be buggier and slower.

I disagree with this. I feel like using Async programming is actually much more powerfull and expressive than theaded programming, especially with Rust combinators on streams of futures (for examples: futures_unordered), which allow to trivially express complex concurrency patterns (such as: wait for the first two requests to return something and discard the third request's response, and btw also cancel that request). Async programming also allows for structured programming, where each task is an owned resource of a parent tasks, which means that lifetimes of tasks can be controlled and runaway threads can't exist (if one is avoiding tokio::spawn). I've been developping [Garage](https://git.deuxfleurs.fr/Deuxfleurs/garage) for some time now (a simple distributed object store that implements a subset of S3, not ready for production!), and I've been in awe about how easy it was to write these complex patterns using async Rust.