Note
英語の本家のページは、 PHPを使って説明 説明していますが、このページではPythonと Tornado を使ったチュートリアルに変えてあります。
Bitbucketの リポジトリ に、このチュートリアルのファイル一式が含まれています。 tutorial/retwis/ フォルダを自分の作業フォルダにおいて、 retwis_start.py に、これから説明する内容を追加で実装していってください。なお、実力に自信のある方は、PHPやRubyの参考実装だけを見ながら、 RegisterHandler や、 FollowHandler クラスもPythonに移植してみてください。
また、 @yssk22 氏がnode.js版を実装してくれました。これもリポジトリの中に入っていますので、興味のある方はこちらのファイルの内容に読み替えてください。
この記事では、PythonとRedisを使って、 Twitterのシンプルなクローン の設計と実装を紹介していきます。プログラミングのコミュニティの中には、キー・バリュー・ストアは、ウェブアプリケーションで使うリレーショナルデータベースの代わりには使えない、特殊なデータベースである、と見ている人もいますが、この記事の中で、それは間違いである、ということを証明します。
このTwitterクローンの名前はRetwisといいます。構造的にシンプルで、パフォーマンスも悪くありませんし、少しの手間でN台のWebサーバとM台のRedisサーバを使った分散環境を構築することもできます。ソースコードは ここ で手に入ります。
Note
本家サイトのPHP版のほか、 Ruby(Sinatra)版 もあります。
キー・バリュー・ストアの本質は、キーに対して、値と呼ばれるどんなデータでも格納できるという点にあります。このデータは、保存時に使用した正確なキーを知っている場合にのみ、後からアクセスができます。値の側から検索する方法はありません。例えば、 SET コマンドを使うと、 bar``という値を、 ``foo というキーに格納することができます。
Redisはデータを永続化して保持します。後で「 foo キーに保持されている値はなんですか？」と問い合わせると、Redisは bar と返事を返します。
GET foo => bar
他に、キー・バリュー・ストアで一般的に提供されている操作が、与えられたキーと関連する値を削除する DEL と、「もし存在していなければセットする(SET-if-not-existes)」という操作(Redisでは SETNX)と、与えられたキーに格納された値を自動でインクリメントする INCR です。
SET foo 10
INCR foo => 11
INCR foo => 12
INCR foo => 13
これまでの説明はシンプルですが、 INCR だけは少し特殊です。これを見ると、「なぜ、自分でも簡単に行えそうなこんなものが操作として提供されているのだろう？」と疑問に思うでしょう。この通り、これと同じ操作は簡単に実装できます。
x = GET foo
x = x + 1
SET foo x
この方法でインクリメントしたときに、この値 x に操作を行うクライアントが一つしかない場合は問題なく動作します。2つのコンピュータが同時にこのデータにアクセスしに行った時に何が起きるか見てみましょう。
x = GET foo (xは10)
y = GET foo (yも10)
x = x + 1 (xは11)
y = y + 1 (yも11)
SET foo x (fooは11になった)
SET foo y (fooここでまた11が設定された)
何かおかしなことがおきています！2回インクリメントしたはずですので、10から12になってもいいのに、11です。これは自作の INCR 操作が、 GET / インクリメント / SET とアトミックな操作になっていません。RedisやMemcachedなどの提供する INCR 操作はアトミックになっています。もし提供されていないとすると、取得して、演算して、格納する操作が終わるまでのすべてにわたって、同時アクセスを防ぐように気を配らなければなりません。
Redisと他のキー・バリュー・ストアの大きな違いとなっているのは、Redisでは INCR のように、複雑な問題に対して使えるような操作が数多く提供されているという点です。また、これがRedisを使うと、SQLのデータベースを使わなくても、誰も怒らないようなウェブアプリケーションを書くことができる秘訣です。
このセクションでは、Twitterクローンをこれから作り上げていく上で必要となる、Redisの機能を紹介していきます。まず最初に知るべき事は、Redisの値が、単なる文字列以外にも持つことが可能である、ということです。Redisは値として、 リスト型 と セット型 をサポートしています。 [1] 。また、これらの値を操作するためのアトミックな操作も多数用意しており、同じキーに対して安全に複数回アクセスできます。それではリストについて見て行きましょう。
LPUSH mylist a (mylistは、'a'という一つの要素を持つリスト)
LPUSH mylist b (mylistは'b,a'を保持している)
LPUSH mylist c (mylistは'c,b,a'を保持している)
脚注
| [1] | (訳注) これ以外にも、 ソート済みセット型 、 ハッシュ型 もサポートしていますが、今回は使いません。 |
LPUSH は、「左にプッシュ」という意味です。これは mylist に対して、リストの左側(ヘッドとも呼ぶ)に要素を追加します。もし、 mylist というキーが存在していなかったとすると、Redisは LPUSH の操作の前に自動的に空のリストを作ります。当然予想できると思いますが、 RPUSH という操作もあります。これはリストの右側(テール)に要素を追加します。
この操作はTwitterクローンを作る上でとても便利です。ユーザのステータス(ツイート)の更新は ユーザ名:updates という名前のリストに格納することができます。もちろん、リストからデータや情報を取得してくる操作もあります。 LRANGE はリストの範囲、もしくは全体のデータを返します。
LRANGE mylist 0 1 => c,b
LRANGE はゼロスタートのインデックスで範囲を指定します。最初の要素のインデックスは0で、2番目が1になります。コマンドの引数は、 LRANGE キー 最初のインデックス 最後のインデックス です。最後のインデックスには、負の数値を指定することもできます。この場合、-1はリストの一番最後の要素の意味となります。-2はその前の要素です。そのため、リストの全要素を取得したい場合には次のように書きます。
LRANGE mylist 0 -1 => c,b,a
他の重要な操作としては、リストの長さを返す LLEN と、 LRANGE に似ていますが、リストの指定された範囲以外の要素を削除した上で、制定範囲の値を返す LTRIM があります。 LTRIM は、 mylist から範囲を GET して、新しく残したい範囲を SET する、といった操作をアトミックに行うことができます。このシステムではこの以上の操作しか使いませんが、ぜひRedisのドキュメントを読んで、リストに対する全ての操作を学ぶようにしてください。
リスト以外にも、Redisは セット型 をサポートしています。これは要素をソートしないで格納するコレクションです。セットに対しては、要素の追加と削除、セットのメンバーの中に属しているかどうかのテスト、他のセットとの積集合の計算などができます。もちろん、セットの要素をリスト化したり、要素数を問い合わせることもできます。例を紹介すると、よく分かるでしょう。まず覚えておく操作は、セットに対して値を追加する SADD 、セットに対する要素の削除を行う SREM 、メンバーとして指定された値が格納されているかどうかのテストする SISMEMBER 、積集合を取る SINTER です。これ以外に、セットの要素数を数える SCARD 、セットの全ての要素を返す SMEMBERS という操作があります。
SADD myset a
SADD myset b
SADD myset foo
SADD myset bar
SCARD myset => 4
SMEMBERS myset => bar,a,foo,b
SMEMBERS の返り値は要素を追加した順序になっていないことに注意してください。セットは要素の順序を保持しません [2] 。もし順序を保持したいのであれば、リストを使う方が良いでしょう。セットに対してはリストにはない操作がいくつかサポートされています。
脚注
| [2] | 順序を保持する sortedset もRedisはサポートしています。 |
SADD mynewset b
SADD mynewset foo
SADD mynewset hello
SINTER myset mynewset => foo,b
SINTER はセット間の積集合を算出する操作ですし、2つ以上のセットに対しても処理を行うことができます。4、5セットから10000以上のセットまでの積集合を算出することができます。最後に、 SISMEMBER の動作について見て行きましょう。
SISMEMBER myset foo => 1
SISMEMBER myset notamember => 0
実装に必要なRedisの動作が一通り理解できたので、実装の準備ができました
もしまだダウンロードしていないのであれば、まずはダウンロードしてください。その .tar.gz ファイルの実装は、1つの .py ファイルと、複数のテンプレートで行われています。実装はシンプルです。Redisと通信するのは、redis-pyというライブラリです。このライブラリは＊＊によって書かれており、自由に使えるライセンスになっています。これはプロジェクトには含まれていないので、最新のバージョンを落としてインストールしてください。
もう一つ準備として行うことは、Redisサーバを起動させることです。ソースコードをダウンロードしてきて make コマンドを起動してコンパイルしてください。その後、 ./redis-server コマンドを起動すると、サーバを起動することができます。Redisで遊んだり、実行させる上では設定を行う必要はありません。 [3]
脚注
| [3] | (訳注) Windowsであっても、cygwinを利用するとビルドすることができます。gccとGNU makeをインストールして、cygwinの中から make を実行してください。 |
リレーショナルデータベースを使ってプログラムを作る場合、この段階で、データベースのテーブル構造などを作っていくことになるでしょう。キー・バリュー・ストアでは何を設計すべきでしょうか？ここで必要になるのは、自分たちのオブジェクトを表現するには、どのようなキーを使っていくのか、ということと、このキーは、どのような値を保持しているのか？ということです。
それでは、ユーザに関連する情報から決めていきます。ユーザ情報に関しては、ユーザ名、ユーザID、パスワード、フォローしている人、フォローされている人などの情報が必要となります。最初の疑問は、システム内ではどのようにユーザを識別すべきか、というものです。ユーザ名がユニークであれば、これはとても良いアイディアです。しかし、メモリの消費を低く抑えたいと思っているので、発言やフォロー情報にひもづけて大量に保存されることになるため、ユーザ名はサイズが大きすぎてしまいます。そのため、リレーショナルデータベースと同様に、ユニークなIDをユーザごとに設定していきます。このidを参照することで、ユーザに対する参照が全て行えるようになります。Redisでは、アトミックな INCR 操作があるため、とても簡単に実装することができます。例えば、「antirez」というユーザを作る場合には、つぎのようにします。
INCR global:nextUserId => 1000
SET uid:1000:username antirez
SET uid:1000:password p1pp0
新しいユーザにユニークなIDを設定するのに、このプログラムでは global:nextUserId キーを利用します。ユーザに関するすべてのデータには、このキーを持たせるようにします。これは、キー・バリュー・ストアに関するデザインパターンです。ぜひ覚えておきましょう。フィールドが定義できたら、ユーザを定義する上でもっと必要な要素を見て行きましょう。例えば、ユーザ名からユーザIDが求められると便利でしょう。
SET username:antirez:uid 1000
最初は奇妙に見えると覆いますが、キー・バリュー・ストアでは、キーを使わないとデータにアクセスできません。Redisに、特定の値に関連するキーを返させることはできません。リレーショナルデータベースの言葉を使って語るのであれば、すべてプライマリーキーによってのみアクセスさせることを強要するという新しいパラダイムが、キー・バリュー・ストアの戦略です。
もう一つ、ソースコードを読み込んでおくべき箇所があります。すべてのユーザは、「フォローしている」「フォローされている」ユーザのリストを持っています。Redisはこれにとても良いデータ構造をサポートしています。それは セット型 です。データスキーマに、この２つのフィールドを追加しましょう。
もう一つ重要な点は、ユーザのホームのページにつぶやきを表示する機能です。これは時間順で表示されるべきです。このような用途に最適なデータ構造は リスト型 です。基本的にすべての新しいデータは、ユーザのつぶやき情報を格納するキーに対して、 LPUSH で追加します。また、 LRANGE を使うと、ページネーション(次のページ、などの処理)なども実装できます。なお、この記事では、つぶやき、アップデート、ポストなどは同じ意味に使っています。
ユーザに関して確認しておくべきことがもう少しだけあります。それは認証です。このアプリケーションの中では、シンプルでしっかりとした方法で認証を実装していきます。どのようなサーバに配置してもすぐ動作するようにしたいので、特定のDBやミドルウェアなどに依存するような方法は取るつもりはありません。そのため、ユーザに関する状態についても、すべてRedisサーバに格納させます。認証したユーザについて、ランダムな文字列をクッキーとして持たせます。このキーによって、クライアントのユーザIDを特定します。堅牢なしくみを動作させるために、次の2つのキーを作ります。
SET uid:1000:auth fea5e81ac8ca77622bed1c2132a021f9
SET auth:fea5e81ac8ca77622bed1c2132a021f9 1000
認証を行うために、ユーザが行わなければならないことはわずかです(retwis.LoginHandler)。
実際のコードは次の通りです。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 | class WelcomeHandler(RequestHandler):
def get(self):
self.render("template/welcome.html", register_error=None, login_error=None)
def post(self):
username = self.get_argument("username", None)
password = self.get_argument("password", None)
# you can change host, port, db with keyword parameter
if not username or not password:
self.render("template/welcome.html", register_error=None, login_error=
"You need to enter both username and password to login")
return
redis = Redis()
userid = redis.get("username:%s:id" % username)
if not userid:
self.render("template/welcome.html", register_error=None, login_error=
"Wrong username or password")
return
realpassword = redis.get("uid:%s:password" % userid)
if realpassword != password:
self.render("template/welcome.html", register_error=None, login_error=
"Wrong username or password")
return
authsecret = redis.get("uid:%s:auth" % userid)
self.set_cookie("auth",authsecret, expires_days=365)
self.redirect("/")
|
このコードはユーザがログインを行うたびに実行されます。次に、Tornadoの @authenticated デコレータで、認証されているかどうかの確認を行えるようにしていきます。ログインチェックのロジックを順を追って説明していきます。
コードは次のようになっています。
1 2 3 4 5 6 7 8 9 10 11 12 | class RedisAuthMixin(object):
def get_current_user(self):
authcookie = self.get_cookie("auth", None)
if authcookie:
redis = Redis()
userid = redis.get("auth:%s" % authcookie)
if userid and redis.get("uid:%s:auth" % userid) == authcookie:
return self.__load_user_information(userid, redis)
def __load_user_information(self, userid, redis):
username = redis.get("uid:%s:username" % userid)
return {"id":userid, "name":username}
|
Tornadoの場合、ハンドラクラスの get_current_user メソッドが None 以外の情報を返すと、そのユーザは認証されているとみなされ、 @authenticated を付けるだけで、認証が必要な処理である、ということを明示できます。ハンドラのコード内では、この情報は、 current_user プロパティ経由で取得するようにします(キャッシュされるので、get_current_user()を呼ぶよりも高速です)。このシステムでは大げさですが、ログインチェックと、ログイン情報の抽出は別のメソッドに分けるとコードが見やすくなります。
認証に関して残っているテーマはログアウトです。どのようにしてログアウトを実装すればいいでしょうか？それは簡単です。 uid:ユーザID:auth に設定するランダムな文字列を改変してしまえばいいのです。古い方の auth:<古い認証文字列> というキーを削除し、新しい auth:<新しい認証文字列> を追加します。
Note
ログイン処理では、ただ auth:<ランダム文字列> を見つけた後に、 uid:<ユーザID>:auth に対してダブルチェックを行っています。パスワードを確認する真の認証はその後に行っています。ランダムな文字列は100%確実に判別できるものではありませんが、もしプログラムなどにバグがあったり、プログラムの実行が中断した場合に、同じユーザを指す、 auth:<何か> キーが複数登録されてしまうかもしれません。次に、ログアウトのコードを示します。
1 2 3 4 5 6 7 8 9 10 11 12 | class LogoutHandler(RedisAuthMixin, RequestHandler):
@authenticated
def get(self):
redis = Redis()
userid = self.current_user["id"]
newauthsecret = getrand()
oldauthsecret = redis.get("uid:%s:auth" % userid)
redis.set("uid:%s:auth" % userid, newauthsecret)
redis.set("auth:%s" % newauthsecret, userid)
redis.delete("auth:%s" % oldauthsecret)
self.redirect("/")
|
ポストやツイートとも呼ばれますが、更新に関してはユーザ情報よりもシンプルです。新しいポストをデータベースに登録する場合は、次のようにします。
INCR global:nextPostId => 10343
SET post:10343 "<発言者ID>|<時間>|Retwis楽しいよ!"
この SET の値にあるように、文字列の中に発言者のIDと時間をいれてしまっているため、このサンプルアプリケーション内では追加でこれらの情報を取得してくるのにDBにアクセスする必要はなくなるため、プログラムがコンパクトになります。
ポストを行うと、ポストのIDが得られます。このIDを、発言者をフォローしている人全員に LPUSH します。 PostHandler を見ると、どのように行っているかを見ることができます。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | class PostHandler(RedisAuthMixin, RequestHandler):
@authenticated
def post(self):
# save status
redis = Redis()
userid = self.current_user["id"]
postid = redis.incr("global:nextPostId")
status = self.get_argument("status").replace("\n", " ")
post = "%s|%d|%s" % (userid, int(time()), status)
redis.set("post:%d" % postid, post)
# spread status to all followers
followers = redis.smembers("uid:%s:followers" % userid)
followers.add(userid)
for fid in followers:
redis.lpush("uid:%s:posts" % fid, postid)
redis.lpush("global:timeline", postid)
redis.ltrim("global:timeline", 0, 1000)
self.redirect("/")
|
このクラスの重要な部分は、 for fid in followers というところです。 SMEMBERS を使ってフォローされている全員を取得し、ループの中で uid:フォローしている人のID:posts に対して、 LPUSH を使って格納していきます。
また、ここではすべてのポストを表示したタイムラインも作っています。ここでは、 global:timeline というキーに対して LPUSH を使って格納するだけです。これを見ると、SQLでは、なぜ ORDER BY を使って時間順に文字列をソートしなければならないか不思議に思いませんか？私は思います。
この処理は、 LRANGE の使用方法に関する良いサンプルとなっています。ここでは、ポストされた内容の一部を取り出し、ブラウザにそれを表示していきます。コードはシンプルです。このコードは、複数箇所から参照されるため、クラスとして実装しています。その一部を表示します。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | def show_post(self, id):
posttemplate = """
<div class="post">
<a class="username" href="/profile?u=%s">%s</a>%s<br>
<i>posted %s ago via web</i>
</div>
"""
postdata = self._redis.get("post:%s" % id);
if not postdata:
return False;
userid, time, post = postdata.split("|", 2)
username = self._redis.get("uid:%s:username" % userid)
self._posts.append(posttemplate % (url_escape(username), username, post, self._elapsed(time)))
return True
|
1 2 3 4 5 6 7 8 9 10 11 | def show_user_posts(self, userid, start, count):
if userid == None:
key = "global:timeline"
else:
key = "uid:%s:posts" % userid
posts = self._redis.lrange(key, start, start+count)
for post in posts:
self.show_post(post)
if len(self._posts) == count:
break
self._is_last = (len(self._posts) != count+1)
|
show_post は単純に1つのポストをHTMLに整形する処理です。 show_user_posts は、表示する範囲のポストを取得してきて、 show_post に処理を投げます。
ユーザID 1000(antirez)が、ユーザDI 1001(pippo)をフォローしたい時の処理を実装していきます。ここでは、 SADD を2回呼ぶことで行えます。
SADD uid:1000:following 1001
SADD uid:1001:followers 1000
同じようなパターンは何度も出てくるでしょう。リレーショナルデータベースの流儀では、 following_id と follower_id の両方をフィールドに持つテーブルを1つ作って実装するでしょう。キー・バリュー型のデータベースの場合はこれとは異なり、 1000が1001をフォローしている という情報と、 1001が1000にフォローされている という2つの関係を両方ともセットに追加します。これはコストはかかりますが、データのアクセスもシンプルで、超高速です。また、それぞれのセットが独立して存在しているため、あなたの独自のTwitterクローンでは、 SINTER を使って、誰かのプロフィールを見たときに「共通のフォロワーが34人います」といったことも実現できるでしょう。
FollowHandler クラスを見ると、フォロワーの追加と削除のコードが書かれています。これはとてもシンプルなコードです。
ここまで実装してきたあなたは既に英雄です。どうもありがとうございます。スケーリングについて話を巣る前に、単一のサーバのパフォーマンスをチェックすることが大切です。Retwisはキャッシュの類を使用しなくても、とても高速です。とても遅く、データがロード済みのサーバに対して、apache benchmarkを実行したところ、クライアントを100台並列させ、10万リクエストを投げたところ、ページビューの平均は5ミリ秒ほどでした。数百万人のユーザがいたとしても、1台のLinuxマシンでさばくことができるだろう、ということを意味しています。
そのため、サーバを複数台に増やさなければならないアプリケーションというものは、例えユーザ数が多かったとしてもほとんどないでしょう。しかし、Twitterを想定すると、多くのトラフィックを処理しなければならないでしょう。どのように行えば良いでしょうか？
最初に行うことは、キーのハッシュに従って別のサーバーで処理が行われるように設定することです。これを行うためのアルゴリズムは数多く知られていますが、RedisのRuby版のライブラリは、コンシステントハッシュを実装しています。一般的な方法としては、ハッシュを使ってキーを数値にして、これをサーバ数で割って余りを計算することで、どのサーバを利用するかを決めることができます。
server_id = crc32(キー) % サーバ数
しかし、この方法を使うと、1つサーバを追加しただけで、数多くのキーを移動しなければならないという問題があります。これは、コンシステントハッシュなどの良いハッシュアルゴリズムを使ったとしても、一般的に発生する問題です。
この場合、キーアクセスはキーの空間に分散するのでしょうか？この場合、すべてのユーザデータは複数のサーバの間に振り分けられて保存されます。使用されているキーをまたがる操作はありません。 SINTER のようなものは同じサーバ内で行われるように注意する必要があります。これは、Redisがmemcachedと異なり、特定のハッシュを強制しないからです。) これとは別に、より頻繁にアクセスされるキーもあります。
例えば、新しいメッセージをポストするたびに、この実装では global:nextPostId というキーをインクリメントしています。この問題を修正するにはどうすれば良いのでしょうか？サーバが一つであれば、インクリメントしていけば数多くのキーを生成することができますが、本当に多くのアクセスがなければ、これは過剰な品質です。IDをインクリメントしない、というトリックもあります。ユニークであれば、インクリメントしていく必要もありません。十分に長いランダムな文字列(md5のサイズがあればほぼ)衝突はしないでしょう。水平方向にスケーラブルにしていくための主な問題はこれで回避することができます。
別の問題としては、 global:timeline があります。これの修正方法はありません。複数のサーバに分けるのであれば、データを利用するタイミングで、マージを行って、順番に並び替え、一つのキーを使うようにする必要があります。繰り返しになりますが、相当多くのポストがある場合でも、一つのサーバで処理できます。一般的なハードウェアであっても、Redisは毎秒10万の書き込みを処理できますので、Twitterのようなサービスでも十分対応できると思います。