Twitterのキャッシュを支えるRedis

https://www.youtube.com/watch?v=rP9EKvWt0zo

1 comment | 2 points | by WazanovaNews 3年弱前 edited


Jshiike 3年弱前 edited | ▲upvoteする | link

TwitterのYao Yuが、大規模サービスのキャッシュにおいてRedisを活用する取組みについて紹介しています。

1) Redisを採用している理由

  • キャッシュだけで、ストレージとしては利用していない。
  • 主なところでは、Twitterのタイムラインで利用している。ホーム画面であれ、ユーザ画面であれ、タイムラインはTweetのインデックスなので、key/valueストア型のRedisを利用するケースとして最適。
  • 以前はmemcachedを使っていたが、問題になったのは、タイムラインでおきるread/writeは、(ユーザが閲覧している範囲に追加反映するということなので)比較的小さいが、オブジェクト自体、つまりタイムライン全体はユーザによっては、数百件、数千件となり、規模が大きいということ。この大きなサイズだとデータベースを直接見に行きたくはない(ので、キャッシュから取得しようとするが)。read-modify-writeをしようとすると、小さなタスクのために大きなオブジェクトを送らなければいけないというジレンマになる。これだと、コストがかかりすぎる。ネットワークをボトルネックにしたくない。ほとんどのキャッシュサービスはギガリンク経由だと、シンプルなread/writeだと100K/秒以上を処理できるが、オブジェクトの平均サイズが1Kとなると、ボトルネックはネットワークになる。
  • 次の問題としては、フレキシブルなスキーマを採用していて、対象のオブジェクトがもつ属性が存在するときもしないときもあるとする。各属性に別々のkeyを用意して、全てに対してリクエストを送らなくてはいけないが、都合よくキャッシュにあるかどうかはわからない。また別の事例としては、時系列で取得していくメトリックス。どのメトリックスデータも同じ名称で、タイムスタンプの違いだけ。それをキャッシュに保存したら、長い共通のプレフィックスのデータを何度も繰り返し保存する作業をすることになる。それらのケースの場合、長い共通のプレフィックスで管理できると、スペースをもっと有効に活用できるようになる。
  • インメモリkey/valueストアは、かなりCPUの負担が軽いことがわかった。ベンチマーク測定したところ、1%のCPU時間で、小さめのkey/valueであれば、1000件/秒以上のリクエストを処理できる。使用されているキャッシュメモリクラスタは、常にCPUをそれほどは使っていない。つまり、シンプルなkey/value構造にするとサーバサイドに大きく余裕ができるということ。よって、Redisは最適。

2) データ構造

ハイブリッドリスト

  • タイムラインはTweet IDのリスト、つまりintegerのリスト。比較的小さい。
  • Redisには、ziplistとlinkedlistという二種類のデータ構造がある。
    • ziplist: キーごとのオーバーヘッドが小さい。スペース効率がいい。
    • linkedlist: フレキシブル。挿入、ノードの移動が負担少なくできる。key当たり、少なくとも二つのpointerを利用するので、integerだけの保管にはオーバーヘッドが大きすぎ。
  • タイムラインは、ziplistのスタックにしている。Redisがziplistとして保持できる最大値がタイムラインの長さになってる。
  • データ構造のデザインとしては今ひとつ。
    • 何件のtweetを保持できるかを、ローレベルのコンポーネントに頼っている。どうやってRedisで設定するか?
    • ziplistを更新する際、tweetの削除とかexpandは、かなりメモリコストのかかる操作。
    • ほとんどのユーザはたくさんtweetするわけではないので、ユーザページのタイムラインは小さくても、ホームのタイムラインは、フォローしているセレブのtweetで大きなサイズになってるかもしれない。それを更新してwrite操作をする際は、小さなタイムラインデータを大量に退避させることになる。つまり、write操作が大きく遅延に影響するかも。
  • そこで、zip listのメモリ効率という利点を活かしながら、もっと予想しやすいメモリ割当を実現するため、ziplistのlinkedlistとするハイブリットリスト形式を採用した。
  • このハイブリットリストはデータセンタ単位では、
    • 割当てられるヒープが40TB
    • 最大3000万QPS
    • 6,000+インスタンス

B-Tree

  • B-Tree(ソートのできる一般的なセカンダリkeyサポート)は、一つのデータ構造で二つのことをやろうとしている。
    • スペース効率のために階層クッキーがほしい。階層クッキーのポイントルックアップをする。
    • 範囲クエリをしたい。階層クッキーで任意の順で範囲クエリをして、結果を取得する。
  • 現状のRedisの場合、セカンダリkeyもしくはフィールドがあればハッシュマップを使う。ソートしたものがほしければ、範囲クエリするが、ソートしたセットの限界はスコア。二倍に翻訳される。つまり、任意のセカンドkeyや名前は、ソーティングには使えない。一方、ハッシュマップの限界は、ハッシュマップはリニアルックアップなので、たくさんのセカンダリkeyやフィールドを一つのプライマリkeyに持つのはよろしくない。
  • B-Treeならそれらの欠点をカバーできる。一つのデータ構造にしたかった。B-TreeのBST実装を参考に、ポイントルックアップとうまく範囲クエリできる仕組みをつくった。
    • 驚くほどルックアップ性能がよい。コードがシンプル。
    • 一方、メモリの最適化はしていないので、B-Treeがメモリ消費の元凶になる可能性はある。
  • Redis B-Treeを、データセンタ単位では、

    • リザーブされているメモリが最大65TB(メモリの最適化をしていない影響で値が大きくなっている。)
    • 900万+QPS
    • 最大4,000インスタンス

3) クラスタ管理

  • Redisがもっと急速に普及しない理由がクラスタ管理。
  • Redisは、データ構造サーバなのでユースケースはかなりwriteに偏ってる。memcachedはimmutableデータのために使われ、その場合は一度writeすればよいので、それほどデータ構造は問題にならない。一方、Redisは頻繁に更新したいから利用される。Redisは、同じオペレーションを何度実行しても結果が変わらないidemponent ではないので、ネットワーク障害、リトライしたり、一時オフラインになったりがおきると、データが壊れることがある。Redisクラスタへのwriteオペレーションは難しい。
  • Redisは、中央で管理された単一のクラスタビューが向いているのではないかと思う。memcachedではクライアントクラスタの実装は、整合性ハッシュなど色々ある。Redisはクラスタマネジャーで管理するのがよいのでは。グローバルビューを操って、その上ですごくよいサービス、例えば、どのシャードがダウンしてるか検知するとか、ダウンしたシャード上のオペレーションを再実行するとか、シャードが復活すればステートを戻すとかができるのでは。そうするとRedisのデータが欠損しない。データが空になっていればまだしも、Redisにおいてデータが一部欠損したかどうか検知ほうはかなり大変。
  • Twemproxyは名前からわかるように、twemcacheだけを利用する予定だったが、Redisサポートを追加してみると、よい成果がでた。
  • proxy style routingについては、Redisクラスタにおける、クラスタ管理、レプリケーション、シャードの復旧などを、タイムラインの機能向け & 一般向けに提供しようという二つのプロジェクトがある。
  • proxy style routingについて、まずオプションは、
    • サーバがお互いに通信し、どういうクラスタにするか合意する。
    • プロキシ
    • クライアントサイドでのクラスタ管理
  • その中で、proxy style routingを試みた理由について。まず、サーバサイドにとって、キャッシュサービスは比較的スループットが高い。ハイパフォーマンスを狙うなら、早いパス(データパス)は遅いパス(コントロールパス)からは分けたほうがよいと思う。クラスタ管理の視点からすると、サーバに色々やらせると、コードが複雑になるだけではなく、ステートフルの問題。つまり、クラスタでバグの修正、新機能の導入する度に、データを絡めてステートフルなサービスを再起動することになる。キャッシュクラスタを管理をしてる人は皆、それが大変だとわかっている。それが、サーバでやるというアプローチを採らなかった理由。サーバは、シンプルで、なるべく早くしたい。
  • なぜクライアントでやらないか?Twitter内で現在、キャッシュクラスタサービスを利用しているのは100プロジェクトくらいある。クライアントでやると、その変更が100個のプロジェクトの各担当者に影響を影響与える。変更にどれだけ時間がかかるかわからない、クイックにイタレーションして、バグも修正しようとすると、クライアント側でやるのはほとんど不可能。
  • サーバとクライアントの間にレイヤを追加すると心配なポイントは、ネットワークで遅延するのではないかということだった。一般的に、ネットワークへの悪影響は遅延の原因になると思うが、実際にプロファイリングしてみたら、取り越し苦労だとわかった。Twitterのシステム環境からすると、ネットワークへの悪影響はでない。 主にJava環境で、Fanagleを利用して通信している。クライアントサイドで、キャッシュサーバまでの遅延を測ると、カーネルまでのラウンドトリップ全体において、遅延は500マイクロ秒以下、つまり0.5ミリ秒以下。一方、実際にリクエストを発行するFanagleのトップにまで行くと、遅延は10ミリ秒近く。つまり、JVMの外側での遅延は、全体の10%にもなってない。
  • プロキシの採用は、障害ポイントが追加されたことになる?
    • プロキシレイヤのデータパスはそれほど悪くない。クライアントはどのプロキシと通信してるかは気にしない。プロキシがタイムアウトでだめになれば、次のプロキシに移るだけ。プロキシレベルではシャーディングは発生しない。全部ステートレス。プロキシを追加していけば、スループット増は簡単。トレードオフは、コストの問題。以前はバックエンドサーバだけでリクエストに応えていたが、今やそれらのリソースをプロキシに割当て、ただフォワードしているだけ。コストが心配で、プロキシの障害はそれほど気にならない。理由は、自分たちでクラスタ管理 / 全部のシャーディングをやっていて、クラスタのビューはプロキシの外側で対処しているから。もし、プロキシ同士がお互いにネゴシエーションしなくてはいけない仕組みだと悲劇。自分のグローバルビューをもつようになるが、グローバルビューが最適なビューだとは限らない。もし、サービスのオブザーバがダウンしたらどうする?リスクを緩和する手法はあって、キャッシュされたビューを保持しておいて、クラスタリーダーやマネジャーがダウンしたケースに対処する。多数のノード同士を直接ハンドリングするより、外側のビューから対応する方が比較的簡単。
  • プロキシとサーバ間には継続的な接続を設定していると思うが、それで何故遅延に影響しないのか?
    • 100Kのオープンコネクションあるが、それで大丈夫。なるべくオープンにしておいて、今のところ悪影響はない。
  • Redisノードを追加したら、どのようにプロキシサーバはデータをデリゲートし始めるのか?
    • シャーディングに抽象化レイヤをもっている。キーが物理的なマシンにマッピングされてないと考えてみるとよい。抽象化されたアドレススペースにマッピングされている。それから、アドレススペースからノードにマッピングする。シャードを追加するとき、クラスタのリーダが全ての抽象化シャードから物理ノードに新しいマップを生成し、キースペースもそれにあわせて移動。新しくアサインされたシャードに対応できるように、バックエンドはステートを修正。それまでに、プロキシも同じ内容でアップデートされている。あまり詳細は話せないが、準備ステージがあって、プロキシが確認のうえ、リクエストをフォワードできるようになっている。
  • ノードがダウンしたら、データをどう読込む?
    • キャッシュクラスタにはデータ補充の責任は持たせていない。誰であれ、キャッシュを利用している者が、整合性を保てるストレージから、不足しているkeyを取得してくることになっている。シャードがダウンしたとわかれば、シャードと紐づいたアドレススペースの移動はしている。復帰した時点で物理サーバの内容をクリアしているので、問題のでるデータは残らない。中心の役割をもつビューの存在が本当に重要なのは、クラスタのステートをキープするのが簡単に理解できるから。
  • TwitterのテクノロジースタックはJVMベースのJava/Scalaライブラリだけど、最近は、プロキシをC++で実装してかなりパフォーマンス改善に成功している。

4) データについての学び

  • 経験からすると、キャッシュ遅延の90%はクライアント側の設定誤り、大量のkeyをリクエストしたり、同じkeyを何度もリクエストしたりというクライアント側の問題であった。「証拠をだせ。どのキーが問題で、どのシャードのどのトラフィックが問題か示せ。」とよく言われたが、障害の切り分けが難しい。SOAアーキテクチャはデバッグが自動的にやりやすくなるわけではない。可視性を高める工夫は別途しないといけない。
  • 全てのコマンドのログを取ることに。高スループットシステムで全てのコマンドのロギングは可能。100kQPSでもできた。
    • ロックを使わないこと。
    • ワーカーをブロックしないこと。ディスクwriteを待たせると、サーバリクエストはひどいことになる。
  • 100 byte/ログあると、データは10MB/秒/ボックス。これを送信することになったらかなり帯域を占める。そこで、事前処理をボックス側でしている。かなりサイズの小さいサマリーを作成することで、ネットワークへの悪影響を抑えている。
  • Stormで集めて、保管して、可視化。エンジニアに対して、上位keyのリスト、トラフィック/秒、トラフィックパターンなどを提示できるようになった。オペレーション側も障害の調査が楽になった。

5) 個人的な学びと見解

  • ユーザ & クラスタが増えると、予想しやすい仕組みが必須になってくる。
  • 「テールの遅延」という法則は正しい。一つのシャードが遅くなると全体が遅くなる。
  • しっかりとした設定が大切。Mesosの採用でコンテナの利用が進んでいるが、スケジューラがCPU/メモリ/ディスク使用量を設定 & モニタリングするようになる。その点でいくと、Redisはexternal fragmentation、つまり、同じデータ量でもっとメモリ使うようになる。
  • コンテナ環境に移行するともっと精緻な設定が必要になる。現在では、バッファーを大きくとることでリスクヘッジしている。リソースの無駄使い。一方で、大きなクラスタは予想を超える規模の事故が起きるケースもあり、リスクは大きい。障害時にサービスがスムーズにでグレードダウン、例えば、設定値をこえれば、超過したリクエストのみを受け付けられるようにしたいが、実際はそうなっていないサービスが多い。もっと精緻な設定ができ、かつスムーズにグレードダウンできるサービスにする必要がある。
  • 遅延の調査で、ベンチマーク調査してみると、クライアントが50ms、サーバが5ms。パーセントがマッチせず、説明つかないケース。こういうことがないように、自分のサービスを自信もって調査できる理解度をしておかないと。
  • MesosでtwemcacheとRedis使ってるが、Mesonのリソース監視では、従前の時間でどれだけCPU使ってるかチェックしている。キャッシュのようなリアルタイム処理やCPU pinningでは、その時間CPUが使われていることがネックになる。リソースをCPUからうまく分離しない限り、タイムシェアリングは問題になる。Mesosは使ってるが、これらの特定のジョブからは外している。
  • ネットワークやディスクの限界を考慮すると、ディスクに保管する前、ネットワークに送るまでに、どうデータを事前計算できるかというのは大事。
  • RedisにおけるLuaスクリプトは、ポテンシャルはあるが、まだ本番に利用できる状態ではない。ブラウザでフラッシュを実行するみたいなもの。他人のコードなので遅い。皆を道連れにする。deployed scriptの方がよいのでは。Lua scriptがコンフィグレーションファイルに入れられるようになれば、もっとコントロールできる。
  • Redisは抽象的なレベルでは要件を満たしているので、Stormよりも優れた高パフォーマンスストリーミング処理のソリューションになれる可能性があるのではないか。
  • Redisへのwish listは、メモリ管理 / Deployable (Lua) script / マルチスレッド。マルチスレッドは大変だから対応してないのはわかるけど、これができればクラスタ管理が相当楽になる。

#twitter #redis


ワザノバTop200アクセスランキング


Back