Hacker News Reader

Comment by brandonbloom | Hacker News Reader

The paper on the underlying Dedalus logic (a datalog variant with explicit time) is much more insightful: http://www.eecs.berkeley.edu/Pubs/TechRpts/2009/EECS-2009-17...

The fundamental idea is to build a language out of primitives which compose monotonically. A very simple example is getting a distributed count of "yes votes". The naive solution is to have each server send a "incrementVote()" RPC calls. But what happens if an RPC is retried? Will your count accidentally be too high? A better solution is to send a "vote(myUUID)" message, which adds the UUID to a set. The number of votes is now the cardinality of the set of UUIDs. Voting is idempotent and the count is monotonic. The goal of Bloom is to create a language in which the right properties are ensured by construction.

View on HN

Needless to say this is becoming a hot area due to distributed database research. Everyone is talking about the CAP theorem. Those that picked the AP side are trying to have their cake and eat it too. INRIA has been sponsoring a couple of papers in it (here is a popular one by Mark Shapiro: http://pagesperso-systeme.lip6.fr/Marc.Shapiro/papers/RR-695...).

The idea is to have auto-convergent types in an AP database cluster. There are some datatypes that can do this: max function, set union, boolean or. [Say one node union-updates set {} with {'a'} and the other with {'b'}. The two operations will both auto-converge so to speak to set {'a','b'}.

If you can detect conflicts (divergent data, aka "siblings" in Riak-speak, ), you could also build you own, app specific, conflict resolution for your application. It is nice if you don't have to and your db provides it by using auto-convergent types.

Naive question: what techniques are used for reliably generating UUIDs? Can you do it without giving each machine a unique identifier first?

Just generate random UUIDs. The probability of their colliding is negligibly low.

The are a few types of standard UUIDs.

https://en.wikipedia.org/wiki/UUID

UUID1 and UUID4 are common. UUID1 are the ones that use machine id and timestamp. UUID4 are supposed to be randomly generated. UUID1 can be traced to a machine that created them and are sortable somewhat, UUID4s are nice because you don't have to worry if machines somehow ended up with non-unique machines (bad VM cloning can easily do that).

I would just use UUID4 for example.

Thanks. That description says:

Version 4 UUIDs have the form xxxxxxxx-xxxx-4xxx-yxxx-xxxxxxxxxxxx where x is any hexadecimal digit and y is one of 8, 9, A, or B

What is the purpose of the 4 and y?

Versioning. The 4 says it is "version 4" in the RFC 4122 taxonomy, and the fact that the first two bits of y are "10" is meant to indicate that this is a UUID following that standard. Certain Microsoft GUIDs start with "110" in that field, and apparently there's another legacy format (Network Computing System) characterized by the first bit of y being "0". Therefore, an RFC 4122 compliant UUID will not overlap with either of these namespaces.

Reply on news.ycombinator.com