Skip to content

Instantly share code, notes, and snippets.

@jeremyworboys
Last active July 16, 2021 10:37
Show Gist options
  • Save jeremyworboys/b5854d9591d7763c5bd7 to your computer and use it in GitHub Desktop.
Save jeremyworboys/b5854d9591d7763c5bd7 to your computer and use it in GitHub Desktop.
<?php
/**
* Fancy ID generator that creates 20-character string identifiers with the following properties:
*
* 1. They're based on timestamp so that they sort *after* any existing ids.
* 2. They contain 72-bits of random data after the timestamp so that IDs won't collide with other clients' IDs.
* 3. They sort *lexicographically* (so the timestamp is converted to characters that will sort properly).
* 4. They're monotonically increasing. Even if you generate more than one in the same timestamp, the
* latter ones will sort after the former ones. We do this by using the previous random bits
* but "incrementing" them by 1 (only in the case of a timestamp collision).
*/
class PushId
{
/**
* Modeled after base64 web-safe chars, but ordered by ASCII.
*
* @var string
*/
const PUSH_CHARS = '-0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ_abcdefghijklmnopqrstuvwxyz';
/**
* Timestamp of last push, used to prevent local collisions if you push twice in one ms.
*
* @var int
*/
private static $lastPushTime = 0;
/**
* We generate 72-bits of randomness which get turned into 12 characters and appended to the
* timestamp to prevent collisions with other clients. We store the last characters we
* generated because in the event of a collision, we'll use those same characters except
* "incremented" by one.
*
* @var array
*/
private static $lastRandChars = [];
/**
* @return string
*/
public static function generate()
{
$now = (int) microtime(true) * 1000;
$isDuplicateTime = ($now === static::$lastPushTime);
static::$lastPushTime = $now;
$timeStampChars = new SplFixedArray(8);
for ($i = 7; $i >= 0; $i--) {
$timeStampChars[$i] = substr(self::PUSH_CHARS, $now % 64, 1);
// NOTE: Can't use << here because javascript will convert to int and lose the upper bits.
$now = (int) floor($now / 64);
}
static::assert($now === 0, 'We should have converted the entire timestamp.');
$id = implode('', $timeStampChars->toArray());
if (!$isDuplicateTime) {
for ($i = 0; $i < 12; $i++) {
$lastRandChars[$i] = floor(rand(0, 64));
}
} else {
// If the timestamp hasn't changed since last push, use the same random number, except incremented by 1.
for ($i = 11; $i >= 0 && static::$lastRandChars[$i] === 63; $i--) {
static::$lastRandChars[$i] = 0;
}
static::$lastRandChars[$i]++;
}
for ($i = 0; $i < 12; $i++) {
$id .= substr(self::PUSH_CHARS, $lastRandChars[$i], 1);
}
static::assert(strlen($id) === 20, 'Length should be 20.');
return $id;
}
/**
* @param bool $condition
* @param string $message
*/
private static function assert($condition, $message = '')
{
if ($condition !== true) {
throw new RuntimeException($message);
}
}
}
@baversjo
Copy link

I noticed that the value of $now always ended with 000. The (int) conversion takes precedence over *1000, so you never get ms precision with above solution. This is a bug specific to the PHP fork; the js implementation has ms in the timestamp.
To fix, replace this line:
$now = (int) microtime(true) * 1000;
with this:
$now = (int) (microtime(true) * 1000);

@romain-w
Copy link

This code does not seem to work since 28/11/2017 01:21 AM (Paris)
The part of the code $now % 64 on line 50 goes into negative
This results in the error:

Fatal error: Uncaught exception 'RuntimeException' with message 'We should have converted the entire timestamp.'

My temporary solution was to add after line 54:
if($now < 0 ) $now = 0;

@frozsgy
Copy link

frozsgy commented Jun 28, 2019

The 61st line sometimes causes errors, since there isn't a 64th character. It should be replaced with $lastRandChars[$i] = floor(rand(0, 63));

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment