1000万ユーザに耐えるサーバを作ってみた

開発環境は次の通りです。

• Node 16.14
• Express 4.17.3
• DynamoDB 2012-08-10

機能要件は次の通りです。

• ツイート機能
• ツイートに対してコメント機能
• フォロー機能
• タイムライン機能

導入

Facebook、Amazon、Youtubeのような数億人のユーザを抱えるサービスでは大量のトラフィックを捌く必要があります。大量のトラフィックを捌くためのアプローチとして一般的に使われるのはスケールアップではなくスケールアウトです。スケールアップは性能の高い機器を使うためにコストが高いです。また、1つのサーバで運用するためにパフォーマンスの限界が存在します。

スケールアウトについて考えます。アプリケーションは大きく3つの層に分けることができます。

• クライアント層
• サーバ層
• データベース層

大量のトラフィックを捌く際に、負荷がかかるのはサーバ層とデータベース層です。サーバ層はデータを処理するのみで保存はしません。そのため、スケールアウトさせることは容易です。

一方、データベース層はスケールアウトによりデータが分散すると、整合性と可用性を保つのが難しくなります。どのデータをどのノードに保存するかを決めるロジックも必要です。ノードの数を増減するときはデータの再配置が必要です。これらの機能ははRDBにはないので、NoSQLを使います。

スケールアウトをサポートしているデータベースの代表的なものとして、BigTable、HBase、DynamoDB、Cassandraなどがあります。

今回、作成するのはSNSのAPIサーバであるため、整合性より可用性が重要です。そのため、DynamoDBを使います。

DynamoDBとは

DynamoDBはKey-Value型のデータベースです。テーブルを作成することができ、各テーブルにはアイテムが保存されます。各アイテムはキーと値を持ちます。

アイテムのキーにはパーティションキーとソートキーを指定することができます。パーティションキーはDynamoDBクラスタの中からノードを決定するために使われます。ソートキーはテーブルのインデックスのようなもので、ソートに使われます。

アイテムの値には属性と値のペアを複数保存することができます。属性はアイテムごとに異なるものを持つことができます。

DynamoDBのクエリは限定的で、基本的にパーティションキーとソートキーのみでアイテムを絞り込みます。それ以外の属性を使いクエリをする場合、全てのアイテムを調べる必要があるのでアイテム数の増加に伴い遅くなります。

他の属性をパーティションキーとして扱いたい場合はGSI(Global Secondaly Index)を使います。他の属性をソートキーとして扱いた場合はLSI(Local Secndary Index)を使います。

データベース設計

DynamoDBのデータベース設計はRDBとは異なります。RDBは柔軟にクエリが可能であるため、データへのアクセスパターンを考慮せずに、最初に正規化されたテーブルを設計します。一方、DynamoDBはクエリが限定的であるために、初めにデータへのアクセスパターンを決めて、それに基づいてテーブル設計を行います。具体的には次の流れで進めていきます。

1. モデリング
2. ユースケースリスト作成
3. テーブル設計
4. クエリ定義作成

モデリング

ER図は次のようになります。

タイムラインではユーザがフォローしているユーザのツイートの一覧を表示します。SNSではタイムラインの表示速度はユーザビリティへの影響が大きいです。より早くタイムラインを表示できるような設計を考えます。

タイムラインのRead Heavy / Write Light

正規化されたテーブル設計の場合は、ツイート時のデータ書き込みにはTweetsテーブルのみにデータを書き込むため負荷が軽いです。一方、タイムラインにおけるデータ読み込みは負荷が重いです。タイムラインを読み込む際の大きな流れとしては次のようになります。

1. フォローしているユーザのID一覧を取得
2. フォローしている各ユーザの投稿を取得
3. 取得した投稿をマージ
4. マージした投稿をソートし直す

タイムライン取得のSQLイメージは次のようになります。

SELECT
  *
FROM 
  tweets
WHERE
  userId IN (
    SELECT followeeId FROM follows WHERE followerId = 'user id'
  )
ORDER BY
  postDate DESC

このやり方ではフォロー数が多くなればなるほど、タイムラインの読み込み負荷が高くなります。Read Heavy / Write Light な手法と言えます。

タイムラインのRead Light / Write Heavy

Read Light / Write Heavyな手法を考えてみます。Timelineテーブルを作成して、タイムラインを読み込みたい場合はタイムラインテーブルにのみ問い合わせるのみにします。一方、ユーザがツイートをしたら、そのユーザのフォロワーのタイムラインにツイートを書き込むようにします。

タイムライン取得のSQLイメージは次のようになります。

SELECT
  *
FROM
  timelines
WHERE
  userId = 'user id'
ORDER BY
  tweetPostDate

今回はこのRead Light / Write Heavyな方法を採用します。

ユースケースリスト作成

機能要件を元にデータのユースケースリストを作成して、データへのアクセス方法を整理します。

テーブルとインデックス設計

ユースケースリストをもとにテーブルとインデックス設計をしていきます。DynamoDBはクエリが限定的ですが、GSIオーバローディングという方法を使うと柔軟なクエリが可能になります。

import { config } from "@src/config";
import { dateToUnixTime } from "./time";

const workerIDBits = 10;
const sequenceBits = 12;

// Use snowflake
// See: https://blog.twitter.com/engineering/en_us/a/2010/announcing-snowflake
export class IdGenerator {
  private workerId: number;
  private lastGenerateAt: number;
  private sequence: number;

  constructor(workerId?: number) {
    this.workerId = config.snowflakeWorkerId;
    this.lastGenerateAt = dateToUnixTime(new Date());
    this.sequence = 0;
  }
  generate(): number {
    const now = dateToUnixTime(new Date());

    if (now == this.lastGenerateAt) {
      this.sequence++;
    } else {
      this.sequence = 0;
    }
    this.lastGenerateAt = now;

    // The bit operators ('<<' and '|' ) can handle numbers within
    // the range of signed 32 bit integer.
    return (
      now * 2 ** (workerIDBits + sequenceBits) +
      this.workerId * 2 ** sequenceBits +
      this.sequence
    );
  }
}