Snowflake

Background

ID generation is an essential part of any application development, and it can be achieved through an uncountable number of methods. These IDs can be used for stuff as simple as an index for DB, to complicated things such as Order ID.

Auto Increment

The simplest, and the most basic ID generation, which almost everyone has used since their school days is the incremental (or the auto-increment) ID. They are easy to use, simple to understand, and usually fulfill the most basic of requirements.

In-memory storage, DB incremental ID, or GID are the most common ways to achieve this. But each method has its limitations of course. And none of them really work for highly-available distributed systems (trust me, I tried!).

1. Single Point of Failure
2. Tracking
3. Hawt-Spot

What Do We Need

There are a few important points we need to tackle to improve the ID Generation.

Single Point Of Failure

To achieve more availability in our distributed system, we need to be able to generate these IDs from different Micro-services. This is the most basic problem to solve. We can simply add a database for all the services to access and use to generate the IDs. But, at the end of the day, this will just push the problem from the service layer to the database layer. What we eventually need, is multiple services that can generate the unique IDs without depending on any external service or database.

Tracking

Most ID generator tools are auto-increment IDs. Which, on one hand, can guarantee uniqueness, but, on the other hand, can be very insecure. It’s weak to brute force attack, and can even allow external parties to calculate the exact number of Orders or Accounts created in a defined range of time. To fix this problem we can either skip random IDs or use a method that gives us random unique IDs.

Hotspot

It’s not common for databases with a large number of entities to have hotspots across the database. It usually occurs when the keys frequently accessed are in the same range and the database has partitioned them in a single partition. Usually, this can be solved by manually sharding the tables and/or databases to distribute the data equally across multiple databases. But, when it comes to using a RocksDB to support larger datasets (especially with TiKV in TiDB) the sequential nature of the ID might hurt the performance even more.

Thanks, Twitter

In 2010 Twitter published a new algorithm for generating random IDs, that promises uniqueness, and increasing numbers over time. And would allow for these IDs to be generated from independent machines, with limited (or even zero!) dependency on any external database.

Snowflake uses int64 bits to generate these IDs based on the timestamp & the machine ID to guarantee uniqueness.

In the initial implementation (reading from left to right) the first bit will be reserved for sign and therefore unused, and it’s followed by 41 bits reserved as the timestamp bits. These bits for timestamp (in millisecond) leaves us with about 69 years (nice!) of ID generation (2^41/(1000*(3600*24)*365)). The timestamp is relative and can be set to start at any arbitrary time, based on the needs of the business. The only thing to consider is, that it can’t be changed (well, not really! but it can’t be changed easily) after the ID generation has been started.
This will leave us with 22 bits to be used for the uniqueness of each ID for a specific timestamp. In the initial design, these 22 bits were divided into 10 + 12 bits, but it can be altered based on the needs of the application as well.
The first 10 are used as machine bits. Each machine will be assigned a number at the start that is unique to that machine, and can’t overlap with any other running machine. This can either be hardcoded to each server or be read from a shared database at the startup. Using these 10 bits should allow us to have 1024 (2^10) nodes running at the same time. The next 12 bits are considered the sequential bits counted in every millisecond. This would give us 4096 IDs per millisecond, per node. But these bits can be switched around accordingly to achieve a more vertical or horizontal design as well.

Coding

So something that would resemble this algorithm would look like this

...
func NewSnowflake(machineID uint16) *Snowflake {
	return &Snowflake{
		machineID: machineID,
	}
}

func (sf *Snowflake) Generate() (uint64, error) {
	var idBuilder uint64
	var err error
	idBuilder = TimeNow64() - BIGBANG

	// add machine id
	idBuilder = idBuilder << BitLenMachine
	idBuilder += uint64(sf.machineID)

	// add timestamp mili
	idBuilder = idBuilder << BitLenSq
	nxtId, err += NextSq()
	idBuilder += uint64(nxtId)
	
	return idBuilder, err
}

// next calculator
var (
	lastTimestamp = uint64(0)
	sqCount       = uint16(0)
	sqStart       = uint16(0)
	mx            sync.Mutex
)

func NextSq() (uint16,err) {
	mx.Lock()
	defer mx.Unlock()

	if TimeNow64() < lastTimestamp {
		return 0, errors.New("time travel features are not supported yet")
	}

	if TimeNow64() == lastTimestamp {
		sqCount += 1
		if sqCount > uint16(math.Pow(2, BitLenSq)) { // 4096 by default
			sqCount = 0 // reset sqCount
		} else if sqCount == sqStart {
			return 0, errors.New("failed to generate an ID due to hitting max count")
		}
	} else {
		sqStart = NewRand()
		sqCount = sqStart + 1
	}
	lastTimestamp = TimeNow64()
	return sqCount, nil
}
...

Final Thoughts & Improvements

There aren’t many ways to improve the algorithm in my opinion, but there are bits we can replace to cater the algorithm to our needs. For example, the timestamp is one of the areas that can lose a couple of bits since 69 years is not a feasible timeline. Another place I would personally reconsider is the sequential ID required from each server. In my experience, the average concurrency hitting each of the servers is less than 100, which leaves us with 7 (or 6, to be safe) to increase the number of servers, as long as we can guarantee the load balance between the servers is doing just fine!