ULID生成速度を40倍にしたった

Transcript

1. 0 ULID⽣成速度を40倍にしたった 2025-04-04 第117回NearMe技術勉強会 @yujiosaka
2. 1 前回
3. 2 前回のおさらい 2
4. 3 WASMとは？ • 低レベルのバイトコードフォーマット • C、C++、Rust等の⾔語のコンパイル対象 • ⾼性能なウェブアプリケーションを実現する • サーバーサイドでの利⽤が増加している
5. 4 WASMの特徴 • 性能 ‒ ほぼネイティブの速度で実⾏ • 多⾔語対応 ‒ 様々なプログラミング⾔語をサポート • クロスプラットフォーム ‒ ブラウザやネイティブのランタイムに対応 • セキュリティ ‒ サンドボックス環境で実⾏ • クロスアーキテクチャ ‒ 複数のCPUアーキテクチャで実⾏（例：ARM、x86）
6. 5 Universally Unique Lexicographically Sortable Identifier 5
7. 6 ULIDの仕様 01HY5BC0ECSP300WP0YEZQ6C5C 48ビットのタイムスタンプパート 80ビットのランダムパート
8. 7 連番の場合 7
9. 8 Aurora MySQLの場合 mysql> SHOW TABLE STATUS LIKE 'users'; +---------+-----------+- -+----------------------+- -+ | Name | Engine | | Auto_increment | | +---------+-----------+- -+----------------------+- -+ | users | InnoDB | | 1 | +---------+-----------+- -+----------------------+- -+
10. 9 Auroraへの連番を使った書き込み AZ1 AZ2 Storage 1 Storage 2 Storage 3 Storage 4 Storage 5 Storage 6 AZ3 Write Replica ①連番をインクリメント ②最新の連番を取得 ③取得した連番を  使って書き込み
11. 10 ランダムな値の場合 10
12. 11 Auroraへのランダムな値を使った書き込み AZ1 AZ2 Storage 1 Storage 2 Storage 3 Storage 4 Storage 5 Storage 6 AZ3 Write Replica ②⽣成したIDを使って書き込み App ①ランダムな値
13. 12 ランダムな値のメリット • 連番のインクリメント‧取得をスキップできる • 書き込みが⾼速化する • アプリケーションでIDを⽣成できる • 処理を並列化しやすい • IDが推測されにくくなる • クローリングされにくい • サービスの規模が推測されにくい
14. 13 ランダムな値のデメリット • インデックスに必要なメモリが増える • インデックスのキャッシュヒット率が下がる • インデックスのリバランシングが発⽣しやすくなる（B-Tree/B+Treeの場合）
15. 14 メモリ上のホットデータ ソート可能 ランダム
16. 15 ランダムな値のデメリット • インデックスに必要なメモリが増える • インデックスのキャッシュヒット率が下がる • インデックスのリバランシングが発⽣しやすくなる（B-Tree/B+Treeの場合）
17. 16 連番のリバランシング 4 7 4 5 6 7 8 1 2 3 4 4 5 1 2 3 • 各ノードは3つまでの値を持つことができるとする • 既存のノードを保ったまま、新しいノードが追加される
18. 17 ランダムのリバランシング P Z P S T Z A J M S S T Z A J P • ページ分割が起きやすくなる • 親ノードの書き換えが起きやすくなる
19. 18 UUIDの歴史 UUID1 ‒ 太陽暦カレンダーとMACアドレス UUID2 ‒ 太陽暦カレンダーとMACアドレスとPOSIXユーザーID UUID3 ‒ MD5でハッシュ化されたnamespaceとname UUID4 ‒ 完全ランダム UUID5 ‒ SHA1でハッシュ化されたnamespaceとname UUID6 ‒ ⽇付とMACアドレス UUID7 ‒ UNIXタイムスタンプとランダム UUID8 ‒ バージョン以外は⾃由 最も使われているバージョン 実はソート可能
20. 19 UUIDv7とULIDのサイズ⽐較 • UUIDv7 • ⽂字列 ‒ 36⽂字 • バイナリ ‒ 128バイト • ULID • ⽂字列 ‒ 26⽂字 • バイナリ ‒ 128バイト
21. 20 WASMで40倍のパフォーマンスを実現する
22. 21 実現⽅法 1. オリジナルのJavaScript実装から単体テストを借りてくる 2. JavaScriptをRustに翻訳する 3. JavaScriptとRustのブリッジコードを書く
23. 22 ベンチマーク 関数 ulid wa-ulid パフォーマンス倍率 encodeTime 3,612,913 ops/sec 1,466,147 ops/sec 0.41x decodeTime 2,022,776 ops/sec 4,885,942 ops/sec 2.42x ulid 47,312 ops/sec 454,704 ops/sec 9.61x
24. 23 TIPS 23
25. 24 // Before String::new(); // After Vec::<char>::with_capacity(len); 1. 効率的なデータ構造を使⽤する
26. 25 const ENCODING: &str = "0123456789ABCDEFGHJKMNPQRSTVWXYZ"; // Before let mut chars = Vec::with_capacity(len); for index in 0..len { chars.push(ENCODING.chars().nth(index).unwrap()); } // After let mut chars = Vec::with_capacity(len); let encoding_bytes = ENCODING.as_bytes(); for index in 0..len { chars.push(encoding_bytes[index] as char); } 2. 不要な変換やメモリの割り当てを避ける
27. 26 const ENCODING_LEN: usize = 32; const TIME_LEN: usize = 10; // Before for i in 0..TIME_LEN { time += i as f64 * (ENCODING_LEN as u64).pow(index as u32) as f64; } // After let powers = [1.0, 32.0, ..., 35184372088832.0] for i in 0..TIME_LEN { time += i as f64 * powers[index]; } 3. 計算結果をキャッシュしておく
28. 27 ベンチマーク 関数 ulid wa-ulid パフォーマンス倍率 encodeTime 3,863,741 ops/sec 4,904,495 ops/sec 1.27x decodeTime 1,951,730 ops/sec 5,336,862 ops/sec 2.73x ulid 44,758 ops/sec 1,933,859 ops/sec 43.20x
29. 28 得るものあれば失うものあり ulid.js wa-ulid.js 4.7kb 110kb
30. 29 Thank you