Case Study: News Feed (Facebook ধরনের)

Fan-out, ranking, celebrity সমস্যা

রোডম্যাপের মাস ১১পড়তে প্রায় ৭ মিনিট

Facebook খুললে প্রথমে যা দেখো, সেই feed এর পেছনে system design এর একটা ক্লাসিক সমস্যা: তুমি ৫০০ জনকে follow করো, প্রত্যেকে দিনে কয়েকটা post দেয়, আর app খোলার ৩০০ ms এর মধ্যে তোমার জন্য সাজানো সর্বশেষ post গুলো দেখাতে হবে। আর কিছু মানুষের (celebrity) লাখো follower। এই case study র মূল বিষয় fan-out। (শেখার জন্য design, আসল Facebook এর ব্যবস্থা না।)

#ধাপ ১: Requirement

Functional:

  • Post (লেখা, ছবি, video), যাদের follow করো তাদের post এর feed
  • Like, comment (feed এ সংখ্যা দেখায়)
  • Feed: সর্বশেষ বা গুরুত্ব অনুযায়ী সাজানো, infinite scroll
  • নতুন post এর খবর

Non-functional:

  • Feed load: p95 < ৩০০ ms
  • নতুন post বন্ধুদের feed এ কয়েক সেকেন্ডে পৌঁছালেই চলে (eventual consistency)
  • বিশাল read: feed দেখা post করার চেয়ে অনেক বেশি
  • Celebrity এর post ও যেন system ডুবিয়ে না দেয়

#ধাপ ২: Estimation

  • DAU ১০ কোটি; প্রতিজন দিনে ২টা post → ২০ কোটি post/দিন (~২,৩০০/সেকেন্ড)
  • প্রতিজন দিনে ১০ বার feed খোলে → ১০০ কোটি feed read/দিন (~১১,৫০০/সেকেন্ড, peak অনেক বেশি)
  • গড় ২০০ জন follower; কিছু account এর ১ কোটির বেশি

সিদ্ধান্ত: Read অনেক বেশি, তাই feed আগে থেকে তৈরি রাখা লাভজনক। কিন্তু celebrity দের জন্য আলাদা কৌশল লাগবে।

#ধাপ ৩: API

HTTP
POST /v1/posts                  {text, media_keys[]}  (Idempotency-Key)
GET  /v1/feed?cursor=...&limit=20
POST /v1/posts/{id}/likes
GET  /v1/posts/{id}/comments?cursor=...

#ধাপ ৪: Data

Data কোথায়
User, follow সম্পর্ক SQL বা graph store; followers(user_id) আর following(user_id) দুই দিকে
Post Wide-column/sharded SQL, author_id দিয়ে ভাগ
প্রতি user এর feed (post id এর তালিকা) Redis sorted set (score = সময় বা rank), সর্বশেষ ৫০০টা
Like/comment এর সংখ্যা Counter (Redis/আলাদা table), denormalized
Media Object storage + CDN

#ধাপ ৫: Fan-out এর দুই পদ্ধতি

Fan-out on write (push) Rahim post দিলো বন্ধু ১ এর feed বন্ধু ২ এর feed ... ২০০ জনের পড়া: শুধু নিজের তৈরি feed (দ্রুত) লেখা: follower এর সংখ্যা গুণ কাজ celebrity: ১ কোটি feed এ লেখা! Fan-out on read (pull) আমি feed খুললাম বন্ধু ১ এর post বন্ধু ২ এর post ... ৫০০ জনের লেখা: শুধু একবার (সস্তা) পড়া: ৫০০ জনের post আনা, মেলানো প্রতিবার feed খুলতে ধীর
Push এ পড়া সস্তা কিন্তু লেখা ব্যয়বহুল; pull এ উল্টো। বাস্তবে দুটোর মিশ্রণ।

#মিশ্র (hybrid) পদ্ধতি

  • সাধারণ user (কয়েকশো follower): post দিলে push — queue হয়ে worker রা প্রতিটা follower এর feed (Redis sorted set) এ post id যোগ করে
  • Celebrity (ধরো ১ লাখের বেশি follower): push না। তাদের post আলাদা জায়গায় থাকে
  • Feed পড়ার সময়: নিজের তৈরি feed + যে celebrity দের follow করো তাদের সর্বশেষ post (pull) → মিলিয়ে সাজাও
  • নিষ্ক্রিয় user (মাসে একবারও আসে না): তাদের feed এ push করা অপচয়; ফিরে এলে pull করে তৈরি
Post service Queue Fan-out worker সাধারণ user হলে push Feed cache user → post id Post store celebrity এর post সহ Feed service cache + celebrity মিলিয়ে, rank করে
সাধারণ user এর post আগে থেকে feed এ ঢোকে; celebrity এর post পড়ার সময় যোগ হয়।

#ধাপ ৬: Deep dive

#Feed পড়ার flow

  1. Redis থেকে user এর feed এর সর্বশেষ ২০০টা post id (cursor অনুযায়ী)
  2. Follow করা celebrity দের সর্বশেষ post id যোগ
  3. Ranking (নিচে) করে প্রথম ২০টা
  4. Post এর বিস্তারিত (লেখা, author, media URL, like সংখ্যা) batch করে আনা (cache থেকে, N+1 এড়িয়ে)
  5. Block বা মুছে ফেলা post বাদ, privacy যাচাই (শুধু বন্ধুদের জন্য post)
  6. next_cursor সহ ফেরত

#Ranking

সর্বশেষ আগে (chronological) সবচেয়ে সহজ। গুরুত্ব অনুযায়ী সাজাতে প্রতিটা প্রার্থী post এর স্কোর: কতটা ঘনিষ্ঠ সম্পর্ক, post এর বয়স, কতজন like/comment করছে, ধরন (ছবি/video), অতীতে এই user কী ধরনের post এ সাড়া দেয়। বড় system এ এটা ML model, দুই ধাপে: হাজার প্রার্থী থেকে সস্তা model এ কয়েকশো, তারপর ভারী model এ চূড়ান্ত সাজানো।

#Like এর সংখ্যা

জনপ্রিয় post এ প্রতি সেকেন্ডে হাজার like; প্রতিটা UPDATE posts SET likes = likes + 1 একটা row এ বিশাল lock এর চাপ।

  • Like এর রেকর্ড আলাদা table এ (কে like করলো, unique), সংখ্যা আলাদা counter এ
  • Counter Redis এ INCR, আর কিছুক্ষণ পর পর database এ batch করে লেখা (write-behind; গ্রহণযোগ্য, কারণ like এর সংখ্যা কয়েক সেকেন্ড পিছিয়ে থাকলে ক্ষতি নেই)
  • আরও বড় হলে counter কে কয়েক টুকরোয় ভাগ (sharded counter), পড়ার সময় যোগ

#নতুন post এর খবর

Feed খোলা থাকলে নিজে থেকে list লাফানো খারাপ অভিজ্ঞতা। "১২টা নতুন post" এর ব্যানার, user চাপলে উপরে যোগ। এর জন্য হালকা polling বা SSE যথেষ্ট।

#মুছে ফেলা, privacy আর edit

Push করা feed এ post id ছড়িয়ে আছে লাখো জায়গায়। মুছে ফেললে সব জায়গা থেকে সরানোর বদলে পড়ার সময় যাচাই করে বাদ দেওয়া (post store এ deleted চিহ্ন) সহজ আর নির্ভরযোগ্য। একই নিয়ম block আর privacy পরিবর্তনে।

#অনুশীলন

#নিজেকে যাচাই করো

Fan-out on write এর মূল দুর্বলতা কী, আর কোথায় সবচেয়ে বেশি দেখা যায়?

লেখার খরচ follower এর সংখ্যার সমান। লাখো follower এর celebrity এর একটা post এ লাখো feed এ লিখতে হয়, যা ধীর আর ব্যয়বহুল।

Hybrid পদ্ধতিতে celebrity এর post feed এ কীভাবে আসে?

Push করা হয় না। Feed পড়ার সময় feed service user এর follow করা celebrity দের সর্বশেষ post আলাদাভাবে এনে আগে থেকে তৈরি feed এর সাথে মিলিয়ে সাজায়।

জনপ্রিয় post এর like count সরাসরি database row এ বাড়ালে কী সমস্যা, আর সমাধান?

একটা row এ হাজার হাজার একসাথে update, lock এর জন্য অপেক্ষা আর ধীরতা। সমাধান: Redis counter আর batch করে database এ লেখা, দরকারে counter কে কয়েক টুকরোয় ভাগ।

চিহ্ন দিলে sidebar আর রোডম্যাপে এই অধ্যায়ের station ভরে যাবে।