New feature suggestion: request-id plugin supports "snowflake" algorithm

[dickens7]

Add support for snowflake algorithm to Request-ID plugin, or provide a separate snowflake algorithm plugin.

[tzssangglass]

This is a feature to be implemented, and as far as I know there is no suitable implementation of the snowflake algorithm in the lua language, see also this comment:

apisix/apisix/core/etcd.lua

Lines 296 to 299 in ac21146

	-- Create a new revision and use it as the id.
	-- It will be better if we use snowflake algorithm like manager-api,
	-- but we haven't found a good library. It costs too much to write
	-- our own one as the admin-api will be replaced by manager-api finally.

[dickens7]

I have my own request-id plugin implements a snowflake algorithm using https://github.com/stuartcarnie/lua-snowflake

[spacewander]

@dickens7
We can add more options in the request-id to control the id generation way.
PR is welcome!

[dickens7]

I am now doing it as a standalone plugin, so I will submit a version first

[spacewander]

@dickens7
Thanks for your PR! I have just taken a quick look at it. Would you submit it as the part of request-id plugin before I can review it?

[spacewander]

And there is a question, how can it handle more than 1024 workers?

[dickens7]

@dickens7
Thanks for your PR! I have just taken a quick look at it. Would you submit it as the part of request-id plugin before I can review it?

no problem
But now there are two problems

1. Is the storage location of worker number reasonable?
   {prefix}/plugins/snowflake/{id}
2. What to do when workers is greater than 1024

[dickens7]

And there is a question, how can it handle more than 1024 workers?

This is a problem. Now only the error log is printed. Subsequent worker_number is nil and an exception will be thrown.

[spacewander]

What about forking that library and modify it?
Currently,

machine bits: 10
per ms bits: 12
timestamp bits: 42

We can change it to

machine bits: 16 (65535 workers)
per ms bits: 10 (512 per ms, which is 512000 per second and is enough as a per worker QPS)
timestamp bits: 38 (8 years, we can change the start point to 2021-01-01)

[Yiyiyimu]

timestamp bits: 38 (8 years, we can change the start point to 2021-01-01)

Or we could implement it like sonyflake to change the time interval from 1ms to 10ms, and then we would have ~80 years. But not sure if 512 per 10ms is enough for us

[tokers]

timestamp bits: 38 (8 years, we can change the start point to 2021-01-01)

Or we could implement it like sonyflake to change the time interval from 1ms to 10ms, and then we would have ~80 years. But not sure if 512 per 10ms is enough for us

It' OK, as it's not possible that a single worker can handle about 51200 QPS.

[spacewander]

@Yiyiyimu @tokers
Maybe my previous words misled you. The number of per ms bits is not equal to QPS. The number is not distributed uniformly. It should be much larger than the QPS. 512 per 10ms is not safe enough to me.

[spacewander]

I just made a simple benchmark, and found the max value of count in a ms is 511, which is the default backlog of the TCP socket. Since the number can be increased, now I recommend using

machine bits: 16
per ms bits: 12
timestamp bits: 36

The epoch needs to be divided by 2 years so that we don't need to update it in 2023.

Also need to notify people if they have customized the backlog.

@dickens7
If you are interested in this change, you can notify us to fork lua-snowflake to api7.

[dickens7]

the first bit should stay at 0 and actually only use 63bit

Sonyflake definition

39 bits for time in units of 10 msec
8 bits for a sequence number
16 bits for a machine id

You might need to fetch 2 bits to do a dial back, to deal with the time callback problem

39 bits for time in units of 10 msec
8 bits for a sequence number
2 bits for back to dial
14 bits for a machine id

The start_time is designed to be configurable

[dickens7]

If you are interested in this change, you can notify us to fork lua-snowflake to api7.

ok.

[spacewander]

the first bit should stay at 0 and actually only use 63bit

Sonyflake definition

39 bits for time in units of 10 msec
8 bits for a sequence number
16 bits for a machine id

You might need to fetch 2 bits to do a dial back, to deal with the time callback problem

39 bits for time in units of 10 msec
8 bits for a sequence number
2 bits for back to dial
14 bits for a machine id

The start_time is designed to be configurable

10 bits for 10 msec is not enough as I proved. Maybe it is faster to change lua-snowflake to support this (only need to change some constants).

[dickens7]

10 bits for 10 msec is not enough as I proved. Maybe it is faster to change lua-snowflake to support this (only need to change some constants).

I will fork lua-snowflake and change it according to this algorithm definition

39 bits saves timestamp, accurate to milliseconds. That means the maximum usable life is 17 years.
14 bits machine bits, can be attached to 16384 machine nodes to generate ID.
10 bits number，the maximum number of unique IDs generated in a millisecond is 1024.

[spacewander]

Great! It would be better if you can make the bit numbers configurable.

The fork is done: https://github.com/api7/lua-snowflake
PR is welcome!

[spacewander]

It would be better if you can make the bit numbers configurable

We can do it in the future

[dickens7]

It would be better if you can make the bit numbers configurable

We can do it in the future

@spacewander
To achieve custom configuration, please merge PR and publish to luarocks.