0

I have an distributed application that sends P2P messages parallel (for fault tolerance) across different channels. This mandates an filter to avoid multiple receivement of the same message. Therfor I added an GUID as an unique ID on each message, before sending it across those channels.

While it works fine, I have some doubts over my choice. I realize that a GUID is a sound way to generate near-perfect unique ids, but most use them for long term uniqueness (such as surrogate keys in a database). My solutions needs only short term uniqueness (only the last few hours), the messages exist only in memory, but there are many messages sent (perhaps 1 million per day times 20 clients)

Is a GUID a bad choice? Does it have hidden detriments for a large count of messages?

Update:

The messages are needed for syncing the application across the network. The messages exist for those few milliseconds until they got processed by the application. They exist either in memory (sender and receiver queue) or on the network during transport.

On the receiver there is a filter (an hash dictionary: key=messageId, value=insertment time ) to check for already received messageIds, and it gets cleaned regularly from older entries.

There is no other message-cache or storage.

6
  • Two of the main concerns I have "ever" heard about this kind of ID are: performance (the time and CPU required to generate one) and space (the footprint in memory or disk). I rarely (if ever) reached a case where these ID were counted by millions, but in such a magnitude these 2 concerns are legit. Regarding the second. Are messages cached somehow? Are all the messages sent or received stored in memory? What's the lifespan of these messages in memory?
    – Laiv
    Jan 2, 2023 at 15:34
  • @Laiv I added details
    – Martin
    Jan 2, 2023 at 15:51
  • 2
    I have read the update. The 2 concerns I mentioned apply to you. But they are only a problem, well, if they are a problem. If you are fine with the footprint of the application in their respective hosts and fine with the bandwidth required for the communication, then GUIDs are adequate. Is only the "long-term" characteristic of GUIDs that concerns you?
    – Laiv
    Jan 2, 2023 at 15:55
  • 1
    omg, everytime you generate a GUID Microsoft add it to their GUID DB. stop wasting them! its not an infinite resource and I need them for cupcake recipe ids!!
    – Ewan
    Jan 2, 2023 at 18:55
  • 2
    @Ewan: I just refreshed this a dozen times just for you wasteaguid.info Jan 2, 2023 at 23:06

4 Answers 4

5

I am just trying to calm my doubts about my choice.

I'm afraid of no answer will calm down your doubts. It's very easy to make a list of with pros and cons of GUIDs (or synthetic IDs) and make you struggle with the question should I care?

Phillip and I agreed on one (possible) problem. The footprint. The size of the message in memory and in the network. But don't look concerned about this.

Perhaps your application has very high recommended system requirements. Say, GB of RAM and several cores. And yet, you don't look concerned about this.

And that's ok. Otherwise, you would have measured the footprint of these IDs in memory and guessed if smaller could make a big deal of improvement. The thing is, your doubts are unfounded. So be confident in your solution. Test it, run some load tests, bring the application to its limit and let the issues emerge, then figure out if GUIDs are involved. But not before.

If it helps, look at it the other way around. GUIDs a future-proof. You can increase the lifespan of the messages in memory (increasing memory as well). Or, if you manage to increase the throughput, you can be confident that the application can handle more messages with a very low chance of ID collisiona.

I know, someone may say ey! RAM is expensive, and the answer to him or her is simple developers' time is even more expensive and change request management is even more expensive... And so on and so forth.

Also, think about this. Generating GUID or UUID is almost free1. O.S. can generate'em almost at cost 0. So, why wouldn't you take advantage of something that is given for free2?


1: 0 development and maintenance required. Costs are measured in computational resources only

2: Regarding "free" Id generation, read @amon's "Random IDs may be simpler in practice". It can be O.S. dependent, but it's worth knowing that it's possible to make your random IDs at cost 0 too.

3

UUIDs are perfectly fine in many scenarios, and are often better than rolling your own solution. But if you know exactly what you need, you may be able to do better.

As Phillip Kendall's answer demonstrates, you can calculate how many bits of entropy you need in an identifier to make collisions unlikely. The parameters here are an acceptable collisions probability, and the volume of identifiers you will be holding at a time. You may conclude that UUIDs would be much larger than you need, which may or may not matter for your P2P protocol.

UUID variants

UUID/GUID is not a single scheme for generating identifiers, but a family of schemes. Whereas UUID-v4 uses random bits (122 bits of entropy, 6 bits of metadata), others involve MAC addresses/node IDs, timestamps, and/or hashed data to derive an ID.

The timestamp-based variants are not optimal for short-term identifiers, since a few bits are “wasted” on representing durations on the order of years. Similarly, using hash functions has no apparent advantages in this context.

Smaller IDs by using counters

Depending on your exact needs, you may be able to generate IDs that have less collision probability in practice than random IDs: let each node that generate IDs have a short node-ID. You guarantee that the short node-ID is unique, for example via some central registry. Each node maintains a counter, with enough bits in the counter to represent the entire volume of active IDs. The counter wraps around. The full ID is the concatenation of the node ID and counter.

Since these IDs are namespaced via the node ID, IDs from different nodes cannot collide. Since the counter is large enough to represent the entire volume of IDs that are active at any time, IDs from one node will not collide (but IDs will eventually be reused).

Concretely, you are suggesting 20 nodes (5 bits) and a volume of maybe 10 million IDs active at any time (24 bits). Rounding up a bit, we might use a 32-bit ID (4 bytes). So, a counter-based ID generation approach would be able to generate effectively unique IDs with only 1/4th as much space per ID compared to the 128-bit UUIDs.

There are some nuances here that make this tricky in practice. For example, ensuring uniqueness of the node-IDs is hard in P2P systems. And if a node crashes, it must make sure that the counter is not reused. The typical way to handle this is to write the current counter to persistent storage on a regular basis, and to fsync() that write every N IDs. When recovering from a crash, the counter is incremented by N in case those IDs had already been used.

Random IDs may be simpler in practice

In contrast, random IDs are easier to generate correctly in a distributed and fault-tolerant manner. This is often easiest by using whatever UUID library is available (which will likely do the following steps).

If you want to generate random IDs in a DIY manner, this is even easier if you aren't trying to generate formally correct UUID-v4 identifiers – just pull as many bytes as you want from a cryptographically secure RNG, for example by reading from /dev/urandom on Linux, or by running a CSPRNG such as ChaCha. The CSPRNG must be seeded from a randomness source provided by the operating system – NOT the current time like many implementations of C's rand() function. Running your own in-process CSPRNG to generate random bits makes it possible to generate identifiers at a volume of over 1GB/s (equivalent to roughly 100 million UUID-v4 IDs per second), so that should be efficient enough for most use cases.

1
  • 1
    Philip's answer can be seen as a demonstration that the calculation is possible, but one should not take his 44 bits for granted.
    – Doc Brown
    Jan 4, 2023 at 13:19
3

UUIDs work. You are afraid they work too well. So what? Unless you really have performance problems using 16 byte UUIDs you are just fine.

1

Does it have hidden detriments for a large count of messages?

Depends what you mean by "hidden"; a GUID is 128 bits, which is significantly more than you need for uniqueness. Handwaving massively:

  • You say 20 million messages per day and you need uniqueness for "a few" hours. Let's say "a few" is 4.
  • Therefore your population is a bit over 3 million messages; let's call it 2^22.
  • The birthday paradox tells us we'll need of the order of (2^22)^2 = 2^44 possible unique IDs to not have a high chance of a collision.
    • This assumes you're generating the IDs randomly. If you can use some of the bits for a timestamp, your life gets even easier but then you need trusted clocks.
  • Therefore you are "wasting" maybe 128 - 44 = 84 bits per message, or about 10 bytes.

Is 10 bytes per message important to you? That's a question only you can answer - if your messages are typically ~1 Kb, 10 bytes is almost certainly irrelevant and you should just take the easy route of using GUIDs. If your messages are typically 10 bytes, doubling their size might be an issue.

1
  • "we'll need of the order of (2^22)^2 = 2^44 possible unique IDs to not have a high chance of a collision." - well, if you really think a chance of 50% is "not a high chance". And now think what happens when the system will probably have to run way longer than just 4 hours in total, even when only 4 hours worth of messages are kept. With a chance of 50% for a collision you will get a few collisions every. day with just 44 bits. I think I would invest a few bits more.
    – Doc Brown
    Jan 2, 2023 at 22:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.