サーバー負荷を減らすための簡易的クーポンコード発行とチェック機構のつくり方
nowork_python_codegenerate
スポンサーリンク

Pythonを使ってランダムでユニークなコードを生成する方法

ハッシュ値を使用して、意味のあるコードを自動生成する

ヒーラー
DBの検索件数が増えれば増えるほど、負荷がかかってパフォーマンスに影響するぞ

世の中のWebサービスの中には、抽選応募や割引クーポンのように、ユーザー獲得を狙ったり、オフラインとオンラインを結びつけたり、マーケティングの施策がいくつかあります。

  • 本の付録に特典コードが付いており、購入者のみがWeb診断テストを受けることができる
  • オンラインショッピングで買い物をすると、次回使える割引クーポンがメールで送られる
  • 商品のラベルやレシートに抽選IDが付いており、Webからプレゼントの抽選応募ができる

はじめに

運営側の立場からすると、上記のようなクーポンコードやアクティベーションのためのアクティベートコードなど、ユニークでランダムな文字列を使って管理することがあると思います。

C6nwEPaQ

例えば上記のような文字列ですね。
このような文字列リストを生成したいとなった場合、ランダムに文字を繋ぎ合わせて、重複のない文字列を発行するプログラムを組むことで実現できるでしょう。
また、Webサイトでも、オンラインで生成できるジェネレーターがいくつかありますので、そのようなツールやサービスを活用すれば、簡単にコードリストを手に入れることができるでしょう。

例えば、数字とアルファベットの大文字小文字を組み合わせて、8文字のユニークな文字列を20件生成したいと設定すれば、すぐに発行することができます。

ジェネレーター

これらのコードをシステムのDBに登録して、照らし合わせるようなプログラムを作成することで、クーポンの使用やアクティベーションを制御することができると思います。

課題

シンプルに考えれば前述のような仕組みで実施可能です。
しかし、このコードの件数が増えれば増えるほど、DBを検索することの負荷が大きくなることは想像できると思います。

インデックスなどDB側での解決方法もいくつか考えられますが、そもそもコードの件数だけ影響が出ることを見直したくなります。

そこで少しでもサーバー負担を軽減させるための以下ちょっとしたアイデアです。

解決案

コードリストはランダムでユニークな文字列である必要があるとして、比較する側を固定の文字列にできれば、負荷の問題は解決します。
もちろん、前述のようなコードの使い道だと、使用したコードは次に使えないように制御する必要があるため、DBアクセスは必ず発生します。しかし、(例えば不正な連続的なアタックなどの対策として)1次チェックのような使い方には有効なのではないかということです。

そこで注目するのがハッシュ値です。
ハッシュ値とは、元になるデータから一定の計算手順により求められた固定長の値をいいます。ハッシュ値はその性質から暗号や認証、デジタル署名などに応用されています。ダイジェスト値とも呼ばれる場合もあります。
WebサービスやWebアプリでは、パスワードをハッシュ化して保持するような使い方で馴染みがあるかもしれません。

ハッシュ値を算出する仕組み(ハッシュ関数)には、MD5SHA-1SHA-256など様々な標準規格があります。

以下、MD5というハッシュ関数でハッシュ値を算出した例です。

「password」という文字列をMD5で算出した場合、以下のようになります。

5f4dcc3b5aa765d61d8327deb882cf99

これに対し、1文字足しただけの「passwords」という文字列をMD5で算出した場合、以下のようになります。

48cccca3bab2ad18832233ee8dff1b0b

ここで分かるのは、たった1文字足しただけでも、ハッシュ値は大きく変わります。そしてどのような入力でも出力の文字数は固定であるということです。
MD5の場合は32文字の16進表記(ビット長: 128)です。

またハッシュ値は、原則として元のデータに復元できることができない一方向です。

尚、MD5の場合、2^128(2の128乗)の組み合わせがあり、10の38乗ほどで、単位でいうと「澗(かん)」という辺りのあまり馴染みのない単位に当たります。
一意性(ユニーク)の保証はないものの、ほとんどユニークな値として考えられるほどの桁といえます。

このMD5の32文字では、コードとしては長すぎるため、ちょうどよい文字数のハッシュ関数を探したいと思います。そこで、CRC32というものがあります。

CRC32

8文字(16進表記)のビット長32bitのハッシュ値を生成できるハッシュ関数です。
もちろんビット長が短い分、一意性も弱くなるのですが、あくまで簡易チェックのような補助的な使用ではよいのではないでしょうか。

そこでこう考えます。
「ハッシュ化すると固定の文字列になるランダムな文字列を必要数分作ってツール化する」

ツール概要

  1. 任意の文字列から代表ハッシュ値を生成する
  2. ランダム(かつユニーク)な文字列を生成する
  3. 代表ハッシュ値と同じになる文字列をピックアップする
  4. 必要数分になるまで2〜3を繰り返す

しかしながら、ビット長の少ないCRC32であっても、理論上、2^32(2の32乗)のおよそ43億とおりに1つの重複が出る計算なので、ツールとしてもあまり現実的ではありません。(やってみてから気付きました)
実際に試しましたが、1億の文字列を作っても、ハッシュ値はひとつも重複しませんでした。
(そして10分くらいかかりました)

そこで、更に半分の16進表記4文字(ビット長16bit)のハッシュ値を採用することにしました。
すると、100万件のランダム文字列から、15〜20件程度のコードリストを生成することができました。

理論上からも15件〜16件程度になるはずですね。
100万 / 2^16 = 15.25...

そのPythonコードは以下のとおりです。

import sys
import random
import string
import zlib

# ランダム文字列生成 (8文字)
def generateRandomString():
	randlst = [random.choice(string.ascii_letters + string.digits) for i in range(8)]
	return ''.join(randlst)

# ランダム文字列リスト生成 (100万件)
def generateRandomStrings():
	randlst = []
	for i in range(1000000):
		randlst.append(generateRandomString())
	return randlst

# ハッシュ値の一致するコードリスト生成
def generateHashs(password, count, seed):
	source = hex(zlib.crc32(password, 0) & 0xffffffff)[2:6]
	print('src:' + source)
	randomlist = generateRandomStrings()
	list = []
	for i, random in enumerate(randomlist):
		hash = zlib.crc32(random, 1) & 0xffffffff
		s = hex(hash)[2:6]
		if source == s:
			#print("[" + str(i) + "] " + random + ":" + s)
			list.append(random)
	return list

if __name__ == '__main__':
    args = sys.argv
    if len(args) > 1:
		hashlist = generateHashs(args[1], 0, "")
		if len(hashlist) == 0:
			print("nothing...")
		for hash in hashlist:
			print(hash)
    else:
        print('Need arguments')

これを実行すると、以下のように、8桁のコードリストを手に入れることができました。

% python generate_hash.py naturalmind
src:c589
wi0rpQJ9
KS3PCmlz
gt10VW8p
yCb5B0L6
vS4Pt7xN
Gzdszicq
wFcNnaT2
BQCaRSDi
ZqEPiJ5Q
OjbAk5a4
V007gklP
PWohfJJO
9gBmjHv2
GpeDVsfo
YAFAJ3MC
WOQ5eL6g

解説

% python generate_hash.py naturalmind

上記の引数で渡している「naturalmind」がキーワードです。
これをCRC32でハッシュ化すると「c589d519」となります。
そのうち先頭の4文字の「c589」を代表値として採用します。(src:c589と出力しています)

そしてgenerateHashsの中で、ランダムな8文字の文字列を100万件生成しています。
それらに対し、代表値と同様CRC32でハッシュ化し、先頭の4文字を代表値と比較します。
一致した元の文字列をリストに格納して、最後に出力しています。(今回は16件)

ちなみに、このコードではユニークかどうかをチェックしていないので、更に一意性のチェックが必要でしょう。

また、generateHashs関数の引数に、countとseedがありますが使用していません。
将来的に、必要件数をcountに入れて、必要件数分に至るまで生成し続けるコードを想定したものです。
また、seedはよりセキュアにするために、代表値をpasswordとseedの組み合わせにすることを想定したものです。

システムとしては、コードを使用するときのプログラム上で、1次チェックとして入力されたコードのハッシュ値と、代表値である先頭の4文字の「c589」と比較すればよいことになります。

完全なものではありませんが、参考になれば幸いです。

さいごに

今回のハッシュ値の使い方はあくまで簡易的なものです。
一意性もセキュリティも全く保たれたものではありません。
しかし、コード発行を工夫することで、ある程度サーバー負担を軽減することもできます。

CRC32のハッシュ値は、このようなクーポンコードの類以外にも、長い文字列(例えばメールアドレス)の検索が必要な場合に、補助インデックスに使うなどの活用もできるようです。


スポンサーリンク

Twitterでフォローしよう

おすすめの記事