ツイートIDの採番
以下の記事でツイートIDからタイムスタンプを抽出する方法を紹介しました。
その過程でTwitterがIDの採番に使用している snowflake におけるID採番処理を C# に移植しましたので、そのソースを公開します。
snowflakeについて
snowflake はGitHub上でソース(scala)が公開されています。
今回紹介するソースはこれを元に実装しています(完全移植ではなく、適宜アレンジしています)。1
採番するIDの構成
READMEファイル や IdWorkerクラス からツイートIDの構成を整理すると、以下のようになります。
- 64bit整数(long値) 2
- 上位のビットから、以下の通りの構成
- 0固定 - 1ビット
- タイムスタンプ(ミリ秒単位) - 41ビット
- マシンID 3 - 10ビット
- シーケンス番号 - 12ビット
- タイムスタンプは任意の基準時刻(カスタムエポック)からの経過ミリ秒
- Twitterでは 2010-11-04 01:42:54.657 を基準としている。
- これは、UNIXエポック(1970/01/01)から 1288834974657ミリ秒 4 経過した時刻。
ID採番処理
snowflake を参考に、C#でID採番処理を実装したのが以下のソースとなります。
snowflake にちなんで SasamiFlake と名付けていますが、深い意味はありません。
using System;
using System.Runtime.CompilerServices;
namespace SasamiFlake
{
/// <summary>
/// ID採番クラス
/// </summary>
public class IdGenerator
{
/// <summary>
/// Twitterにおける日時の基点
/// </summary>
/// <remarks>
/// UNIXエポック(1970/01/01)からの経過ミリ秒数。<br />
/// UTC時刻で 2010-11-04 01:42:54.657 を基点としている。
/// </remarks>
public const long TwitterEpoch = 1288834974657L;
/// <summary>
/// UNIXエポック
/// </summary>
/// <remarks>
/// DateTime型の基点(0001/01/01)からのUNIXエポック(1970/01/01)時点での経過ミリ秒数。
/// </remarks>
public const long Epoch = 62135596800000L;
/// <summary> シーケンス番号のビット数 </summary>
public const int SequenceBits = 12;
/// <summary> ワーカーIDのビット数 </summary>
public const int WorkerIdBits = 5;
/// <summary> データセンターIDのビット数 </summary>
public const int DatacenterIdBits = 5;
/// <summary> タイムスタンプのビット数 </summary>
public const int TimestampBits = 41;
/// <summary> シーケンス番号のシフト数 </summary>
public const int SequenceShift = 0;
/// <summary> ワーカーIDのシフト数 </summary>
public const int WorkerIdShift = SequenceBits;
/// <summary> データセンターIDのシフト数 </summary>
public const int DatacenterIdShift = SequenceBits + WorkerIdBits;
/// <summary> タイムスタンプのシフト数 </summary>
public const int TimestampShift = SequenceBits + WorkerIdBits + DatacenterIdBits;
/// <summary> シーケンス番号のマスク </summary>
public const long SequenceMask = -1L ^ (-1L << SequenceBits);
/// <summary> ワーカーIDのマスク </summary>
public const long WorkerIdMask = -1L ^ (-1L << WorkerIdBits);
/// <summary> データセンターIDのマスク </summary>
public const long DatacenterIdMask = -1L ^ (-1L << DatacenterIdBits);
/// <summary> タイムスタンプのマスク </summary>
public const long TimestampMask = -1L ^ (-1L << TimestampBits);
/// <summary> ワーカーIDの最大値 </summary>
public const long MaxWorkerId = WorkerIdMask;
/// <summary> データセンターIDの最大値 </summary>
public const long MaxDatacenterId = DatacenterIdMask;
/// <summary> ワーカーID </summary>
public long WorkerId { get; }
/// <summary> データセンターID </summary>
public long DatacenterId { get; }
/// <summary> シーケンス番号 </summary>
private long sequence = 0L;
/// <summary> 最後にIDを採番した時点のタイムスタンプ </summary>
private long lastTimestamp = -1L;
/// <summary>
/// コンストラクタ
/// </summary>
/// <param name="workerId">ワーカーID</param>
/// <param name="datacenterId">データセンターID</param>
public IdGenerator(long workerId, long datacenterId)
{
// ワーカーID
if (workerId > MaxWorkerId || workerId < 0)
{
throw new ArgumentOutOfRangeException($"worker Id can't be greater than {MaxWorkerId} or less than 0");
}
this.WorkerId = workerId;
// データセンターID
if (datacenterId > MaxDatacenterId || datacenterId < 0)
{
throw new ArgumentOutOfRangeException($"datacenter Id can't be greater than {MaxDatacenterId} or less than 0");
}
this.DatacenterId = datacenterId;
}
/// <summary>
/// 新しいIDを採番する。
/// </summary>
/// <returns>新しいID</returns>
public long NewId() => this.GenerateId();
/// <summary>
/// 新しいIDを生成する。
/// </summary>
/// <returns>新しいID</returns>
[MethodImpl(MethodImplOptions.Synchronized)]
private long GenerateId()
{
// タイムスタンプを取得
var timestamp = GetTimestamp();
// タイムスタンプの巻き戻りが発生していた場合、タイムスタンプが切り替わるまで待機
// (システム時刻の補正により発生する可能性がある)
if (timestamp < this.lastTimestamp)
{
timestamp = TilNextMillis(this.lastTimestamp);
}
// 同じタイムスタンプで採番された場合、シーケンス番号をインクリメント
if (timestamp == this.lastTimestamp)
{
this.sequence = (this.sequence + 1L) & SequenceMask;
if (this.sequence == 0L)
{
// シーケンス番号がオーバーフローした場合、タイムスタンプが切り替わるまで待機
timestamp = TilNextMillis(this.lastTimestamp);
}
}
// 前回採番時からタイムスタンプが変わった場合、シーケンス番号を0から割り当てる
else
{
this.sequence = 0L;
}
// タイムスタンプ更新
this.lastTimestamp = timestamp;
// IDを求めて返す
return ((timestamp - TwitterEpoch) << TimestampShift)
| (this.DatacenterId << DatacenterIdShift)
| (this.WorkerId << WorkerIdShift)
| this.sequence;
}
/// <summary>
/// タイムスタンプを取得する。
/// </summary>
/// <remakrs>
/// システム時刻をUNIXエポック(1970/01/01)からの経過ミリ秒数で取得する。
/// </remakrs>
/// <returns>タイムスタンプ</returns>
private static long GetTimestamp()
{
return (DateTime.UtcNow.Ticks / TimeSpan.TicksPerMillisecond) - Epoch;
}
/// <summary>
/// タイムスタンプが切り替わるまで待機する。
/// </summary>
/// <param name="lastTimestamp">前回取得時のタイムスタンプ</param>
/// <returns>待機後のタイムスタンプ</returns>
private static long TilNextMillis(long lastTimestamp)
{
var timestamp = GetTimestamp();
while (timestamp <= lastTimestamp)
{
timestamp = GetTimestamp();
}
return timestamp;
}
}
}
注意点
簡単なテストは行っていますが、IDの仕様を理解する為に実装したものなので、参考レベルに留めて頂けるようお願いします。
ライセンス情報
上記ソース(以降 SasamiFlake)には、特定のオープンソースライセンスを適用しません。
あくまで参考ソースとして、閲覧に留めて頂けると幸いです。
ただし、各自の責任で SasamiFlake を参考にしてID採番処理を実装される分には、自由にしていただけます。
- SasamiFlake の出典を明記する必要はありません。
- 当方は一切の責任を負いませんので、自己責任にてお願いいたします。
- SasamiFlake の改変元である snowflake のライセンス条項に従う必要がある可能性があります。
SasamiFlake は Apache License 2.0 でライセンスされている snowflake を改変したものです。
- snowflake
Copyright 2010-2012 Twitter, Inc.
Licensed under the Apache License, Version 2.0 (the "License"); you may not use this
file except in compliance with the License. You may obtain a copy of the License athttp://www.apache.org/licenses/LICENSE-2.0Unless required by applicable law or agreed to in writing, software distributed
under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR
CONDITIONS OF ANY KIND, either express or implied. See the License for the
specific language governing permissions and limitations under the License.
余談
プログラミングの学習レベルではビット演算を知っていましたが、実際にビット演算を使用したのが初めてだったので、とても勉強になりました。