muyo/sno

This can be useful when multiple containers on one physical machine are to write as a cluster to a partition defined by the machine's ID (or simpler - multiple processes on one host). Or if multiple remote services across the globe were to do that.

var PeoplePartition = sno.Partition{'P', 0}

// In process/container/remote host #1
generator1, err := sno.NewGenerator(&sno.GeneratorSnapshot{
	Partition: PeoplePartition,
	SequenceMin: 0,
	SequenceMax: 32767 // 32768 - 1
}, nil)

// In process/container/remote host #2
generator2, err := sno.NewGenerator(&sno.GeneratorSnapshot{
	Partition: PeoplePartition,
	SequenceMin: 32768,
	SequenceMax: 65535 // 65536 - 1
}, nil)

You will notice that we have simply divided our total pool of 65,536 into 2 even and non-overlapping sectors. In the first snapshot SequenceMin could be omitted - and SequenceMax in the second, as those are the defaults used when they are not defined. You will get an error when trying to set limits above the capacity of generators, but since the library is oblivious to your setup - it cannot warn you about overlaps and cannot resize on its own either.

The pools can be defined arbitrarily - as long as you make sure they don't overlap across currently online generators.

It is safe for a range previously used by another generator to be assigned to a different generator under the following conditions:

• it happens in a different timeframe in the future, i.e. no sooner than after 4msec have passed (no orchestrator is fast enough to get a new container online to replace a dead one for this to be a worry);
• if you can guarantee the new Generator won't regress into a time the previous Generator was running in.

If you create the new Generator using a Snapshot of the former as it went offline, you do not need to worry about those conditions and can resume writing to the same range immediately - the obvious tradeoff being the need to coordinate the exchange of Snapshots.

If your clusters are always fixed size - reserving ranges is straightforward. With dynamic sizes, a potential simple scheme is to reserve the lower byte of the partition for scaling. Divide your sequence pool by, say, 8, keep assigning higher ranges until you hit your divider. When you do, increment partition by 1, start assigning ranges from scratch. This gave us 2048 identifiable origins by using just one byte of the partition.

That said, the partition pool available is large enough that the likelihood you'll ever need this is slim to none. Suffice to know you can if you want to.

Besides for guaranteeing a collision-free ride, this approach can also be used to attach more semantic meaning to partitions themselves, them being placed higher in the sort order. In other words - with it, the origin of an ID can be determined by inspecting the sequence alone, which frees up the partition for another meaning.

How about...

var requestIDGenerator, _ = sno.NewGenerator(&GeneratorSnapshot{
    SequenceMax: 32767,
}, nil)

type Service byte
type Call byte

const (
    UsersSvc   Service = 1
    UserList   Call    = 1
    UserCreate Call    = 2
    UserDelete Call    = 3
)

func genRequestID(svc Service, methodID Call) sno.ID {
    id := requestIDGenerator.New(byte(svc))
    // Overwrites the upper byte of the fixed partition. 
    // In our case - we didn't define it but gave a non-nil snapshot, so it is {0, 0}.
    id[6] = byte(methodID)

    return id
}

The sequence never overflows and the generator is designed with a single-return New() method that does not return errors nor invalid IDs. Realistically the default generator will never overflow simply because you won't saturate the capacity.

But since you can set bounds yourself, the capacity could shrink to 4 per 4msec (smallest allowed). Now that's more likely. So when you start overflowing, the generator will stall and pray for a reduction in throughput sometime in the near future.

From sno's persective requesting more IDs than it can safely give you immediately is not an error - but it may require correcting on your end. And you should know about that. Therefore, if you want to know when it happens - simply give sno a channel along with its configuration snapshot.

When a thread requests an ID and gets stalled, once per time unit, you will get a SequenceOverflowNotification on that channel.

type SequenceOverflowNotification struct {
    Now   time.Time // Time of tick.
    Count uint32    // Number of currently overflowing generation calls.
    Ticks uint32    // For how many ticks in total we've already been dealing with the *current* overflow.
}

Keep track of the counter. If it keeps increasing, you're no longer bursting - you're simply over capacity and eventually need to slow down or you'll eventually starve your system. The Ticks count lets you estimate how long the generator has already been overflowing without keeping track of time yourself. A tick is roughly 1ms.

The order of generation when stalling occurs is undefined. It is not a FIFO queue, it's a race. Previously stalled goroutines get woken up alongside inflight goroutines which have not yet been stalled, where the order of the former is handled by the runtime. A livelock is therefore possible if demand doesn't decrease. This behaviour may change and inflight goroutines may get thrown onto the stalling wait list if one is up and running, but this requires careful inspection. And since this is considered an unrealistic scenario which can be avoided with simple configuration, it's not a priority.

sno attempts to eliminate the issue entirely - both despite and because of its small pool of bits to work with.

The approach it takes is simple - each generator keeps track of the highest wall clock time it got from the OS*, each time it generates a new timestamp. If we get a time that is lower than the one we recorded, i.e. the clock drifted backwards and we'd risk generating colliding IDs, we toggle a bit - stored from here on out in each sno generated until the next regression. Rinse, repeat - tick, tock.

(*IDs created with a user-defined time are exempt from this mechanism as their time is arbitrary. The means to bring your own time are provided to make porting old IDs simpler and is assumed to be done before an ID scheme goes online)

In practice this means that we switch back and forth between two alternating timelines. Remember how the pool we've got is 16,384,000 IDs per second? When we tick or tock, we simply jump between two pools with the same capacity.

Why not simply use that bit to store a higher resolution time fraction? True, we'd get twice the pool which seemingly boils down to the same - except it doesn't. That is due to how the sequence increases. Even if you had a throughput of merely 1 ID per hour, while the chance would be astronomically low - if the clock drifted back that whole hour, you could get a collision. The higher your throughput, the bigger the probability. ID's of the Snowflake variant, sno being one of them, are about guarantees - not probabilities. So this is a sno-go.

(I will show myself out...)

The simplistic approach of tick-tocking entirely eliminates that collision chance - but with a rigorous assumption: regressions happen at most once into a specific period, i.e. from the highest recorded time into the past and never back into that particular timeframe (let alone even further into the past).

This generally is exactly the case but oddities as far as time synchronization, bad clocks and NTP client behaviour goes do happen. And in distributed systems, every edge case that can happen - will happen. What do?

• Sonyflake goes to sleep until back at the wall clock time it was already at previously. All goroutines attempting to generate are blocked.
• snowflake hammers the OS with syscalls to get the current time until back at the time it was already at previously. All goroutines attempting to generate are blocked.
• xid goes ¯\(ツ)/¯ and does not tackle drifts at all.
• Entropy-based specs (like UUID or KSUID) don't really need to care as they are generally not prone, even to extreme drifts - you run with a risk all the time.

The approach one library took was to keep generating, but timestamp all IDs with the highest time recorded instead. This worked, because it had a large entropy pool to work with, for one (so a potential large spike in IDs generated in the same timeframe wasn't much of a consideration). sno has none. But more importantly - it disagrees on the reasoning about time and clocks. If we moved backwards, it means that an adjustment happened and we are now closer to the correct time from the perspective of a wider system.

sno therefore keeps generating without waiting, using the time as reported by the system - in the "past" so to speak, but with the tick-tock bit toggled.

If another regression happens, into that timeframe or even further back, only then do we tell all contenders to wait. We get a wait-free fast path most of the time - and safety if things go southways.

Even though the toggle is not part of the milliseconds, you can think of it as if it were. Toggling is then like moving two milliseconds back and forth, but since our milliseconds are floored to increments of 4msec, we never hit the range of a previous timeframe. Alternating timelines are as such sorted as if they were 2msec apart from each other, but as far as the actual stored time is considered - they are timestamped at exactly the same millisecond.

They won't sort in an interleaved fashion, but will be right next to the other timeline. Technically they were created at a different time, so being able to make that distinction is considered a plus by the author.

Untyped integers can pass as uint8 (i.e. byte) in Go, so the following would work and keep things tidy:

const (
	PersonType = iota
	OtherType
)

type Person struct {
	ID   sno.ID
	Name string
}

person := Person{
	ID:    sno.New(PersonType),
	Name: "A Special Snöflinga",
}

• IDs for requests in a HTTP context: 1 byte is enough to contain one of all possible standard HTTP status codes. Et voila, you now got all requests that resulted in an error nicely sorted and clustered.
  Limit yourself to the non-exotic status codes and you can store the HTTP verb along with the status code. In that single byte. Suddenly even the partition (if it's tied to a machine/cluster) gains relevant semantics, as you've gained a timeseries of requests that started fail-cascading in the cluster. Constrain yourself even further to just one bit for OK or ERROR and you made room to also store information about the operation that was requested (think resource endpoint).

• How about storing a (immutable) bitmask along with the ID? Save some 7 bytes of bools by doing so and have the flags readily available during an efficient sequential key traversal using your storage engine of choice.

• Want to version-control a Message? Limit yourself to at most 256 versions and it becomes trivial. Take the ID of the last version created, increment its metabyte - and that's it. What you now have is effectively a simplistic versioning schema, where the IDs of all possible versions can be inferred without lookups, joins, indices and whatnot. And many databases will just store them close to each other. Locality is a thing.
  How? The only part that changed was the metabyte. All other components remained the same, but we ended up with a new ID pointing to the most recent version. Admittedly the timestamp lost its default semantics of moment of creation and instead is moment of creation of first version, but you'd store a revisedAt timestamp anyways, wouldn't you?
  And if you really wanted to support more versions - the IDs have certain properties that can be (ab)used for this. Increment this, decrement that...

• Sometimes a single byte is all the data that you actually need to store, along with the time when something happened. Batch processing succeeded? sno.New(0), done. Failed? sno.New(1), done. You now have a uniquely identifiable event, know when and where it happened, what the outcome was - and you still had 7 spare bits (for higher precision time, maybe?)

• Polymorphism has already been covered. Consider not just data storage, but also things like (un)marshaling polymorphic types efficiently. Take a JSON of {id: "aaaaaaaa55aaaaaa", foo: "bar", baz: "bar"}. The 8-th and 9-th (0-indexed) characters of the ID contain the encoded bits of the metabyte. Decode that (use one of the utilities provided by the library) and you now know what internal type the data should unmarshal to without first unmarshaling into an intermediary structure (nor rolling out a custom decoder for this type). There are many approaches to tackle this - an ID just happens to lend itself naturally to solve it and is easily portable.

• 2 bytes for partitions not enough for your needs? Use a fixed byte as the metabyte -- you have extended the fixed partition to 3 bytes. Wrap a generator with a custom one to apply that metabyte for you each time you use it. The metabyte is, after all, part of the partition. It's just separated out for semantic purposes but its actual semantics are left to you.