Haber akışı (news feed)

Problem

"Twitter, Instagram ya da LinkedIn benzeri bir sosyal ağ için ana sayfa akışını tasarla. Kullanıcı takip ettiği kişilerin gönderilerini görür; yeni gönderiler takipçilerin akışına kısa sürede düşmelidir. Akış sayfalanabilir ve sıralanabilir olmalı."

Bu sorunun kalbi tek bir karardır: bir gönderi yazılırken mi takipçilerin akışına dağıtılacak (fan-out on write), yoksa akış okunurken mi takip edilen kişilerin gönderilerinden toplanacak (fan-out on read)? Mülakatçı bu kararı sayılarla vermeni, iki uçta da çıkan problemi (yazma patlaması ve okuma maliyeti) görmeni ve 50 milyon takipçili bir hesabın ("celebrity problem") karışık bir model gerektirdiğini bulmanı bekler. Martin Kleppmann'ın DDIA kitabının ilk bölümünde Twitter'ın ana sayfa zaman çizelgesi tam da bu trade-off'un örneği olarak anlatılır.

Netleştirme soruları ve varsayımlar

Kapsam dışı: arama, öneri ("tanıyor olabileceğin kişiler"), reklam yerleştirme, bildirimler, mesajlaşma.

Kapasite tahmini

Okuma:
  200M DAU x 10 akış açma          = 2 milyar akış okuması/gün
  2.000.000.000 / 86.400          ≈ 23.000 /s ortalama, tepe (x3) ≈ 70.000 /s
  Her okuma 20 gönderilik sayfa   -> tepede ~1,4 milyon gönderi hidrasyonu /s (cache'ten)

Yazma:
  50M gönderi/gün                 ≈ 580 /s ortalama, tepe ≈ 1.700 /s

Fan-out on write maliyeti:
  gönderi atanların ortalama takipçisi 300 varsayımıyla
  50M x 300 = 15 milyar timeline eklemesi/gün ≈ 174.000 /s ortalama, tepe ≈ 520.000 /s

Dev hesap:
  50M takipçili bir hesabın tek gönderisi = 50M ekleme
  fan-out kapasitesi 500.000 ekleme/s ise -> 100 saniye, ve bu süre boyunca diğer gönderiler bekler

Timeline cache (kullanıcı başına son 500 gönderi id'si), Redis 7.0'da ölçüldü:
  sorted set (500 eleman, skiplist kodlaması) ≈ 57 KB/kullanıcı -> 200M x 57 KB ≈ 11,4 TB
  list (500 id, quicklist)                    ≈ 5,2 KB/kullanıcı -> 200M x 5,2 KB ≈ 1,05 TB

Gönderi depolama:
  50M x ~1 KB (metin + meta, medya hariç) ≈ 50 GB/gün ≈ 18 TB/yıl

Bu hesap mülakatın yönünü belirler:

1. Okuma yazmanın yaklaşık 40 katı (23.000 akış okuması / 580 gönderi). Okumayı ucuzlatan her şey değerlidir; bu, fan-out on write'ı destekler.
2. Fan-out on write, yazmayı 300 kat çoğaltır ve dev hesaplarda tek bir gönderi dakikalar süren bir iş haline gelir. Saf push modeli bu yüzden yetmez.
3. Veri yapısı seçimi bellek faturasını 10 kat değiştirir. Timeline'ı sorted set yerine kompakt bir listede tutmak 11 TB ile 1 TB arasındaki farktır.

API

POST /api/v1/posts
Idempotency-Key: ...
{ "text": "...", "mediaIds": ["m_123"] }
-> 201 { "postId": "1849203948123451392", "createdAt": "..." }

GET /api/v1/feed?limit=20&cursor=1849203948123451392
-> 200 { "items": [ { "postId": "...", "author": {...}, "text": "...", "media": [...],
                      "likeCount": 1204, "likedByMe": false } ],
         "nextCursor": "1849203801111111111" }

DELETE /api/v1/posts/{postId}
POST   /api/v1/users/{userId}/follow
DELETE /api/v1/users/{userId}/follow

• Cursor tabanlı sayfalama. OFFSET ile sayfalama, kullanıcı sayfayı kaydırırken yeni gönderiler geldiğinde aynı gönderiyi iki kez ya da hiç göstermemeye yol açar. Cursor, son görülen gönderinin id'sidir; zamana göre sıralı (Snowflake benzeri) id'ler bunu doğal kılar.
• Akış cevabı hidrate edilmiş gönderiler içerir (yazar adı, avatar, beğeni sayısı); istemci 20 gönderi için 20 ayrı istek atmaz.

Veri modeli

-- Gönderiler: yazar bazında, zamana göre sıralı (Cassandra / CQL)
CREATE TABLE posts_by_author (
    author_id  bigint,
    post_id    bigint,        -- Snowflake benzeri, zamana göre sıralı
    text       text,
    media_ids  list<text>,
    status     text,          -- ACTIVE, DELETED
    PRIMARY KEY ((author_id), post_id)
) WITH CLUSTERING ORDER BY (post_id DESC);

-- Gönderiyi id ile okumak için (hidrasyon)
CREATE TABLE posts_by_id (
    post_id    bigint PRIMARY KEY,
    author_id  bigint,
    text       text,
    media_ids  list<text>,
    status     text
);

-- Sosyal graf: iki yönde de sorgulanır
CREATE TABLE followers (followee_id bigint, follower_id bigint, created_at timestamp,
                        PRIMARY KEY ((followee_id), follower_id));
CREATE TABLE following (follower_id bigint, followee_id bigint, created_at timestamp,
                        PRIMARY KEY ((follower_id), followee_id));

• Timeline cache (Redis): tl:{userId} → en yeni başta olacak şekilde gönderi id'lerinin listesi, en fazla 500 eleman (LPUSH + LTRIM). Sorted set'e göre yaklaşık 10 kat az bellek; bedeli, araya sıralı ekleme yapılamaması (ekleme her zaman başa). Gönderi id'leri zamana göre artan olduğu için bu kabul edilebilir; yine de farklı yazarların fan-out'u paralel işlendiğinden liste sadece yaklaşık sıralıdır, okuma tarafı adayları id'ye göre yeniden sıralar.
• Gönderi cache'i: post:{postId} → gönderi gövdesi; hidrasyon MGET ile toplu yapılır.
• Sayaçlar: Beğeni ve yorum sayıları ayrı bir sayaç servisinde; sıcak gönderilerde sayaç tek satırda değil, parçalara bölünmüş (sharded counter) tutulur ve periyodik toplanır.
• Partition çarpıklığı: followers tablosunda dev bir hesabın partition'ı 50 milyon satır olur. Bu partition zaman veya hash ile alt kovalara bölünür ((followee_id, bucket)), aksi halde tek bir node'u ısıtır ve partition boyutu sınırlarını zorlar.

Yüksek seviye tasarım

flowchart LR
    U[İstemci] --> GW[API gateway]
    GW --> PS[Gönderi servisi]
    GW --> FS[Akış servisi]
    PS --> PDB[(Gönderi deposu)]
    PS --> PC[(Gönderi cache'i)]
    PS -->|PostCreated| K[(Kafka)]
    K --> FO[Fan-out worker'ları]
    FO --> GS[(Sosyal graf)]
    FO --> TC[(Timeline cache)]
    FS --> TC
    FS --> CEL[Dev hesap gönderileri cache'i]
    FS --> PC
    FS --> CNT[Sayaç servisi]
    FS --> RK[Sıralama servisi]
    MEDIA[Medya servisi] --> CDN[CDN]
    U --> CDN

Yazma yolu: Gönderi servisi gönderiyi depoya ve cache'e yazar, outbox üzerinden PostCreated event'i yayınlar ve kullanıcıya hemen 201 döner. Fan-out worker'ları event'i tüketir, yazarın takipçilerini sayfalar halinde okur ve her takipçinin timeline listesinin başına gönderi id'sini ekler.

Okuma yolu: Akış servisi kullanıcının timeline listesinden cursor'dan sonraki id'leri alır, takip ettiği dev hesapların son gönderileriyle birleştirir, silinmiş/engellenmiş olanları ayıklar, gönderileri ve sayaçları toplu okuyarak hidrate eder, sıralama uygular ve sayfayı döner.

Derinlemesine

Fan-out on write, fan-out on read ve karışık model

Okuma yazmanın 40 katı olduğu için varsayılan model push'tur. Ama iki istisna vardır:

1. Dev hesaplar: Takipçi sayısı bir eşiğin (ör. 100.000) üstündeyse gönderi fan-out edilmez. Bu hesapların son gönderileri ayrı bir "dev hesap gönderileri" cache'inde tutulur ve okuma anında, kullanıcının takip ettiği dev hesapların listesiyle birleştirilir. Ortalama bir kullanıcı birkaç ila birkaç düzine dev hesap takip ettiği için okuma tarafındaki ek maliyet sınırlıdır.
2. Pasif kullanıcılar: Son 30 gündür giriş yapmamış takipçilere fan-out yapılmaz. Bu kullanıcı geri döndüğünde timeline'ı pull modeliyle bir kez yeniden kurulur (takip ettiklerinin son gönderilerinden) ve sonra push moduna döner.

Bu karışık modelde okuma yolu şöyle görünür:

feed(user, cursor):
  ids_push   = timeline_cache.range(user, after=cursor, limit=60)
  celebs     = following_celebrities(user)                    # cache'li, küçük liste
  ids_pull   = merge( celebrity_posts_cache.range(c, after=cursor, limit=20) for c in celebs )
  candidates = merge_by_post_id_desc(ids_push, ids_pull)
  candidates = filter(candidates, deleted, blocked, muted)
  page       = rank_or_take(candidates, 20)
  return hydrate(page), next_cursor(page)

limit=60 gibi fazladan aday çekmek, filtreleme ve sıralama sonrası 20 gönderi kalmasını garanti etmek içindir.

Fan-out'un işletilmesi

• Kafka partition anahtarı authorId: Aynı yazarın gönderileri sırayla fan-out edilir. Dev hesaplar zaten fan-out dışında olduğu için tek bir partition'ın ısınması sınırlanır.
• Takipçi listesini sayfalı okumak: 80.000 takipçili bir yazar için takipçiler 1.000'lik sayfalar halinde okunur ve her sayfa ayrı bir alt iş (Kafka mesajı) olur; iş paralel worker'lara yayılır ve bir worker çökerse sadece o sayfa tekrar işlenir.
• Pipelining: 1.000 takipçinin timeline'ına yazmak Redis'e 1.000 LPUSH + LTRIM demektir; bunlar pipeline'lanır ve hash tag olmadan farklı node'lara dağılır.
• Idempotency: Aynı event tekrar işlenirse aynı id ikinci kez listeye eklenebilir. Okuma tarafında id bazında tekilleştirme yapmak, yazma tarafında "listede var mı" kontrolünden ucuzdur.
• Öncelik: Fan-out kuyruğu geride kalırsa yeni gönderiler takipçilere geç düşer. Lag metriği ve otomatik ölçekleme; aşırı durumda pasif kullanıcılara fan-out tamamen durdurulur (degradation).

Timeline cache'in ömrü ve yeniden kurulması

• Timeline listesi en fazla 500 id tutar; daha eski sayfalar istenirse (nadir) pull modeliyle depodan üretilir.
• Redis bir timeline'ı kaybederse (eviction, node kaybı) akış servisi pull modeliyle yeniden kurar ve cache'e yazar. Yani timeline cache türetilmiş veridir; doğruluk kaynağı gönderi deposu ve sosyal graftır. Bu, Redis'te kalıcılığın şart olmamasını sağlar ama toplu bir kayıp sonrası "yeniden kurma fırtınası" riskini doğurur: aynı anda milyonlarca kullanıcının timeline'ı pull ile kurulmaya çalışılır. Önlem: yeniden kurmayı kullanıcı başına tekil (single-flight) yapmak ve bir eşik üstünde geçici olarak sadece dev hesap + takip edilen ilk N kişiyle kısmi akış göstermek.
• Bellek: 200 milyon kullanıcı x 5,2 KB ≈ 1 TB. Pasif kullanıcıların timeline'ı tutulmadığında (ör. aktif 120 milyon) bu ≈ 630 GB'a iner; 64 GB'lık node'larda replikalarla birlikte birkaç düzine node.

Read-your-writes: kendi gönderini hemen görmek

Fan-out asenkron olduğu için kullanıcı gönderi atıp hemen akışını yenilediğinde gönderisini göremeyebilir. İki çözüm: (1) gönderi servisi yazarın kendi timeline'ına senkron ekleme yapar; (2) akış servisi okuma sırasında kullanıcının son birkaç dakikadaki kendi gönderilerini birleştirir. İkincisi fan-out hattına bağımlılığı tamamen kaldırır.

Silme, düzenleme, takipten çıkma ve engelleme

Silinen bir gönderiyi 50 milyon timeline'dan çıkarmak, onu eklemek kadar pahalıdır. Bunun yerine okuma anında filtreleme yapılır: hidrasyon sırasında gönderinin status alanı DELETED ise atlanır. Gönderi cache'i silmede hemen güncellenir (commit sonrası invalidation). Düzenleme de aynıdır: timeline'da sadece id durur, içerik hidrasyonda güncel okunur.

Takipten çıkma ve engelleme de aynı mantıkla okuma anında filtrelenir (kullanıcının takip/engel listesi cache'lidir), arka planda ise bir temizlik işi timeline'dan ilgili id'leri asenkron temizler.

Sıralama (ranked feed)

Kronolojik akıştan sıralı akışa geçiş iki aşamalı bir yapıdır:

1. Aday üretimi: Timeline listesi + dev hesap gönderileri + (istenirse) öneri kaynakları; birkaç yüz aday.
2. Sıralama: Her aday için özellikler (yazarla etkileşim geçmişi, gönderinin yaşı, beğeni hızı, içerik tipi) toplanır ve bir model puan verir. Özellik okuma maliyeti yüzünden özellikler önceden hesaplanıp bir feature store'da tutulur.

Gecikme bütçesi önemlidir: akış isteği için toplam 200 ms varsa sıralamaya 50-80 ms kalır. Sıralanmış sonuç kısa süreli (ör. oturum boyunca) cache'lenir; kullanıcı aşağı kaydırdıkça aynı sıralı listeden sayfalar verilir, her sayfada yeniden sıralanmaz (aksi halde gönderiler sayfalar arasında zıplar). Mülakatta model detayına girmek beklenmez; iki aşamalı yapıyı, gecikme bütçesini ve sıralamanın cache'lenmesini söylemek yeterlidir.

Sayaçlar ve hidrasyon

Bir akış sayfası 20 gönderi, 20 yazar ve 20 sayaç demektir. Hidrasyon tek tek değil toplu yapılır (MGET ve çoklu anahtar okuma); yazar profilleri de ayrı bir cache'tedir. Viral bir gönderinin beğeni sayacı saniyede binlerce kez artar: tek bir satır ya da tek bir Redis anahtarı sıcaklaşır. Sayaç N alt anahtara bölünür (likes:{postId}:0..15), artırma rastgele bir alt anahtara gider, okuma kısa TTL'li toplanmış bir değerden yapılır. Beğeni sayısının birkaç saniye geride olması kabul edilir.

Medya

Görsel ve videolar akış servisinden geçmez: istemci medya servisinden imzalı bir yükleme URL'i alır, dosyayı nesne deposuna yükler, gönderide sadece mediaId vardır. Akış cevabındaki medya URL'leri CDN'i gösterir. Akış servisinin bant genişliği bu sayede küçük kalır.

Darboğazlar, hatalar ve trade-off'lar

Trade-off'lar:

• Push ve pull: Okuma ucuzluğu için yazma çoğaltmasını kabul ettik; dev hesaplar ve pasif kullanıcılar için pull'a döndük.
• Kompakt liste ve sorted set: 10 kat bellek tasarrufu için sadece başa ekleme ve id sırasına dayandık.
• Okuma anında filtreleme: Silme ve takipten çıkma ucuz; bedeli her okumada filtreleme ve fazladan aday çekme.
• Eventual consistency: Takipçiler gönderiyi saniyeler (dev hesapta biraz daha) sonra görür; yazar kendi gönderisini hemen görür.

Üç seviyede cevap

Soru: "Fan-out on write mı, fan-out on read mi? Neden?"

Soru: "Timeline cache'i nasıl tutarsın? Bellek ne kadar tutar?"

Soru: "Bir gönderi silindiğinde onu milyonlarca akıştan nasıl kaldırırsın?"

Mülakatçı için

Takip soruları:

• Kullanıcı yeni birini takip etti. O kişinin eski gönderileri akışa ne zaman ve nasıl girer?
• Akışa reklam ekleyeceğiz: her 5 gönderide bir. Sayfalama ve cache nasıl etkilenir?
• İki bölgeli bir kurulumda fan-out nerede yapılır?
• Sıralama modeli değişti; eski ve yeni modelin etkisini nasıl karşılaştırırsın?

Seviye beklentisi: Mid seviyede push/pull karşılaştırması, celebrity problemi, id tabanlı timeline ve cursor sayfalama beklenir. Senior'dan sayılarla karar, bellek hesabı, okuma anında filtreleme, cache'in yeniden kurulması ve sıralama katmanının gecikme bütçesi beklenir. Staff seviyesinde aday eşik geçişlerini, çok bölgeyi ve deney altyapısını tartışabilir.

Hızlı tekrar

Kaynaklar

• Martin Kleppmann, Designing Data-Intensive Applications, Bölüm 1: Twitter ana sayfa zaman çizelgesi örneği üzerinden yük parametreleri ve fan-out trade-off'u.
• Alex Xu, System Design Interview: An Insider's Guide (Cilt 1): "Design a News Feed System" bölümü.
• Redis: Key eviction: Cache olarak kullanılan Redis'te bellek politikaları.
• Redis Cluster specification: Anahtarların slot'lara dağılımı ve asenkron replikasyon.
• Discord: How Discord Stores Billions of Messages: Büyük partition problemi ve zaman kovalarıyla bölme (takipçi tablolarındaki çarpıklık için de geçerli fikir).