lasciva blog

開発して得た知見やwebビジネスのストック

Spotifyのバックエンドの記事のまとめ

Spotifyの公式ブログや、登壇した動画、記事を中心に読んで面白かったものを簡単にまとめた。全部は読めてないが、バックエンドのものを中心に読んだ。

engineering.atspotify.com

モチベーションとしては、「なぜSpotifyは遅延なくスムーズに再生できるのか」を知りたかったが、探したところ肝心な部分は記載されてなさそうだった。
今回は記載してないが、エンジニアが増えてもスケールするための文化や、そのためのインフラや設計などについての記事も多く、他の企業よりも成長に注力している印象を受けた。

Creative usernames and Spotify account hijacking

engineering.atspotify.com

Usernameにunicodeをサポートしたことで、アカウントがハイジャックされるバグが発生した。

Usernameは大文字小文字などを区別しないようにした方が紛らわしくなくなるので、望ましい。しかし、それだけでは不十分で、Ω(ギリシャ文字)とΩ(電気の単位)もややこしいので、区別すべき。

これは、XMPPのnodeprep canonicalization メソッドがサポートしているのでそれが使える。

このメソッドがすべてのunicode文字列をサポートできておらず、この関数に冪等性が保証されておらず、複数回実行する必要があった。

最終的には2回実行した結果と1回実行した結果が異なる場合は、許可しないことで解決した。

How to shuffle songs?

engineering.atspotify.com

Fisher–Yates shuffleというアルゴリズムを使って、完全にランダムなシャッフルな実装を行っていた。しかし、ユーザの問い合わせから、ギャンブラーの誤謬などのように人間がランダムに感じにくいということに気づいた。

ユーザが期待するランダムは、アーティストなどのグループごとに全体の中で均等な間隔でシャッフルされることである。例えば、100曲あるプレイリストの中であるアーティストの曲が3曲があるとすると、1-33, 34-66, 67-100のそれぞれに1回ずつ再生され、かつそれぞれの間で適度な隔たりがあるように(例えば1, 66,67などは避ける)ことが期待されている。 f:id:hacking15dog:20200720115115p:plain

そこで、上図のように各アーティストごとにFisher-Yates shuffleでランダムにシャッフルして、それぞれの間隔を決めたあとに、合成するようなアルゴリズムにした。アーティスト間で1番目の順番が重複しないように、各アーティストごとにoffsetを設定した。

Fisher–Yates shuffle

有限な集合からランダムな順列を生成するアルゴリズム

1-Nの数字を記載して、それをランダムにピックアップして並べることで実現される。

これの改良版であるAlgorithm Pは、以下のようにランダム化されてない部分(A)とされた部分(B)に分けて、Aの最後尾の要素と、Aの中からランダムにピックアップしたものを入れ替え、Bの先頭に加えることで、ランダムな順列を生成する。計算量がO(N)になる。

array = (1..8).to_a
(array.length - 1).downto(0) do |i|
  j = rand(i)
  array[i], array[j] = array[j], array[i]
end

Floyd–Steinberg dithering

画像処理でよく使われるアルゴリズムで、例えば最大256色までしか使えないGIF形式への変換の際に使われている。

f:id:hacking15dog:20200720115141p:plain

Switching user database on a running system

engineering.atspotify.com

ダウンタイムなしで、PostgreからCassandraにどのように切り替えたかについての記事。

Postgreを使っていたが、readのスケーラビリティに限界が来た。更に、writeはLondonのデータセンターにあるmasterのみで行っていたので、ネットワークの問題が発生するとSPOFとなる問題を抱えていた。

そこで、Cassandraにダウンタイムなしで切り替えることに。

完全に切り替える前にはdarkloadとしてCassandraを稼働させておくことで、バグの発見等を行った。

実際に切り替える際には、users DBにアクセスするのはRESTful HTTPリクエストでラップすることで、切り替えなどのロジックを知るサービスを1つにした。そして切り替えの際にはconfigを更新して、PostgreとCassandraが並行でmasterとして稼働するのを避けるために全サービスインスタンスを同時にリスタートさせた。

ELS: latency based load balancer, part 1

engineering.atspotify.com

LBのロジックはいくつかある。ラウンドロビンは、重いリクエストが集中したインスタンスがあった場合にレイテンシーが悪化してしまう。Join the Shortest Queueでは、ラウンドロビンの問題が解決できるが、エラーを高速に返すインスタンスが存在した場合などに、全体のエラー率が高くなってしまう。

Expected Latency Selector (ELS)

これらの問題を解決するために、ELSを開発した。これは確率的なLBで、各マシンが重さを持ち、その比重になるようにリクエストを振り分ける。ELSは以下のような項目を計測する。

  • 各マシンの成功した場合のレイテンシーと成功率
  • LBと各マシン間での突出したリクエスト数
  • エラーのレイテンシー(遅いエラーレスポンスよりも速い方が望ましい)

Relative circuit breaker

失敗の割合がインスタンス全体の平均より悪い場合のみに、サーキットブレーカーを発動させるように設定できるように改善させた。全体のエラー率が高い場合は発動させないなど。

Pros and cons of ELS

LIMITATIONS

ADVANTAGES

  • 素晴らしパフォーマンス: JSQと比べて、エラーがない場合はほとんど同じ、マシンがダウンしている場合は傑出したベンチマーク
  • ローカルで計測できるメトリクスのみ使用するため、コードがシンプルでエラーを抑えられる
  • Relative circuit breakerによって、パフォーマンスが平均に比べ著しく悪いときのみ発動できる
  • ローカルで計測できるメトリクスのみを使用するため、100以上あるSpotifyのバックエンドサービスの修正が不要。
  • 半年運用してきたので、この技術の信頼性が高い

Backend-driven native UIs

atscaleconference.com

www.slideshare.net

APIにViewModelのような情報を返させることで、UI変更を簡単に行えるようにした。 f:id:hacking15dog:20200720121028p:plain

The Brilliance of Spotify Internal APIs to Mitigate Payments | Nordic APIs

nordicapis.com

決済のAPI設計に関する記事。
グローバルで展開すると、世界中の通貨や、地域特有の決済方法に対応しないといけない。

そこで、拡張しやすいように、決済のバックエンドをCheckoutとBillingのAPIで切り分けた。

f:id:hacking15dog:20200720113747p:plain

The Checkout API

  • バイスごとに料金が異なったり、国によって税金が異なったりする
  • 適切なフォームを表示して、オファーコードの有無や、クライアントのデバイス情報、国の情報を収集する
  • バックエンドが次の操作をクライアントに対して指示する

The Billing API

  • バックエンドとPayment Providersの橋渡しになるAPI
  • 16ものPayment Providersごとに異なるビジネスロジックを隠蔽する
  • 16 different Payment Providers
  • モニタリングも行いやすくなる

4 Reasons Why API Design is Critical to Subscription Services

  • 支払いプラットフォームから独立したAPIを提供できる
  • 内部でのインテグレーション: 会計プラットフォームやセキュリティ、モニタリングなどの連携が行いやすくなる
  • 成長のためのスケーリング: 新しいビジネスロジックとの互換性をサポートしやすくなる
  • カスタマイズの可能性

Scalable User Privacy

engineering.atspotify.com

ユーザの個人情報をセキュアにかつスケーラブルに扱うために、どのような設計にしたかという記事。

Why we encrypt

各ユーザごとに暗号キーを使っている。そうすることで、データが漏洩しても無意味なものにできる。

また、中央集約的に各ユーザのデータのライフサイクルをコントロールできる。データの削除する際には、暗号キーを破棄するだけで、データが参照できなくなるため、削除漏れを防ぐことができる。

データ保存する際には暗号化させるというシンプルなルールだけで、各チームは設計を比較的自由に行い、プライバシーポリシーの標準を守ることができる。

考えていた他の案

  1. 一つのサービスが他のすべてのサービスのユーザ情報を削除するAPIを呼ぶ方法
    • サービス数が多いと、すべてのシステムで正常に処理されたかどうかの保証が難しい
    • We want to keep our datasets immutable, because scanning through petabytes of data every time we want to delete a few rows for a single user is too expensive.
  2. 一つのDBのみに保存し、サービスはそのDBのキーとなるトークンを保持する
    • 様々なサービスの要件を満たすのが難しい
    • アクセスパターンが異なるので、キャッシュもできない

Introducing Padlock: a global key-management system

暗号キーを管理するPadlockという内部のサービスを開発した。元となるキーを返すのではなく、派生したキーを返す。こうすることで、元となるキー自体はPadlockのみに留め、他のサービスに公開する必要がなくなる。

また、カテゴリごとに各ユーザのキーを別のものにしている。

Building at Spotify scale

  • 直線的にスケールさせ、1ユニットあたり100万lookup/秒を実現させた
  • レイテンシー
    • 多くのサービスがどのリクエストでも必要なため、オーバーヘッドを小さく抑えなければならない
    • SLOは99パーセンタイルのレイテンシーが15ms以下。実際には通常時は5ms程度の
  • 高可用性
    • ダウンすると、個人情報を扱うサービスもダウンしてしまうので重要
    • SLOでは99.95%に設定し、99.99%に上げられるかもしれない

Cassandraとmemcacheで構成。他のDBはまだテストできる状態でなかったので、移行するのもあり。

速くエラーレスポンスを返すために、リトライは行わない。その代わり、クライアントがリトライを行うか判断する。

Running Padlock with high reliability

高可用性を担保するために、いくつか工夫している。

  1. リリースフロー
    • まずステージング環境で動作確認
    • 承認を得た後に、3ステップ(1つのカナリーマシン、1つのリージョン、全グローバル)で本番環境
  2. プロビジョニング
    • 全リージョンに配置することで、リージョン全体がダウンしても他のリージョンにリダイレクトさせる
  3. 2つのデプロイメントグループを用意した
    • リスキーな差分のあるデプロイのリスクを軽減できる
    • 片方のmemcacheがダウンしても、もう一つの方が稼働し続ける

また、フェイルオーバーを確実に行えるようにするため、人為的にサービスやDB、データセンター全体をダウンさせることで、機能するか確認を行っている。

Testing of Microservices

engineering.atspotify.com

Why do we write tests?

テストが必要な理由は、以下。

  • コードがすべきことをしている自信を与える
  • 速く正確で信用でき、予測できるフィードバックを提供する
  • テストを書くときに見落とされがちなメンテナンスを容易にする

Microservices test strategy

f:id:hacking15dog:20200720120235p:plain

Integrationテストにフォーカスすべき。

Integrated Tests

Integrated Testsとは、「別のシステムの正確さに基づいて合格または不合格になるテスト」のことである。例えば、共有のテスト環境で実行しなければならなかったり、ローカル環境で他のサービスを立ち上げたりしなければならなかったりするとその兆候がある。

Integration Tests

DBやサービスを立ち上げ、APIコールをしてそのレスポンスを検証するようなテスト。実装の詳細は含まない。

実行に数msから数sかかるため、時間とのトレードオフだが、開発やメンテナンスのことを考えるとそれに見合う。また、実装が複雑な場合は、エラーになった際に実装の詳細を確認しなければならないかもしれない。

Final Thoughts

  • コードがすべきことをしている自信を与える
    • inputであるリクエストと、outputであるレスポンスを検証しているので、内部実装に関係なく結果がわかる
  • 速く正確で信用でき、予測できるフィードバックを提供する
    • フィードバックは十分速いが、テストが失敗した場合はスタックトレースを見ないといけないかもしれない
  • テストを書くときに見落とされがちなメンテナンスを容易にする
    • エッジからテストしているので、破壊していないと自信を持ってメンテナンスとボーイスカウトを行うことができる。本当に速く行うことができる

さらに、エッジからテストをしているのでサービスのIFのコントラクトを破っていないことを自信を深めることができる。

このようにマイクロサービスを分離されたコンポーネントとしてテストしているので、その意味ではマイクロサービスが新しいUnitとなり、それがマイクロサービスの実装の詳細のUnitテストを避けている理由である。