Gun – “Self-hosted Firebase”(gun.js.org)
gun.js.org
Gun – “Self-hosted Firebase”
http://gun.js.org/
7 comments
I don't see what's hand-wavy about it. He makes a clear and succinct point: In a distributed database, managing consistency at scale gets complex because most systems are designed to assume a centralized authority [of consistency]. By removing the centralized authority and making conflict resolution the main mode of operation, the design can (according to the author) be made simpler.
I don't disagree with any of that, and it's not a new idea (Lotus Notes and CouchDB come to mind as databases that solve replication through conflict handling), although I'm not seeing a clear description of how this synchronization algorithm actually works. There's a description in the wiki [1], but it's unfinished. (Looking at the code, the entire project looks like quick-and-dirty, unfinished prototype, actually.)
[1] https://github.com/amark/gun/wiki/Conflict-Resolution-with-G...
I don't disagree with any of that, and it's not a new idea (Lotus Notes and CouchDB come to mind as databases that solve replication through conflict handling), although I'm not seeing a clear description of how this synchronization algorithm actually works. There's a description in the wiki [1], but it's unfinished. (Looking at the code, the entire project looks like quick-and-dirty, unfinished prototype, actually.)
[1] https://github.com/amark/gun/wiki/Conflict-Resolution-with-G...
Consenus, replication and consistency are potential solutions and their own problems to another entire set of really hard problems. If you're going to say you solved them you better say how, and most importantly, what tradeoffs you made to do so.
Good point, I'm definitely lacking coverage on my documentation. But we're working on it.
GUN is a AP system, so you do not get Strong (Global) Consistency, instead it is Eventually Consistent and Highly Available. For more information on this, check out the wiki: https://github.com/amark/gun/wiki/CAP-Theorem .
Basically you do NOT get linearizability for free, you have to build that ontop where it is baked explicitly into the data, with a CRDT or DAG or something. In the future, there should be extensions for this so you don't have to worry about it.
GUN is a AP system, so you do not get Strong (Global) Consistency, instead it is Eventually Consistent and Highly Available. For more information on this, check out the wiki: https://github.com/amark/gun/wiki/CAP-Theorem .
Basically you do NOT get linearizability for free, you have to build that ontop where it is baked explicitly into the data, with a CRDT or DAG or something. In the future, there should be extensions for this so you don't have to worry about it.
I'd love to see Kyle Kingsbury put that through it's paces.
Me too! I'm lucky enough to be talking alongside Kyle at https://2015.distributed-matters.org/ber/ in a few weeks. I'm hoping to get to know him and see if he'll bash up my database and help find flaws (I'm very confident in the mathematics of the system, however implementations are far from academic).
Seems a lot like CouchDB/PouchDB. Which makes the fact that the words "couch" and "pouch" do not appear anywhere on this page rather concerning to me, because the obvious questions I have are:
1. How is this better than CouchDB
2. How does this differ from CouchDB
3. Why did you not implement this on top of CouchDB
The lack of mention suggests the developers either have no clue what already exists, know that their solution can't compete with existing solutions, or don't really care about being better and are just having fun implementing their own system from scratch. None of those answers make me want to take a deeper look.
1. How is this better than CouchDB
2. How does this differ from CouchDB
3. Why did you not implement this on top of CouchDB
The lack of mention suggests the developers either have no clue what already exists, know that their solution can't compete with existing solutions, or don't really care about being better and are just having fun implementing their own system from scratch. None of those answers make me want to take a deeper look.
You are right, it is very similar to Couch/PouchDB. Honestly, I tried Couch back in 2010 and wasn't very impressed and haven't really kept up with it since. Although I regularly hear good things about it and am aware it is one of the rare ones that is offline first. MongoDB wound up winning that market, so I didn't really think to provide a comparison to Couch.
So pardon my out-of-date ignorance:
1. Depends upon what you want. GUN can do dynamic queries and has realtime push notifications baked right in. What you didn't ask is how GUN is worse. Well, CouchDB is stable and has security - stuff which we're still working on.
2. GUN is a graph database which allows you to have key-value, relational, and document based data. Couch is a document based database. GUN gets embedded into your application server, while CouchDB has to run its own database server which then requires maintenance.
3. Mathematically speaking, any matrix (table) or tree (document) can be represented in a graph. But not all graphs can be represented as a matrix or tree. So building GUN ontop of CouchDB would have come with a lot of overhead, especially since CouchDB does not have dynamic queries.
Hope this helps! Let me know if you have any other questions.
So pardon my out-of-date ignorance:
1. Depends upon what you want. GUN can do dynamic queries and has realtime push notifications baked right in. What you didn't ask is how GUN is worse. Well, CouchDB is stable and has security - stuff which we're still working on.
2. GUN is a graph database which allows you to have key-value, relational, and document based data. Couch is a document based database. GUN gets embedded into your application server, while CouchDB has to run its own database server which then requires maintenance.
3. Mathematically speaking, any matrix (table) or tree (document) can be represented in a graph. But not all graphs can be represented as a matrix or tree. So building GUN ontop of CouchDB would have come with a lot of overhead, especially since CouchDB does not have dynamic queries.
Hope this helps! Let me know if you have any other questions.
> It requires zero maintenance and runs on your own infrastructure.
I don't understand how these two claims are not contradictory.
> All conflict resolution happens locally in each peer using a deterministic algorithm.
How exactly does this happen? Via CRDTs? Consensus? How do you handle conflicts?
I'm very skeptical about this sort of largely content-free copy fronting what should be a pretty complicated distributed system.
I don't understand how these two claims are not contradictory.
> All conflict resolution happens locally in each peer using a deterministic algorithm.
How exactly does this happen? Via CRDTs? Consensus? How do you handle conflicts?
I'm very skeptical about this sort of largely content-free copy fronting what should be a pretty complicated distributed system.
Good point, haven't heard that one before. Let me clarify. GUN requires no additional maintenance because it gets embedded into your app, compared to most databases which require you to run (and maintain) a database server.
If you do not want to even run your own app servers, I'm more then happy to let you use my free GUN backend so that way you do not even have to worry about that.
Consensus? Absolutely not. I definitely need to add more documentation and resources on this - in fact I'm doing a talk on how my conflict resolution algorithm works out in Berlin in a few weeks. Check the conference out at: https://2015.distributed-matters.org/ber/ . After that I should have much better materials on this available for people.
Briefly and naively, the way it works is a Vector Clock + Timestamp combo. Timestamps have bad exploits, and Vector Clocks don't work well in ephemeral environments. If you combine the two together they compensate for the vulnerabilities of the other. Every peer acts as a state machine operating inside of an open-closed boundary function (nothing fancy here, this is the same stuff you learned in middle/highschool). This does NOT give you Global Consistency, as different peers might have slightly different boundaries because of clock drift (you can use a separate service to minimize this), but they will all become Eventually Consistent.
This helpful? Any other questions?
If you do not want to even run your own app servers, I'm more then happy to let you use my free GUN backend so that way you do not even have to worry about that.
Consensus? Absolutely not. I definitely need to add more documentation and resources on this - in fact I'm doing a talk on how my conflict resolution algorithm works out in Berlin in a few weeks. Check the conference out at: https://2015.distributed-matters.org/ber/ . After that I should have much better materials on this available for people.
Briefly and naively, the way it works is a Vector Clock + Timestamp combo. Timestamps have bad exploits, and Vector Clocks don't work well in ephemeral environments. If you combine the two together they compensate for the vulnerabilities of the other. Every peer acts as a state machine operating inside of an open-closed boundary function (nothing fancy here, this is the same stuff you learned in middle/highschool). This does NOT give you Global Consistency, as different peers might have slightly different boundaries because of clock drift (you can use a separate service to minimize this), but they will all become Eventually Consistent.
This helpful? Any other questions?
> If you combine the two together they compensate for the vulnerabilities of the other.
Do you have a reference for this? I don't mean to keep sounding like a skeptic, but these are pretty big claims. I'm also genuinely curious about this claim and would really like to look into it further.
Do you have a reference for this? I don't mean to keep sounding like a skeptic, but these are pretty big claims. I'm also genuinely curious about this claim and would really like to look into it further.
No worries, getting database stuff correct is important and you have a right to know how things work before building anything on top of it. You don't want to build a house on a cracked foundation, I'm the same way and I'm trying my best to engineer these things properly.
Here is a link explaining the algorithm https://github.com/amark/gun/issues/87#issuecomment-13636276... pretty briefly, it is also in a terrible location that nobody would know to look for (I need to move it out into the wiki or something).
And to answer your question directly, here is how they compensate each other:
1. Timestamps' vulnerability is to accidental or malicious clock drift. I can change my machine's local clock to be 2 years in the future. If you use timestamps to decide who "wins" in a conflict, my edits will win for the next 2 years. That sucks and is evil.
2. Vector clocks were invented to get around some of these problems. You increment a vector on every local change such that it is higher than the highest known vector. So Alice updates a value to "Hello World" at state 1, then to "Hello Mars" at state 2, if she then receives an update from Bob of "Hello Jupiter" at state 5, Alice then has to jump all the way up to and past Bob to change the value - say "Hello Pluto" at state 6. This gets around the timestamp vulnerability, because even if Bob were to say the update is at state 999998 all Alice has to do is increment it again to 999999, she doesn't have to wait 2 years or corrupt her clock.
3. Vector clocks' vulnerability is that since the clock is relative to the machine, if the machine reboots it loses its clock. Or even if the machine persists it, it has to play "catch up" when it comes back online - but while it is coming back online nothing stops two machines from accidentally incrementing to the same conflicting clock. At this point you are skrewed, unless you implement some other deterministic resolution - and plenty do exist. But the point of this is that vector clocks were designed for fairly permanent machines, but we now live in a emphemeral world where we might spin up a hundred servers to handle some load and then shut them down. If you do this, you lose the machine's vectors.
4. But timestamps don't have this problem, machines spinning up and down usually do some sort of NTP that gives them a rough estimate of time - drift aside, they don't need to remember anything. So when you combine these two together you get a vector timestamp relative to other vector timestamps. Aka every update includes its local timestamp (which might have drift) but the receiving computer calculates a vector relative to its own local timestamp (which might also have drift). If the sending peer is being malicious, the computed vector will be large which then receiving peer can use to mitigate the timestamp exploit. Equally as much, you can have any number of ephemeral peers coming and going through the network without fear of conflicts occurring or losing vectors.
Does that make sense? I'll be presenting on these subjects at the conference, which Kyle Kingsbury is doing the keynote. So I'll have an opportunity to talk to him and I'm hoping he'll also review the algorithm (the actual algorithm is in the code which you should look at, and I linked to a brief explanation of it at the top of this post) and help me set up Jepsen tests.
Overall, I need a LOT more documentation on this and I'm also wanting to formally verify it with TLA or Coq. We'll also be building a battle testing suite to hammer gun on in real deployed environments to see where problems lie. So please, give it a shot and slam me with any questions or problems you encounter. Have you seen this demo? https://medium.com/@marknadal/gun-0-2-0-pre-release-auto-rec...
Cheers!
Here is a link explaining the algorithm https://github.com/amark/gun/issues/87#issuecomment-13636276... pretty briefly, it is also in a terrible location that nobody would know to look for (I need to move it out into the wiki or something).
And to answer your question directly, here is how they compensate each other:
1. Timestamps' vulnerability is to accidental or malicious clock drift. I can change my machine's local clock to be 2 years in the future. If you use timestamps to decide who "wins" in a conflict, my edits will win for the next 2 years. That sucks and is evil.
2. Vector clocks were invented to get around some of these problems. You increment a vector on every local change such that it is higher than the highest known vector. So Alice updates a value to "Hello World" at state 1, then to "Hello Mars" at state 2, if she then receives an update from Bob of "Hello Jupiter" at state 5, Alice then has to jump all the way up to and past Bob to change the value - say "Hello Pluto" at state 6. This gets around the timestamp vulnerability, because even if Bob were to say the update is at state 999998 all Alice has to do is increment it again to 999999, she doesn't have to wait 2 years or corrupt her clock.
3. Vector clocks' vulnerability is that since the clock is relative to the machine, if the machine reboots it loses its clock. Or even if the machine persists it, it has to play "catch up" when it comes back online - but while it is coming back online nothing stops two machines from accidentally incrementing to the same conflicting clock. At this point you are skrewed, unless you implement some other deterministic resolution - and plenty do exist. But the point of this is that vector clocks were designed for fairly permanent machines, but we now live in a emphemeral world where we might spin up a hundred servers to handle some load and then shut them down. If you do this, you lose the machine's vectors.
4. But timestamps don't have this problem, machines spinning up and down usually do some sort of NTP that gives them a rough estimate of time - drift aside, they don't need to remember anything. So when you combine these two together you get a vector timestamp relative to other vector timestamps. Aka every update includes its local timestamp (which might have drift) but the receiving computer calculates a vector relative to its own local timestamp (which might also have drift). If the sending peer is being malicious, the computed vector will be large which then receiving peer can use to mitigate the timestamp exploit. Equally as much, you can have any number of ephemeral peers coming and going through the network without fear of conflicts occurring or losing vectors.
Does that make sense? I'll be presenting on these subjects at the conference, which Kyle Kingsbury is doing the keynote. So I'll have an opportunity to talk to him and I'm hoping he'll also review the algorithm (the actual algorithm is in the code which you should look at, and I linked to a brief explanation of it at the top of this post) and help me set up Jepsen tests.
Overall, I need a LOT more documentation on this and I'm also wanting to formally verify it with TLA or Coq. We'll also be building a battle testing suite to hammer gun on in real deployed environments to see where problems lie. So please, give it a shot and slam me with any questions or problems you encounter. Have you seen this demo? https://medium.com/@marknadal/gun-0-2-0-pre-release-auto-rec...
Cheers!
Yes, I am skeptical about automatic conflict resolution too. But the project is interesting and uses many right concepts.
I believe deepstream which received good feedback on HN also solves a similar problem.
With such proliferation of self hosted FireBase, can anyone in the know share their experiences with these solutions?
With such proliferation of self hosted FireBase, can anyone in the know share their experiences with these solutions?
Also see http://hood.ie for what appears to be a similar goal.
Just now noticed my project was on HN! Awesome, thanks to whoever submitted it. Will be replying to the comments now.
how does this not have more votes? im skeptical about the self hosted firebase claim, for instance, how would you scale this?
With a two way dotted arrow, obviously.
That's some of the most hand-wavy drivel I've ever read.