spider-gazelle / rethinkdb-orm

RethinkDB ORM for Crystal lang
MIT License
24 stars 0 forks source link

ID generator #31

Closed kimburgess closed 3 years ago

kimburgess commented 3 years ago

Implements a new ID generator with high collision resistance, strong in-process uniqueness and protection against enumeration attacks.

The existing form and API remains to reduce external impact, but improves on entropy.

example-CVwb9JzmoJ
   │        │ 
   │        └time-sortable tail
   │ 
   └table name

The approach is designed to provide useful performance under observed real-world conditions:

  1. Short term bursts within a single process - occurs during batch operations either during environment init, or multiple entities being created from a single, or set of related requests.
  2. Distributed, low rate generation across a number of processes and machines (normal service operation).

Within a process, ID's are guaranteed unique and non-repeating for a minimum 230-1 generations and continue indefinitely without periodic behaviour. Ignoring external collisions, this provides at least 1,073,741,823 id's per second.

Across processes, 30 bits of entropy is available per second. This provides a collisions probably of ~0.012% at a sustained 500 model creations per second and no coordination required.

kimburgess commented 3 years ago

Note: failing specs due to unrelated issue addressed in #30. Status will return to green with the combo of these two PR's.

kimburgess commented 3 years ago

Point to consider before merge (and document as part of any release using this). There is a small slice of time between 2014-01-01 and ~2014-01-31 where ID's may overlap with the previous form, but collision probably is low.

More importantly, new ID's generated through until ~2050 are shorter than the old form. This will result in them sorted ahead of any previously built ones. Hopefully that behaviour is not dependant on solely in downstream systems, but worth flagging just in case.