ongardie

The issue if realms stored HMAC(realm_id + PIN), where PINs are presumed to be low-entropy, then an individual realm could brute-force the PIN. Specifically, an adversary with access to a single realm's database could enumerate PINs, run them through the HMAC along with the realm ID, and test locally whether that's the correct PIN. That would already be bad because users might reuse PINs across services. Then, if the adversary had valid auth tokens for other realms, they would be able to use that PIN to recover the secret shares from other realms and reconstruct the secret.

The Juicebox protocol is designed to prevent this. A realm can't individually test whether or not a PIN is correct.

Note: I'm a former employee of/contributor to Juicebox.

I included the paper proof for Raft in my PhD dissertation, but there's a good chance it contains errors. Here's a quote from the intro: "The proof shows that the specification preserves the State Machine Safety property. The main idea of the proof is summarized in Section 3.6.3, but the detailed proof is much more precise. We found the proof useful in understanding Raft’s safety at a deeper level, and others may find value in this as well. However, the proof is fairly long and difficult for humans to verify and maintain; we believe it to be basically correct, but it might include errors or omissions. At this scale, only a machine-checked proof could definitively be error-free." From Appendix B of my dissertation: https://github.com/ongardie/dissertation/#readme

This Coq proof is an enormous step forward. It's that machine-checked proof I was hoping someone would do when I wrote the above paragraph. 1) Assuming the TCB is correct, we know the Verdi implementation satisfies linearizability. 2) Assuming the TCB is correct and the Verdi implementation and the Raft paper/dissertation/spec are equivalent, then the Raft algorithm satisfies linearizability too.

I'm more willing to believe that the Verdi implementation implements Raft faithfully than I am willing to believe that my hand proof is correct. If you're really worried about (2), you have the option of using the Verdi generated implementation. If you're less worried about (2), you can now have more confidence in the safety of the Raft algorithm in general.

If the network is split into AB and CDE, then only CDE will be able to reach a quorum. If a client is on the AB side of that split, no consensus algorithm could guarantee freshness on a read. LogCabin clients will continually retry until they can talk to a functioning leader (and clients can put a timeout on that) so that you get a guaranteed fresh read every time; other systems could choose to return a stale result right away instead. It's up to the implementation, but I strongly recommend people not do stale reads by default.

Raft implementations can choose to implement reads in various ways. In LogCabin reads are linearizable, meaning that the results are current as of sometime after the read request was initiated, and it doesn't rely on bounded clock drift to make this guarantee. That's about the best you can do in terms of freshness in a distributed system. Other implementations might offer weaker read semantics or give the client the option. Check out 6.3-6.4 in my dissertation for a ton more detail: https://github.com/ongardie/dissertation#readme

Yes, good point. I welcome Mr. McCaffrey to give it a spin, if he's so willing. And though there may be critical bugs left to find, I don't feel like I've misrepresented the current state of LogCabin.

Good timing then, and I'd be happy to talk more about whether LogCabin is a good fit for your use.

RAMCloud used to depend on an earlier version of LogCabin (before the data model was a key-value tree), then John rewrote the RAMCloud end of that and switched it to using ZooKeeper, but he made it pluggable on the RAMCloud side. So we just need an "ExternalStorage" implementation for LogCabin in RAMCloud to make that work again. It should be relatively straightforward and I'm confident they'd welcome a well-written and tested patch, but no one has volunteered yet.

I guess the answer is no, I haven't really looked at it. Anyone have experience with it in a large-ish project outside of Node?

Maybe, but I don't think it matters much. The comment there explains the issue, and I vaguely remember my measurements showing that this wasn't a big deal.

I do think it's an interesting (dare I say) limitation of epoll, and something I'd think about if I was redesigning epoll.

Please file an issue on github if you have ideas on how to improve this without adding significant complexity.

In part that's because I don't see other Raft implementations as competitors. A major goal in Raft was to enable many implementations. It'd be a huge fail if everyone switched to LogCabin and abandoned all the other Raft implementations.

Really though, it's probably not a feature list that'll make people want to use LogCabin. In Scale Computing's case, it's that they have a C++ code base that they could integrate LogCabin well with, and they know they can work with and maintain the code if they need to.

This question came up at the CoreOS Fest earlier today too. I think everyone wants libraries as well as services, and I'd like that too for LogCabin one day. It's just a bit harder when you start thinking about the details. It's not impossible though. As one example, CockroachDB is using etcd's Raft implementation as a library.

Part of the issue is that we want to have libraries with small simple interfaces, and a consensus library is probably going to be on the large side, as it has to interface with the disk, the network, and the state machine, plus membership changes, log compaction, who's the leader, configuration settings, debug logging, etc.

Another issue is that, as a library, it has to be in the language you're using. And if that language is C++ or similar, it has to be compatible/convenient with whatever threading approach you're using.

Then there's performance/memory. Some Raft implementations are designed to keep relatively small amounts of data in memory (like LogCabin or etcd), and others are meant to store large amounts on disk (like HydraBase). Some are optimized more for performance, others for safety.

I think we'll get libraries eventually. Keep in mind Raft is still very young. Paxos is around 26 years old, Raft is only .5 to 3 years old (depending on when you start counting). I like to think that Raft lowered the cost of developing a consensus system/library significantly, but it still takes time to develop mature implementations. Right now we have a lot of implementations in early stages; I wonder if some of these efforts will consolidate over time into really flexible libraries.

It's a good question, and I don't really know where the community as a whole sits on Byzantine vs non-Byzantine. A few thoughts:

Byzantine is more complex, and most people in industry aren't doing it: there are a lot of Byzantine papers out there but few real-world implementations. I think Byzantine is important for uses where the nodes really can't be trusted for security reasons, and maybe there's easier fault-tolerance payoffs elsewhere when the entire system is within one trust domain such as a single company.

Byzantine consensus is slower and requires more servers.

If you don't have independent implementations running on each of your servers, the same software bug could still take out your entire cluster. You get some benefit if the hardware fails independently, but you don't get protection from correlated software outages. Maybe the difficulty in characterizing which faults a particular deployment can handle makes it harder to sell to management.

With Raft, we were just trying to solve non-Byzantine consensus in a way people could understand, and we think it's still a useful thing to study even if your ultimate goal is Byzantine consensus. You might be interested in Tangaroa, from the CS244b class at Stanford, where Christopher Copeland and Hongxia Zhong did some work towards a Byzantine version of Raft [1][2] and Heidi Howard's blog post on it [3]. But really, Castro and Liskov's PBFT is a must read here [4].

[1] http://www.scs.stanford.edu/14au-cs244b/labs/projects/copela...

[2] https://github.com/chrisnc/tangaroa

[3] http://hh360.user.srcf.net/blog/2015/04/conservative-electio...

[4] http://pmg.csail.mit.edu/papers/osdi99.pdf

There's not currently an extern "C" wrapper, but I don't think that'd be too much work to write.

Compaction in LogCabin uses a snapshotting approach. It writes a header to a snapshot file, then forks off a child process to write the data into a snapshot. The data is just each node in the tree serialized as a protobuf using a pre-order traversal, IIRC. Much more detail on compaction [1] mentioning LogCabin explicitly.

LogCabin does currently keep all data in memory, so it never touches disk for read requests. It also keeps a copy of the entire log in memory for now, but I hope to address that eventually [2].

[1] https://github.com/ongardie/dissertation#readme

[2] https://github.com/logcabin/logcabin/issues/106

You end up needing consensus for a lot of fault-tolerant systems that need to provide consistent results. For example, if your system allows users to choose their own usernames, and you're trying to guarantee that all usernames are unique, and your system needs to automatically deal with server failures, then I think you also need consensus.

Another way to think about it is that consensus gets you the equivalent of a compare-and-swap operation in a distributed setting. Just as compare-and-swap is useful for building synchronization primitives with shared memory, consensus is useful for building synchronization primitives across a network.

[1] https://en.wikipedia.org/wiki/Compare-and-swap

I've certainly been to that page before :)

I come from an academic lineage of log-based projects, from log-structured filesystems [1] which structure disks as a log, to RAMCloud [2][3][4] whose durability/recovery aspects are a distributed and partially in-memory extension of that, to Raft and LogCabin that are built around the concept of a replicated log for consensus.

LogCabin used to export a log-oriented data model, by the way, where the name made a bit more sense even. There was some talk of renaming it to TreeHouse now that it exports a key-value tree, but that one didn't really catch on.

[1] https://web.stanford.edu/~ouster/cgi-bin/papers/lfs.pdf

[2] http://ramcloud.stanford.edu

[3] https://www.usenix.org/conference/fast14/technical-sessions/...

[4] https://web.stanford.edu/~ouster/cgi-bin/papers/RumblePhd.pd...

I think I'd have to agree with you now: REST APIs seem to help with adoption. LogCabin was initially created for use with RAMCloud ( http://ramcloud.stanford.edu ), which mostly hand-rolls its RPC serialization to achieve its extreme performance goals (it budgets about 1 microsecond in software overhead per RPC). I thought I was being user-friendly in LogCabin by using protobufs, and at the time, something as embarrassingly slow as HTTP+JSON was unthinkable. I don't think it's too late to add a REST API to LogCabin, and it'd be pretty easy to make a REST proxy. Maybe that's worth doing for easier adoption from other languages. I also think the CLI client makes the barrier to entry pretty low for people that just want to test it out.

LogCabin uses its event loop for network operations but then hands requests off to threads to process. I started out with libevent2, but the problem is it doesn't deal with having multiple threads very well (error-prone and inefficient). It's also not as well-documented as the man pages for epoll, so I ended up using epoll directly instead. What was really lost in the libevent2 -> epoll conversion was platform independence, but I think it might be better to get that back through well-placed #ifdefs or relying on some other library; I wouldn't go back to libevent2.