ULIDみたいな独自IDを作る【TypeScript】
ULIDとは？
ソート可能な文字列型のIDです。先頭にタイムスタンプ、末尾にランダム文字列を配置しているので、ULIDでソートすると作成日時順に並びます。
詳しい仕様はこちら
独自IDの仕様
- 使える文字は0-9とa-zの合計36文字（36進数）
- Numberは2〜36進数ならtoString()で変換できるので楽です
- タイムスタンプ部は9桁
- 現在のUNIX時間を36進数に変換すると8桁ですが、
2059/05/26 02:38:27.456以降は9桁となるので9桁としました
- 現在のUNIX時間を36進数に変換すると8桁ですが、
- ランダム部は7桁
- 7桁の36進数は約4万個のIDを作成すると衝突する確率が1%ぐらいみたいです（タイムスタンプ部が1ミリ秒ごとに変わるので、1ミリ秒に4万行のレコードを作成する必要のある巨大システム以外では問題ないと思われます）
ULIDのソースを見る
ULIDみたいなIDを作りたいので、まずはULIDのソースを見てみます。個人的にはDenoの実装のほうがわかりやすかったので、そちらを参考にしました。
実装
実装していきます。nodeのバージョンは21.6.0です。
（nodeで使うことを想定していますが、ブラウザでも動くと思います）
タイムスタンプ部
ユニックスタイムを文字列に変更するだけです。今回の場合はtoString()で変換できます。
function encodeTimestamp(timestamp: number) {
return timestamp.toString(36).padStart(9, '0')
}
他のエンコードを使う場合
toString()で変換できない場合は独自に作成する必要があります。
ULIDでは文字セットから1文字ずつピックアップしていっているようです。
any-baseというライブラリを使うとこの辺を簡単に実装できます。
公式のREADMEから引用var anyBase = require('any-base'), dec2hex = anyBase(anyBase.DEC, anyBase.HEX), shortId = anyBase(anyBase.DEC, '0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ_-+!@#$^'), longId = anyBase('0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ_-+!@#$^', anyBase.DEC); dec2hex('123456'); // return: '1E240' shortId('1234567890'); // return: 'PtmIa' longId('PtmIa'); // return: '1234567890'
ランダム部
ランダム値を生成し、文字列に変換します。ID生成ライブラリであるnanoidを使えば楽に実装できますが、せっかくなので今回は乱数生成から実装していきます。
文字セットからランダムに文字を取得したものを指定桁数分並べています。
const CHARSET = '0123456789abcdefghijklmnopqrstuvwxyz'
function encodeRandom(length: number) {
// 0〜65535の乱数をlengthの数だけ得る
const randomValues = new Uint16Array(length)
globalThis.crypto.getRandomValues(randomValues)
const randomString = randomValues.reduce((accumulator, randomValue) => {
// 0〜65535の乱数を0〜[文字列セットの長さ]-1の乱数に変換する
let randomIndex = Math.floor(randomValue / 0xffff * CHARSET.length)
if (randomIndex === CHARSET.length) {
// randomValue / 0xffffがちょうど1だった場合、indexが文字セットの長さと同じになってしまうので、調整
randomIndex = CHARSET.length - 1
}
// 先程作成したインデックスを使って文字セットから文字を取得し、結合していく
return accumulator + CHARSET.charAt(randomIndex)
}, '')
return randomString
}
なぜUint8ArrayではなくUint16Arrayを使用しているの？
Uint8Arrayを使用すると一部の文字の出現頻度に大きく偏りが発生するからです。理由は長くなるので記事の最後に書きます。
タイムスタンプ部とランダム部を結合
最後にタイムスタンプ部とランダム部を結合すれば完成です。
function myId() {
return encodeTimestamp(Date.now()) + encodeRandom(7)
}
完成
最終的なコードはこちらです。
const CHARSET = '0123456789abcdefghijklmnopqrstuvwxyz'
function encodeTimestamp(timestamp: number) {
return timestamp.toString(36).padStart(9, '0')
}
function encodeRandom(length: number) {
const randomValues = new Uint16Array(length)
globalThis.crypto.getRandomValues(randomValues)
const randomString = randomValues.reduce((accumulator, randomValue) => {
let randomIndex = Math.floor(randomValue / 0xffff * CHARSET.length)
if (randomIndex === CHARSET.length) {
randomIndex = CHARSET.length - 1
}
return accumulator + CHARSET.charAt(randomIndex)
}, '')
return randomString
}
function myId() {
return encodeTimestamp(Date.now()) + encodeRandom(7)
}
nanoidを使った場合
nanoIdを使った場合は数行で書けます。やっぱり便利なライブラリは使ったほうがいいですね。
import { customAlphabet } from 'nanoid'
function myId() {
const timestamp = Date.now().toString(36).padStart(9, '0')
const nanoid = customAlphabet('0123456789abcdefghijklmnopqrstuvwxyz', 7)
const random = nanoid()
return timestamp + random
}
ランダム部生成にUint8Arrayを使わない理由
ランダム部の生成にUint8Arrayを使うと特定の文字の出現頻度が大きく偏ります。その理由は以下のコードを実行してみるとわかりました。
const obj = {} as Record<number, number>
for(let i = 0; i < 256; i++) {
const n = Math.floor(i / 255 * 36)
obj[n] = obj[n] ? obj[n] + 1 : 1
}
console.log(obj)
{
"0": 8,
"1": 7,
"2": 7,
"3": 7,
"4": 7,
"5": 7,
"6": 7,
"7": 7,
"8": 7,
"9": 7,
"10": 7,
"11": 7,
"12": 8,
"13": 7,
"14": 7,
"15": 7,
"16": 7,
"17": 7,
"18": 7,
"19": 7,
"20": 7,
"21": 7,
"22": 7,
"23": 7,
"24": 8,
"25": 7,
"26": 7,
"27": 7,
"28": 7,
"29": 7,
"30": 7,
"31": 7,
"32": 7,
"33": 7,
"34": 7,
"35": 7,
"36": 1
}
0〜255までの数値を255で割って36を掛け、小数点以下を切り捨てると0, 12, 24になる数だけ1つ多くなります。実際のコードでは36が出た場合は35として扱うので、インデックスが0, 12, 24, 35である0, c, o, zの出現頻度が高くなってしまいます。
そこで、Uint16Arrayを使うことでこれを軽減できます。
{
"0": 1821,
"1": 1820,
"2": 1821,
"3": 1820,
"4": 1821,
"5": 1820,
"6": 1820,
"7": 1821,
"8": 1820,
"9": 1821,
"10": 1820,
"11": 1820,
"12": 1821,
"13": 1820,
"14": 1821,
"15": 1820,
"16": 1821,
"17": 1820,
"18": 1820,
"19": 1821,
"20": 1820,
"21": 1821,
"22": 1820,
"23": 1820,
"24": 1821,
"25": 1820,
"26": 1821,
"27": 1820,
"28": 1821,
"29": 1820,
"30": 1820,
"31": 1821,
"32": 1820,
"33": 1821,
"34": 1820,
"35": 1820,
"36": 1
}
これでも偏りが気になる場合はUint32ArrayやBigUint64Arrayを使うとさらに軽減できます（そこまで気にするならライブラリを使った方がいいと思います）。
ちなみに、参考にしているULIDのコードではUint8Arrayを使っていますが、ULIDは32進数を使っており、256をちょうど8ずつ分けられるので問題ありません。
Discussion