53-bit SessionID collision risk, is it a problem?

[tsukkiren]

Hi, this library looks fantastic, but one thing holding me back is the SessionID size.

Why not use a full 128-bit UUID? Unless there is a central server coordinating everything, it seems possible for two forks of a document to end up with two identical SessionIDs that then cannot be later merged.

[streamich]

Hi @tsukkiren, the 53-bit session IDs (sid) should not be a problem. I think even smaller values would work.

The reason for choosing 53-bit values is because it is the largest numeric value in JavaScript with which one can performantly work with. Storing and working with 128-bit UUID is inefficient. There are storage costs, but also runtime costs: all algorithms need to constantly do sid comparisons and having a sid in a number is the most efficient way.

Also, runtime memory costs, all document nodes and RGA chunks have an ID assigned to them, when a document with thousands of nodes is loaded, it is thousands of nodes times the number of bytes the sid consumes. If the sid is represented by UUID I reckon it woud use at least 10x more memory (be they stored in Uint8Array or [number, number, number, number] 4-tuple).

The likelihood that two sids can collide is one in 2 ** 53 = 9007199254740992, even if they collide it does not necessarily mean that the document gets into a corrupted state. I have not tested it, but in theory it should get corrupted only if two peers generate the same sid AND edit the same part of the document (conflicting change) AND do it concurrently AND the changes are semantically different.

If there is a central server, non of that applies; the server just enforces the Patch order and contents. The library even has the ability to run the JSON CRDT in the "server-clock" mode, where sid is set to 1 for all peers.

Going forward the 53-bit value could potentially be increased to 64 bits. The 53-bit limitation currently exists in binary storage format (not in compact nor in verbose). The binary format would need to be modified to allow 64-bit values. Also, at runtime the sid is represented as number, we could change it to bigint in the future.

[tsukkiren]

Question: Is there actually any cost to increasing the sid size to 128 bits? It seems it would cost an extra 64 bits per patch in storage, and an extra 64 bits per id in a document. I guess that's insignificant even with thousands of patches and dozens of users?

Would it slow the patch processing time at all? If an sid is just a 64-bit pointer to a 128-bit value in memory then it seems no more memory cost per patch item than directly using a 64-bit sid value.

[tsukkiren]

Also

I don't think there will ever be millions of contributors for a single document. Simply because all session IDs need to be stored in the clock table. Say, you had a million contributors each identified by their own sid, which is UUID (16 bytes), that is 16 MB of data just to store the clock table.

I don't mean a million contributors in a single document but a million contributors across a million forks, any of which could be merged with any other.

I agree collision risks are still low, but not sure I see the advantage to keeping at 53/64 bits when seems so cheap to bump up the size and not have to think about these things.

[streamich]

I don't think Birthday Problem applies that way if sid is checked for all already known used sids. To use Birthday Paradox calculation here one would need to take as N the number of concurrently chosen sids. So, if at the same time 3 users pick a sid we need to calculate 3 out of 2 ** 53 probability. (Which according to the Birthday Paradox formula makes it less likely than one in quadrillion (million billion).)

Costs of storing extra sid entropy are not small. Patch and model sizes would grow by more than 64 bits for each sid stored. Assuming there are million million documents the extra storage cost would be well into petabytes. Also, code changes and runtime performance.

We are not increasing the sid entropy unless there is a good concrete reason. So far I have not seen one.

It does not matter how many millions of contributors and how many millions of forks there are. What matters is how many of them are actually merged, if only two forks are merged and users of those forks picked sids concurrently that is Birthday Paradox probability of N = 2 out of 2 ** 53.

If those users did not pick their sid concurrently. For example, one user forked from another. There will be 0% chance of collision, as that second user will check for all known sids when forking.

I did not really follow the idea of document IDs. Document IDs should be something completely external, which internal model knows nothing about.

[tsukkiren]

I did not really follow the idea of document IDs. Document IDs should be something completely external, which internal model knows nothing about.

I meant the reverse (document aware of the internal model), but on second though reusing the CRDT logical clock for entity ids in the JSON document a bad idea (if you copied an entity to another document the clock value and therefore id would change). Makes sense to keep these things separate.

Other than that, you're right. Birthday Problem applies to only concurrent chosen sids later merged into one document, which should never approach a million. I'm trying hard to find a scenario where collision risk is likely and not finding one. I think my 1/180 above is actually 1/18,000, dropping to 1 / 18billion for 1000 concurrently chosen ids.

Maybe just change Math.random() to cryptographic randomness in the sid generator function and 53-bits is good.

Thanks for thinking this through with me.

[streamich]

Thanks for you inputs, I've updated the forking code, now when forking, out-of-the-box the document will check for all already consumed sids. Which means the collision chance is 0% when you are "connected". And when you don't have network, the collision chance is the number of forks created while all peers were offline out of 9007199253740992 possibility space, as per Birthday Paradox formula (one in million billion chance for five forks created concurrently).

I don't think we need cryptographically secure random number generator here. Because we generate only one number, and it happens very infrequently on different user's devices in different moments of time; their randomly seeded Math.random() should be enough.

V8 uses 128 bits of entropy in Math.random(), we need only 53 bits.