Hagiwara Takayukiタイムライン処理を軽量化できるアルゴリズム思いついたので置いておきます。
ユーザーごとに購読先の情報をcounting bloom filterのハッシュとして保存しておいて、投稿側のハッシュとマッチさせるのが基本。これでフォロワー全員分を保存する必要がなくなる。
bloom filterのハッシュはidとあわせても非常に軽い(20バイト程度)ので、最新の投稿や接続中のユーザーの投稿をメモリ上で持っておいてここでマッチさせることで少ないメモリ消費で高速化が可能
固定式のskipgraphとしてメンバーのハッシュ和を検索対象として持つノードを保存しておけば過去投稿についてもやはり高速に取得できる
All GNU social JP content and data are available under the