That collision resolution algorithm looks like a doozie from a "malicious peer" point of view.
Updates in the past are "recorded and discarded", updates in the future queue up. First, let's see if we can run our peers out of memory with a few (billion) quick future updates. Funny thing, gzip; it's so easy to compress highly repetitive patterns. Could also just try and spam the historical log too, could we fill the disk as well as working memory?
If we don't run everything out of memory, let's just write out a few billion updates for every state interval, and make sure it evaluates as "greater than" (yay, JavaScript) any real value. Those updates should preemptively overwrite every other update that comes in.
Do you have an operating window of less than, say, 300ms? Heaven help the poor client from Sidney who keeps trying to update a master in London. Their updates will always be discarded (I'm not certain, but the docs read as if this occurs even when updating a value which hasn't been overwritten by a future state). Darn you, speed of light; why can't you be just a little faster?
I guess you can only hope that your clients all decide to be honest and never change your code. Or get their state counter (or clock) too far out of sync.
This is a really great comment, thank you - hopefully I can address some of the points you brought up:
- LRU/GC hasn't been added (planned for v0.8.x), so you are correct sending in a bunch of updates will crash the peer currently. The "out of bound" updates (for everybody else not sure what the parent is referencing, see this tech talk where I explain what is going on: http://gun.js.org/distributed/matters.html ) are volatile (this is intentional) because they are considered potentially malicious, so upon crash they'll be lost as it is the origin peer's responsibility to retry updates (and gun automatically does) until ACKs have been received. Thankfully, updates that are "within bounds" will be kept safe.
- However, you are right (in your "If we don't...") "within bound" updates may also be malicious. GUN's base algorithm is designed to work in an entirely ad-hoc anonymous mesh network. To deal with this, we just recently announced our Security, Encryption, and Authorization framework to handle trusted peers, here: https://github.com/amark/gun/wiki/auth
- GUN is master-master, so no, even with a sliding window of 300ms from latency shouldn't effect the data. Your Sydney to London example is good, I've played a live action game built on top of GUN from Australia <-> USA, and even with P2P logic (no master server) it is responsive. The whole space ship game is only 190 LOC and you can play it here: http://gunjs.herokuapp.com/game/space.html (Warning: it is kinda a lame game, but proof conflicting updates in game states work just fine.)
- Also, fun fact, in a Master-Master system, the clock drift/skew on machines from different continents can become quite bad. Since we don't have atomic clocks like Spanner, we had to write a P2P version of NTP that runs along side the game. You can test how well it works across your devices here: http://gunjs.herokuapp.com/game/nts.html
- Additionally, very rarely are you going to have that many writes within a 300ms span on the /same/ record. However you very easily might have that many for a Twitter like app. Back a year ago, we ran this load test on a prototype storage driver for work loads like this (append-only) and scaled to 100M+ messages for $10/day (all costs: CPU, disk, backup), check out the proof here: https://www.youtube.com/watch?v=x_WqBuEA7s8
Thank you very much for writing your comment. Did I miss anything? More than happy to address any other concerns. The more we can challenge the assertions/claims of database vendors (like me), the better the industry will be off. Let me know if I can answer anything else. Thanks again!
It would be good to see your claims backed up with data and benchmarks. I would love to see you run the Jepsen test suite against GUN also, so it's clear how it behaves in weird circumstances.
Agreed! I know Kyle, and we're planning on having him review the system, but we're still polishing some things up on our end and he's backlogged. You'll definitely hear about it when it happens.
As for the other claims, most of these links are already scattered throughout the comments, but here they are again:
Updates in the past are "recorded and discarded", updates in the future queue up. First, let's see if we can run our peers out of memory with a few (billion) quick future updates. Funny thing, gzip; it's so easy to compress highly repetitive patterns. Could also just try and spam the historical log too, could we fill the disk as well as working memory?
If we don't run everything out of memory, let's just write out a few billion updates for every state interval, and make sure it evaluates as "greater than" (yay, JavaScript) any real value. Those updates should preemptively overwrite every other update that comes in.
Do you have an operating window of less than, say, 300ms? Heaven help the poor client from Sidney who keeps trying to update a master in London. Their updates will always be discarded (I'm not certain, but the docs read as if this occurs even when updating a value which hasn't been overwritten by a future state). Darn you, speed of light; why can't you be just a little faster?
I guess you can only hope that your clients all decide to be honest and never change your code. Or get their state counter (or clock) too far out of sync.