経緯と問題

DynamoDB で効率よいシャーディングの実施のために、キーの末尾に特定の識別子を付与する方法はベストプラクティスとして公式でも紹介されている。

今回は、このシャーディングを行うためにユーザー固有のID (文字列) を元に識別子を計算したいと考えた。その対策として、以下のようなコードを書いた。

バグありなのでこのコードは利用しないこと！

def primary_key(uid: str) -> str:
    num = hash(uid) % 10
    return f'SampleData.{num:02d}'

hash 関数は Python の組み込み関数であり、整数を返す。
実際にこれでテストをすると、同じ uid の入力に対して、同じ結果を返してくれるため、一見正しそうに見える。

しかし、このプログラムを AWS Lambda 上で動かしたところ、同じ uid を使っているにも関わらず、異なる値が出力されることがあった。 例えば、primary_key('ABC') に対して、SampleData.00 と返すこともあれば、SampleData.02 を返すこともある、ということである。

原因

例えば以下で説明されている。 Python3.2 以前は実は同じ値が返っていたようだが、Python3.3 以降はデフォルトでは実行環境が変わると異なる値が返るようになっている。

Python のデータモデルのドキュメントに以下の様な記載がある。

注釈デフォルトでは、文字列とバイト列の hash() 値は予測不可能なランダム値で "ソルト" されます。 ハッシュ値は単独の Python プロセス内では定数であり続けますが、Python を繰り返し起動する毎に、予測できなくなります。
この目的は、慎重に選ばれた入力で辞書挿入の最悪性能 O(n^2) 計算量を悪用することで引き起こされるサービス妨害 (denial-of-service, DoS) に対する保護です。詳細は http://www.ocert.org/advisories/ocert-2011-003.html を参照してください。

ハッシュ値の変更は、集合のイテレーション順序に影響します。Python はこの順序付けを保証していません (そして通常 32-bit と 64-bit の間でも異なります)。

バージョン 3.3 で変更: ハッシュのランダム化がデフォルトで有効になりました。

引用 (一部強調) - https://docs.python.org/ja/3/reference/datamodel.html#object.__hash__

AWS Lambda では実行系（コンテナ）の個数は自動的に起動／停止されて管理されるため、hash の結果は環境ごとに異なり、結果として同一の値を返さないという問題が発生していた。

対処方法

hash ではなく hashlib を使って入力が同じなら同じ出力を得るようにする。
以下は異なる Python の対話環境を立ち上げて処理した一例だが、hashlib を使う場合は同一の整数が得られており、組み込みの hash 関数を用いた場合は異なる値が得られていることが分かる。

$ python
>>> import hashlib
>>> uid = 'ABC'
>>> int(hashlib.sha256(uid.encode()).hexdigest(), 16)
82243227265268364450164513578198692919354401419942992332018465930427597709176
>>> hash(uid)
-6783415564974188218

$ python
>>> import hashlib
>>> uid = 'ABC'
>>> int(hashlib.sha256(uid.encode()).hexdigest(), 16)
82243227265268364450164513578198692919354401419942992332018465930427597709176
>>> hash(uid)
6230289585255038598

テスト用のハッシュ算出には sha256 を用いたが、DynamoDB で用いる場合には簡単な計算で良いと書いてあるため、MD5 でも十分だとは思う。

修正版

import hashlib
def primary_key(uid: str) -> str:
    num = int(hashlib.md5(uid.encode()).hexdigest(), 16) % 10
    return f'SampleData.{num:02d}'

Pythonの組み込みhash関数を使ってバグを作った話

経緯と問題

原因

対処方法