在 Spanner 中產生序列

本文說明資料庫管理員和應用程式開發人員，如何在採用 Spanner 的應用程式中產生不重複的數字序列。

簡介

商家通常需要簡單的專屬數字 ID，例如員工編號或發票號碼。傳統關聯式資料庫通常會提供一項功能，可產生不重複的單調遞增數字序列。這些序列可用於為儲存在資料庫中的物件產生專屬 ID (列鍵)。

不過，使用單調遞增 (或遞減) 的值做為資料列鍵，可能不符合 Spanner 的最佳做法，因為這會在資料庫中建立熱點，導致效能降低。本文建議使用 Spanner 資料庫表和應用程式層邏輯，實作序號產生器。

或者，Spanner 支援內建的位元反轉序列產生器。如要進一步瞭解 Spanner 序列產生器，請參閱「建立及管理序列」。

序列產生器的需求

每個序號產生器都必須為每筆交易產生不重複的值。

視用途而定，序列產生器可能也需要建立具有下列特徵的序列：

  • 排序：序列中的較低值不得在較高值之後發布。
  • 無間隙：序列中不得有間隙。

序列產生器也必須以應用程式要求的頻率產生值。

要滿足所有這些需求可能很困難，尤其是在分散式系統中。如有需要達成成效目標，您可以放寬序列必須依序播放且不得有間斷的要求。

其他資料庫引擎有處理這些需求的做法。舉例來說，PostgreSQL 中的序列和 MySQL 中的 AUTO_INCREMENT 資料欄可為個別交易產生不重複的值，但如果交易回溯，就無法產生無間隙的值。詳情請參閱 PostgreSQL 說明文件中的附註，以及 MySQL 中的 AUTO_INCREMENT 影響。

使用資料庫資料表資料列的序列產生器

應用程式可以使用資料庫表格來儲存序列名稱和序列中的下一個值，藉此實作序列產生器。

在資料庫交易中讀取及遞增序列的 next_value 儲存格，即可產生不重複的值，不需要在應用程式程序之間進行任何進一步的同步處理。

首先，請定義資料表，如下所示：

CREATE TABLE sequences (
    name STRING(64) NOT NULL,
    next_value INT64 NOT NULL,
) PRIMARY KEY (name)

如要建立序列，請在資料表中插入資料列，並填入新的序列名稱和起始值，例如 ("invoice_id", 1)。不過，由於系統會為產生的每個序列值遞增 next_value 儲存格，因此效能會受到資料列更新頻率的限制。

Spanner 用戶端程式庫會使用可重試的交易來解決衝突。如果在讀寫交易期間讀取的任何儲存格 (欄值) 在其他位置遭到修改，交易就會遭到封鎖，直到其他交易完成為止，然後中止並重試，以便讀取更新的值。這樣做可以盡量縮短寫入鎖定的時間，但這也表示交易可能會嘗試多次，才能成功提交。

由於每列一次只能發生一筆交易，因此發布序號值的最高頻率與交易的總延遲時間成反比。

這項交易總延遲時間取決於多項因素，例如用戶端應用程式與 Spanner 節點之間的延遲時間、Spanner 節點之間的延遲時間，以及 TrueTime 不確定性。舉例來說，多區域設定的交易延遲時間較長，因為必須等待不同區域的節點確認寫入作業達到仲裁數量，才能完成交易。

舉例來說，如果單一儲存格 (單一資料列中的一個資料欄) 的讀取更新交易延遲時間為 10 毫秒 (ms)，則發布序號值的理論頻率上限為每秒 100 次。無論用戶端應用程式執行個體數量或資料庫中的節點數量為何，這項上限都適用於整個資料庫。這是因為單一資料列一律由單一節點管理。

下一節將說明如何解決這項限制。

應用程式端導入

應用程式程式碼必須讀取及更新資料庫中的 next_value 儲存格。方法有很多種，每種方法都有不同的效能特徵和缺點。

簡單的交易內序列產生器

處理序號產生的最簡單方法，就是在應用程式需要新的序號值時，於交易中遞增資料欄值。

應用程式會在單一交易中執行下列操作：

  • 讀取 next_value 儲存格，取得要在應用程式中使用的序列名稱。
  • 遞增及更新序列名稱的 next_value 儲存格。
  • 針對應用程式需要的任何欄值，使用擷取的值。
  • 完成應用程式交易的其餘部分。

這個程序會產生有序且無間隙的序列。如果資料庫中的 next_value 儲存格沒有更新為較低的值，序號也會是唯一值。

由於序號值是在較廣泛的應用程式交易中擷取，序號產生頻率上限取決於整體應用程式交易的複雜程度。複雜的交易延遲時間較長，因此序號產生頻率上限較低。

在分散式系統中，可能會同時嘗試許多交易，導致序號值發生高度爭用。由於 next_value 儲存格是在應用程式的交易中更新，因此任何嘗試同時遞增 next_value 儲存格的其他交易都會遭到第一個交易封鎖，並重新嘗試。這會大幅增加應用程式成功完成交易所需的時間，進而導致效能問題。

下列程式碼提供簡單的交易內序號產生器範例，每個交易只會傳回單一序號值。這項限制存在的原因是，使用 Mutation API 進行交易時，寫入作業必須在交易修訂後才會顯示，即使是同一交易中的讀取作業也一樣。因此，在同一交易中多次呼叫此函式，一律會傳回相同的序列值。

以下範例程式碼說明如何實作同步 getNext() 函式： 

/**
 * Returns the next value from this sequence.
 *
 * <p>Should only be called once per transaction.
 */
long getNext(TransactionContext txn) {
  Struct result =
      txn.readRow(
          SEQUENCES_TABLE, Key.of(sequenceName), Collections.singletonList(NEXT_VALUE_COLUMN));
  if (result == null) {
    throw new NoSuchElementException(
        "Sequence " + sequenceName + " not found in table " + SEQUENCES_TABLE);
  }
  long value = result.getLong(0);
  txn.buffer(
      Mutation.newUpdateBuilder(SEQUENCES_TABLE)
          .set(SEQUENCE_NAME_COLUMN)
          .to(sequenceName)
          .set(NEXT_VALUE_COLUMN)
          .to(value + 1)
          .build());
  return value;
}

下列程式碼範例顯示如何在交易中使用同步 getNext() 函式：

// Simple Sequence generator created outside transaction, eg as field.
private SimpleSequenceGenerator simpleSequence = new SimpleSequenceGenerator("my Sequence");

public void usingSimpleSequenceGenerator() {
  dbClient
      .readWriteTransaction()
      .run(
          new TransactionCallable<Void>() {
            @Nullable
            @Override
            public Void run(TransactionContext txn) {
              // Get a sequence value
              long nextValue = simpleSequence.getNext(txn);
              // Use nextValue in the transaction
              // ...
              return null;
            }
          });
}

改善交易內同步序列產生器

您可以修改上述抽象概念，追蹤交易中發出的序號值，在單一交易中產生多個值。

應用程式會在單一交易中執行下列操作：

  • 讀取 next_value 儲存格，取得要在應用程式中使用的序列名稱。
  • 在內部將這個值儲存為變數。
  • 每次要求新的序列值時，都會遞增儲存的 next_value 變數，並緩衝寫入作業，在資料庫中設定更新後的儲存格值。
  • 完成應用程式交易的其餘部分。

如果您使用抽象層，則必須在交易中建立這個抽象層的物件。要求第一個值時，物件會執行單一讀取作業。物件會在內部追蹤 next_value 儲存格，因此可以產生多個值。

先前版本適用的延遲和爭用相關注意事項，同樣適用於這個版本。

以下範例程式碼說明如何實作同步 getNext() 函式：

private final TransactionContext txn;
@Nullable private Long nextValue;

/** Creates a sequence generator for this transaction. */
public SynchronousSequenceGenerator(String sequenceName, TransactionContext txn) {
  super(sequenceName);
  this.txn = txn;
}

/**
 * Returns the next value from this sequence.
 *
 * <p>Can be called multiple times in a transaction.
 */
public long getNext() {
  if (nextValue == null) {
    // nextValue is unknown - read it.
    Struct result =
        txn.readRow(
            SEQUENCES_TABLE, Key.of(sequenceName), Collections.singletonList(NEXT_VALUE_COLUMN));
    if (result == null) {
      throw new NoSuchElementException(
          "Sequence " + sequenceName + " not found in table " + SEQUENCES_TABLE);
    }
    nextValue = result.getLong(0);
  }
  long value = nextValue;
  // increment and write nextValue to the database.
  nextValue++;
  txn.buffer(
      Mutation.newUpdateBuilder(SEQUENCES_TABLE)
          .set(SEQUENCE_NAME_COLUMN)
          .to(sequenceName)
          .set(NEXT_VALUE_COLUMN)
          .to(nextValue)
          .build());
  return value;
}

下列程式碼範例說明如何在要求兩個序列值時，使用同步 getNext() 函式：

public void usingSynchronousSequenceGenerator() {
  dbClient
      .readWriteTransaction()
      .run(
          new TransactionCallable<Void>() {
            @Nullable
            @Override
            public Void run(TransactionContext txn) {
              // Create the sequence generator object within the transaction
              SynchronousSequenceGenerator syncSequence =
                  new SynchronousSequenceGenerator("my_sequence", txn);
              // Get two sequence values
              long key1 = syncSequence.getNext();
              long key2 = syncSequence.getNext();
              // Use the 2 key values in the transaction
              // ...
              return null;
            }
          });
}

交易外 (非同步) 序列產生器

在前兩個實作中，產生器的效能取決於應用程式交易的延遲時間。您可以透過個別交易遞增序號，提高最高頻率，但這樣做會導致序號出現間隙。(這是 PostgreSQL 使用的方法)。應用程式開始交易前，您應先擷取要使用的序號值。

應用程式會執行下列作業：

  • 建立第一筆交易，以取得及更新序號值：
    • 讀取 next_value 儲存格，取得要在應用程式中使用的序列名稱。
    • 將這個值儲存為變數。
    • 遞增及更新資料庫中序號名稱的 next_value 儲存格。
    • 完成交易。
  • 在另一個交易中使用傳回的值。

這項獨立交易的延遲時間會接近最短延遲時間， 成效則會接近每秒 100 個值的理論最大頻率 (假設交易延遲時間為 10 毫秒)。由於序號值是分開擷取，應用程式交易本身的延遲時間不會改變，且爭用情形會降到最低。

不過，如果要求序號值但未使用，序號中就會留下間隙，因為無法回溯要求的序號值。如果應用程式在要求序號值後，於交易期間中止或失敗，就可能發生這種情況。

以下範例程式碼說明如何實作函式，從資料庫擷取並遞增 next_value 儲存格：

/**
 * Gets the next sequence value from the database, and increments the database value by the amount
 * specified in a single transaction.
 */
protected Long getAndIncrementNextValueInDB(long increment) {
  return dbClient
      .readWriteTransaction()
      .run(
          txn -> {
            Struct result =
                txn.readRow(
                    SEQUENCES_TABLE,
                    Key.of(sequenceName),
                    Collections.singletonList(NEXT_VALUE_COLUMN));
            if (result == null) {
              throw new NoSuchElementException(
                  "Sequence " + sequenceName + " not found in table " + SEQUENCES_TABLE);
            }
            long value = result.getLong(0);
            txn.buffer(
                Mutation.newUpdateBuilder(SEQUENCES_TABLE)
                    .set(SEQUENCE_NAME_COLUMN)
                    .to(sequenceName)
                    .set(NEXT_VALUE_COLUMN)
                    .to(value + increment)
                    .build());
            return value;
          });
}

您可以輕鬆使用這個函式擷取單一新序號值，如下列非同步 getNext() 函式的實作方式所示：

/**
 * Returns the next value from this sequence.
 *
 * Uses a separate transaction so must be used <strong>outside</strong>any other transactions.
 * See {@link #getNextInBackground()} for an alternative version that uses a background thread
 */
public long getNext() throws SpannerException {
  return getAndIncrementNextValueInDB(1);
}

下列程式碼範例說明如何在要求兩個序列值時，使用非同步 getNext() 函式：

// Async Sequence generator created outside transaction as a long-lived object.
private AsynchronousSequenceGenerator myAsyncSequence =
    new AsynchronousSequenceGenerator("my Sequence", dbClient);

public void usingAsynchronousSequenceGenerator() {
  // Get two sequence values
  final long key1 = myAsyncSequence.getNext();
  final long key2 = myAsyncSequence.getNext();
  dbClient
      .readWriteTransaction()
      .run(
          new TransactionCallable<Void>() {
            @Nullable
            @Override
            public Void run(TransactionContext txn) {
              // Use the 2 key values in the transaction
              // ...
              return null;
            }
          });
}

在上述程式碼範例中，您可以看到序列值是在應用程式交易外部要求。這是因為 Cloud Spanner 不支援在同一執行緒中，於某項交易內執行另一項交易 (也稱為巢狀交易)。

如要解決這項限制，請使用背景執行緒要求序號值，並等待結果：

protected static final ExecutorService executor = Executors.newCachedThreadPool();

/**
 * Gets the next value using a background thread - to be used when inside a transaction to avoid
 * Nested Transaction errors.
 */
public long getNextInBackground() throws Exception {
  return executor.submit(this::getNext).get();
}

批次序號產生器

如果您也捨棄序列值必須依序排列的規定，就能大幅提升效能。這可讓應用程式保留一批序列值，並在內部發布。個別應用程式例項有自己的值批次，因此發放的值不會依序排列。此外，如果應用程式執行個體未使用整批值 (例如應用程式執行個體已關閉)，序列中就會留下未使用的值。

應用程式會執行下列作業：

  • 為每個序列維護內部狀態，其中包含起始值、批次大小和下一個可用值。
  • 從批次要求序號值。
  • 如果批次中沒有剩餘值，請執行下列操作：
    • 建立交易，讀取及更新序列值。
    • 讀取序列的 next_value 儲存格。
    • 將這個值儲存在內部，做為新批次的起始值。
    • 將資料庫中的 next_value 儲存格遞增一個量，該量等於批次大小。
    • 完成交易。
  • 傳回下一個可用值，並遞增內部狀態。
  • 在交易中使用傳回的值。

採用這個方法後，只有在需要預留新批次序號值時，使用序號值的交易才會發生延遲。

好處是增加批次大小後，效能可提升至任何層級，因為限制因素會變成每秒發出的批次數量。

舉例來說，如果批次大小為 100，且取得新批次的延遲時間為 10 毫秒 (因此每秒最多 100 個批次)，則每秒可發出 10,000 個序列值。

以下範例程式碼說明如何使用批次處理實作 getNext() 函式。請注意，程式碼會重複使用先前定義的 getAndIncrementNextValueInDB() 函式，從資料庫擷取新的序列值批次。

/**
 * Gets a new batch of sequence values from the database.
 *
 * <p>Reads next_value, increments it by batch size, then writes the updated next_value back.
 */
private synchronized void getBatch() throws SpannerException {
  if (next_value <= last_value_in_batch) {
    // already have some values left in the batch - maybe this has been refreshed by another
    // thread.
    return;
  }
  next_value = getAndIncrementNextValueInDB(batchSize);
  last_value_in_batch = next_value + batchSize - 1;
}

/**
 * Returns the next value from this sequence, getting a new batch of values if necessary.
 *
 * When getting a new batch, it creates a separate transaction, so this must be called
 * <strong>outside</strong> any other transactions. See {@link #getNextInBackground()} for an
 * alternative version that uses a background thread
 */

public synchronized long getNext() throws SpannerException {
  if (next_value > last_value_in_batch) {
    getBatch();
  }
  long value = next_value;
  next_value++;
  return value;
}

下列程式碼範例說明如何在要求兩個序列值時，使用非同步 getNext() 函式：

// Batch Sequence generator created outside transaction, as a long-lived object.
private BatchSequenceGenerator myBatchSequence =
    new BatchSequenceGenerator("my Sequence", /* batchSize= */ 100, dbClient);

public void usingBatchSequenceGenerator() {
  // Get two sequence values
  final long key1 = myBatchSequence.getNext();
  final long key2 = myBatchSequence.getNext();
  dbClient
      .readWriteTransaction()
      .run(
          new TransactionCallable<Void>() {
            @Nullable
            @Override
            public Void run(TransactionContext txn) {
              // Use the 2 key values in the transaction
              // ...
              return null;
            }
          });
}

同樣地，由於 Spanner 不支援巢狀交易，因此必須在交易外要求值 (或使用背景執行緒)。

非同步批次序列產生器

對於效能要求極高的應用程式，如果無法接受任何延遲增加，您可以準備好新一批值，在目前這批值用盡時使用，藉此提升先前批次產生器的效能。

如要達到這個目標，請設定門檻，指出批次中剩餘的序號值數量過低時。達到門檻後，序列產生器就會在背景執行緒中開始要求新的一批值。

與舊版相同，值不會依序發放，如果交易失敗或應用程式例項關閉，序列中就會出現未使用的值。

應用程式會執行下列作業：

  • 為每個序列維護內部狀態，其中包含批次的起始值和下一個可用值。
  • 從批次要求序號值。
  • 如果批次中的剩餘值少於門檻，請在背景執行緒中執行下列操作：
    • 建立交易，讀取及更新序列值。
    • 讀取 next_value 儲存格，找出要在應用程式中使用的序列名稱。
    • 在內部將這個值儲存為下一個批次的起始值。
    • 將資料庫中的 next_value 儲存格遞增一個等於批次大小的量
    • 完成交易。
  • 如果批次中沒有剩餘值，請從背景執行緒擷取下一個批次的起始值 (如有必要，請等待執行緒完成)，並使用擷取的起始值做為下一個值，建立新的批次。
  • 傳回下一個值，並遞增內部狀態。
  • 在交易中使用傳回的值。

為獲得最佳效能，背景執行緒應在目前批次用完序號值之前啟動並完成。否則應用程式就必須等待下一批資料，延遲時間也會增加。因此，您需要根據發放序號值的頻率，調整批次大小和低閾值。

舉例來說，假設擷取新值批次需要 20 毫秒的交易時間、批次大小為 1000，且每秒最多可發出 500 個值 (每 2 毫秒一個值)。在發出新值批次的 20 毫秒期間，系統會發出 10 個序列值。因此，剩餘序號值的門檻應大於 10，以便在需要時提供下一批序號。

以下範例程式碼說明如何使用批次處理實作 getNext() 函式。請注意，程式碼會使用先前定義的 getAndIncrementNextValueInDB() 函式，透過背景執行緒擷取一組序列值。

/**
 * Gets a new batch of sequence values from the database.
 *
 * <p>Reads nextValue, increments it by batch size, then writes the updated nextValue back.
 * Stores the resulting value in  nextBatchStartValue, ready for when the existing pool of values
 * is exhausted.
 */
private Long readNextBatchFromDB() {
  return getAndIncrementNextValueInDB(batchSize);
}

/**
 * Returns the next value from this sequence.
 *
 * If the number of remaining values is below the low watermark, this triggers a background
 * request for new batch of values if necessary. Once the current batch is exhausted, then a the
 * new batch is used.
 */
public synchronized long getNext() throws SpannerException {
  // Check if a batch refresh is required and is not already running.
  if (nextValue >= (lastValueInBatch - lowWaterMarkForRefresh) && pendingNextBatchStart == null) {
    // Request a new batch in the background.
    pendingNextBatchStart = executor.submit(this::readNextBatchFromDB);
  }

  if (nextValue > lastValueInBatch) {
    // batch is exhausted, we should have received a new batch by now.
    try {
      // This will block if the transaction to get the next value has not completed.
      long nextBatchStart = pendingNextBatchStart.get();
      lastValueInBatch = nextBatchStart + batchSize - 1;
      nextValue = nextBatchStart;
    } catch (InterruptedException | ExecutionException e) {
      if (e.getCause() instanceof SpannerException) {
        throw (SpannerException) e.getCause();
      }
      throw new RuntimeException("Failed to retrieve new batch in background", e);
    } finally {
      pendingNextBatchStart = null;
    }
  }
  // return next value.
  long value = nextValue;
  nextValue++;
  return value;
}

以下程式碼範例顯示如何使用非同步批次 getNext() 函式，在交易中要求使用兩個值：

// Async Batch Sequence generator created outside transaction, as a long-lived object.
private AsyncBatchSequenceGenerator myAsyncBatchSequence =
    new AsyncBatchSequenceGenerator("my Sequence", /* batchSize= */ 1000, 200, dbClient);

public void usingAsyncBatchSequenceGenerator() {
  dbClient
      .readWriteTransaction()
      .run(
          new TransactionCallable<Void>() {
            @Nullable
            @Override
            public Void run(TransactionContext txn) {
              // Get two sequence values
              final long key1 = myBatchSequence.getNext();
              final long key2 = myBatchSequence.getNext();
              // Use the 2 key values in the transaction
              // ...
              return null;
            }
          });
}

請注意，在這種情況下，可以在交易中要求值，因為新的一批值是在背景執行緒中擷取。

摘要

下表比較四種序列產生器的特性：

同步 非同步 批次 非同步批次
不重複的值 是 是 是 是
全域排序值 是 是 無
但如果負載夠高，且批次大小夠小，值就會彼此接近		 無
但如果負載夠高，且批次大小夠小，值就會彼此接近
無間隙 是 否 否 否
成效 每筆交易的延遲時間，
(每秒約 25 個值)		 每秒 50 到 100 個值 每秒 50 到 100 個批次值 每秒 50 到 100 個批次值
延遲時間增加 > 10 毫秒
高爭用時顯著增加 (交易耗費大量時間時)		 每筆交易 10 毫秒
高爭用時顯著增加		 10 毫秒，但僅限擷取新批次的值時 如果批次大小和低門檻設為適當值，則為零

上表也說明，您可能需要針對全域排序值和無間隙值序列的要求做出妥協，才能產生不重複的值，同時符合整體效能要求。

效能測試

您可以使用效能測試/分析工具 (與上述序列產生器類別位於同一個 GitHub 存放區)，測試每個序列產生器，並展示效能和延遲特性。這項工具會模擬 10 毫秒的應用程式交易延遲，並同時執行多個要求序號值的執行緒。

由於只會修改單一資料列，因此效能測試只需要單一節點的 Spanner 執行個體即可。

舉例來說，下列輸出內容顯示在 10 個執行緒的同步模式中，效能與延遲時間的比較：

$ ITERATIONS=2000
$ MODE=SYNC
$ NUMTHREADS=10
$ java -jar sequence-generator.jar \
   $INSTANCE_ID $DATABASE_ID $MODE $ITERATIONS $NUMTHREADS
2000 iterations (10 parallel threads) in 58739 milliseconds: 34.048928 values/s
Latency: 50%ile 27 ms
Latency: 75%ile 31 ms
Latency: 90%ile 1189 ms
Latency: 99%ile 2703 ms

下表比較各種模式和並行執行緒數量的結果，包括每秒可發出的值數量，以及第 50、90 和 99 個百分位數的延遲時間：

模式和參數 執行緒數量 每秒值 第 50 個百分位數的延遲時間 (毫秒) 第 90 個百分位數的延遲時間 (毫秒) 第 99 個百分位數的延遲時間 (毫秒)
同步處理 10 34 27 1189 2703
同步處理 50 30.6 1191 3513 5982
ASYNC 10 66.5 28 611 1460
ASYNC 50 78.1 29 1695 3442
批次
(大小 200)		 10 494 18 20 38
BATCH (批次大小 200) 50 1195 27 55 168
ASYNC BATCH
(batch size 200, LT 50)		 10 512 18 20 30
ASYNC BATCH
(batch size 200, LT 50)		 50 1622 24 28 30

您可以看到，在同步 (SYNC) 模式下，隨著執行緒數量增加，競爭也會增加。這會導致交易延遲時間大幅增加。

在非同步 (ASYNC) 模式中，由於取得序列的交易較小，且與應用程式的交易分開，因此爭用較少，頻率也較高。不過，仍可能發生爭用情形，導致第 90 百分位延遲時間較長。

在批次 (BATCH) 模式中，延遲時間會大幅縮短，但第 99 個百分位數除外，因為這對應於產生器需要從資料庫同步要求另一批序號值的情況。BATCH 模式的效能比 ASYNC 模式高出許多。

50 個執行緒的批次模式延遲時間較長，因為序列發布速度太快，導致限制因素是虛擬機器 (VM) 執行個體的效能 (在本例中，測試期間 4 個 vCPU 的機器 CPU 使用率為 350%)。使用多部機器和多個程序會顯示與 10 個執行緒批次模式類似的整體結果。

在 ASYNC BATCH 模式中，延遲時間的變化幅度很小，效能也較高 (即使有大量執行緒也是如此)，因為從資料庫要求新批次的延遲時間完全獨立於應用程式交易。

後續步驟