6

Let's say we have multiple (somewhat autonomous) (micro-)services, and when entities are created, the ID (UUIDs or whatever) can be set externally. How can we ensure that an ID remains unique across all services while protecting against someone maliciously trying to create ID collisions in separate services? While preserving the concept of externally generated IDs and not sacrificing to much performance or be overly verbose/leaky/complex.

The only solutions I've come up with so far are:

  1. Centralized ID checks (at least if they are generated externally): This approach, however, would break the decentralized nature of the system and add a single point of failure. The simplest way to implement this might be a shared database table, where services can reserve IDs.
  2. Prefixing/namespacing IDs: This approach would be somewhat verbose and may leak information. This would allow a service to ensure uniqueness within its own namespace, for instance through a DB unique index. Which may require an additional table storing all reserved IDs within a service.

This question is not about how to safely generate unique IDs in a distributed System, outside of malicious intent. The answer to that could be using UUIDv4.

The Question is also not how to prevent ID collisions / inconsistencies within a service. The answer to that might be Unique Indexes when using an SQL DB. However, the same problem and solutions may apply within a service, across multiple tables or in high performance scenarios maybe even within a table.

Lastly a workaround might be to not allow IDs to be set externally, or only allowing to set intermediary/reference IDs that may be translated/mapped to actually unique IDs and returned to the client. But it is not my immediate goal to find a workaround breaking the initial design.

Thank you!

12
  • 8
    It seems that if you allow externally set IDs, you give up their uniqueness within your system. You can't ensure uniqueness if you don't control them. The only options you're left with are either injecting uniqueness on top of the provided external ID (your option #2 or variations thereof) or enforcing uniqueness by checking against known IDs (your option #1). Why do you want externally injected IDs? Apr 24 at 12:06
  • @JorisTimmermans thanks for your reply. I believe externally generated IDs can be a valuable feature when separating frontend and backend, allowing the UI or any client-app to control the ID allows for more flexibility. I have worked with systems not addressing this issue and am currently working on a system using solution #2. I agree however that more specific use cases would lead to more specific answers, but this question is broader / more architectural.
    – Philippe
    Apr 24 at 12:36
  • I'm struggling with the concept of "malicious duplicate Ids" ... I'll need to do some research, but my intuition is "this is simply a risk you must take if you allow other systems to generate Ids." Apr 24 at 13:18
  • 3
    I think what I'm struggling with the most is the "malicious" part. To be honest, I've never thought about this attack vector before. That's the interesting aspect of this question to me. Just imagining a hacker generating UUIDs in an infinite loop while laughing maniacally. Maybe this is a blindspot in my skills. I just can't seem to see how "malicious duplicate Ids" could translate to a security breach. I think a good answer to this question should include that (for people like me). Apr 24 at 13:29
  • 1
    When you mention "flexibility" - it sounds to me as if perhaps just associating some sort of user data with the entity is enough. If the client wants to use the user data as their ID, that's fine, your system doesn't need to care as long as there's another ID there that the client cannot override. And it's up to the client to ensure that their ID is unique enough for their context. Apr 25 at 7:30

4 Answers 4

10

There is no such thing as uniqueness without context. You may think your 42 is special but I can assure you other people have used 42 before.

This may lead you to thinking a large UUID or a centralized context (1) is required but you can have distributed contexts as you mention in (2). However, making each context set a self identifying prefix is only one way to do that. Let me ask, do you know who is talking to you?

The prefix only needs to be sent to you when you don't. And if you don't you're trusting the prefix to not be a lie. And weren't we trying to stop trusting these numbers?

An alternative way to do (2) is use the fact that you know who is talking to you and put the prefix on it yourself. Now you can trust it.

Well, to some extent. This puts each context in a sandbox. Now the only IDs they can collide with are their own.

8
  • I agree from an implementation/client perspective most of the time a prefix is implicitly already obvious. Only when entities from multiple services or local and non-local entities are handled at the same time, does the process really need to be aware of a prefix. And also there probably really is no simple solution to this problem, if the complexity is required.
    – Philippe
    Apr 24 at 15:57
  • 1
    @Philippe to be exact. We don't care which web address, or host we're talking to. We care which context. Ya know, the thing picking IDs. Indirections between those can certainly mess this up. Within a context the ID counter must obey the Highlander rule: there can be only one. Apr 24 at 16:30
  • 1
    @Philippe hash prefixed local UID and you get global UID without leakage.
    – Basilevs
    Apr 24 at 16:35
  • @Basilevs true. Apr 24 at 16:37
  • Also, don't assume all 1 to 1 relationships stay that way without enforcement. Apr 24 at 16:38
3

Fundamentally, a central registry is required for uniqueness.

The system of assigning a unique prefix to different allocators, still has the centralised element of assigning the unique prefix itself to each allocator.

Generalised, the prefix method is basically a pattern whereby an allocator reserves a block from the central registry, then proceeds to dole out individual items from that pre-allocated block. The only question is how often coordination needs to occur with the central registry.

So the strict answer to how you prevent malicious duplicates in a truly distributed environment is: you don't.

Instead, the question should be how often the central registry is consulted in your design, and what latency can be tolerated by that design (if the central registry is slow to respond, or not always available).

8
  • To add, if you base the prefix on the service (type) handling the request, the central authority for those prefixes could be a document in the development environment (i.e., to get a new prefix, the service needs to be modified, rebuilt and re-deployed). Apr 24 at 13:53
  • @BartvanIngenSchenau, exactly. Essentially, a block is allocated from the central registry to a service at compile-time. There is no possibility of reallocation at runtime (nor is there necessarily any need), and the coordination with the central registry occurs through the process of recompiling and distributing the software itself from a central source.
    – Steve
    Apr 24 at 14:12
  • I think the logic of this answer is flawed. The standard method of creating unique IDs without a central registry is to use GUIDs. The prefixes for each allocator can be GUIDs as well.
    – Doc Brown
    Apr 24 at 20:13
  • @DocBrown, my recollection of GUIDs is that it's based partly on the MAC address of the allocator (MACs being allocated centrally), and partly on the time of allocation (assumed to be fine-grained enough to make every allocation occur at a uniquely numbered moment). And collisions are only very unlikely in a single context of use, not guaranteed to be "globally unique" despite the name.
    – Steve
    Apr 24 at 20:42
  • 1
    Essentially he asks, "I run a lottery where people freely choose their own numbers; how do I ensure the same number is not picked twice, by anybody, ever? Including the case where the same person, since he can choose his own number, may try to play the same number twice.". Maintaining a central register of allocated numbers, and consulting it so as to veto any duplicate proposal, seems to me to be the only possible method. (2/2)
    – Steve
    Apr 25 at 3:20
1

You need to specify more information about the distributed service. Most systems have some central components.

For example, you could shard on the ID. so when an ID comes in you takes it hash to find out which shard is going to deal with it.

This will ensure that you still hit the duplicate key error. Even though you don't have a central index the same ID will got the same node and a duplicate error will be raised.

Maybe you can make it so duplicates don't matter, like if i have a ObjectA with id 1 and an ObjectB with id 1, if i always know if I want A or B the collision isn't critical.

Maybe you can do eventual consistency audits to catch the duplicates after the fact. If you are just worried about malicious creation this might be enough.

8
  • I believe sharding is more of a solution “within” a single service / table, and not across multiple services / separate databases. But within a single table this seems a good solution. Especially if you have a very large table and need to optimise for performance.
    – Philippe
    Apr 24 at 14:12
  • say you have a whole bunch of services that operate on a single large model, say Customer. so you have PlaceOrder, ChangeAddress, DoSums, whatever, as long as they have the customerid you could shard on that even if the services do things which dont change the customer object
    – Ewan
    Apr 24 at 16:01
  • true, with a shared database or context the problem does not really exist, or is easily solved. but i mainly had scenarios in mind where services do not have shared tables.
    – Philippe
    Apr 24 at 16:11
  • i don't mean a shared table, say i have some order service with placeOrder(custId,order) I can shard on the customerid and hit the same datacenter/distributed node as the CreateCustomer(customer) call would have hit
    – Ewan
    Apr 24 at 17:46
  • at that point you dont have to worry about the other distributed nodes and what customers they have, because if your node doesn't have it, it doesn't exist
    – Ewan
    Apr 24 at 17:47
0

Well quick answer is "you cant". If you have no control over what happens, there might be malitious ID and there is no way to prevent it.

The most minimalistic and good-performing solution I can think of is to have central service that generates IDs. However instead of having database and remember which IDs are used and which not, it will generate random ID (such as UUID which has almost zero chance of duplication), put it inside JWT token and then JWT token must be used when sending the object for persistance. You can check that ID sent in resource and in JWT is the same (+obviously you will check its valid JWT created by your service)

However I would not personally abuse the system that much. If you need unique IDs, it means its important to create resources somewhere eventually with these unique IDs. The clients application should be able to handle some kind of objects without IDs (or with some their own internal IDs) and assign the "real ID" when the resource is created in some core component.

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.