はじめに
SSDのFlash Translation Layer (FTL)の研究者は、1年に1回はFTLのシミュレータをいちから作る人種です（言い過ぎ）。
そんな感じで、PythonでSSDのFTLのシミュレータを実装していた時の話です。SSDの容量全体（LBA領域全体）に対する4 KBランダムライトコマンドを発生させてそのシミュレータに入力して挙動を確かめていました。
ランダムライトですので疑似乱数系列生成ライブラリを使用してコマンドの先頭LBAを生成していたのですが、どうも挙動が期待と異なるので調べたところ、生成された系列が私の期待する「ランダム系列」ではありませんでした。
結論から言うと私の勘違い（仕様を確認せずに実装したこと）が原因なのですが、自分の備忘録を兼ねて記事として残します。
※ 投稿してからPythonのアドベントカレンダーに空きがあったので登録させていただきました。
まとめ
- Pythonの
random.randrange(min, max)の連続実行は「取り出した値を袋の中に戻してまた袋から値を取り出す」動作になり「minからmaxまで重複せずにランダムに取り出す」動作にはならない - 「minからmaxまで重複せずにランダムに取り出す」には、minからmaxまで1つずつリストに入れてシャッフルして1つずつ取り出せば良い（ただしメモリ爆食い）
- ライブラリは思い込みで使わず仕様や動作を確認してから使うべき
使用目的と期待値
FTLのアルゴリズム評価における下準備（プリコンディショニング）のため、SSDの容量全体に対して容量分のランダムライト（サイズは4 KB、先頭LBAは4 KBアライン）を行いたくて、コマンドの先頭LBAをランダムに生成する、というのが使用目的でした。
期待値は、例えば1 TBのSSDをシミュレートする場合は1 TBを4 KBで分割して得られる全領域（以降クラスタと呼びます）の先頭LBAが、1 TB書き込むうちに、ランダムな出現順で、必ず1回は出現することです。
ここでポイントになるのは、上記「各クラスタは必ず1回は出現すること」という期待値が実は「各クラスタは正しく1回（だけ）出現すること」と同じであることです。
なぜなら、上の例では容量1 TBなので総書き込み量は1 TBであり、かつ全クラスタが少なくとも1回は書き込まれることが条件なので、結果的に各クラスタが正確に1回だけ書き込まれる必要があるからです。
実装方法
こんな感じに書きました。NumPyを使用しても同じように書けるはずです。
import random
def generate_command( _max_lba ):
cluster_head_lba = random.randrange( 0, _max_lba, 8 )
return cluster_head_lba
このテスト時はセクタサイズは512バイトと仮定していましたので、「全域4 KBランダムライト」という仕様から、「0から最大LBA (_max_lba)までの整数のうち8の倍数をランダムに選ぶ」と設計し、そのまま深く考えずにこのように実装しました。
起きたこと
これでプログラムを走らせたところ、SSD容量分書き込み終わる前に「同じクラスタへの書き込みが発生する」という事態が発生しました。
以下は再現させたログの一部です。「NANDフラッシュメモリのブロック0のインデックス0xBB1に最新データが記録されているクラスタ0xB44361が上書き（無効化）された」ということを示しています。
[I] invalidated: cluster 0x00B44361, block 0x00000000, index 0x00000BB1
[I] invalidated: cluster 0x0A8016B3, block 0x00000008, index 0x000009CA
[I] invalidated: cluster 0x08E9B185, block 0x00000000, index 0x0000054E
[I] invalidated: cluster 0x0D15B83F, block 0x00000004, index 0x00000C21
[I] invalidated: cluster 0x090A9DE4, block 0x00000005, index 0x000011D2
つまり「SSD容量分書き終わる前にクラスタ0xB44361の2回目の書き込みが行われた」ことを示していて、「SSD容量分書き終わるまでに各クラスタが正しく1回（だけ）出現すること」という期待値と異なります。
なにを間違えたか
よくよく考えればライブラリの仕様通りの動作です。以下はPython公式ドキュメントからの引用です。
random.randrange(start, stop[, step])
Return a randomly selected element from range(start, stop, step).Python 3.12.0ドキュメント "random — Generate pseudo-random numbers"より引用
単に指定された範囲からひとつ要素（値）を選択するだけです。ですので、このメソッドを同じ引数（範囲）で複数回呼び出したら、毎回同じ範囲（候補）から要素が選択されるわけで、近い試行において同じ値を引く可能性も確率的にはゼロではありません。
最初にも言及しましたが、このメソッドを複数回呼び出すと「取り出した値を袋の中に戻してまた袋から値を取り出す」ことになります。この動作の理解不足が私のミスでした。
こちらでも説明されています。
- Pythonでランダムな小数・整数を生成するrandom, randrange, randintなど
取得した値が重複しているかどうかチェックすれば重複を避けられますが、取得済みの値を記録する領域とその取得済みの値（リスト）を走査する処理が必要になるため、スマートな実装ではありません。
どうしたか
以下のように力づくで解決しました。NumPyを使うほうが処理時間が短いかもしれません。
import random
import deque
num_clusters = max_lba >> 3
cluster_list = list( range( num_clusters ) )
random.shuffle( cluster_list )
cluster_queue = deque( cluster_list )
# クラスタ（の先頭LBAを3ビット右シフトした値）を取得する処理
cluster = cluster_queue.pop()
要は、全クラスタ（アドレス）を重複せずに格納したリストを作成し、そのリストをシャッフルして順序をランダム化した上でキューを作成し、使うときはそのキューから順番に取り出す、という実装です。
これであれば、最初に作成したリスト(cluster_list)には全クラスタが1つずつしか存在しないので、全クラスタを取り出し終わるまでに同じクラスタが再度出現することはありません。
また、全クラスタ取り出し終えた（＝cluster_queueの要素数がゼロ）後は、またcluster_listをシャッフルしてキューを作ることで前回とは異なる順序でクラスタを取り出すことができます。
この実装の一番大きな課題は、SSDの容量が大きくなればなるほど「全クラスタ（アドレス）を重複せずに格納したリスト」のメモリ使用量が増えることです。
上のコードではリストに入れる要素数を減らしています（max_lbaを3ビット右シフトしている＝1/8にしている）が、それでも1 TBのSSDには4 KB単位のクラスタが244,190,646個（約2億個）あるので、各要素を4バイトで表現したとするとおよそ1 GBのメモリを消費します。さらにcluster_listとcluster_queueの2つあるので倍の2 GB程度必要です。ただ、メモリさえ積んでいるならこの力づくの解決法のほうがシンプルです。
さいごに
今回は、私がSSDのFTLシミュレータを評価する際に躓いた点をまとめました。
なお、SSD（のFTL）のランダムアクセス評価で発生させるコマンドの先頭LBAが「SSD容量分アクセスするまで重複しない」ものである、という仕様（規定）は存在しません。このため毎回ramdon.randrange(min, max)で取り出した値を使用してシミュレーションしても間違いではありません。
特に、SSDの全体的な性能や特徴を時間をかけずに容量の一部を使用して評価する場合などであれば、そこまで気にする必要はない違いです。また使用できるメモリ容量に制約がある場合はこの厳密な方法は選択できないと考えられます。
しかし、FTLの詳細な評価を行う場合、定常状態を作り出した後にそこからさらに大きなサイズ（例：容量の数倍）の書き込みを行うことも多いです。その際は「SSD容量分アクセスするまで重複しない」という制約を課したほうがより厳しい条件となります。このため、この違いを意識する必要があります。
ライセンス表記
この記事はクリエイティブ・コモンズ 表示 - 継承 4.0 国際 ライセンスの下に提供されています。