Provide true monotonicity guarantee

[rrichardson]

Thanks for creating such a great utility. I love how well organized and especially well documented it is.

Would there be interest in an API for this which provides a next_monotonic but does so using a thread-safe context and the value is updated atomically? I understand that this might be a major departure from the scope of this crate, which is why I'm asking. I'm happy to make the enhancements, but only if you are interested in such a scope change/increase.

If so, here's my thoughts:

1. Ulid isn't actually guaranteed to be monotonically increasing: If 2 Id's are generated in the same millisecond, their date bits will be equal, but the random bits could be ordered incorrectly.
   Multiple ULIDs per millisecond not guaranteed ulid/spec#11
2. If we want true monotonicity, we need to have a counter whose significant bits are higher than the random bits.
3. So we steal 12 bits from random to create a counter. (to legacy ULIDs, this is still valid "random" data)
4. We atomically compare and swap the date of the previously generated Ulid.
5. To do so, it needs to live in its own 64bit word that is aligned.
6. Luckily, we don't need the entire previous Ulid, just the timestamp that was used to create it.
7. I was thinking we could wrap the Timmestamp in a simple struct that is just UlidContext (and it would need to be wrapped in an Arc in order to be passed across threads safely.
8. The Timestamp would be shifted 12 bits to the left to allow for the counter.
9. So a thread-friendly next_monotonic function might be:

    fn threadsafe_next_monotonic(ctx: Arc<UlidContext>) -> Option<Ulid> {
        let mut next = unix_epoch_ms() << 12;
        let mut current = ctx.0.load(Ordering::Acquire);
        let mut counter = current >> 48; 
        while next != ctx.0.compare_and_swap(current, next, Ordering::Acquire) {
          current = ctx.0.load(Ordering::Acquire); 
          next = current + 1;
        }
        return ulid_with_context_and_rng(ctx, &mut rand::thread_rng());
    }

This isn't correct code, and I'm sure the algo could be made to be safer and more efficient.
That's the basic idea, though.
It would be a bit slower than the non-threaded version, but, that is usually the case.

Edit : Man I really typo'd the crap out of this post. I need to get more sleep

[huxi]

I'm not sure about this change.
I considered something - not exactly but similar - while implementing the support for monotonic ULIDs.

I decided to implement it the way it's done right now because it takes away the responsibility of thread-safety from this crate and puts the burden on the user. Not because I'm lazy or afraid of implementing it, but because it's use-case-specific what kind of monotonicity is required/desired.

So if you call the next_strictly_monotonic_from_timestamp_with_rng function, it's up to the user where they got previous_ulid, timestamp and rng from. Those could come from a an Arc<Contex> or simply from a local variable in case of single-threaded use.

I ultimately implemented it like this because of separation of concerns and the current Rust restraint that it's impossible (to my knowledge) to write code receiving either a Rc<Something> or Arc<Something>, decided at build-time.

Please don't consider this as a strict "no" from my side. I just wanted to explain the rationale for the current implementation.

[rrichardson]

I understand your point. That's why I asked.
I am pushing the ULID spec owners to amend their recommendation. If you think about it, incrementing an 80 bit random number one time and thinking it will actually make it higher than the previous number is kind of a silly notion. edit This is unfair to say. This obviously does work, simply by repeating the last value, incremented by one, but it is provably not the best approach.

Perhaps the middle ground is to fix the existing monotonic implementation so that it does provide monotonicity guarantees, but leaves the multi-threading as an exercise for the user.

[huxi]

@rrichardson
I just released 0.10.0 with the following new functions:

• next_monotonic_from_timestamp_with_rng_and_postprocessor
• next_strictly_monotonic_from_timestamp_with_rng_and_postprocessor

You'd use them in your own use-case specific implementation like this:

fn postprocessor_fn(ulid: Ulid) -> Ulid {
    // zero out lowest 32 bits
    Ulid::from(u128::from(ulid) & 0xFFFF_FFFF_FFFF_FFFF_FFFF_FFFF_0000_0000)
}

let previous_ulid = /* obtained from somewhere unspecified */;
let ulid = Ulid::next_strictly_monotonic_from_timestamp_with_rng_and_postprocessor(
    Some(previous_ulid),
    timestamp,
    &mut rand::thread_rng(),
    Some(&postprocessor_fn),
);

Hope this helps.