Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Creator of Raft Algorithm introduces LogCabin

sourcegraph.com

Post reply on HN
Print view View original

21–30 of 53 posts

Re: Creator of Raft Algorithm introduces LogCabin

#21

Post by ongardie »

alexnewman wrote: post #17

Congrats, how does compaction work? I assume you can serve kvs from memory?

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

Re: Creator of Raft Algorithm introduces LogCabin

#24

Post by justinmk »

ongardie wrote: post #10
misframer wrote: post #5

I'm not a C++ programmer, and work mainly with Go. I'm curious to know if it is usual for C++ developers to implement their own event loops for network transports, as Diego has done here [0]. The other example I know is Replicant [1], which is used by HyperDex, and it uses a custom event loop too [2]. [0] https://github.com/logcabin/logcabin/tree/master/Event [1] https://github.com/rescrv/Replicant [2] https://github…

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 indepe…

> What was really lost in the libevent2 -> epoll conversion was platform independence

Did you consider libuv?

Re: Creator of Raft Algorithm introduces LogCabin

#25

Post by rxaxm »

diego, thanks so much for raft! i'm a student in the brown class you shout out, and i can testify as to its relative simplicity and the clarity with which you guys communicate the ins and outs.

i have a question for you, though. why is raft not concerned with byzantine failure? the focus on byzantine fault tolerance from the paxos family of algos (and a lot of the literature/educationally material on distributed consensus) makes me feel like it's important, but your approach suggests it perhaps isn't. do you think this focus is a side-effect of the ubiquity of paxos which is disproportionately concerned with this due to its roots in academia?

Re: Creator of Raft Algorithm introduces LogCabin

#26

Post by hueving »

ongardie wrote: post #12
windlep wrote: post #4

First thoughts in my head.... 1) Ah, cool, creator of Raft algo, so some of the 'obvious' mistakes in an implementation should've been resolved by now (though if ppl weren't trying to use it in production.... who knows). 2) Great, C++, it should be efficient and fast with consistent RAM usage (Go's GC is a bit.... eh... still). 3) Oh, you need a C++ client library. :( I would love to say that API's don't matter, but…

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 embarra…

Tons of people are super comfortable with HTTP and have tooling built around testing and debugging it, even if the performance is crappier.

It's an ugly cousin of premature optimization that you have to deal with if you're producing APIs for your software. If the API requires anything that isn't braindead simple, you are going to lose out to competitors due to the learning curve.

Re: Creator of Raft Algorithm introduces LogCabin

#27

Post by mavelikara »

I have a slightly off-topic question for Diego and other people experienced with distributed systems.

Why are consensus algorithms always developed as systems, not as libraries? Zookeeper, etcd and LogCabin all operate as a cluster of processes which other nodes connect to over a client library.

I can imagine that the distributed-state-machine-replication-mechanism of Raft or ZAB being implemented as a library where the user has to provide an implementation of the communication layer. Such a library can be used as a starting point for building other more complex systems which aim to provide a low-friction install experience. For example, one good thing about both Cassandra and ElasticSearch is that they both have homogeneous clusters where all nodes play the same role. Incidentally, from what I understand, they both embed a consensus implementation within.

Similarly, a membership service (and failure detector) over gossip protocols will also be very useful.

An installation guide which starts with "First, install Zookeeper cluster. Then, install a SWARM cluster. Then ..." is not very appealing. That being the case, I wonder why there is no mature OSS library which provides these services. What does HN think about this situation?

Re: Creator of Raft Algorithm introduces LogCabin

#28

Post by ongardie »

rxaxm wrote: post #25

diego, thanks so much for raft! i'm a student in the brown class you shout out, and i can testify as to its relative simplicity and the clarity with which you guys communicate the ins and outs. i have a question for you, though. why is raft not concerned with byzantine failure? the focus on byzantine fault tolerance from the paxos family of algos (and a lot of the literature/educationally material on distributed cons…

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

Re: Creator of Raft Algorithm introduces LogCabin

#29

Post by halayli »

This is a very inefficient way to handle events.

https://github.com/logcabin/logcabin/blob/master/Event/Loop....

an event can be read/write, and each fd:event_type should be able to map to a different Event::file.

In its current form, if you receive 2000 events, you'll need to unnecessarily context switch 2000 times.

Re: Creator of Raft Algorithm introduces LogCabin

#30

Post by alecthomas »

mavelikara wrote: post #27

I have a slightly off-topic question for Diego and other people experienced with distributed systems. Why are consensus algorithms always developed as systems, not as libraries? Zookeeper, etcd and LogCabin all operate as a cluster of processes which other nodes connect to over a client library. I can imagine that the distributed-state-machine-replication-mechanism of Raft or ZAB being implemented as a library where…

There are at least two Raft libraries for Go, so they do exist.
Post reply on HN