search

f4b6a3 / tsid-creator

A Java library for generating Time-Sorted Unique Identifiers (TSID).
MIT License
475 stars 50 forks source link

Fix incremental generation #24

Closed fillumina closed 1 year ago

fillumina commented 1 year ago

In rare cases it is possible that a new generated TSID value is less than the previous one thus violating the requirement of being an incremental identifier.

This is caused by the CLOCK_DRIFT_TOLERANCE check in TsidFactory#getTime(): when the factory generates more than CLOCK_DRIFT_TOLERANCE * 2^(counterBits) values within the same millisecond (time = clock.millis() is unchanged), the condition

if ((time > this.lastTime - CLOCK_DRIFT_TOLERANCE) && (time <= this.lastTime))

is not satisfied and time is not updated by the incremented this.lastTime. This results in the final TSID being less in value than the previous one. It happens in rare cases but it may be easily corrected by removing the drift check.

The drift check is not needed anyway because a drift in time will be automatically adjusted by the time <= this.lastTime condition (as showed in the included IncrementalTest).

I also removed the synchronized keyword from getTime() because it is called within a synchronized block in create() anyway.

fabiolimace commented 1 year ago

You are right @fillumina. Checking clock drift is not necessary and can break monotonicity in rare cases. PR accepted!

I will also include a reference to your article in the README.md file.

Thanks for the contribution!

fabiolimace commented 1 year ago

Released v5.2.1. 🎉

fillumina commented 1 year ago

Hi Fabio, you are welcome! I really like the project, keep it up Francesco

On Sat, Jan 28, 2023 at 9:21 PM Fabio Lima @.***> wrote:

You are right @fillumina https://github.com/fillumina. Checking clock drift is not necessary and can break monotonicity in rare cases. PR accepted!

I will also include a reference to your article in the README.md file.

Thanks for the contribution!

— Reply to this email directly, view it on GitHub https://github.com/f4b6a3/tsid-creator/pull/24#issuecomment-1407478439, or unsubscribe https://github.com/notifications/unsubscribe-auth/AAMP5VUCEZ5FHGL4J4PDGYLWUV5VTANCNFSM6AAAAAAUEGJVMQ . You are receiving this because you were mentioned.Message ID: @.***>

fillumina commented 1 year ago

Hi Fabio, are you aware of this project I just found by chance? https://tsid.com/en

I have also written a blob where I think I speak quite well about your project, it might interest you.

https://fillumina.wordpress.com/2023/02/06/the-primary-key-dilemma-id-vs-uuid-and-some-practical-solutions/

Regards Francesco

On Wed, Feb 8, 2023 at 6:33 PM Francesco Illuminati @.***> wrote:

Hi Fabio, you are welcome! I really like the project, keep it up Francesco

On Sat, Jan 28, 2023 at 9:21 PM Fabio Lima @.***> wrote:

You are right @fillumina https://github.com/fillumina. Checking clock drift is not necessary and can break monotonicity in rare cases. PR accepted!

I will also include a reference to your article in the README.md file.

Thanks for the contribution!

— Reply to this email directly, view it on GitHub https://github.com/f4b6a3/tsid-creator/pull/24#issuecomment-1407478439, or unsubscribe https://github.com/notifications/unsubscribe-auth/AAMP5VUCEZ5FHGL4J4PDGYLWUV5VTANCNFSM6AAAAAAUEGJVMQ . You are receiving this because you were mentioned.Message ID: @.***>

fabiolimace commented 1 year ago

Hello Francesco!

Very interesting! I don't think the Travel Sentry IDs are the same as this project's IDs, but it's really nice to know it could be a use case.

I added your most recent article to README.md. Thanks!

Also added a link to your ID Encryptor as it solves the next sequence value guessing attack issue.

Best regards Fabio