Case study: news feed — fan-out on write বনাম read আর ranking

১ · সমস্যা আর পরিধি — কী বানাচ্ছি, কী বানাচ্ছি না

সকালে ফোন খুলে প্রথম যে পাতাটি দেখেন — বন্ধুর ছবি, প্রিয় লেখকের নতুন লেখা — সেটিই news feed, বা home timeline. প্রতিটি মানুষের তালিকা আলাদা, প্রতি মুহূর্তে বদলায়, আর কোটি মানুষ একসাথে চাইলেও দ্রুত খুলতে হয়। এই পর্বে একটি কাল্পনিক social অ্যাপের feed নকশা করব, পর্ব ৬ — একটি নকশা কীভাবে এগোয়-এর ধাপ মেনে: requirement → হিসাব → API → data model → বড় ছবি → গভীরে → ভাঙন। আগের মডিউলগুলোর ধারণা এখানে শুধু প্রয়োগ হবে, link-সহ।

Functional requirement — ব্যবহারকারী যা করতে পারবেন

• পোস্ট: লেখা আর কয়েকটি ছবি; মোছা; public বা শুধু follower-দের জন্য।
• Follow: একমুখী — অনুমতি লাগে না (বন্ধুত্বের মতো দুমুখী নয়); unfollow, block, mute.
• Home timeline: যাঁদের follow করেন তাঁদের পোস্ট, সময়ের বা সাজানো ক্রমে, scroll করলে পরের পাতা।
• সাড়া: like আর comment, আর প্রতিটি পোস্টে তাদের সংখ্যা।

Non-functional requirement — কতটা ভালোভাবে (সংখ্যাগুলো ধরা যাক)

• পড়া-ভারী আর দ্রুত: feed খোলার server-এর দিকের p99 ২০০ ms-এর নিচে — লক্ষ্য p99-এ, গড়ে নয় (পর্ব ৪ — Latency, throughput আর percentile).
• সতেজতা: follower-দের feed-এ নতুন পোস্ট p99 ১০ সেকেন্ডে; like-এর সংখ্যা কয়েক সেকেন্ড পিছিয়ে চলে।
• Durability আর availability: পোস্ট কখনো হারাবে না; feed-এর আগে-তৈরি তালিকা হারালে আবার বানানো যায়। কোনো অংশ বিকল হলেও feed খুলবে, হয়তো সরল রূপে।
• সঠিকতা: নিজের পোস্ট সঙ্গে সঙ্গে নিজের feed-এ; মোছা পোস্ট বা block করা মানুষের পোস্ট পরের পড়াতেই অদৃশ্য।
• মোবাইল-প্রধান: ধরা যাক বেশিরভাগ ব্যবহারকারী ফোনে, অনেকের network ধীর বা মাঝে মাঝে বিচ্ছিন্ন — ছোট উত্তর, কয়েক মাপের ছবি, নিরাপদ retry.

যে প্রশ্নগুলো আগে জিজ্ঞাসা করবেন

২ · হিসাব — পড়া, লেখা, fan-out আর memory

পর্ব ৩ — Back-of-the-envelope হিসাব-এর নিয়মে, প্রতিটি অনুমান আলাদা করে লিখে। নিচের সংখ্যাগুলো কোনো বাস্তব অ্যাপের পরিসংখ্যান নয় — শুধু ধরে নেওয়া মান, যাতে নকশার সিদ্ধান্তগুলো সংখ্যায় দাঁড়ায়:

• DAU ২ কোটি, মোট account ৬ কোটি; প্রতি সক্রিয় ব্যবহারকারী দিনে গড়ে ০.২৫টি পোস্ট আর ১০ বার feed খোলেন, প্রতিবার ২০টি পোস্ট।
• যিনি পোস্ট করেন তাঁর গড়ে ২০০ জন follower; ব্যস্ততম ঘণ্টায় চাপ গড়ের ৩ গুণ (peak factor).
• প্রতিটি timeline-এ ৫০০টি ৮-byte ID, আর প্রতি timeline-এ ১০০ byte বাড়তি হিসাব (key, store-এর নিজস্ব overhead — সংস্করণভেদে আলাদা)।
• একটি পোস্টের সারি ১ KB; ২০% পোস্টে ছবি, মূল ছবি ২০০ KB, আর feed-এ দেখানো ছোট রূপ ৫০ KB.

// News-feed estimation. Every input below is an assumption, not a real statistic.
const DAU = 20e6, registered = 60e6;     // daily active users; all accounts
const postsPerDAU = 0.25;                // posts per active user per day
const opensPerDAU = 10, pageSize = 20;   // feed opens per day; posts shown per open
const avgFollowers = 200;                // followers per posting author (push model)
const peak = 3;                          // peak hour = 3 x the daily average
const ids = 500, idBytes = 8, perTimelineOverhead = 100;   // bytes
const DAY = 86400, fmt = n => Math.round(n).toLocaleString("en-US");

const postsDay = DAU * postsPerDAU, readsDay = DAU * opensPerDAU;
const postsS = postsDay / DAY, readsS = readsDay / DAY;
console.log("posts/day     " + fmt(postsDay) + "   avg/s " + fmt(postsS) + "   peak/s " + fmt(postsS * peak));
console.log("feed opens/s  avg " + fmt(readsS) + "   peak " + fmt(readsS * peak) +
  "   read:write = " + (readsS / postsS).toFixed(0) + ":1");
const fan = postsS * avgFollowers;
console.log("push fan-out writes/s  avg " + fmt(fan) + "   peak " + fmt(fan * peak));
console.log("hydrated posts/s at peak  " + fmt(readsS * peak * pageSize));

const perTL = ids * idBytes + perTimelineOverhead;          // one timeline in cache
for (const [who, n] of [["DAU only", DAU], ["all accounts", registered]]) {
  const gb = n * perTL / 1e9;
  console.log(("timelines: " + who).padEnd(24) + gb.toFixed(0).padStart(5) + " GB, x2 replicas " +
    (2 * gb).toFixed(0) + " GB");
}
const textKB = 1, imgShare = 0.2, imgKB = 200, years = 5;    // post row; original image
const tb = x => (x / 1e9).toFixed(1) + " TB";                // input in KB
console.log("post rows over " + years + " y: " + tb(postsDay * textKB * 365 * years) +
  "   images: " + tb(postsDay * imgShare * imgKB * 365 * years));
const thumbKB = 50;                                           // image size inside the feed
const gbit = readsS * pageSize * imgShare * thumbKB * 1e3 * 8 / 1e9;
console.log("feed image egress  avg " + gbit.toFixed(1) + " Gbit/s   peak " +
  (gbit * peak).toFixed(1) + " Gbit/s (mostly from the CDN)");

posts/day     5,000,000   avg/s 58   peak/s 174
feed opens/s  avg 2,315   peak 6,944   read:write = 40:1
push fan-out writes/s  avg 11,574   peak 34,722
hydrated posts/s at peak  138,889
timelines: DAU only        82 GB, x2 replicas 164 GB
timelines: all accounts   246 GB, x2 replicas 492 GB
post rows over 5 y: 9.1 TB   images: 365.0 TB
feed image egress  avg 3.7 Gbit/s   peak 11.1 Gbit/s (mostly from the CDN)

৩ · API — পোস্ট, feed, follow আর like

REST-এর নিয়মগুলো পর্ব ৮ — REST API নকশা-এ; এখানে শুধু এই সমস্যার পাঁচটি সিদ্ধান্ত।

1. ছবি সরাসরি storage-এ: POST /v1/media একটি স্বল্পমেয়াদি presigned URL দেয়; app ছবি সোজা object storage-এ তোলে (পর্ব ২৬ — Object storage), আমাদের server দিয়ে নয়।
2. পোস্টে idempotency: ধীর network-এ app আবার পাঠাবেই; idempotency key না থাকলে একই পোস্ট দুবার, সব follower-এর feed-এ।
3. Like আর follow স্বভাবেই idempotent: PUT /v1/posts/{id}/like দুবারেও একটি like, DELETE-এ ফেরানো; “গণনা ১ বাড়ানো” ধাঁচের API-তে retry গণনা বাড়ায়।
4. Feed-এর পাতা cursor দিয়ে: “৪১ নম্বর থেকে ২০টি” (offset) নয় — ওপরে নতুন পোস্ট ঢুকলে offset সরে গিয়ে একই পোস্ট দুবার আসে। কারণ আর বিকল্প অংশ ৭-এ।
5. নতুন পোস্টের খবর: feed নিজে থেকে ওপরে সরে না; app মাঝে মাঝে জিজ্ঞাসা করে বা খোলা সংযোগে খবর পায় (পর্ব ১০ — Real-time যোগাযোগ), আর ব্যবহারকারী “নতুন পোস্ট” বোতাম চাপলে ওপরের পাতা আসে।

POST /v1/posts HTTP/1.1
Authorization: Bearer <token>
Idempotency-Key: 8b1d4c2e-5f6a-4b7c-9d8e-1a2b3c4d5e6f
Content-Type: application/json

{ "text": "Rajshahi-te aaj aam-er haat", "media_ids": ["m_77a1"], "visibility": "public" }

HTTP/1.1 201 Created
Location: /v1/posts/1847562093310976001

{ "post_id": "1847562093310976001", "created_at": "2026-10-28T07:15:02Z" }

GET /v1/feed?limit=20&cursor=eyJzIjoiZjlhMiIsIm8iOjQwfQ HTTP/1.1
Authorization: Bearer <token>

HTTP/1.1 200 OK
Content-Type: application/json

{
  "items": [
    { "post_id": "1847562093310976001",
      "author": { "id": "u_311", "name": "Rina", "avatar": "https://cdn.example.com/a/u_311_96.webp" },
      "text": "Rajshahi-te aaj aam-er haat",
      "media": [{ "url": "https://cdn.example.com/m/m_77a1_640.webp", "w": 640, "h": 480 }],
      "likes": 128, "comments": 9, "liked_by_me": true }
  ],
  "next_cursor": "eyJzIjoiZjlhMiIsIm8iOjYwfQ"
}

খেয়াল করুন: post_id স্ট্রিং, কারণ ৬৪-bit সংখ্যা JavaScript-এর সাধারণ number-এ নিখুঁত থাকে না। ID-টি Snowflake-ধাঁচের — সময়ের ক্রমে সাজানো, তাই ID থেকেই পোস্টের বয়স বোঝা যায় (পর্ব ২৩)। liked_by_me প্রতিটি পাঠকের নিজের, তাই feed-এর উত্তর ব্যক্তিগত — CDN-এ যায় শুধু ছবি।

৪ · Data model — কোন ডেটা কোথায়, কোন key-তে ভাগ

প্রথম নিয়ম: সত্যের উৎস আর দ্রুত পড়ার কপি আলাদা। পোস্ট, follow আর like টেকসই store-এ; timeline cache হলো সেগুলো থেকে বানানো একটি read model — আসলে একটি materialized view, ইচ্ছাকৃত denormalization (পর্ব ৩৫ — Event sourcing আর CQRS; ডেটাবেস কোর্সের Denormalization). হারালে আবার বানানো যায় — এই একটি বাক্যই অংশ ৭ আর ৯-এর অনেক সিদ্ধান্তের ভিত্তি।

Partition key (পর্ব ২৩ — Partitioning আর sharding): পোস্টকে author_id দিয়ে ভাগ করলে বিখ্যাত লেখকের partition একটি hot spot, আর সেটি বাড়তেই থাকে। তাই পোস্টের সারি post_id-এর hash-এ, আর লেখকের তালিকা আলাদা index-এ, মাস ধরে ভাঙা। followers-এ বিখ্যাত কারও partition কোটি সারির হতে পারে — followee_id-এর সাথে একটি bucket নম্বর জুড়ে কয়েক ভাগে রাখলে fan-out worker-রা সমান্তরালে পড়ে। Query-গুলো সবই key ধরে, join নেই — তাই wide-column store স্বাভাবিক পছন্দ, sharded SQL-ও চলে (পর্ব ২০ — SQL বনাম NoSQL).

৫ · বড় ছবি — লেখার পথ আর পড়ার পথ

সিস্টেম দুই পথে ভাগ: লেখার পথ পোস্ট টেকসইভাবে রেখে পেছনে follower-দের timeline-এ ছড়ায়; পড়ার পথ timeline থেকে ID নিয়ে ছেঁকে, সাজিয়ে, পূর্ণ পোস্ট বানায়। মাঝে একটি message queue — পোস্টকারীকে fan-out-এর অপেক্ষা করতে হয় না।

লেখার পথ — চার ধাপে

(১) Gateway-তে token আর rate limit (পর্ব ১১ — Reverse proxy, API gateway আর BFF). (২) Post service একই local transaction-এ পোস্টের সারি আর outbox-এ একটি event লেখে, যাতে “পোস্ট আছে, event নেই” না হয় (পর্ব ২৫ — Distributed transaction), তারপর 201. (৩) Relay event-টি queue-তে তোলে (পর্ব ৩১ — Message queue; বড় আকারে পর্ব ৩৩ — Log-ভিত্তিক streaming). (৪) Fan-out worker সক্রিয় follower-দের timeline-এ ID বসায় — অংশ ৬-এর stepper.

পড়ার পথ — একটি অনুরোধ শুরু থেকে শেষ

নিচে পাঠক u42 feed খুললেন (সময়গুলো ধরে নেওয়া):

LRANGE timeline:u42 0 499
1847562093310976001
1847561987043233792
1847561870220394496
… আরও ৪৯৭টি · মোট প্রায় ৪ KB

post cache:  MGET post:… ×22  → ২০ hit, ২ miss
post store:  ২টি ID ধরে       → ১টি পাওয়া, ১টি মোছা (tombstone)
বৈধ ২১টি      → স্কোরের ক্রমে প্রথম ২০টি
user cache:  লেখকের নাম, ছবি  → ২০ hit
counter:     like, comment    → cache থেকে
উত্তর: ২০টি পোস্ট + next_cursor · ছবি app আনে CDN থেকে

৩১০ জন followee থাকা সত্ত্বেও পড়া হলো মাত্র ৩টি তালিকা — push-এর পুরস্কার। আর মোছা পোস্টটি ধরা পড়ল পড়ার মুহূর্তে, timeline না ঘেঁটেই — শুধু ID রাখার পুরস্কার।

৬ · গভীরে ১ — fan-out on write, on read, না hybrid?

মোট কাজের তুলনা পর্ব ২ — Requirement আর trade-off-এর অংশ ৬-এ: মানুষ পোস্টের চেয়ে বেশিবার feed খুললে push সস্তা। আমাদের অনুপাত ৪০:১, তাই প্রথম উত্তর push. কিন্তু মোট সংখ্যা লুকায় একটি পোস্টের সবচেয়ে খারাপ খরচ আর পড়ার লেজ।

Follower-সংখ্যা লম্বা লেজের (heavy-tailed): অল্প কয়েকজনের বিপুল, বাকিদের অল্প। নিচে ২০,০০০ জনের একটি কাল্পনিক graph — প্রত্যেকে ১০ থেকে ১৪৯ জনকে follow করেন, কাকে তা ঠিক হয় Pareto-ধাঁচের জনপ্রিয়তায়, আর তিনজন ইচ্ছা করে খুব জনপ্রিয়। প্রত্যেকে একটি পোস্ট দিলেন; প্রতিটি T-তে দেখানো হলো কতজন pull-এ, প্রতি পোস্টে লেখা, মোট লেখা, আর feed খুলতে কয়টি তালিকা মেলাতে হয়।

// Push vs pull vs hybrid on a seeded follower graph with a heavy tail and 3 huge accounts.
function mulberry32(a) { return () => { a = (a + 0x6D2B79F5) | 0; let t = Math.imul(a ^ (a >>> 15), 1 | a);
  t = (t + Math.imul(t ^ (t >>> 7), 61 | t)) ^ t; return ((t ^ (t >>> 14)) >>> 0) / 4294967296; }; }
const rnd = mulberry32(56), N = 20000;
const w = Array.from({ length: N }, () => Math.pow(1 - rnd(), -1 / 1.8));   // Pareto popularity
w[0] = 900; w[1] = 500; w[2] = 300;                                       // three celebrities
const cum = []; w.reduce((s, x, i) => (cum[i] = s + x), 0);
const pick = () => { const r = rnd() * cum[N - 1]; let lo = 0, hi = N - 1;
  while (lo < hi) { const m = (lo + hi) >> 1; cum[m] < r ? lo = m + 1 : hi = m; } return lo; };
const follows = [], fol = new Array(N).fill(0);           // follows[u] = whom u follows
for (let u = 0; u < N; u++) {
  const s = new Set(), k = 10 + Math.floor(rnd() * 140);  // 10..149 followees each
  while (s.size < k) { const v = pick(); if (v !== u) s.add(v); }
  follows.push([...s]); s.forEach(v => fol[v]++);
}
const pct = (a, p) => [...a].sort((x, y) => x - y)[Math.ceil(p / 100 * a.length) - 1];
const sorted = [...fol].sort((x, y) => y - x);
console.log("followers: median " + pct(fol, 50) + ", p99 " + pct(fol, 99) +
  ", top 5: " + sorted.slice(0, 5).join(", "));
console.log("T      pulled   writes/post p50  p99    max   total writes   read sources p50  p99");
for (const T of [Infinity, 5000, 1000, 200, 0]) {          // Infinity = pure push, 0 = pure pull
  const wpp = fol.map(f => (f <= T ? f : 0));                 // one post by every user
  const src = follows.map(l => (T === 0 ? l.length : 1 + l.filter(v => fol[v] > T).length));
  const tot = wpp.reduce((a, b) => a + b, 0);
  const pulled = fol.filter(f => f > T).length;
  console.log(String(T === Infinity ? "push" : T === 0 ? "pull" : T).padEnd(6) + String(pulled).padStart(7) +
    String(pct(wpp, 50)).padStart(18) + String(pct(wpp, 99)).padStart(5) + String(Math.max(...wpp)).padStart(7) +
    tot.toLocaleString("en-US").padStart(15) + String(pct(src, 50)).padStart(19) + String(pct(src, 99)).padStart(5));
}

followers: median 53, p99 450, top 5: 14610, 10899, 7792, 5702, 5472
T      pulled   writes/post p50  p99    max   total writes   read sources p50  p99
push        0                53  450  14610      1,585,932                  1    1
5000        6                53  442   4199      1,536,010                  3    7
1000       37                53  407    997      1,485,338                  6   13
200       891                51  178    200      1,191,585                 20   43
pull    20000                 0    0      0              0                 79  148

পড়ার লেজ — কেন pull-এ p99 খারাপ

পর্ব ৪-এর fan-out-এর সূত্রে K-টি অংশের প্রতিটি ১% সময় ধীর হলে অন্তত একটি ধীর হওয়ার সম্ভাবনা 1 − 0.99^K. Pull-এর মাঝের পাঠকের K = ৭৯-এ প্রায় ৫৪.৮%, K = ১৪৮-এ প্রায় ৭৭.৪%; hybrid-এ (T = ১,০০০) K = ৬-এ প্রায় ৫.৯%, ১৩-তে প্রায় ১২.২%. Pull-এর সমস্যা শুধু বেশি কাজ নয় — বেশি tail latency.

বিখ্যাতের পোস্ট — কত দেরি?

ধরা যাক fan-out-এর ক্ষমতা ঠিক অংশ ২-এর peak, সেকেন্ডে ৩৪,৭২২টি লেখা। তখন ১ কোটি follower-এর একজনের একটি পোস্ট একাই প্রায় ২৮৮ সেকেন্ড (প্রায় ৫ মিনিট) পুরো fan-out দখল করে, বাকিদের পোস্ট আটকে — এটিই celebrity problem. Hybrid-এ সেই পোস্ট যায় শুধু author timeline-এ।

নিচের stepper-এ দুটি পোস্ট: সাধারণ লেখক রিনার (৪ জন follower), আর বিখ্যাত S-এর (২,০০,০০০ জন)। সীমা T = ১০,০০০ ধরা হলো; প্রতিটি timeline সর্বোচ্চ ৫০০টি ID রাখে।

ZADD timeline:B 1761635702114 9001
     (score = পোস্টের সময়, ms · সদস্য = post ID)
ZREMRANGEBYRANK timeline:B 0 -501   (সবচেয়ে পুরোনোগুলো বাদ, ৫০০ থাকে)
… C আর D-তে একই …
E: timeline:E নেই → লেখা বাদ

Fan-out-কে সস্তা আর নিরাপদ রাখার আরও কয়েকটি কৌশল

• জোট আর অগ্রাধিকার: follower-দের cache shard ধরে ভাগ করে প্রতি shard-এ একটি pipeline (batching); online follower আগে; বড় লেখকের fan-out আলাদা queue-তে, যাতে সাধারণ পোস্ট না আটকায় (পর্ব ১৮ — Overload সামলানো)।
• সীমার কিনারায় ওঠানামা: কারও follower ৯,৯৯৯ আর ১০,০০১-এর মাঝে দুললে পোস্ট একবার push, একবার pull. ওঠা আর নামার আলাদা সীমা রাখুন (যেমন ১০,০০০-এ উঠলে pull, ৮,০০০-এর নিচে নামলে push).
• Unfollow: পুরোনো ID পড়ার সময় “এখনো follow করেন কি?” দেখে ছাঁকা, পরে ধীরে মোছা।

৭ · গভীরে ২ — timeline-এর ভাণ্ডার, hydration, rebuild আর পাতা

কেন শুধু ID, কেন সীমিত দৈর্ঘ্য

পুরো পোস্টের (১ KB) বদলে ৮-byte ID-তে memory ১২৫ ভাগের এক ভাগ; আর সম্পাদনা, মোছা বা লেখকের ছবি বদলে লাখো timeline-এ হাত দিতে হয় না — পূর্ণ রূপ আসে পড়ার সময় post cache থেকে, cache-aside-এ (পর্ব ২৮; পর্ব ২৯ — Eviction আর invalidation). ৫০০-র পরে কেউ নামলে বাকিটা author timeline থেকে pull — বিরল।

List না sorted set? List-এ memory কম, কিন্তু দেরিতে আসা event ক্রম ভাঙে আর একই ID দুবার ঢোকে। Sorted set-এ সদস্য post ID, score পোস্টের সময় (ms) — ক্রম আর duplicate-রোধ আপনা থেকে, দামে বেশি memory (সংস্করণভেদে; নিজে মাপুন)। পুরো ৬৪-bit ID-কে score করবেন না: score একটি double, ২^৫৩-এর বড় পূর্ণসংখ্যা নিখুঁত রাখে না (ডেটাবেস কোর্সের Redis).

অনুপস্থিতদের বাদ, ফিরলে rebuild

শুধু DAU-র timeline-এ ৮২ GB, সবার রাখলে ২৪৬ GB — বাড়তিটুকু প্রায় পড়াই হতো না। তাই ধরা যাক ৩০ দিন অনুপস্থিত হলে timeline মোছে, fan-out তাঁকে বাদ দেয়; ফিরলে followee-দের author timeline থেকে শেষ পোস্ট এনে সময়ের ক্রমে মিলিয়ে নতুন করে বানানো হয়। এটি k-way merge: সাজানো তালিকাগুলোর মাথা একটি heap-এ রেখে প্রতিবার সবচেয়ে নতুনটি তোলা (DSA কোর্সের Heap, heapsort আর priority queue). নিচে ৮ জন followee, প্রত্যেকের ৫০টি পোস্ট।

// Pull at read time: k-way merge of followees' newest-first post lists with a max-heap.
function mulberry32(a) { return () => { a = (a + 0x6D2B79F5) | 0; let t = Math.imul(a ^ (a >>> 15), 1 | a);
  t = (t + Math.imul(t ^ (t >>> 7), 61 | t)) ^ t; return ((t ^ (t >>> 14)) >>> 0) / 4294967296; }; }
const rnd = mulberry32(7), K = 8, PER = 50, N = 10;        // 8 followees, 50 recent posts each
const now = 1000000;                                        // seconds; post time = its sort key
const lists = Array.from({ length: K }, (_, a) => {
  const gap = 600 * (a + 1) ** 2;                           // some authors post far more often
  let t = now - Math.floor(rnd() * gap);
  return Array.from({ length: PER }, () => ({ a: "u" + a, t: (t -= 1 + Math.floor(rnd() * gap)) }));
});
let cmp = 0;
const heap = [], less = (i, j) => (cmp++, heap[i].p.t < heap[j].p.t);
const swap = (i, j) => ([heap[i], heap[j]] = [heap[j], heap[i]]);
function push(x) { heap.push(x); let i = heap.length - 1;
  while (i > 0 && less((i - 1) >> 1, i)) { swap(i, (i - 1) >> 1); i = (i - 1) >> 1; } }
function pop() { const top = heap[0], last = heap.pop();
  if (heap.length) { heap[0] = last; let i = 0;
    for (;;) { let b = i; const l = 2 * i + 1, r = l + 1;
      if (l < heap.length && less(b, l)) b = l; if (r < heap.length && less(b, r)) b = r;
      if (b === i) break; swap(i, b); i = b; } }
  return top; }

lists.forEach((l, s) => push({ p: l[0], s, k: 0 }));        // the head of each list
const out = [];
while (out.length < N) {
  const x = pop(); out.push(x.p);
  if (x.k + 1 < PER) push({ p: lists[x.s][x.k + 1], s: x.s, k: x.k + 1 });
}
out.forEach((p, i) => console.log(String(i + 1).padStart(2) + ". " + p.a + "  " + (now - p.t) + " s ago"));
const taken = {}; out.forEach(p => (taken[p.a] = (taken[p.a] || 0) + 1));
console.log("taken per author:", JSON.stringify(taken));
console.log("heap comparisons: " + cmp + "   sort all " + K * PER + " then cut: about " +
  Math.round(K * PER * Math.log2(K * PER)) + " comparisons");

 1. u0  45 s ago
 2. u0  632 s ago
 3. u0  1052 s ago
 4. u1  1189 s ago
 5. u0  1365 s ago
 6. u1  1509 s ago
 7. u0  1609 s ago
 8. u0  1889 s ago
 9. u0  2033 s ago
10. u0  2365 s ago
taken per author: {"u0":8,"u1":2}
heap comparisons: 77   sort all 400 then cut: about 3458 comparisons

Post store, post cache আর ছবি

Post store post_id-এর hash-এ ভাগ, প্রতি ভাগে leader আর replica (পর্ব ২২ — Replication); hydration-এর ১,৩৮,৮৮৯/s-এর প্রায় সবটা post cache থেকে, আর ভাইরাল পোস্ট app server-এর ছোট TTL-এর L1-এ। ছবি presigned URL-এ object storage-এ ওঠে; একটি পেছনের কাজ কয়েক মাপের রূপ বানায় (পর্ব ৩৭ — Background job); রূপগুলোর URL বদলায় না, তাই CDN-এ দীর্ঘ মেয়াদে cache হয় (নেটওয়ার্ক কোর্সের Web cache, proxy আর CDN).

Cursor দিয়ে পাতা — offset কেন ভাঙে

Offset-এর পাতায় প্রথম পাতার পর ওপরে ৩টি নতুন পোস্ট এলে পুরোনো ১৮–২০ নম্বর সরে ২১–২৩-এ, দ্বিতীয় পাতায় আবার আসে। সময়ের ক্রমে সমাধান keyset: cursor-এ “এই post ID-র চেয়ে পুরোনো” — Snowflake ID সময়ে সাজানো। Ranked feed-এ স্কোর বদলায়, তাই প্রথম পাতার সাজানো ID-তালিকা কয়েক মিনিটের একটি “feed session”-এ রাখা হয়, cursor-এ session আর অবস্থান — উপরের cursor-টি base64-এ ঠিক এটাই: {"s":"f9a2","o":40}. নতুন পোস্টের জন্য ওপরে “নতুন পোস্ট” বোতাম। Offset বনাম cursor-এর সাধারণ আলোচনা পর্ব ৮-এ।

Consistency — কার কাছে কী প্রতিশ্রুতি

পর্ব ৪০ — CAP, PACELC আর consistency model-এর ভাষায় follower-দের feed eventually consistent: queue আর replication lag-এ কয়েক সেকেন্ড দেরি স্বাভাবিক। তিনটি জায়গায় কড়া প্রতিশ্রুতি:

• নিজের পোস্ট নিজে দেখা (read-your-writes): না পেলে মানুষ আবার পোস্ট করেন। পড়ার সময় পাঠকের নিজের শেষ কয়েক মিনিটের পোস্ট post store-এর leader বা app-এর মনে রাখা তালিকা থেকে জুড়ে দিন — fan-out-এর ওপর ভরসা নয়।
• সময় পেছায় না (monotonic reads): একবার দেখা পোস্ট পরের refresh-এ পিছিয়ে থাকা replica থেকে পড়ে উধাও হবে না — একই ব্যবহারকারীকে একই replica-তে রাখা সাধারণ উপায়।
• মোছা আর block সঙ্গে সঙ্গে: timeline-কে বিশ্বাস না করে পড়ার মুহূর্তে বর্তমান অবস্থা দেখে ছাঁকা — অংশ ৫-এর stepper-এর ধাপ ৪ আর ৬।

৮ · গভীরে ৩ — ranking আর like-গণনা

সময়ের ক্রম থেকে সাজানো feed

সবচেয়ে সরল feed reverse-chronological — নতুনটি ওপরে; স্বচ্ছ, কিন্তু অংশ ৭-এর আউটপুটের মতো ঘন ঘন পোস্টকারী পাতা দখল করেন, আর বন্ধুর জরুরি খবর চাপা পড়ে। তাই বেশিরভাগ বড় feed কোনো না কোনোভাবে সাজানো, পর্ব ২৭-এর খোঁজের ranking-এর মতো ধাপে:

1. Candidate generation: সস্তা নিয়মে কয়েকশো প্রার্থী — নিজের timeline cache, বিখ্যাতদের নতুন পোস্ট, হয়তো follow-এর বাইরের কিছু সুপারিশ।
2. Feature আর স্কোর: প্রতিটি প্রার্থীর কয়েকটি সংকেত — বয়স, লেখকের সাথে পাঠকের সম্পর্ক বা affinity, like-comment-এর মতো engagement signal — একটি সূত্রে বা প্রশিক্ষিত মডেলে একটি সংখ্যা।
3. Re-ranking আর ছাঁকনি: একই লেখকের পোস্ট পরপর না রাখা, দেখা পোস্ট বাদ, নীতিমালা আর privacy-র ছাঁকনি, তারপর পাতা।

নিচে একটি হাতে-লেখা সূত্র, কোনো বাস্তব পণ্যের নয়:

Log-এর কারণে ১০০০তম like-এর মূল্য প্রথম কয়েকটির চেয়ে অনেক কম; comment-এর ওজন like-এর ৩ গুণ, কারণ comment-এ বেশি মনোযোগ লাগে (ধরে নেওয়া)। শেষ গুণকটি time decay: প্রতি half-life-এ স্কোর অর্ধেক। ৩০টি কাল্পনিক প্রার্থীতে A (w_a = ২, w_e = ১, half-life ৬ ঘণ্টা), তারপর দুটি বদল — B: engagement-এর ওজন ৩ গুণ; C: half-life ২৪ ঘণ্টা।

// Rank 30 seeded candidate posts: recency decay x (affinity + engagement). Not a real product's formula.
function mulberry32(a) { return () => { a = (a + 0x6D2B79F5) | 0; let t = Math.imul(a ^ (a >>> 15), 1 | a);
  t = (t + Math.imul(t ^ (t >>> 7), 61 | t)) ^ t; return ((t ^ (t >>> 14)) >>> 0) / 4294967296; }; }
const rnd = mulberry32(2026);
const posts = Array.from({ length: 30 }, (_, i) => ({
  id: "p" + String(i + 1).padStart(2, "0"),
  age: +(rnd() * 48).toFixed(1),                  // hours since posted
  aff: +(rnd() ** 2).toFixed(2),                  // 0..1: how much this reader interacts with the author
  likes: Math.floor(Math.pow(1 - rnd(), -1.3) * 3) - 3, comments: 0 }));
posts.forEach(p => (p.comments = Math.floor(p.likes * rnd() * 0.2)));

function score(p, W) {
  const eng = Math.log10(1 + p.likes + 3 * p.comments);        // diminishing returns
  return (W.aff * p.aff + W.eng * eng) * Math.pow(0.5, p.age / W.halfLife);
}
function best(W, n = 10) {
  return [...posts].sort((a, b) => score(b, W) - score(a, W) || a.age - b.age).slice(0, n);
}
const show = (label, list) => console.log(label.padEnd(15) + list.map(p => p.id).join(" "));
const A = { aff: 2, eng: 1, halfLife: 6 };
show("chronological", [...posts].sort((a, b) => a.age - b.age).slice(0, 10));
show("ranked A", best(A));
show("B: eng x3", best({ ...A, eng: 3 }));
show("C: halfLife 24", best({ ...A, halfLife: 24 }));

console.log("\nid    age h  aff  likes  com  score A");
for (const p of best(A, 5))
  console.log(p.id.padEnd(6) + p.age.toFixed(1).padStart(5) + p.aff.toFixed(2).padStart(6) +
    String(p.likes).padStart(7) + String(p.comments).padStart(5) + score(p, A).toFixed(3).padStart(9));
const viral = posts.reduce((m, p) => (p.likes > m.likes ? p : m));
console.log("most liked: " + viral.id + " (" + viral.likes + " likes, " + viral.age + " h old) rank A: " +
  (best(A, 30).indexOf(viral) + 1) + ", rank B: " + (best({ ...A, eng: 3 }, 30).indexOf(viral) + 1) +
  ", rank C: " + (best({ ...A, halfLife: 24 }, 30).indexOf(viral) + 1));

chronological  p29 p04 p18 p23 p28 p10 p08 p06 p13 p05
ranked A       p29 p18 p23 p08 p04 p28 p13 p06 p14 p20
B: eng x3      p29 p23 p04 p18 p08 p06 p28 p13 p14 p20
C: halfLife 24 p29 p08 p18 p23 p14 p13 p06 p28 p20 p04

id    age h  aff  likes  com  score A
p29     0.9  0.83     37    2    2.977
p18     8.5  0.95      6    1    1.086
p23     8.6  0.01    151   16    0.859
p08    13.3  0.61    158   28    0.776
p04     2.0  0.00      7    0    0.717
most liked: p16 (246 likes, 47.7 h old) rank A: 21, rank B: 19, rank C: 14

Feature-এর সতেজতা আর মডেল — ধারণার স্তরে

প্রতিটি সংকেতের সতেজতার চাহিদা আলাদা (feature freshness): affinity সাধারণত রাতের batch-এ (পর্ব ৩৬ — Batch আর stream processing), like-গণনা stream থেকে মিনিটে, আর block বা মোছা কোনো feature নয় — পড়ার মুহূর্তের বাধ্যতামূলক ছাঁকনি। বড় সেবাগুলোর প্রকাশিত বিবরণে প্রায়ই সূত্রের বদলে প্রশিক্ষিত মডেল “পাঠক সাড়া দেবেন কি না”-র সম্ভাবনা অনুমান করে (learning to rank-এর ধারণা)। একটি নীরব বিপদ training-serving skew — মডেল শিখেছিল এক রকম feature-মানে, চালু অবস্থায় পায় আরেক রকম; প্রতিকারে প্রায়ই পরিবেশনের মুহূর্তের feature-ই log করে প্রশিক্ষণে নেওয়া হয়। মডেলের ভেতরটা এই কোর্সের বাইরে; system design-এর প্রশ্ন: feature কোথা থেকে, কত দ্রুত, আর ranker বিকল হলে কী।

Like-গণনা — সত্য একটি সারিতে, দেখানো সংখ্যা আরেক জায়গায়

প্রতিবার SELECT COUNT(*) মানে peak-এ সেকেন্ডে ১,৩৮,৮৮৯টি গণনা-query; আবার প্রতি like-এ একটি সারিতে +1 মানে ভাইরাল পোস্টে hot row — ধরা যাক সেকেন্ডে ৫,০০০টি like এক lock-এর লাইনে। তাই তিন স্তর:

1. সত্য: likes(post_id, user_id)-এ unique শর্ত — দুবার like অসম্ভব, retry নিরাপদ; “আমি like করেছি কি না” এখান থেকে।
2. দেখানোর গণনা: aggregator এক সেকেন্ডের like জমিয়ে একবারে “+৫,০০০” লেখে; গরম পোস্টে sharded counter — ১৬ ভাগে প্রতিটিতে সেকেন্ডে প্রায় ৩১৩, পড়ায় যোগফল (cache-এ)।
3. মেলানো: পেছনের কাজ মাঝে মাঝে সত্যের টেবিল থেকে গুনে ফারাক ঠিক করে।

সব গণনা নিখুঁত হওয়ারও দরকার নেই: কতজন আলাদা মানুষ দেখেছেন — কয়েক KB-এর HyperLogLog, প্রায় ১% ভুলে; এই ঘণ্টায় কোন পোস্ট সবচেয়ে সাড়া পাচ্ছে — count-min sketch (দুটিই পর্ব ৪৫-এ)। পর্দায় “১২ হাজার” থাকলে কয়েকশোর ফারাক কেউ টের পান না।

৯ · ভাঙন, trade-off আর বিস্তার

কোনটি মরলে কী হয়

১০ গুণ বড় হলে

DAU ২০ কোটি হলে peak-এ fan-out সেকেন্ডে প্রায় ৩.৫ লাখ লেখা, সক্রিয়দের timeline প্রায় ৮২০ GB (replica-সহ ১.৬ TB-এর বেশি)। হাতল: timeline ছোট করা; “সক্রিয়” ৩০ থেকে ৭ দিন; T নামানো; region ধরে আলাদা cache আর fan-out (পর্ব ৫১ — Failover আর disaster recovery). বড় খরচ timeline cache-এর RAM, fan-out আর CDN — দাম প্রদানকারী ও সময়ভেদে, তাই নিজে হিসাব করুন।

মোছা আর privacy-র প্রচার

পোস্টের কপি ছড়িয়ে আছে বহু জায়গায় — লাখো timeline-এ ID, post cache, CDN-এ ছবি, খোঁজের index, গণনা, backup. তাই মোছা দুই ধাপে। সঙ্গে সঙ্গে: post store-এ tombstone; hydration সেটি দেখেই বাদ দেয়, timeline-এ ID থাকলেও। পেছনে, নিশ্চিতভাবে: post cache মোছা, CDN-এ purge, index থেকে সরানো, timeline-এর ID ধীরে পরিষ্কার, আর retention policy মেনে backup-এর মেয়াদে মোছা। Account মোছায় crypto-shredding-এর মতো কৌশল আলোচিত; আইনের চোখে কতটা যথেষ্ট, তা এখতিয়ারভেদে আলাদা। Privacy বদল বা block-ও পড়ার মুহূর্তে যাচাই — “এই পাঠক কি এটি দেখার অধিকারী?” — object-level authorization (পর্ব ৫২ — নকশায় নিরাপত্তা; privacy by design).

অপব্যবহার ঠেকানো — রক্ষার দিক থেকে

• হারের সীমা: প্রতি account-এ পোস্ট, follow আর like-এর হার সীমিত, নতুন account-এ আরও কড়া (পর্ব ৪৯ — Rate limiting); follow-এর সীমা fan-out-এর খরচও বাঁধে।
• ছড়ানোর আগে যাচাই: সন্দেহজনক account-এর পোস্ট fan-out-এর আগে spam ও নীতিমালা-যাচাই পেরোয় — লাখো timeline-এ পৌঁছানোর আগেই থামে। Report থেকে পর্যালোচনা, নিশ্চিত হলে মোছার পথ।
• ভুয়া follower আর like: হঠাৎ অস্বাভাবিক লাফ চিহ্নিত করা, সন্দেহজনক সাড়া ranking-এ না গোনা। Unique শর্ত দুবার গোনা ঠেকায়, ভুয়া account নয় — সেজন্য আচরণ-বিশ্লেষণ।

কী মাপবেন, কিসে alert

পর্ব ৫০ — Observability ধরে: feed-এর p99 আর ত্রুটির হার; fan-out lag — পোস্ট থেকে follower-এর timeline পর্যন্ত সময়ের p99 (লক্ষ্য ১০ সেকেন্ড); queue-র সবচেয়ে পুরোনো event-এর বয়স; timeline cache-এর hit ratio আর মিনিটে rebuild (হঠাৎ বাড়লে একটি node মরেছে); hydration-এ না-পাওয়ার হার; খালি feed-এর হার; আর দেখানো ও সত্যের গণনার ফারাক। Alert দিন ব্যবহারকারীর অভিজ্ঞতায়, CPU-তে নয়।

১০ · AI-এর যুগে — news feed-এর নকশা যাচাই

AI-কে feed-এর নকশা চাইলে কয়েক সেকেন্ডে পরিচ্ছন্ন ছবি আসে — Kafka, Redis, Cassandra, microservices, ML ranker. শব্দগুলো ঠিক; সমস্যা থাকে সংখ্যায়, লেজে আর বিকলে:

AI-এর feed নকশা হাতে পেলে — যাচাইয়ের চেকলিস্ট

• পোস্ট/s, পড়া/s, fan-out লেখা/s আর memory নিজে, এককসহ, আবার হিসাব করেছি
• সবচেয়ে বড় follower-সংখ্যায় একটি পোস্টের খরচ আর দেরি দেখেছি; hybrid-এর সীমা আর পড়ার দাম লেখা আছে
• Timeline-এ শুধু ID, দৈর্ঘ্যের সীমা, অনুপস্থিতদের নিয়ম আর rebuild-এর পথ আছে
• নিজের পোস্ট, মোছা আর block-এর প্রতিশ্রুতি নাম ধরে লেখা
• প্রতিটি বাক্সের বিকল ও প্রতিকার লেখা; অন্তত একটি simulation বা load test-এ যাচাই করেছি
• Product-এর সীমা আর দাম অফিসিয়াল documentation-এ মিলিয়েছি