Twitter風のIDを採番するプログラムをC#で書いてみた

# ツイートIDの採番

以下の記事でツイートIDからタイムスタンプを抽出する方法を紹介しました。
その過程でTwitterがIDの採番に使用している **snowflake** におけるID採番処理を C# に移植しましたので、そのソースを公開します。

https://qiita.com/haruka_kotani/items/0e2096cbd527015a2d96


## snowflakeについて

**snowflake** はGitHub上でソース(scala)が公開されています。
今回紹介するソースはこれを元に実装しています(完全移植ではなく、適宜アレンジしています)。[^1]

https://github.com/twitter-archive/snowflake

[^1]: 現時点ではプロジェクトは公開されていませんが、tagから当時のソースが取得可能です。


## 採番する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] 経過した時刻。

[^2]: 先頭ビットが0固定なので、符号の有無(signed/unsigned)は考慮不要。
[^3]: IdWorkerクラスでは、ワーカーID と データセンターID にそれぞれ5ビットずつ割り当てている。
[^4]: IdWorkerクラス の twepoch で定義されている。


# ID採番処理

**snowflake** を参考に、C#でID採番処理を実装したのが以下のソースとなります。
**snowflake** にちなんで **SasamiFlake** と名付けていますが、深い意味はありません。

```csharp
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](https://www.apache.org/licenses/LICENSE-2.0 "Apache License, Version 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 at
> 
>     http://www.apache.org/licenses/LICENSE-2.0
> 
> Unless 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.

## 余談

プログラミングの学習レベルではビット演算を知っていましたが、実際にビット演算を使用したのが初めてだったので、とても勉強になりました。