Search code examples
c++cuuiduniqueidentifieruid

Possible to generate 8-byte Unique ID for an entity

I need a unique identifier to distinguish entities, but in reality these entities don't have a lot, and the uid can be repeated when the entity is destroyed. Entities are created in a distributed system and can be created multiple times at the same time.

Currently using a popular UUID library, but UUID is a 128-bit number. According to the design of my system, an int type is more than enough. If uid can be recycled, 8-byte should ok. So I think there is a lot of optimization space.

For example:

bool isEqual(const char *uid1, const char *uid2) {
    return strcmp(uid1, uid2) == 0;
}

If I can make uid an integer instead of a string, then I don't need to use the string comparison function.

bool isEqual(int uid1, int uid2) {
    return uid1 == uid2;
}

But I don't know now that there are mature libraries that meet my needs.

So I want to ask you:

  • How feasible if I implement it myself?
  • What difficulties will I encounter?
  • What should I pay attention to?
  • Is there a library that already implements similar functions?
  • Worth it?

BTW, I can use C/C++/lua.

Solution

  • If you want a custom dedicated uid generation on a fully controlled distributed system, you have 3 possibilities:

    1. A central system generates simply serial values and the other systems ask it for each new uid. Simple and fully deterministic, but the generator is a Single Point Of Failure
    2. Each (logical) system receives an id and combines it with a local serial number. For example if the number of systems is beyond 32000 you could use 16 bits for the system id and 48 bits for the serial. Fully deterministic but requires an admin to give each system its id
    3. Random. High quality random number generators that comply with crypto requirements should give you pseudo uid with a low probability of collision. But it is only probabilistic so a collision is still possible.

    Point to pay attention to:

    • race conditions. If more than one process can be client for a generator, you must ensure that the uid generation is correctly synchronized
    • uid recycling. If the whole system must be designed to live long enough to exhaust a serial generator, you will have to keep somewhere the list of still existing entities and their uid
    • for the probabilistic solution, the risk of collision is proportional to the maximum number of simultaneous entities. You should carefully evaluates that probability and evaluates whether the risk can be accepted.

    Are such solutions already implemented?

    Yes, in database systems that allow automatic id generation.

    Worth it?

    Only you can say...