8 ms·

Why should a Trace-ID be 128 bits? (A Surprisingly Long Answer)

13 points by elza_1111 5mo ago

gpderetta 4mo ago
TL;DR Birthday Paradox.
- qbane 4mo ago
  tl;dr we reinvented UUID and it works well
  - drdaeman 4mo ago
    Certainly not true. UUIDs have structure to them, and variants. Trace IDs are just 128-bit numbers, with any further semantics (almost) completely non-standardized (some systems encode timestamps, etc). They slapped a “last 56 bits are random” flag (not in the ID itself but as external metadata, so not like UUID at all) later giving IDs just a bit of semantics, but it’s not a reinvention of UUIDs.
    - qbane 4mo ago
      Okay, sightly more bits than UUID v4. The whole article is merely reasoning "why at least 128 bits are required", and if you smuggle some non-random data inside these bits the entropy can only drop, making it more vulnerable to collision, i.e. inferior to UUID v4.
      - ralferoo 4mo ago
        I kind of addressed this in https://news.ycombinator.com/item?id=48060549 https://news.ycombinator.com/item?id=48060549 Actually, because the birthday paradox has k^2 as a term, this is actually less true than you might think. Having a time component actually reduces the chance of collisions over the long run, albeit at a cost of reducing the number that can be safely generated in any given quantum. If you consider a 128-bit random number, you effectively have 64 bits of allocation space before you are likely to get a collision. If you devote 48-bits to time, which provides millisecond accuracy for 9000 years, you then have 80 bits of randomness, effectively giving 40 bits of allocation space per millisecond before you are likely to get a collision. Instead of approx 2^64 allocations across all time before a collision, you instead have 2^40 (1 trillion per millisecond). That sounds like a poor deal, until you realise that the factor is only 2^24, or 16777216ms or under 280 minutes. So in reality, reducing the random space and increasing bits that are guaranteed unique is actually a great trade.
        qbane 4mo ago
        I realized that my mentioning UUID without v4 was misleading.
devin 4mo ago
From a practical standpoint, isn't it usually the case that there are retention periods for traces given how numerous they can be? I bring this up because this article starts with "I asked Claude", but it doesn't explore the the length of time you're generating IDs over at all, which is an important aspect to consider when selecting size.
- singron 4mo ago
  Yes. The original Dapper used 64 bit trace ids and collisions were rarely a problem. If you don't drop any spans from a trace, you can completely disambiguate a collision since the trace will have two distinct root spans. If you are missing spans, you might have a break in the parent-child links. Even with infinite retention, your analysis will bucket by time somehow, so a collision might have no effect if the collision doesn't happen at a proximate time. If you are manually looking at traces, it will be very obvious there is a collision unless they happen at the same time. Also, birthday paradox only expresses probability that there is a collision somewhere, but if you are filtering or looking at single spans, then the probabiliy that you actually see a collision is greatly reduced. I think for basically all systems, an additional 64-bits has insignificant additional cost, so you may as well prevent collisions, but I think it could be a reasonable tradeoff if it mattered.
  - devin 4mo ago
    nod Adding this to my growing list of "things experienced engineers would discuss which is conspicuously missing in this case" The future is going to be filled with "best practices" trendslop decision-making.
ralferoo 4mo ago
Surprised the author didn't even think about the logical conclusion of his closing paragraph: "128 bits is the ideal sweet spot, collision safety effectively forever, and it happens to match the size of a UUID, which means every database, every language, and every protocol already knows how to handle it." UUIDs are already generated randomly for exactly the same reason. Rather than inventing something new, they should have just used a UUID.
- benmmurphy 4mo ago
  Generating 16 random bytes is simpler than generating a random UUID
  - drdaeman 4mo ago
    And there’s a good reason for that, because UUIDs have additional properties. I don’t know if versioning, partial ordering, or stable references are useful for traces or not, but with UUIDs those could’ve been a possibility.
  - ralferoo 4mo ago
    It basically makes no odds, unless you consider applying a constant AND and constant OR operator complicated - as UUID v4 is just 122 random bits and 6 bits fixed. UUID v7 is a 48 bit timestamp, 74 random bits and 6 bits fixed. Sure, this is a little more complicated, but it's often worth it for many applications because it can be sorted, so keys will be approximately monotonically increasing.
    - benmmurphy 4mo ago
      I think UUIDv7 could make sense but I suspect the recommendations in the spec predate UUIDv7. Also, if you want sorted schemes then there are slightly more efficient schemes than UUIDv7. With UUID you are always sacrificing some bits to distinguish between the UUID types which I guess does not really matter in practice but it seems unnecessary.
      - 4mo ago
_trampeltier 4mo ago
Why not 256, "because of bandwith costs". An adblocker does save bandwith costs, but not a handful bytes from an ID.

13 points by elza_1111 5mo ago

gpderetta 4mo ago

TL;DR Birthday Paradox.

qbane 4mo ago
tl;dr we reinvented UUID and it works well
- drdaeman 4mo ago
  Certainly not true. UUIDs have structure to them, and variants. Trace IDs are just 128-bit numbers, with any further semantics (almost) completely non-standardized (some systems encode timestamps, etc). They slapped a “last 56 bits are random” flag (not in the ID itself but as external metadata, so not like UUID at all) later giving IDs just a bit of semantics, but it’s not a reinvention of UUIDs.
  - qbane 4mo ago
    Okay, sightly more bits than UUID v4. The whole article is merely reasoning "why at least 128 bits are required", and if you smuggle some non-random data inside these bits the entropy can only drop, making it more vulnerable to collision, i.e. inferior to UUID v4.
    - ralferoo 4mo ago
      I kind of addressed this in https://news.ycombinator.com/item?id=48060549 https://news.ycombinator.com/item?id=48060549 Actually, because the birthday paradox has k^2 as a term, this is actually less true than you might think. Having a time component actually reduces the chance of collisions over the long run, albeit at a cost of reducing the number that can be safely generated in any given quantum. If you consider a 128-bit random number, you effectively have 64 bits of allocation space before you are likely to get a collision. If you devote 48-bits to time, which provides millisecond accuracy for 9000 years, you then have 80 bits of randomness, effectively giving 40 bits of allocation space per millisecond before you are likely to get a collision. Instead of approx 2^64 allocations across all time before a collision, you instead have 2^40 (1 trillion per millisecond). That sounds like a poor deal, until you realise that the factor is only 2^24, or 16777216ms or under 280 minutes. So in reality, reducing the random space and increasing bits that are guaranteed unique is actually a great trade.
      - qbane 4mo ago
        I realized that my mentioning UUID without v4 was misleading.

devin 4mo ago

From a practical standpoint, isn't it usually the case that there are retention periods for traces given how numerous they can be? I bring this up because this article starts with "I asked Claude", but it doesn't explore the the length of time you're generating IDs over at all, which is an important aspect to consider when selecting size.

singron 4mo ago
Yes. The original Dapper used 64 bit trace ids and collisions were rarely a problem. If you don't drop any spans from a trace, you can completely disambiguate a collision since the trace will have two distinct root spans. If you are missing spans, you might have a break in the parent-child links. Even with infinite retention, your analysis will bucket by time somehow, so a collision might have no effect if the collision doesn't happen at a proximate time. If you are manually looking at traces, it will be very obvious there is a collision unless they happen at the same time. Also, birthday paradox only expresses probability that there is a collision somewhere, but if you are filtering or looking at single spans, then the probabiliy that you actually see a collision is greatly reduced. I think for basically all systems, an additional 64-bits has insignificant additional cost, so you may as well prevent collisions, but I think it could be a reasonable tradeoff if it mattered.
- devin 4mo ago
  nod Adding this to my growing list of "things experienced engineers would discuss which is conspicuously missing in this case" The future is going to be filled with "best practices" trendslop decision-making.

ralferoo 4mo ago

Surprised the author didn't even think about the logical conclusion of his closing paragraph: "128 bits is the ideal sweet spot, collision safety effectively forever, and it happens to match the size of a UUID, which means every database, every language, and every protocol already knows how to handle it." UUIDs are already generated randomly for exactly the same reason. Rather than inventing something new, they should have just used a UUID.

benmmurphy 4mo ago
Generating 16 random bytes is simpler than generating a random UUID
- drdaeman 4mo ago
  And there’s a good reason for that, because UUIDs have additional properties. I don’t know if versioning, partial ordering, or stable references are useful for traces or not, but with UUIDs those could’ve been a possibility.
- ralferoo 4mo ago
  It basically makes no odds, unless you consider applying a constant AND and constant OR operator complicated - as UUID v4 is just 122 random bits and 6 bits fixed. UUID v7 is a 48 bit timestamp, 74 random bits and 6 bits fixed. Sure, this is a little more complicated, but it's often worth it for many applications because it can be sorted, so keys will be approximately monotonically increasing.
  - benmmurphy 4mo ago
    I think UUIDv7 could make sense but I suspect the recommendations in the spec predate UUIDv7. Also, if you want sorted schemes then there are slightly more efficient schemes than UUIDv7. With UUID you are always sacrificing some bits to distinguish between the UUID types which I guess does not really matter in practice but it seems unnecessary.
    - 4mo ago

_trampeltier 4mo ago

Why not 256, "because of bandwith costs". An adblocker does save bandwith costs, but not a handful bytes from an ID.