New subject-ID expression: quadratic probing, extended range

[pavel-kirienko]

https://en.m.wikipedia.org/wiki/Quadratic_probing

[pavel-kirienko]

If we extend the subject-ID space to 16 bits (#14) and reserve the lowest ones for v1.0 pinned topics and keeping 65535 reserved for future needs, then in the most naive case we end up with $2^{16}-8192 = 57344$ identifiers. Picking good $c_1,c_2$ for this number is tricky. However, we could simplify the problem by adjusting the subject-ID space such that it is a prime number. The nearest primes are 57347, 57349, 57367, 57373, 57383, and 57389.

The maximum fixed subject-ID that is actually used in v1.0 is 8184, meaning that we have at most $2^{16}-8184 = 57352$ available values, if we sacrifice the top few items in the v1 space that are not currently used. This means that we can pick 57349.

Choosing 57349 results in the allowed range of [8187, 65535], then we just go with $c_1=0,c_2=1$, and the subject-ID allocation expression becomes:

8187 + (hash + evictions * evictions) % 57349

This scheme is valid until the subject-ID space utilization exceeds 50%, meaning that the theoretical scalability cap is 28674 topics.

[pavel-kirienko]

We can reserve subject-IDs 8185 and 8186 as they are neither used in v1.0 nor needed for v1.1. I don't have a particular use for them in mind yet but it could possibly be useful in the future.

[pavel-kirienko]

If the subject-ID range is transport-dependent and scales with the max number of topics, then we have:

• 16 or 17 bits for CAN
• 23 bits for IPv4 (multicast MAC limit)
• 32 bits for IPv6 (see GAAP and related RFCs)
• unlimited for serial

The modulus values that work are:

• CAN: 57349 as above; if we go with 17 bits: $2^{17}-8187=122885$, nearest prime 122869
• IPv4: $2^{23}-8187=8380421$, nearest prime 8380417
• IPv6: $2^{32}-8187=4294959109$, nearest prime 4294959083

The 0.1% collision probability per modulus is reached with the number of topics:

• 57349: 12 topics
• 122869: 17 topics
• 8380417: 130 topics
• 4294959083: 2933 topics