9 ms·
Rqlite: Replicated SQLite using the Raft consensus protocol
- danielvf 11y agoHey! This was the Stripe CTF 3 final challenge problem. Good work making a polished version.
- mbell 11y agoIt was a fun level :) Anyone know if Stripe is planning another CTF? The last one was great fun.
- biokoda 11y agoActorDB takes this about 100 steps further. It replicates the actual WAL pages instead of SQL commands. So the leader executes the SQL, followers just write the pages from leader. https://github.com/biokoda/actordb https://github.com/biokoda/actordb It uses LMDB to store everything instead of storing raft log in one place and SQLite in another. It can run thousands of SQLite instances at the same time and it actually compresses the pages when storing to LMDB. You can query it with a MySQL client library (though Thrift is recommended). You can have multiple raft clusters, there is a complementary actordb_console app to manage it easily, it supports distributed transactions and more.
- atombender 11y agoActorDB is very cool, but from what I gather it's — at least nominally — designed to work with many small databases (one per "actor") as opposed one large one, and that the constraints it puts on the query model means you have to carefully design your data model to be heavily compartmentalized from the beginning. It also poses some problems for database-wide queries, which have to fan out to every separate actor database. Whereas rqlite acts like one single SQLite instance, and can work with existing schemas. Please do correct me if I'm wrong. Would ActorDB be happy and perform well with, say, just one actor?
- biokoda 11y agoIt would perform well with one actor when compared to a single SQLite instance. Not compared to PostgreSQL/MySQL due to the concurrency model being optimized for many concurrent actors, not concurrent access to a single actor. A single actor can still execute thousands of queries per second however. Compared to a single SQLite instance ActorDB has two major advantages. No write multiplication due to using LMDB and compression which means reads/writes are significantly smaller. SQLite will always write everything twice. First to WAL, then to the SQLite file and it has no compression capabilities. It should completely trounce rqlite in the performance department.
- lobster_johnson 11y agoThanks, that's useful. I know nothing about SQLite's concurrency model, but it's not surprising that it can't compete with Postgres. Does this mean that ActorDB relies on LMDB to replace the WAL? I don't know enough about LMDB either, but I presume it has some kind of redo log.
- biokoda 11y agoYes ActorDB takes sqlite3.c, takes out the wal.c code and replaces it with calls to LMDB. There is no redo log, LMDB is designed in such a way that it does not require it. It is actually verified as the safest storage engine design out there.
- thesz 11y agoDo you have a link on the LMDB verification? What I know is that SQLite IS safe to use even on unsafe file systems. There was a discussion here few months ago (link was from danloo.com).
- biokoda 11y agohttps://www.usenix.org/conference/osdi14/technical-sessions/presentation/pillai https://www.usenix.org/conference/osdi14/technical-sessions/...
- continuational 11y agoThis is exactly what I'm looking for. One small database per entity, with the option of distributed transactions across the databases. It sounds wonderful. How mature is it?
- biokoda 11y agoWe eat our own dog food and use ActorDB for everything we do. Things that are critical for the company. Multiple products are using it without issue.
- continuational 11y agoThank you. What do you do about secondary indexes? Say, if you want to search for users by name? To elaborate: I imagine sharding my data per user, so that I have one actor per user. But I still want a search bar on my page where I can type in a name and find the user in question. A multi-actor query would probably be too inefficient in this case. Did you have a similar problem, and if so, how did you solve it?
- biokoda 11y agoActorDB can have multiple actor types, each with a completely different schema. I would create a new actor type for this purpose and have a single actor in it. This would just contain the names of users. It would be easy to query and manage. Another option is to create a new KV type and have the names there. This is much more scalable bit a bit more difficult to query. Needed if you really need many thousands of queries per second. On the other hand if your scale is such that search by name is a big load, it is probably better to complement the DB with elasticsearch and move text search to it. This is how the big boys do it.
- continuational 11y agoThat makes sense. Thank you for the explanation.
- pyvpx 11y agocan anyone recommend a good overview of Raft vs. Paxos?
- krat0sprakhar 11y agoWhile this doesn't answer your question, you will find this interesting - https://ramcloud.stanford.edu/~ongaro/userstudy/ https://ramcloud.stanford.edu/~ongaro/userstudy/
- dang 11y agoThat's pretty interesting and doesn't look like it has been discussed on HN before. You should submit it.
- wyldfire 11y agoI'm almost positive that I heard about it here. It's Raft's primary distinguishing feature from Paxos, right? But hey, if you hadn't heard about it then there's a good chance that other HNers haven't either.
- georgeaf99 11y agoI'm not sure that this experiment is all that useful in determining the practicality of using Raft instead of Paxos. Anybody implementing one of these algorithms is going to be spending more than one hour learning it. In my experience, there a lots of corollaries that must be proven in order to actually implement the spec described by the Raft paper (mainly due to weak assumptions that cannot be assumed in all production systems). Paxos is a bit more established, so this is not as big of an issue; however, I still do not have an intuitive understanding of Paxos. This can (and will) lead to non-deterministic bugs in your implementation. A more useful study would track bugs in Raft & Paxos implementations.
- mslot 11y agoI can't really give an overview, but I'll tell you what I know :). Paxos is a rather simple algorithm for reaching consensus on a value once: http://research.microsoft.com/en-us/um/people/lamport/pubs/paxos-simple.pdf http://research.microsoft.com/en-us/um/people/lamport/pubs/p... The two phases of the algorithm are described at the bottom of page 5. Section 3 also describes how to use Paxos to implement log replication, Multi-Paxos, which is comparable to Raft. Unfortunately, this section does a lot of hand-waving, so it requires the implementer to have a thorough understanding of the underlying issues and find good solutions to problems such as membership changes. Conversely, the Raft paper is much more instructive to implementers, giving a clear overview of the necessary functions, messages and state: https://ramcloud.stanford.edu/raft.pdf https://ramcloud.stanford.edu/raft.pdf Personally, I find Multi-Paxos a lot more elegant, as it essentially derived by working backwards from the safety constraints. As a distributed systems researcher, it is very obvious to me why it works and I can do a basic implementation almost from memory. Unlike Raft it is also independent of time. Another nice property is that it is symmetric/masterless. All nodes can do reads and writes at any time, though whether that's a good idea is another matter. Of course, these are rather subjective and mostly aesthetic notions. Multi-Paxos is generally seen as harder to implement, because the Paxos Made Simple paper is not very explicit about implementation, and the original paper is... well... read it :) http://research.microsoft.com/en-us/um/people/lamport/pubs/lamport-paxos.pdf http://research.microsoft.com/en-us/um/people/lamport/pubs/l... Raft is getting quite popular, because people find it easy to follow the instructions of the paper, but this can be slightly deceptive. For example, using stable storage for your state is essential for crash-safety (meaning fsync-ing before answering), but I don't see where Hashicorp's raft implementation does that. Raft relies on the combination of several rules to reach consensus reliably, for which Ongaro has given a rather elaborate proof using 20 pages of TLA+ in his thesis. It's quite easy to make a mistake in your implementation and break one of the rules. The same goes for Paxos, but the rules are, at least to some extent, more obvious. A big benefit of Raft is that it already includes quite a few optimizations that would be necessary to make a Multi-Paxos implementation efficient, and you don't have to come up with them yourself. You can generally expect Raft implementations to outperform Multi-Paxos implementations. On the other hand, Multi-Paxos can be tailored to a specific use-case, such as Google's Megastore, Chubby and Spanner, which would be much more difficult with Raft.
- api 11y agoWas thinking of doing this myself! Awesome.
- bernardom 11y agoBranding feedback: I can't be the only one who immediately thought this had something to do with R! sqldf is a pretty popular package in R; RSQLite also exists. Maybe the R language shouldn't have a monopoly on packages starting with R, though...
- philips 11y agoHere is a similar project built on the etcd raft package: https://github.com/chzchzchz/raftsql https://github.com/chzchzchz/raftsql The etcd raft package is used by CockroachDB and etcd. The godoc is over here: https://godoc.org/github.com/coreos/etcd/raft https://godoc.org/github.com/coreos/etcd/raft
- TheHippo 11y ago> rqlite reports a small amount anonymous data to Loggly, each time it is launched. This data is just the host operating system and system architecture and is only used to track the number of rqlite deployments. Reporting can be disabled by passing -noreport=true to rqlite at launch time. This is very close to the end of the Readme in my opinion the wrong default setting.
- otoolep 11y agoThis behaviour has been in the program from the very start, and was a poor decision on my part. I've pulled it completely from the code.
- mslot 11y agoI've written something similar for PostgreSQL using Paxos: https://github.com/citusdata/pg_paxos https://github.com/citusdata/pg_paxos . It can replicate tables across a set of PostgreSQL servers. pg_paxos is an extension that uses PostgreSQL's query execution hooks so it doesn't require any external components. An advantage of pg_paxos is that you can do reads and writes on any node. Would love to know what people think and whether it's something you would use (if rigorously tested). Small warning: it replicates SQL queries and doesn't stop you from using volatile functions like now() yet, which would give inconsistent results. A possible application is a reliable cron service. Each cron node tries to add an entry to a replicated locks table with the same primary key on any of the PostgreSQL nodes. Only one will succeed and then runs the cron job. Some more details in these slides: http://www.p2d2.cz/files/pg_paxos.pdf http://www.p2d2.cz/files/pg_paxos.pdf
- paulryanrogers 11y agoPgpool replication can work that way too
- CodeWriter23 11y agoWhat was your motivation to DIY instead of using Bucardo?
- mslot 11y agoBucardo provides asynchronous (eventually consistent) replication. If you need strong consistency with fault-tolerance, you need something like pg_paxos, but it comes at a significant performance penalty so it's not really an alternative for existing replication solutions.
- CodeWriter23 11y agoThanks. I've been looking at PG replication solutions to get rid of the hand-coded synchronization built into a couple of my apps that date back to the dial-up days.
- ktRolster 11y agoI'm having trouble understanding this (but everyone here thinks it's rather cool, so I think I'm missing something). I've used SQLite mainly for small, app-local data storage (because it's easier than creating a custom file-format). What is the purpose of doing replication on such a database?
- nine_k 11y agoImagine a replica of client data on mobile devices, one shard per client.
- otoolep 11y agoIf you don't care about losing your data if you lose your host machine, then there is no point. The point is to have copies of your SQLite data on multiple different machines so if you lose one of the machines, you don't lose your data. The same reason anyone replicates a database.
- otoolep 11y agoThough there are other reasons to replicate databases -- read replicas. rqlite can do this do.
- ziedaniel1 11y ago"Due to the nature of Raft, there is a very small window (milliseconds) where a node has been disposed as leader, but has not yet changed its internal state. Therefore, even with the leader check in place, there is a very small window of time where out-of-date results could be returned." No, that's absolutely not inherent to the nature of Raft. It sounds like they're making the same mistake that etcd did, simply relying on whether a node believes it's still the leader rather than having it confirm that fact by committing a log entry: https://aphyr.com/posts/316-jepsen-etcd-and-consul https://aphyr.com/posts/316-jepsen-etcd-and-consul
- otoolep 11y agoWe're way ahead of you. https://github.com/otoolep/rqlite/issues/5 https://github.com/otoolep/rqlite/issues/5 But yeah, that is awkwardly phrased -- let me fix it.
- otoolep 11y agoDone. You're right that it's not Raft, it's rqlite. Though I plan to add an option that will send all queries through Raft, if so requested.
- ziedaniel1 11y agoGreat - sorry for the harsh words, I guess I've just come to expect people to screw up distributed systems :)
- ignoramous 11y agoSince SQLite can do in-memory, does this now make a good replacement for distributed in-memory databases like memSQL and voltDB? Also, could this act as a replacement to memcached/redis? To me, it looks like there's a explosion in database solutions, that most solutions are converging with overlapping set of features.
- pkolaczk 11y agoThe description suggests it was fault-tolerant, but then I read about all writes and queries going through a single leader, which is an obvious SPOF. Even if temporary, SPOF is still a SPOF.
- allengeorge 11y agoYou can have a leader and still be fault tolerant... At any rate, if the leader dies another member of the cluster is elected and operations proceed. Yes, it's not "always available", but that's the trade-off you make when you impose strong consistency.
- pkolaczk 11y ago"Not always available" means "not fault tolerant" to me. You can have strong consistency with no leader and no temporary SPOF with Egalitarian Paxos. And even with standard Paxos/Raft it is possible to architect the system to not have a single leader, but multiple leaders responsible for different partitions of data.
- allengeorge 11y agoEven if you had multiple leaders responsible for different partitions you'd still be (temporarily) unavailable if the leader died, so...while you have improved the system's availability characteristics you haven't changed the underlying fault model. Also, keep in mind that not everything has to go through the leader. If your application is OK with stale reads you can read committed data from any follower, allowing you to be available (for some definition of available) while the master is down. Also, IIRC most practical strongly-consistent systems aren't egalitarian (I'd love to hear otherwise) and instead, rely on a leader.
- otoolep 11y agoRelative to a single SQLite database, rqlite is pretty fault-tolerant.