Str::orderedUuid()は先頭の48ビットでタイムスタンプで表しているため、順序が保証されるらしい。

はじめに

Laravelのmigrationsでテーブルを作成する際は、 $table->id() としてidカラムがPKになることが多いかと思いですが、AUTO_INCREMENTだと都合が悪い場合もあります。その代替としては、GUIDをPKとする方法が一般的かと思われます。

ただし、アプリケーションでランダムに作成されたGUIDはそれ単体では連続性が保証されないので、
INSERTのオーバーヘッドが増加する可能性があります。

Laravelでは Str::orderedUuid() というメソッドでtime-orderedなUUID(version 4)を生成することが出来ます。
これを利用してorderedなUUIDをPKにすることで、INSERT時のデメリットを解消出来るということなのですが、

そもそもUUIDなのにtime-orderedってどういうことなのか？
どのようにtime-orderedを実現しているのか？

というところが気になったのでソースを深ぼって見ました。

Str::orderedUuid

とりあえず Str:orderedUuid の中身を見てみる。

/**
 * Generate a time-ordered UUID (version 4).
 *
 * @return \Ramsey\Uuid\UuidInterface
 */
public static function orderedUuid()
{
    if (static::$uuidFactory) {
        return call_user_func(static::$uuidFactory);
    }

    $factory = new UuidFactory;

    $factory->setRandomGenerator(new CombGenerator(
        $factory->getRandomGenerator(),
        $factory->getNumberConverter()
    ));

    $factory->setCodec(new TimestampFirstCombCodec(
        $factory->getUuidBuilder()
    ));

    return $factory->uuid4();
}

RandomGeneratorにCombGeneratorを、CodecにTimestampFirstCombCodecを指定し、UuidFactory::uuid4 を呼び出しています。RandomGeneratorとCodecがどのように使われているかは後述するとして、UuidFactory::uuid4 の中身を見てみます。

public function uuid4(): UuidInterface
{
    $bytes = $this->randomGenerator->generate(16);

    return $this->uuidFromBytesAndVersion($bytes, 4);
}

ここで先程指定したRandomGeneratorのgenerateを呼び出しています。そこで生成されたバイト文字列とバージョンを示す4を引数として uuidFromBytesAndVersion を呼び出しています。

/**
 * Returns an RFC 4122 variant Uuid, created from the provided bytes and version
 *
 * @param string $bytes The byte string to convert to a UUID
 * @param int $version The RFC 4122 version to apply to the UUID
 *
 * @return UuidInterface An instance of UuidInterface, created from the
 *     byte string and version
 *
 * @psalm-pure
 */
private function uuidFromBytesAndVersion(string $bytes, int $version): UuidInterface
{
    /** @var array $unpackedTime */
    $unpackedTime = unpack('n*', substr($bytes, 6, 2));
    $timeHi = (int) $unpackedTime[1];
    $timeHiAndVersion = pack('n*', BinaryUtils::applyVersion($timeHi, $version));

    /** @var array $unpackedClockSeq */
    $unpackedClockSeq = unpack('n*', substr($bytes, 8, 2));
    $clockSeqHi = (int) $unpackedClockSeq[1];
    $clockSeqHiAndReserved = pack('n*', BinaryUtils::applyVariant($clockSeqHi));

    $bytes = substr_replace($bytes, $timeHiAndVersion, 6, 2);
    $bytes = substr_replace($bytes, $clockSeqHiAndReserved, 8, 2);

    if ($this->isDefaultFeatureSet) {
        return LazyUuidFromString::fromBytes($bytes);
    }

    return $this->uuid($bytes);
}

uuidFromBytesAndVersion では引き渡されたバイト文字列のうち、versionとvariantを示す桁を置換しています。最後にそのバイト文字列からUuidクラスをnewして返却しています。

要するに Str:orderedUuid では、「RandomGeneratorで生成されたバイト文字列からUuidを生成している」ということのようです。

CombGenerator

CombGeneratorは COMB と呼ばれる連続性を持ったGUIDを生成します。
当該クラスのPhpDocに生成方法についての記述があります。

/**
 * CombGenerator generates COMBs (combined UUID/timestamp)
 *
 * The CombGenerator, when used with the StringCodec (and, by proxy, the
 * TimestampLastCombCodec) or the TimestampFirstCombCodec, combines the current
 * timestamp with a UUID (hence the name "COMB"). The timestamp either appears
 * as the first or last 48 bits of the COMB, depending on the codec used.
 *
 * By default, COMBs will have the timestamp set as the last 48 bits of the
 * identifier.
 * (略)
 */

DeepL翻訳にそのまま突っ込んだのが以下。

CombGenerator は StringCodec (そして、その代理として
TimestampLastCombCodec) または TimestampFirstCombCodec と共に使われる場合、CombGenerator は現在のタイムスタンプをUUIDと結合します。
タイムスタンプとUUIDを組み合わせます（”COMB “という名前に由来します）。タイムスタンプは
タイムスタンプは、使用するコーデックに応じて、COMBの最初または最後の48ビットとして表示されます。
デフォルトでは、COMBはタイムスタンプを識別子の最後の48ビットとして設定されます。

CombGeneratorがやっていることは、COMBと呼ばれるUUIDとtimestampを組み合わせた (combined) バイト文字列を生成するところまでで、timestampの48ビットをどこに割り当てるかはCodecによりけり、ということが窺えます。以下はその処理を司るメソッドです。

/**
 * @throws InvalidArgumentException if $length is not a positive integer
 *     greater than or equal to CombGenerator::TIMESTAMP_BYTES
 *
 * @inheritDoc
 */
public function generate(int $length): string
{
    if ($length < self::TIMESTAMP_BYTES) {
        throw new InvalidArgumentException(
            'Length must be a positive integer greater than or equal to ' . self::TIMESTAMP_BYTES
        );
    }

    $hash = '';
    if (self::TIMESTAMP_BYTES > 0 && $length > self::TIMESTAMP_BYTES) {
        $hash = $this->randomGenerator->generate($length - self::TIMESTAMP_BYTES);
    }

    $lsbTime = str_pad(
        $this->converter->toHex($this->timestamp()),
        self::TIMESTAMP_BYTES * 2,
        '0',
        STR_PAD_LEFT
    );

    return (string) hex2bin(
        str_pad(
            bin2hex($hash),
            $length - self::TIMESTAMP_BYTES,
            '0'
        )
        . $lsbTime
    );
}

大まかには、以下の流れで処理されていきます。

生成する文字列からTIMESTAMP_BYTESの桁数を除いた桁数の文字列を生成する
現在のtimestampを16進表記に置き換えた文字列を生成する
1の文字列の末尾に2を結合する

TimestampFirstCombCodec

生成したUuidクラスを文字列に変換する際にCodecによるencodeが呼び出されます。

/**
 * @psalm-return non-empty-string
 */
public function toString(): string
{
    return $this->codec->encode($this);
}

ここに来てようやく TimestampFirstCombCodec が使われるのです。

encodeの処理自体は比較的シンプルで、

CombGeneratorで生成したバイト文字列の末尾から48ビット(timestamp)と先頭の48ビットを入れ替える
UUIDのフォーマットに合わせて桁を区切り、 “-” でつなげる

というものになっています。

/**
 * @psalm-return non-empty-string
 * @psalm-suppress MoreSpecificReturnType we know that the retrieved `string` is never empty
 * @psalm-suppress LessSpecificReturnStatement we know that the retrieved `string` is never empty
 */
public function encode(UuidInterface $uuid): string
{
    $bytes = $this->swapBytes($uuid->getFields()->getBytes());

    return sprintf(
        '%08s-%04s-%04s-%04s-%012s',
        bin2hex(substr($bytes, 0, 4)),
        bin2hex(substr($bytes, 4, 2)),
        bin2hex(substr($bytes, 6, 2)),
        bin2hex(substr($bytes, 8, 2)),
        bin2hex(substr($bytes, 10))
    );
}

/**
 * Swaps bytes according to the timestamp-first COMB rules
 */
private function swapBytes(string $bytes): string
{
    $first48Bits = substr($bytes, 0, 6);
    $last48Bits = substr($bytes, -6);

    $bytes = substr_replace($bytes, $last48Bits, 0, 6);
    $bytes = substr_replace($bytes, $first48Bits, -6);

    return $bytes;
}