分散システム向けの固有 ID 生成ソリューションの概要-php手册-php.cn

一意のシステム ID は、システムを設計するときによく遭遇する問題であり、よくこの問題に悩まされます。 ID を生成するには、さまざまなシナリオ、ニーズ、パフォーマンス要件に適応するさまざまな方法があります。したがって、一部のより複雑なシステムには複数の ID 生成戦略があります。ここでは、一般的な ID 生成戦略をいくつか示します。

1. データベースの自己増加シーケンスまたはフィールド

最も一般的な方法。データベースを使用すると、データベース全体が固有になります。

利点:

シンプルで便利なコードと許容可能なパフォーマンス。
#数値 ID は自然に並べ替えられるため、並べ替えが必要なページングや結果に役立ちます。

#欠点:

# データベースの移行時や複数のデータベースバージョンの場合、データベースの構文と実装が異なります。サポートされている処理が必要です。
#単一データベース、読み取り/書き込み分離、または 1 つのマスターと複数のスレーブの場合、生成できるマスターデータベースは 1 つだけです。単一障害点が発生するリスクがあります。
#パフォーマンスが要件を満たさない場合、拡張は困難です。
複数のシステムを統合する必要がある場合、またはデータ移行が関係する場合は、かなりの時間がかかります。痛い。
最適化計画:

これはデータベースまたはプログラムを使用して生成でき、一般に世界で唯一のものです。

利点:

#ID 生成のパフォーマンスは非常に優れており、基本的にパフォーマンスの問題は発生しません。
データ移行、システムデータ結合、データベースの場合は世界で唯一。変化しても、それをスムーズに受け止めることができます。
欠点:

並べ替えがないため、傾向が増加することは保証できません。

UUID は文字列を使用して保存されることが多く、クエリ効率は比較的低くなります。
大規模なデータベースの場合、ストレージ容量を考慮する必要があります。額。
#大量のデータを転送する
# は読み取れません。
3. Redis による ID の生成
データベースを使用して ID を生成するパフォーマンスが十分でない場合は、Redis を使用して ID を生成することもできます。 IDを生成します。これは主にシングルスレッドである Redis に依存しているため、グローバルに一意な ID の生成にも使用できます。これは、Redis のアトミック操作 INCR および INCRBY を使用して実現できます。

Redis クラスターを使用すると、より高いスループットを得ることができます。クラスター内に 5 つの Redis があるとします。各 Redis の値はそれぞれ 1、2、3、4、5 に初期化でき、ステップサイズはすべて 5 になります。各 Redis によって生成される ID は次のとおりです:

A: 1,6,11,16,21 B: 2,7,12,17,22 C: 3,8,13,18,23 D: 4 , 9,14,19,24 E: 5,10,15,20,25

これは、どのマシンにロードされるかによって決まります。将来的に変更するのは困難です。ただし、基本的には 3 ～ 5 台のサーバーでサーバーのニーズを満たすことができ、すべてのサーバーで異なる ID を取得できます。ただし、ステップサイズと初期値は事前に必要です。 Redis クラスターを使用すると、単一障害点の問題も解決できます。

また、Redis を使用して毎日 0 から始まるシリアル番号を生成する方が適しています。たとえば、注文番号 = 日付の場合、番号はその日に自動的に増加します。毎日 Redis でキーを生成し、蓄積に INCR を使用できます。

利点:

## はデータベースに依存せず、柔軟で便利で、データベースよりもパフォーマンスが優れています。

#数値 ID は自然に並べ替えられるため、並べ替えが必要なページングや結果に役立ちます。
欠点:

システムに Redis がない場合は、新しいコンポーネントを導入する必要があり、システムの複雑さ。

#コーディングと構成に必要な作業負荷は比較的大きくなります。

4. Twitter のスノーフレークアルゴリズム

Snowflake は Twitter のオープンソースの分散 ID 生成アルゴリズムであり、結果は長い ID になります。中心となるアイデアは、ミリ秒数として 41 ビット、マシン ID として 10 ビット (5 ビットがデータセンター、5 ビットがマシン ID)、ミリ秒以内のシリアル番号として 12 ビット (つまり、各ノードが4096 ID を生成します）、最後には符号ビットがあり、常に 0 になります。特定の実装コードは、https://github.com/twitter/snowflake

で見つけることができます。

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

public class IdWorker {
// ==============================Fields===========================================
/** 开始时间截 (2015-01-01) */
private final long twepoch = 1420041600000L;
 
/** 机器id所占的位数 */
private final long workerIdBits = 5L;
 
/** 数据标识id所占的位数 */
private final long datacenterIdBits = 5L;
 
/** 支持的最大机器id，结果是31 (这个移位算法可以很快的计算出几位二进制数所能表示的最大十进制数) */
private final long maxWorkerId = -1L ^ (-1L << workerIdBits);
 
/** 支持的最大数据标识id，结果是31 */
private final long maxDatacenterId = -1L ^ (-1L << datacenterIdBits);
 
/** 序列在id中占的位数 */
private final long sequenceBits = 12L;
 
/** 机器ID向左移12位 */
private final long workerIdShift = sequenceBits;
 
/** 数据标识id向左移17位(12+5) */
private final long datacenterIdShift = sequenceBits + workerIdBits;
 
/** 时间截向左移22位(5+5+12) */
private final long timestampLeftShift = sequenceBits + workerIdBits + datacenterIdBits;
 
/** 生成序列的掩码，这里为4095 (0b111111111111=0xfff=4095) */
private final long sequenceMask = -1L ^ (-1L << sequenceBits);
 
/** 工作机器ID(0~31) */
private long workerId;
 
/** 数据中心ID(0~31) */
private long datacenterId;
 
/** 毫秒内序列(0~4095) */
private long sequence = 0L;
 
/** 上次生成ID的时间截 */
private long lastTimestamp = -1L;
 
//==============================Constructors=====================================
/**
 * 构造函数
 * @param workerId 工作ID (0~31)
 * @param datacenterId 数据中心ID (0~31)
 */
public IdWorker(long workerId, long datacenterId) {
    if (workerId > maxWorkerId || workerId < 0) {
        throw new IllegalArgumentException(String.format("worker Id can&#39;t be greater than %d or less than 0", maxWorkerId));
    }
    if (datacenterId > maxDatacenterId || datacenterId < 0) {
        throw new IllegalArgumentException(String.format("datacenter Id can&#39;t be greater than %d or less than 0", maxDatacenterId));
    }
    this.workerId = workerId;
    this.datacenterId = datacenterId;
}
 
// ==============================Methods==========================================
/**
 * 获得下一个ID (该方法是线程安全的)
 * @return SnowflakeId
 */
public synchronized long nextId() {
    long timestamp = timeGen();
 
    //如果当前时间小于上一次ID生成的时间戳，说明系统时钟回退过这个时候应当抛出异常
    if (timestamp < lastTimestamp) {
        throw new RuntimeException(
                String.format("Clock moved backwards.  Refusing to generate id for %d milliseconds", lastTimestamp - timestamp));
    }
 
    //如果是同一时间生成的，则进行毫秒内序列
    if (lastTimestamp == timestamp) {
        sequence = (sequence + 1) & sequenceMask;
        //毫秒内序列溢出
        if (sequence == 0) {
            //阻塞到下一个毫秒,获得新的时间戳
            timestamp = tilNextMillis(lastTimestamp);
        }
    }
    //时间戳改变，毫秒内序列重置
    else {
        sequence = 0L;
    }
 
    //上次生成ID的时间截
    lastTimestamp = timestamp;
 
    //移位并通过或运算拼到一起组成64位的ID
    return ((timestamp - twepoch) << timestampLeftShift) //
            | (datacenterId << datacenterIdShift) //
            | (workerId << workerIdShift) //
            | sequence;
}
 
/**
 * 阻塞到下一个毫秒，直到获得新的时间戳
 * @param lastTimestamp 上次生成ID的时间截
 * @return 当前时间戳
 */
protected long tilNextMillis(long lastTimestamp) {
    long timestamp = timeGen();
    while (timestamp <= lastTimestamp) {
        timestamp = timeGen();
    }
    return timestamp;
}
 
/**
 * 返回以毫秒为单位的当前时间
 * @return 当前时间(毫秒)
 */
protected long timeGen() {
    return System.currentTimeMillis();
}
 
//==============================Test=============================================
/** 测试 */
public static void main(String[] args) {
    IdWorker idWorker = new IdWorker(0, 0);
    for (int i = 0; i < 1000; i++) {
        long id = idWorker.nextId();
        System.out.println(Long.toBinaryString(id));
        System.out.println(id);
    }
}}

ログイン後にコピー

スノーフレークアルゴリズムは、独自のプロジェクトのニーズに応じて変更できます。たとえば、将来のデータセンターの数、各データセンターのマシンの数、統一ミリ秒内に発生する可能性のある同時実行数を推定して、アルゴリズムに必要なビット数を調整します。

利点:

## はデータベースに依存せず、柔軟で便利で、データベースよりもパフォーマンスが優れています。
#ID は、単一マシン上で時間に応じて増加します。

は単一マシン上で増分ですが、分散環境が関与するため、各マシンクロック上のクロックは完全に同期することができず、場合によってはグローバルな増分が達成されない状況が発生する可能性があります。

zookeeper は、主に znode データバージョンを通じてシリアル番号を生成します。32 ビットおよび 64 ビットのデータバージョン番号を生成できます。顧客顧客は、このバージョン番号を一意のシリアル番号として使用できます。

Zookeeper が固有 ID の生成に使用されることはほとんどありません。主な理由は、zookeeper に依存し、複数のステップで API を呼び出すためです。競合が大きい場合は、分散ロックの使用を検討する必要があります。したがって、同時実行性の高い分散環境では、パフォーマンスは理想的ではありません。

6. MongoDB の ObjectId

MongoDB の ObjectId は、スノーフレークアルゴリズムに似ています。これは軽量になるように設計されており、同じ世界的に独自の方法を使用して、さまざまなマシンで簡単に生成できます。 MongoDB は最初から分散データベースとして設計されており、複数のノードを処理することが中心的な要件です。シャーディング環境での生成がはるかに簡単になります。形式は次のとおりです: [src/main/resources/objectId.png] ここに画像の説明を記述します:

分散システム向けの固有 ID 生成ソリューションの概要最初の 4 バイトは、標準エポックから始まるタイムスタンプです。、単位は秒です。タイムスタンプは、次の 5 バイトと組み合わされて、第 2 レベルの一意性を提供します。タイムスタンプが最初に来るため、ObjectId はおおよそ挿入された順序で並べ替えられることを意味します。効率化の指標として利用するなどに便利です。これらの 4 バイトは、文書が作成された時刻も意味します。ほとんどのクライアントライブラリは、ObjectId からこの情報を取得するメソッドを公開します。次の 3 バイトはホストの一意の識別子です。通常はマシンのホスト名のハッシュです。これにより、異なるホストが競合することなく異なる ObjectId を生成することが保証されます。同じマシン上の複数の同時プロセスによって生成される ObjectId が一意であることを確認するために、次の 2 バイトは ObjectId を生成したプロセス識別子 (PID) から取得されます。最初の 9 バイトにより、同じ秒内に異なるマシン上の異なるプロセスによって生成された ObjectId が一意であることが保証されます。最後の 3 バイトは、同じ秒内に同じプロセスによって生成された ObjectId も異なることを保証するために、自動的に増加するカウンターです。各プロセスは、同じ秒内に最大 2563 (16 777 216) 個の異なる ObjectId を持つことができます。