Technical Specification

フィルタリングシステム仕様書

Xのホームタイムラインにおいて、ユーザーに表示される投稿の品質と関連性を確保するためのフィルタリングシステムの詳細仕様です。

1. フィルタリングシステム概要

1.1 目的

フィルタリングシステムは、Xのホームタイムラインにおいて、ユーザーに表示される投稿の品質と関連性を確保するための重要なコンポーネントです。 候補となる投稿群から不適切、重複、または不要な投稿を効率的に除外し、最終的にユーザーに最適なコンテンツのみを配信します。

1.2 設計原則

早期除外(Early Filtering)

不要な投稿を可能な限り早い段階で除外し、後続処理の計算コストを削減

段階的フィルタリング

Pre-Scoring FiltersとPost-Selection Filtersの2段階構成

効率性

HashSetやBloom Filterを活用した高速な重複検出

ユーザープライバシー尊重

ブロック・ミュート設定の完全な反映

1.3 アーキテクチャ

フィルタリングパイプライン全体像
候補投稿(Candidates)

Pre-Scoring Filters(10種類)

DropDuplicatesCoreDataHydrationAgeFilter...
Scoring(スコアリング)
Selection(選択)

Post-Selection Filters(2種類)

VFFilterDedupConversation
最終結果(Final Results)

2. Pre-Scoring Filters

スコアリング処理の前に適用されるフィルター群です。計算コストの高いスコアリング処理の前に明らかに不要な投稿を除外することで、システム全体の効率を向上させます。

1. DropDuplicatesFilter

同一のtweet_idを持つ重複した投稿候補を除外。複数のソース(Phoenix、Thunder等)から取得された候補に同じ投稿が含まれる場合に発生。

ファイル:home-mixer/filters/drop_duplicates_filter.rs
計算量:O(n)
判定条件:tweet_idが既出の場合に除外

2. CoreDataHydrationFilter

投稿の基本メタデータ(コアデータ)が正しくハイドレート(取得・設定)されているかを検証。不完全なデータを持つ投稿を除外。

ファイル:home-mixer/filters/core_data_hydration_filter.rs
計算量:O(n)
判定条件:author_id != 0 かつ tweet_textが空でない

3. AgeFilter

指定された期間より古い投稿を除外。タイムラインの鮮度を維持するために使用。Snowflake IDから時刻を抽出して判定。

ファイル:home-mixer/filters/age_filter.rs
計算量:O(n)
判定条件:Snowflake IDからの時刻 <= MAX_POST_AGE

4. SelfTweetFilter

閲覧ユーザー自身が投稿したツイートをタイムラインから除外。プロフィールページで確認できるため除外。

ファイル:home-mixer/filters/self_tweet_filter.rs
計算量:O(n)
判定条件:candidate.author_id != query.user_id

5. RetweetDeduplicationFilter

同一の投稿が複数のリツイートとして候補に含まれる場合、最初に出現したもののみを保持。

ファイル:home-mixer/filters/retweet_deduplication_filter.rs
計算量:O(n)
判定条件:元ツイートIDで重複チェック

6. IneligibleSubscriptionFilter

有料サブスクリプション専用コンテンツに対して、ユーザーがサブスクライブしていない場合に除外。

ファイル:home-mixer/filters/ineligible_subscription_filter.rs
計算量:O(n)
判定条件:サブスクライブ済みまたは通常投稿

7. PreviouslySeenPostsFilter

ユーザーが既に閲覧した投稿を除外。Bloom Filterと明示的な既読リストの両方を使用して効率的に判定。

ファイル:home-mixer/filters/previously_seen_posts_filter.rs
計算量:O(n * m)
判定条件:seen_idsまたはBloom Filterに含まれる場合

8. PreviouslyServedPostsFilter

直前のタイムラインリクエストで既に配信された投稿を除外。無限スクロール時の重複を防止。

ファイル:home-mixer/filters/previously_served_posts_filter.rs
計算量:O(n * m)
判定条件:is_bottom_request時にserved_idsに含まれる場合

9. MutedKeywordFilter

ユーザーが設定したミュートキーワードを含む投稿を除外。トークナイザーを使用して正確なキーワードマッチング。

ファイル:home-mixer/filters/muted_keyword_filter.rs
計算量:O(n * k)
判定条件:ミュートキーワードにマッチする場合

10. AuthorSocialgraphFilter

閲覧ユーザーがブロックまたはミュートしているユーザーの投稿を除外。

ファイル:home-mixer/filters/author_socialgraph_filter.rs
計算量:O(n)
判定条件:ブロック/ミュートユーザーリストに含まれる場合

Snowflake IDについて

XのツイートIDはSnowflake形式を採用しており、ID自体に作成時刻が埋め込まれています。

64-bit Snowflake ID 構造
1bit
未使用
41bit
時刻
10bit
DC
12bit
シーケンス
  • - 41ビットの時刻部分からミリ秒単位のタイムスタンプを抽出
  • - 基準時刻(Twitter Epoch: 2010-11-04T01:42:54.657Z)からの経過時間

Bloom Filterについて

Bloom Filterは確率的データ構造で、メモリ効率が良く大量のIDを少ないメモリで管理可能です。

判定結果意味
may_contain() = false確実に含まれていない
may_contain() = true含まれている可能性がある(偽陽性あり)
偽陽性率は設定可能(通常1%以下)。クライアントから送信され、サーバー側で検証に使用されます。

3. Post-Selection Filters

スコアリングと選択(TopK選出)の後に適用されるフィルター群です。選択された上位候補に対してのみ実行されるため、より計算コストの高い処理を行うことができます。

3.1 VFFilter(Visibility Filtering)

違反コンテンツフィルター

Visibility Filteringサービスの結果に基づいて、ポリシー違反コンテンツを除外します。

Safety Level対象説明
TimelineHomeIn-Network投稿フォロー中ユーザーの投稿向け
TimelineHomeRecommendationsOut-of-Network投稿おすすめ投稿向け(より厳格)

除外されるコンテンツ:

削除済み投稿
スパム
暴力的コンテンツ
ヘイトスピーチ
センシティブコンテンツ
ポリシー違反

Post-Selectionで実行される理由

VFサービス呼び出しは高コストのため、選択後の少数候補のみを対象としています。 In-NetworkとOut-of-Networkで異なるSafety Levelが適用されます。

3.2 DedupConversationFilter

会話スレッド重複排除フィルター

同一会話スレッド内の複数の投稿が選択された場合、最もスコアの高い投稿のみを保持します。

会話スレッドの構造
会話の起点(Conversation Root): ID = 100
返信1: ID = 101, ancestors = [100]
返信1-1: ID = 103, ancestors = [100, 101]
返信2: ID = 102, ancestors = [100]

全ての投稿の conversation_id は 100(最小の祖先ID)となります

4. フィルタリングパイプラインの実行順序

4.1 完全な実行順序

パイプライン実行フロー
[候補取得]

Pre-Scoring Filters(順序固定)

  1. 1DropDuplicatesFilter- 重複排除(最優先)
  2. 2CoreDataHydrationFilter- メタデータ検証
  3. 3AgeFilter- 古い投稿除外
  4. 4SelfTweetFilter- 自分の投稿除外
  5. 5RetweetDeduplicationFilter- リツイート重複排除
  6. 6IneligibleSubscriptionFilter- サブスクリプション制限
  7. 7PreviouslySeenPostsFilter- 既読投稿除外
  8. 8PreviouslyServedPostsFilter- 既配信投稿除外
  9. 9MutedKeywordFilter- ミュートキーワード
  10. 10AuthorSocialgraphFilter- ブロック/ミュートユーザー

[Scoring - スコアリング]

PhoenixScorer, WeightedScorer, AuthorDiversityScorer, OONScorer

[Selection - TopK選択]

Post-Selection Filters(順序固定)

  1. 1VFFilter- 違反コンテンツ除外
  2. 2DedupConversationFilter- 会話スレッド重複排除
[最終結果]

4.2 実行順序の設計原則

順序フィルター理由
1DropDuplicates重複を最初に除外し、後続処理を効率化
2CoreDataHydration不完全データを早期排除
3Ageシンプルな判定で大量除外可能
4SelfTweetシンプルな判定
5RetweetDeduplication重複系フィルターの後半
6IneligibleSubscriptionユーザー設定に基づくフィルター開始
7PreviouslySeenBloom Filter使用(やや複雑)
8PreviouslyServed条件付きフィルター
9MutedKeywordテキスト処理(計算コスト高め)
10AuthorSocialgraphユーザー設定フィルターの最後

4.3 フィルターの有効化条件

フィルター有効化条件デフォルト
PreviouslyServedPostsFilteris_bottom_request == true無効
MutedKeywordFiltermuted_keywordsが空でない有効(空なら即リターン)
AuthorSocialgraphFilterブロック/ミュートリストが空でない有効(空なら即リターン)

5. データ構造

5.1 PostCandidate(投稿候補)

フィルターが処理する主要なデータ構造です。

PostCandidate 構造体rust
pub struct PostCandidate {
    pub tweet_id: i64,                          // ツイートID
    pub author_id: u64,                         // 投稿者ID
    pub tweet_text: String,                     // 投稿テキスト
    pub in_reply_to_tweet_id: Option<u64>,      // 返信先ツイートID
    pub retweeted_tweet_id: Option<u64>,        // リツイート元ツイートID
    pub retweeted_user_id: Option<u64>,         // リツイート元ユーザーID
    pub score: Option<f64>,                     // 最終スコア
    pub in_network: Option<bool>,               // フォロー中ユーザーの投稿か
    pub ancestors: Vec<u64>,                    // 会話の祖先ツイートIDリスト
    pub visibility_reason: Option<FilteredReason>, // VF結果
    pub subscription_author_id: Option<u64>,    // サブスク専用投稿の著者ID
    // ... その他のフィールド
}

5.2 ScoredPostsQuery(クエリ)

フィルターに渡されるコンテキスト情報です。

ScoredPostsQuery 構造体rust
pub struct ScoredPostsQuery {
    pub user_id: i64,                           // 閲覧ユーザーID
    pub seen_ids: Vec<i64>,                     // 既読投稿IDリスト
    pub served_ids: Vec<i64>,                   // 既配信投稿IDリスト
    pub is_bottom_request: bool,                // 下方向スクロールか
    pub bloom_filter_entries: Vec<BloomFilterEntry>, // Bloom Filter
    pub user_features: UserFeatures,            // ユーザー設定
    // ... その他のフィールド
}

5.3 UserFeatures(ユーザー設定)

UserFeatures 構造体rust
pub struct UserFeatures {
    pub muted_keywords: Vec<String>,            // ミュートキーワード
    pub blocked_user_ids: Vec<i64>,             // ブロックユーザーID
    pub muted_user_ids: Vec<i64>,               // ミュートユーザーID
    pub followed_user_ids: Vec<i64>,            // フォローユーザーID
    pub subscribed_user_ids: Vec<i64>,          // サブスクライブ中ユーザーID
}

5.4 FilterResult(フィルター結果)

FilterResult 構造体rust
pub struct FilterResult<C> {
    pub kept: Vec<C>,      // 保持された候補
    pub removed: Vec<C>,   // 除外された候補
}

6. パフォーマンス考慮事項

6.1 計算量まとめ

フィルター時間計算量空間計算量
DropDuplicatesFilterO(n)O(n)
CoreDataHydrationFilterO(n)O(1)
AgeFilterO(n)O(1)
SelfTweetFilterO(n)O(1)
RetweetDeduplicationFilterO(n)O(n)
IneligibleSubscriptionFilterO(n)O(m)
PreviouslySeenPostsFilterO(n * b)O(b)
PreviouslyServedPostsFilterO(n * s)O(1)
MutedKeywordFilterO(n * k * t)O(k)
AuthorSocialgraphFilterO(n)O(1)
VFFilterO(n)O(1)
DedupConversationFilterO(n)O(c)

凡例:

  • n: 候補数
  • m: サブスクライブユーザー数
  • b: Bloom Filter数
  • s: served_ids数
  • k: ミュートキーワード数
  • t: 平均トークン数
  • c: 会話数

6.2 最適化テクニック

早期リターン

空のリストに対する処理をスキップ

HashSet活用

O(1)ルックアップのためのHashSet使用

Bloom Filter

メモリ効率の良い確率的データ構造

Arc共有

トークナイザー等の重いオブジェクトの共有

パーティション最適化

partitionメソッドによる効率的な分割

関連ドキュメント

X レコメンドアルゴリズム - オープンソース ドキュメント