5 ms·

How are you ensuring global-uniqueness in your global id space when you have multiple systems that may not even be in contact with each other a lot of the time?

• eru 15y ago
  Like steve-howard said: You choose randomly from a large enough space. That way you can make collisions as improbable as you like. (You can also add an identifier for each system and the current time, if you don't trust your source of randomness. But that's beside the point.)
  • jbri 15y ago
    So in other words, roll your own GUID implementation? Instead of using the built-in, highly-tested stuff?
    • eru 15y ago
      Oh, I was just answering the question in general. The standard GUID implementations use that trick somewhere, too.
  • saurik 15y ago
    That's not what steve-howard said, and it certainly isn't how GUID/UUIDs work: they are based on a combination of your MAC address, a process ID, a sequential ID, a timestamp, and a random number; with this algorithm, global uniqueness is confirmed. A "type 4" UUID, or as we like to call "not a UUID", is a 128-bit random number, and only got defined to retroactively deal with use cases of UUID that caused "too much information leakage" (such as Word documents).
    • eridius 15y ago
      Global uniqueness is certainly not "confirmed". With a 128-bit key, you have at most 2^128 different values (and it's actually slightly less because I think the different UUID schemes all reserve at least one digit). Sure, collisions are extremely unlikely, but they are also extremely unlikely with the simple 128-bit random number.
      • saurik 15y ago
        Actually, no: they are "confirmed". The collisions in this scheme are administratively controlled. Think about it this way: with careful planning, you can use a 24-bit number and have a reasonably large space of non-conflicting values. I wouldn't trust rand() for this, but if there was a single server allocating numbers in sequential order, this would be fine. While at 128-bits, rand() starts becoming reasonable, the UUID algorithm is designed to produce the "actually guaranteed to be globally unique" experience that the sequentially incrementing counter did. On an individual computer, this requires coordinating with a library (preferably OS-supported, such as on Windows) in order to obtain global locks, allowing identifiers to then be identified by a timestamp (to guarantee that you can reuse the hardware later; this requires your clock to be monotonically increasing on any given piece of hardware, which in practice means "make it accurate"; there is a sequence numbering mechanism for allowing clock rollbacks). Between computers, node identifiers are MAC addresses, which are unique by administrative fiat (blocks are allocated to companies, who are responsible for guaranteeing the uniqueness of their devices; if you feel like some of these providers are not abiding by this, you can simply not use their hardware for your networking infrastructure, which is a good idea anyway due to how Ethernet works). If you haven't skimmed the spec, I recommend you do at some point: http://www.ics.uci.edu/~ejw/authoring/uuid-guid/draft-leach-uuids-guids-01.txt http://www.ics.uci.edu/~ejw/authoring/uuid-guid/draft-leach-... """This specification defines the format of UUIDs (Universally Unique IDentifier), also known as GUIDs (Globally Unique IDentifier). A UUID is 128 bits long, and if generated according to the one of the mechanisms in this document, is either guaranteed to be different from all other UUIDs/GUIDs generated until 3400 A.D. or extremely likely to be different (depending on the mechanism chosen). UUIDs were originally used in the Network Computing System (NCS) [1] and later in the Open Software Foundation's (OSF) Distributed Computing Environment [2]."""
      • eru 15y ago
        With all the locks and stuff, I guess there's a bigger chance you screw up a complicated scheme and get two identical ids, than if you just us a good quality source of random bits. At least if your key is long enough. (I don't know, if 128 bits is enough.)
• famousactress 15y ago
  Partition the keyspace among the systems up front... if that's a problem you've got. Makes sense though. Maybe the pain is worth the GUID solution if you're doing id generation across a highly distributed set of machines.. like end-user boxes or something. But in a SAAS deployment where you might have a handful of DB masters, letting them all assign out a portion of a 64 bit keyspace is plenty fine.
  • jpitz 15y ago
    What about in a peer-to-peer/multi master scenario where nodes can be added or removed at whim?
  • famousactress 15y ago
    @jpitz - In those scenarios the keys can be pre-partitioned. Server A gets 0-N keys, Server B gets N-2N keys... If you have a situation where the peers pop up or come down dynamically, then you can build some sort of keymaster that does a sexier job allocating these blocks of keys to the nodes. If stuff is crazy dynamic, then I start to see value in the GUID.. but I frankly don't think most of us have problems that deserve them.
    • jpitz 15y ago
      With all due respect… a keymaster is just another component that can fail in a distributed system. GUIDs just work. I don't think I have an exceptional use case, and my nodes are dynamic in that very sense. Meta: I don't get why you are being downmodded, especially as I am being upvoted. Can someone help me understand why? Even though I disagree with you, famousactress, I do find your comments contributing to the discussion.
      • famousactress 15y ago
        I think the downvoting is pretty natural. It's kind of flamebait to jump on a thread mostly about GUIDs and call them weird. Plus I was super busy yesterday and didn't really take the time to do a decent job communicating why I'm not reinventing the wheel, and why I think GUIDs present a poor tradeoff for most projects. So yeah, in general.. maybe a touch harsh, but I'd argue my comments weren't super high value.