Java製のSnowflakeライクな分散環境用IDジェネレータ「oleoleflake」

oleoleflakeというユニークID生成用ライブラリを作りました。

概要

oleoleflakeはSnowflake風のIDを生成するためのライブラリです。
Snowflakeは64ビットのフィールドを分割し、マシンID、タイムスタンプ、マシンローカルなシーケンスを組み合わせてユニーク性を担保しています。詳しくは各位ググっていただきたい所存ですが、参考になりそうなリンクをいくつか貼っておきます。

• 「Twitterのsnowflakeについて」 https://www.slideshare.net/moaikids/20130901-snowflake
• 「スケーラブルな採番とsnowflake」 http://kyrt.in/2014/06/08/snowflake_c.html

oleoleflakeはビットフィールドの配置をカスタマイズしたID生成器を作ることができます。また生成されたIDから各ビットフィールドの値を抽出したり、任意のタイムスタンプでのIDを生成する機能を用意しています。
マシンIDを中央管理するような仕組みは用意していないため、静的な設定値を使うか、自前でZookeeper等で管理したものがあれば、それを利用することもきます。

利用方法

jitpackで公開しています。以下のリンク先の手順でインポートしてください。
https://jitpack.io/#rerorero/oleoleflake

機能

ビットフィールドの配置をカスタマイズしたID生成器を作る

Id64Genはスレッドセーフな64ビット（Long値）ID生成器です。Id64Gen.builder()を利用してビルダパターンで生成します。
Snowflakeと同じビット配置のID生成器を作成する場合次のようになります。

ID生成器作成例

Id64Gen gen = Id64Gen.builder()
    .nextBit(1).unusedField()
    .nextBit(41).timestampField()
        .tickPerMillisec()
        .startAt(Instant.parse("2017-01-01T00:00:00.00Z"))
    .nextBit(5).constantField().name("data-center-id").value(1)
    .nextBit(5).constantField().name("worker-id").value(2)
    .nextBit(12).sequenceField()
    .build();

...

// idを発行する
Long id = gen.next().id();

上位ビットから順にどのようにビットフィールドを利用するかを定義していきます。nextBit(bitSize)がビットフィールドの区切りで、合計が64ビットになるように指定します。利用できるフィールドの種類は次のものがあります。

タイムスタンプフィールド

timestampField()は独自のタイムスタンプフィールドを定義します。1つのIDに1つまで定義できます。
tickPerMillisec()またはtickPerSecond()でタイムスタンプがミリ秒か秒かを指定します。
startAt(Instant)でタイムスタンプの開始時間を指定します。

定数フィールド

constantField()は常に同じ値になるフィールドです。1つのIDに複数持つことができます。
各定数フィールドにはname(String)で一意の名前を与えます。この名前は、IDからフィールドの値を取得する時に利用できます。

idから定数フィールドの値を取得する例

Long workerId = gen.parseConstant("worker-id", id); // 2

Snowflakeの例ではワーカーごとに1つのID生成器インスタンスを利用する想定で、ワーカーIDを定数フィールドとしています。

変数フィールド

bindableField()はIDを生成するたびに変わるフィールドです。idを生成する時にフィールドの値を指定する必要があります。（今回のSnowflakeの例では使用していません）
IDにシャードキーを含めてDBをシャーディングしているようなケースで、このフィールドが利用できます。
Builderで.nextBit(10).bindableField().name("user-group") のようにフィールドに名前をつけておき、id発行の際に値をbind()します。

変数フィールド

Long shardKey = 3;
Long id = gen.next().bind("shard-key", shardKey).id();

// idからフィールドの値を取得する
Long shardKey = gen.parseBindable("shard-key", id); // 3

シーケンスフィールド

sequenceField()はgen.next().id()でidが発行される時、一つ前に発行したidとタイムスタンプが同じ場合に値がインクリメントするフィールドを定義します。タイムスタンプが更新されると（時間が進むと）初期値（デフォルトは0でstartAt()で変更できます）にリセットされます。
シーケンスが最大になった時、 next().id() はタイムスタンプが次に進むまでブロック（スピンロック）する実装になっています。ブロックが多発するとCPU負荷が上がってしまうため、シーケンスフィールドは余裕を持った長さを確保するのが望ましいですね。

なお、タイムスタンプフィールドが存在しない場合は、シーケンスフィールドはリセットされることなくnext().id()のたびにインクリメントされ続けるフィールドになります。

シーケンスフィールドは1つのIDに1つまでしか持てません。

未使用フィールド

unusedField() は常に0となるフィールドを定義します。1つのIDに複数持つことができます。
Snowflakeでは上位1ビットをSignedFieldとして利用していません。これにより生成されるLong値は常に0以上になります。

タイムスタンプとシーケンスを指定してidを作成する

snapshot()はフィールドの値を指定したidを作ることができます。IDに含まれるタイムスタンプで範囲を指定するクエリを作るような時に便利です。こういったクエリをセカンダリインデックス不要で使えるのが、UUIDや普通の分散シーケンスIDにはない、Snowflake系IDの優位性の一つだと思います。

2017/1/1のデータを取得する例

Long from = gen.snapshot()
    .putTimestamp(Instant.parse("2017-01-01T00:00:00.00Z"))
    .putSequence(Long.valueOf(0))
    .id();

Long to = gen.snapshot()
    .putTimestamp(Instant.parse("2017-01-02T00:00:00.00Z"))
    .putSequence(Long.valueOf(0))
    .id() - 1;

String sql = String.format("SELECT * FROM table WHERE id BETWEEN %d AND %d", from, to);

バイナリID

IdBytesGen では byte[] のID生成器を作成できます。Id64Genと同じように各種フィールドが利用できます。HBaseのようなバイナリ形式のキーが扱えるストレージでの利用を想定しています。

バイナリid

// IdBytesGen.builder()にはバイト数を指定します。nextBit()にはフィールドのビット数を指定します。
IdBytesGen gen = IdBytesGen.builder(12)
    .nextBit(32).bindableLongField().name("group-hash")
    .nextBit(43).timestampField()
        .tickPerMillisec()
        .startAt(Instant.parse("2017-01-01T00:00:00.00Z"))
    .nextBit(21).sequenceField()
    .build();

...

// ID発行
byte[] id = gen.next().bind("group-hash", crc32.getValue()).id();

終わりに

SnowflakeライクなIDを生成するライブラリは世の中にいくつかあるようですが、その多くはフィールド配置が固定で、必要とするユースケースにそぐわない場合があります。そこで汎用的なID生成器を目指してこのライブラリを作りました。
是非oleoleflakeでオレオレSnowflakeを作ってみてください。