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

There Is No Now – Problems with Simultaneity in Distributed Systems

queue.acm.org

Post reply on HN
Print view View original

21–30 of 72 posts

Re: There Is No Now – Problems with Simultaneity in Distributed Systems

#21

Post by brianzelip »

jamespitts wrote: post #15

This is an excellent overview. Simultaneity isn't just for machines -- it is necessary for people being connected together online as well. Time sync is a huge part of creating a shared experience, and this will become more widely appreciated as virtual reality develops socially. We solved this in a very limited way at rapt.fm for our timed rap battles. We maintained a shared clock tick (with adjustment), allowing UI…

:) for the dude eating from a bowl of cereal at the end of the rapt.fm landing page background vid

Re: There Is No Now – Problems with Simultaneity in Distributed Systems

#22

Post by nostrademons »

dragonwriter wrote: post #14
tlarkworthy wrote: post #13

Spanner is externally serializable so you do get a 'now'. You just don't know what the agreed now was until after the write. The idea that there is no 'now' is of course, preposterous, we have very strict laws of physics supporting the concept of now (sans relativity) and eventually our engineering will be able to track that very accurately. Spanner is a step on that journey. These kinds of 'impossible' articles will…

> we have very strict laws of physics supporting the concept of now (sans relativity) Laws of physics "sans relativity" aren't the actual laws of physics in our universe. There very much is no now except the now that is also here . Its quite accurate to say that simultaneity does not exist in distributed systems, and simultaneity is less valid as even an approximation the more widely distributed a system is.

To add some context & numbers to dragonwriter's point, the speed-of-light delay from New York to San Francisco is about 21ms [1]. This is about 5 disk seeks, 1200 random SSD reads, 200K main memory reads (without caching), or 10M CPU cycles [2]. Speed of light delays absolutely matter in a distributed system.

[1] http://chimera.labs.oreilly.com/books/1230000000545/ch01.htm...

[2] http://www.eecs.berkeley.edu/~rcs/research/interactive_laten...

Re: There Is No Now – Problems with Simultaneity in Distributed Systems

#23

Post by epistasis »

dragonwriter wrote: post #14
tlarkworthy wrote: post #13

Spanner is externally serializable so you do get a 'now'. You just don't know what the agreed now was until after the write. The idea that there is no 'now' is of course, preposterous, we have very strict laws of physics supporting the concept of now (sans relativity) and eventually our engineering will be able to track that very accurately. Spanner is a step on that journey. These kinds of 'impossible' articles will…

> we have very strict laws of physics supporting the concept of now (sans relativity) Laws of physics "sans relativity" aren't the actual laws of physics in our universe. There very much is no now except the now that is also here . Its quite accurate to say that simultaneity does not exist in distributed systems, and simultaneity is less valid as even an approximation the more widely distributed a system is.

Furthermore, at the timescales (nanoseconds) and distances (meters to thousands of kilometers) at which a distributed application operates, relativity is a much better approximation to reality than the intuitive Newtonian physics.

If 3D chip designs let us take a couple racks of hardware into a few centimeters, then perhaps there will be a more Newtonian "now" possible, but it seems that once we can do that we'll just want to build even bigger systems that can analyze more data, and get back to distributed systems again.

Re: There Is No Now – Problems with Simultaneity in Distributed Systems

#24

Post by bdamm »

logicallee wrote: post #19
rdtsc wrote: post #11

Keeping an always consistent state in a large distributed you are fighting against the law of physics. Like it is mentioned, Google did it with their F1/Spanner SQL database. But that also mean GPS receivers with antennas on the roofs of data centers. Which is yet another thing that can fail and it, either by itself or in a cascade of other failures will lead to unspecified and possibly undesirable behavior. Recently…

I'm not an expert, and it sounds like you are, so I appreciate your feedback here: what do you even mean by a consistent state? even in theory a person initiating a new additional record in Auckland, New Zealand at the same time somebody iniatiates a change in Gibraltar or London (which are antipodal to the former[1]) 66 milliseconds away, cannot have a confirmation in less than 120 milliseconds, right? So do you jus…

There are many systems which can work just fine in an eventually-consistent manner. A database of people (customers, users, etc) is a classic example of such a thing.

In general I think consistency is over valued. There are plenty of cases where it is important. Lots of people are brainwashed in college to think that all data must be consistent all the time, and that's just not necessary.

Re: There Is No Now – Problems with Simultaneity in Distributed Systems

#25

Post by nosuchthing »

stcredzero wrote: post #18

With the way the world looks now, and the way it's shaping up to be in the future, we should be thinking about designing systems where there is no "now" but rather, there is instead a notion of "everything syncs soon." There can be a robust consensus reality in such a system, but it has to exist a short interval of time in the past. I'm currently working on a multiplayer game design on these principles.

Having played a multiplayer mobile game that uses a "everything syncs soon" protocol, and at the same time relies on the main mechanics of the game being timing the moves of characters against your opponents it often can lead to making the game highly unpredictable and jittery with "alternate timeline warps" when it resyncs, having nullified important moves.

Re: There Is No Now – Problems with Simultaneity in Distributed Systems

#26

Post by stcredzero »

jchrisa wrote: post #20
stcredzero wrote: post #18

With the way the world looks now, and the way it's shaping up to be in the future, we should be thinking about designing systems where there is no "now" but rather, there is instead a notion of "everything syncs soon." There can be a robust consensus reality in such a system, but it has to exist a short interval of time in the past. I'm currently working on a multiplayer game design on these principles.

If you want to let a mature open source sync system do the heavy lifting we've recently added Unity 3D support to Couchbase Lite. http://developer.couchbase.com/mobile/unity/ Hello world is a game where players drop shapes into a world and they automatically sync / appear on other devices. Sorry about the plug -- great article Justin! I sent it to my team because I think it does a great job stepping back from the buz…

Interesting. However I'm not just looking for syncing stats and inventory. What I'm talking about is designing a new game mechanic around the realities of distributed gaming, then designing a more robust server around that. The server will be finalizing entity positions, damage, and collisions a half second behind "real-time," and the game mechanic will be designed around this in a way that preserves player autonomy and immediate response. (Basically, deemphasizing aiming while emphasizing tactical dodging where the player seeks to minimize received damage over time.)

great job stepping back from the buzzwords

Those pesky buzzwords. You were just caught out being misled by one. (sync -- which typically means what you thought it did, but also has a generalized meaning)

Re: There Is No Now – Problems with Simultaneity in Distributed Systems

#27

Post by chris_va »

logicallee wrote: post #19
rdtsc wrote: post #11

Keeping an always consistent state in a large distributed you are fighting against the law of physics. Like it is mentioned, Google did it with their F1/Spanner SQL database. But that also mean GPS receivers with antennas on the roofs of data centers. Which is yet another thing that can fail and it, either by itself or in a cascade of other failures will lead to unspecified and possibly undesirable behavior. Recently…

I'm not an expert, and it sounds like you are, so I appreciate your feedback here: what do you even mean by a consistent state? even in theory a person initiating a new additional record in Auckland, New Zealand at the same time somebody iniatiates a change in Gibraltar or London (which are antipodal to the former[1]) 66 milliseconds away, cannot have a confirmation in less than 120 milliseconds, right? So do you jus…

I've spent too much of my life on this problem :).

The short version is that you can expose the different read/write modes to the client, and let them decide on what works best for their use case.

For spanner, table 2 in the paper[1] highlights the different interaction modes (read/write transaction, read wait for pending transactions, read skip pending transactions, read at some past timestamp). Each operation gives you a "consistent" view of the data, where "consistent" means that you don't see partial transactions.

It turns out that, for most high-qps web applications, you want a recent consistent view of the data, but you don't care about pending transactions. That means you can read at "now", or at "now - 1 second" without any latency penalty.

Clients doing read/write will care about pending transactions, but you can be opportunistic if the transactions do not overlap. Settling transactions does require quorum synchronization, so you are limited to max(median+1(latency)) milliseconds. These databases are usually keyed by something that minimizes transaction overlap (e.g. you can shard a counter, that kind of thing).

Regional migration of quorums (e.g. counter for asia, counter for europe) can also be done. So, the counter for "asia" consists in a "segment" (not the actual terminology, but we'll go with it) where the quorum exists mostly distinct asia regions. Metadata for the segment (which everything reads at startup, and is kept up to date) will tell you what servers are responsible.

[1] http://static.googleusercontent.com/media/research.google.co...

Re: There Is No Now – Problems with Simultaneity in Distributed Systems

#28

Post by xxxyy »

logicallee wrote: post #19
rdtsc wrote: post #11

Keeping an always consistent state in a large distributed you are fighting against the law of physics. Like it is mentioned, Google did it with their F1/Spanner SQL database. But that also mean GPS receivers with antennas on the roofs of data centers. Which is yet another thing that can fail and it, either by itself or in a cascade of other failures will lead to unspecified and possibly undesirable behavior. Recently…

I'm not an expert, and it sounds like you are, so I appreciate your feedback here: what do you even mean by a consistent state? even in theory a person initiating a new additional record in Auckland, New Zealand at the same time somebody iniatiates a change in Gibraltar or London (which are antipodal to the former[1]) 66 milliseconds away, cannot have a confirmation in less than 120 milliseconds, right? So do you jus…

Given a set of perfectly synchronized distributed clocks you may not even have to wait the 66ms. Incoming transactions (both local and remote) go into the write-ahead log, their ordering is given by the timestamps (which are consistent, because clocks are synchronized). Periodic heartbeats from other nodes give you a green light to commit or abort parts of the write-ahead log into permanent database. All nodes will make the same decisions wrt each transaction.

You will only have to wait for the commited/aborted response, which cannot be achieved faster than 2*66=132ms (and this system can come arbitrarily close to that, by increasing the heartbeat frequency).

There is no need to wait any time before running a subsequent transaction though. Confirmations will flow with a 132ms delay, but there is no limit on transactions concurrency.

Re: There Is No Now – Problems with Simultaneity in Distributed Systems

#29

Post by tlarkworthy »

dragonwriter wrote: post #14
tlarkworthy wrote: post #13

Spanner is externally serializable so you do get a 'now'. You just don't know what the agreed now was until after the write. The idea that there is no 'now' is of course, preposterous, we have very strict laws of physics supporting the concept of now (sans relativity) and eventually our engineering will be able to track that very accurately. Spanner is a step on that journey. These kinds of 'impossible' articles will…

> we have very strict laws of physics supporting the concept of now (sans relativity) Laws of physics "sans relativity" aren't the actual laws of physics in our universe. There very much is no now except the now that is also here . Its quite accurate to say that simultaneity does not exist in distributed systems, and simultaneity is less valid as even an approximation the more widely distributed a system is.

The error bars on relativistic affects we can expect to experience on earth are pico seconds. So we can pack millions of transactions per second if we get our clocks syncs correct and reliable. The future dbs will be not like we have now.

Re: There Is No Now – Problems with Simultaneity in Distributed Systems

#30

Post by marknadal »

Hallelujah, we need more articles like this. I work in distributed systems, and people hate hate hate hearing the truth, let's summarize the article:

1. You cannot beat the speed of light.

2. Machines break. Even the most reliable ones.

3. Networks are unreliable. Even local area networks.

4. It is an exciting time for distributed systems: CRDTs, Hybrid Logical Clocks, Zookeeper, etc.

These are things I feel like I've been preaching a lot, but get upset responses "Well, certainly Globally Consistent systems work, most databases are!" Lies, as @rdtsc mentions:

"Keeping an always consistent state in a large distributed [system] you are fighting against the laws of physics."

Next up, that is why master-master replication is important, because at some point your primary will go down (or at least the network to it). I started an interesting thought experiment that turned into a full on open source project: What if we were to build a database in the worst possible environment (the browser, aka javascript and unreliability)? What algorithms would we need to use to make such a system still survive and work?

This is why I chose and worked on solutions involving Hybrid Logical Clocks and CRDTs, which are at the core of my http://github.com/amark/gun database. An AP system with eventual consistency and no notion of "now", as every replica runs in its own special-relativity "state machine" view of the world.

These are all interesting concepts, and the article was a good one. I recommend it.

Post reply on HN