在 Spanner 中生成序列

本文档介绍了数据库管理员和应用开发者在使用 Spanner 的应用中生成唯一数字序列的方法。

简介

在很多情况下，企业需要一个简单且唯一的数字 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 ms 的事务延迟时间）。由于将单独检索序列值，因此不会更改应用事务本身的延迟时间，并可最大程度地减少争用。

但是，如果请求但不使用序列值，则序列中会有间断，因为无法回滚请求的序列值。如果在请求序列值后，应用在事务期间取消或失败，则会发生这种情况。

以下示例代码展示了如何实现检索和递增数据库中的 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 ms 的延迟时间才会获得新批次），因此每秒最多 100 个批次，则每秒可以发出 10000 个序列值。

以下示例代码展示了如何使用批次实现 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 ms，批次大小为 1000，最大序列发出频率为每秒 500 个值(每 2 ms 一个值)。在发出新一批值的 20 ms 期间，将发出 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;
            }
          });
}

请注意，在这种情况下，可以在事务内请求值，因为将在后台线程中检索新一批值。

总结

下表比较了四种类型的序列生成器的特性：

同步 异步 批次 异步批次
唯一值 是 是 是 是
全局有序值 是 是 否
但在负载足够大且批次大小足够小的情况下，值将彼此接近		 否
但在负载足够大且批次大小足够小的情况下，值将彼此接近
无间断 是 否 否 否
性能 1/事务延迟时间，
（每秒约 25 个值）		 每秒 50-100 个值 每秒 50-100 个值批次 每秒 50-100 个值批次
延迟时间增加 > 10 ms
显著较高，争用激烈（事务需要大量时间时）		 每个事务 10 ms
显着较高，争用激烈		 10 ms，但仅当检索到新一批值时 如果将批次大小和低阈值设置为适当值，则为零

上表还说明了这样一个事实，即您可能需要在满足整体性能要求的同时，折衷考虑全局有序值和无间断值系列的要求，以便生成唯一值。

性能测试

您可以使用与上一序列生成器类位于同一 GitHub 代码库中的性能测试/分析工具，来测试其中每个序列生成器，并展示性能和延迟时间特性。该工具可模拟 10 ms 的应用事务延迟时间，并同时运行多个请求序列值的线程。

性能测试仅需要要用于测试的单节点 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 百分位的延迟时间 (ms) 第 99 百分位的延迟时间 (ms) 第 99 百分位的
延迟时间 (ms)
SYNC 10 34 27 1189 2703
SYNC 50 30.6 1191 3513 5982
ASYNC 10 66.5 28 611 1460
ASYNC 50 78.1 29 1695 3442
BATCH
（大小 200）		 10 494 18 20 38
BATCH（批次大小 200） 50 1195 27 55 168
ASYNC BATCH
（批次大小 200，LT 50）		 10 512 18 20 30
ASYNC BATCH
（批次大小 200，LT 50）		 50 1622 24 28 30

您可以看到，在同步 (SYNC) 模式下，随着线程数增加，争用也更激烈。这会显著增加事务延迟时间。

在异步 (ASYNC) 模式下，由于获取序列的事务较小且与应用事务分开，因此争用没有那么激烈，并且频率更高。但是，仍然可能出现争用，从而第 90 百分位的延迟时间较长。

在批次 (BATCH) 模式下，延迟时间显着减少，但第 99 百分位除外，这对应于生成器需要从数据库同步请求另一批序列值的情况。BATCH 模式下的性能比 ASYNC 模式下的性能高出许多倍。

50 个线程的批次模式具有更长的延迟时间，因为发出序列的速度非常快，因此限制因素是虚拟机 (VM) 实例的能力（在这种情况下，一台有 4 个 vCPU 的机器在测试期间以 350% CPU 运行）。使用多台机器和多个进程将显示类似于 10 个线程的批次模式的总体结果。

在 ASYNC BATCH 模式下，即使有大量线程，延迟时间变化也最小，并且性能更高，因为从数据库请求新批次的延迟时间与应用事务完全无关。

后续步骤