Uber / Maps Design - বৃষ্টির সন্ধ্যায় কাছের গাড়ি খোঁজা

০০ যে প্রশ্নগুলোর উত্তর খুঁজবো

Ride-hailing app এর কাজটা শুনতে খুব সহজ। একজন মানুষ গাড়ি চায়, কাছের একজন driver তাকে তুলে নেয়। কিন্তু “কাছের” শব্দটার পেছনে লুকিয়ে আছে এই সেশনের সবচেয়ে মজার সমস্যাগুলো। লাখো গাড়ি প্রতি মুহূর্তে জায়গা বদলাচ্ছে। তার মধ্যে কয়েক millisecond এ ঠিক মানুষটাকে খুঁজে বের করতে হবে।

এটাই এই কোর্সের শেষ সেশন, আর সবচেয়ে কঠিন design টাও। এখানে আগের প্রায় সবকিছু একসাথে কাজে লাগবে: Redis (সেশন ০৪), region ধরে shard (সেশন ০৫), index (সেশন ০৭), event (সেশন ১০), আর feed ও chat এর মতো real-time update (সেশন ২৫ ও ২৬)।

আমরা একটা কাল্পনিক ঢাকার app বানাবো, নাম “চলো”। এই stage এর বাকি case study র মতো এখানেও একই ক্রমে এগোবো: requirement, হিসাব, API আর data model, high-level design, তারপর গভীরে কয়েকটা অংশ, আর শেষে bottleneck।

০১ একটা ride-hailing app এর functional আর non-functional requirement কী?

শুক্রবার, সন্ধ্যা ৬টা ১০। তৃষা Banani র ১১ নম্বর রোডে অফিস থেকে বের হলো। আকাশ কালো হয়ে এসেছিলো, গেট পার হতেই ঝুম বৃষ্টি নামলো। মিরপুরে মা অপেক্ষা করছেন, আজ তাকে ডাক্তারের কাছে নিতে হবে। তৃষা মোবাইল বের করে “চলো” app খুললো। ঠিক একই মিনিটে Banani আর Gulshan এর আরো কয়েক হাজার মানুষ একই কাজ করলো।

তৃষার মাথায় তখন একটাই প্রশ্ন: “গাড়ি পাবো তো?” এই প্রশ্নের উত্তর দিতে system কে পেছনে কী কী করতে হয়, সেটাই আজকের গল্প।

Functional requirement: app কী কী করবে

Functional requirement মানে system কোন কোন কাজ করতে পারবে। “চলো” এর জন্য মূল কাজগুলো এই:

1. Driver এর location নেওয়া: Online প্রতিটা driver এর app কয়েক সেকেন্ড পরপর GPS থেকে নিজের অবস্থান পাঠায়।
2. কাছের গাড়ি দেখানো: তৃষা app খুললেই map এ আশেপাশের গাড়িগুলো দেখতে পায়।
3. Ride request আর matching: তৃষা pickup আর drop-off দিয়ে request পাঠায়। System একজন উপযুক্ত driver খুঁজে তাকে offer দেয়।
4. Trip track করা: Driver কোথায় আছে, কত মিনিটে আসবে (ETA), trip কোন অবস্থায় আছে, সবই তৃষা দেখতে পায়।
5. ভাড়া হিসাব: দূরত্ব, সময় আর চাহিদা দেখে ভাড়া ঠিক হয়।

Non-functional requirement: কাজগুলো কেমনভাবে করবে

Non-functional requirement মানে কাজগুলো কতটা দ্রুত, কতটা নির্ভরযোগ্যভাবে হবে।

• কম latency: Request পাঠানোর কয়েক সেকেন্ডের মধ্যে driver এর offer যাওয়া চাই। Map এর গাড়িগুলো যেন কয়েক সেকেন্ডের বেশি পুরোনো না হয়।
• উঁচু availability: বৃষ্টির সন্ধ্যাতেই app সবচেয়ে বেশি দরকার। ঠিক তখন app down হলে মানুষ রাস্তায় ভিজবে।
• Trip এর জন্য strong consistency: একজন driver কখনো একসাথে দুইটা trip পাবে না। একটা trip দুইজন driver কে দেওয়াও চলবে না।
• Location এর জন্য eventual consistency যথেষ্ট: Map এ রফিকের গাড়ি ৪ সেকেন্ড পুরোনো জায়গায় দেখালে কোনো ক্ষতি নেই। (Eventual consistency এর ধারণা সেশন ০৩ এ দেখেছেন।)

০২ প্রতি ৪ সেকেন্ডে driver location update এলে write load কত?

Design শুরুর আগে মোটা দাগে একটা হিসাব করে নিতে হয়। এর নাম back-of-envelope estimation: খামের পেছনে লেখা যায় এমন ছোট হিসাব, যা দিয়ে বোঝা যায় কোন অংশটা ভারী। (এই হিসাবের পুরো কৌশল সেশন ২৩ এ আছে।)

প্রথমে ঠিক করি, driver কত ঘনঘন location পাঠাবে। ঢাকার রাস্তায় একটা গাড়ি গড়ে ঘণ্টায় ৩০ km চললে প্রতি সেকেন্ডে প্রায় ৮ মিটার এগোয়। ৪ সেকেন্ড পরপর update এলে map এর গাড়ি বড়জোর ৩৩ মিটার পিছিয়ে থাকে। তৃষার চোখে সেটা প্রায় ধরাই পড়ে না। ১ সেকেন্ড পরপর পাঠালে write চার গুণ হতো, আর driver এর মোবাইলের ব্যাটারি আর data খরচও বাড়তো। তাই ৪ সেকেন্ড একটা ভালো মাঝামাঝি।

এবার শুক্রবার সন্ধ্যার ঢাকা ধরে হিসাবটা করি:

# ধরে নিই: ঢাকা, শুক্রবার সন্ধ্যা
online_drivers      = 100,000            # 1 লাখ
update_interval     = 4 s
update_size         = ~100 bytes         # driver_id, lat, lng, speed, heading, ts

# Write: location update
writes_per_sec      = 100,000 / 4        = 25,000 write/s
bandwidth           = 25,000 × 100 B     = 2.5 MB/s      # ~20 Mbps
updates_per_day     = 12,500/s × 86,400  ≈ 1.08 billion  # দিনে গড়ে 50,000 online
history_per_day     ≈ 1.08 billion × 100 B ≈ 108 GB      # সব ping জমালে

# শুধু latest location (memory তে)
latest_only         = 100,000 × 100 B    = 10 MB         # এক Redis এ সহজে ধরে

# Read: nearby driver (map এ গাড়ি দেখানো)
open_apps           = 300,000                            # বৃষ্টিতে app খোলা
reads_per_sec       = 300,000 / 5 s      = 60,000 read/s # প্রতি 5 s এ refresh

# তুলনা: ride request
requests_per_sec    = 40,000 / 3,600     ≈ 11 request/s  # পিক ঘণ্টায় 40,000
write_vs_request    = 25,000 : 11        ≈ 2,000 গুণ

হিসাবটা থেকে তিনটা জরুরি কথা বেরিয়ে আসে।

1. Location write ই সবচেয়ে ভারী কাজ: প্রতি সেকেন্ডে 25,000 write আসছে, অথচ ride request আসছে মাত্র ১১টা। এই system এর চাপের আসল উৎস তৃষারা নয়, driver দের মোবাইল।
2. সব ping চিরকাল রাখার দরকার নেই: Matching এর জন্য শুধু প্রতিটা driver এর সর্বশেষ location লাগে। সেটা মাত্র 10 MB, পুরোটা memory তে ধরে যায়। বাকি পুরোনো ping গুলো পরে traffic আর ETA হিসাবের জন্য সস্তা storage এ পাঠিয়ে দিলেই হয়।
3. Read ও কম নয়: বৃষ্টিতে তিন লাখ মানুষ app খুলে রাখলে প্রতি সেকেন্ডে 60,000 বার “আমার আশেপাশে কে আছে?” প্রশ্ন আসে।

০৩ API, data model আর high-level design দেখতে কেমন?

API আর data model

Driver app আর rider app server এর সাথে কয়েকটা সহজ API দিয়ে কথা বলে। Data কোথায় থাকবে, সেটা আগের হিসাব থেকেই ঠিক হয়ে গেছে:

# API: driver app
POST /v1/drivers/location        {lat, lng, speed, heading, ts}   ← প্রতি 4 s এ
POST /v1/trips/T-90412/accept                                        ← offer নিলে

# API: rider app
GET  /v1/drivers/nearby?lat=23.7937&lng=90.4043&radius=2km     ← map এর গাড়িগুলো
POST /v1/trips                   {pickup, dropoff} → {trip_id, state: "MATCHING"}
GET  /v1/trips/T-90412           → state, driver এর location, ETA

# Data model
driver_location  (Redis GEO, memory)   driver_id → (lat, lng), শুধু latest
driver           (SQL)                 driver_id, name, car_no, rating, status
trip             (SQL)                 trip_id, rider_id, driver_id, pickup, dropoff,
                                       state, fare, created_at, version
location_history (Kafka → cold store)  সব ping, পরে traffic আর ETA হিসাবের জন্য

খেয়াল করুন, driver এর location কোনো SQL table এ নেই। সেটা থাকে Redis এ, যেটা memory তে data রাখা একটা দ্রুত store (সেশন ০৪ এ cache হিসেবে চিনেছেন)। Redis এর GEO নামে একটা বিশেষ সুবিধা আছে, যা location রাখা আর কাছের জিনিস খোঁজার জন্যই বানানো। এটা কীভাবে কাজ করে, সেটা সেশনের ০৫ নম্বর অংশে দেখবো।

Trip এর data থাকে SQL database এ, কারণ সেখানে transaction আর durability দরকার। Durability মানে একবার লেখা data crash এর পরও হারায় না।

High-level design

তিনটা service তিনটা আলাদা দায়িত্ব নেয়:

• Location service: Driver দের 25,000 ping/s নেয়। প্রতিটা ping এ Redis GEO তে ঐ driver এর পুরোনো location মুছে নতুনটা বসায়। সাথে ping টা Kafka তে পাঠায়। Kafka হলো একটা distributed log, যেখানে event গুলো ক্রম অনুযায়ী জমা থাকে (সেশন ০৮ আর ১০)। পরে অন্য service গুলো সেখান থেকে পড়ে traffic এর গতি আর ETA হিসাব করে।
• Matching service: তৃষার request পেলে Redis GEO থেকে কাছের driver খোঁজে, ETA দেখে সেরা জনকে বাছে, আর offer পাঠায়।
• Trip service: Trip এর পুরো জীবন সামলায়, request থেকে ভাড়া কাটা পর্যন্ত। প্রতিটা ধাপ SQL database এ লেখে।

একটা ছোট বাস্তব সমস্যাও আছে। বৃষ্টিতে মোবাইল network দুর্বল হয়, তাই একটা পুরোনো ping নতুন ping এর পরে পৌঁছাতে পারে। এজন্য প্রতিটা ping এ timestamp থাকে। Location service আগে timestamp মিলিয়ে নেয়, আর পুরোনো ping এলে সেটা দিয়ে নতুন location overwrite করে না।

০৪ lat/lng এর উপর plain SQL query কেন slow?

প্রথমবার এই সমস্যা দেখলে সবার মাথায় একটা সহজ সমাধান আসে। Driver এর location একটা SQL table এ রাখি, আর এভাবে খুঁজি:

SELECT driver_id FROM driver_location
WHERE lat BETWEEN 23.7892 AND 23.7982
  AND lng BETWEEN 90.3994 AND 90.4092;     -- তৃষার চারপাশে ~1 km × 1 km

lat আর lng এ index দিলে তো দ্রুত হওয়ার কথা। (Index আর B-tree এর ধারণা সেশন ০৭ এ আছে।) কিন্তু এখানে একটা ফাঁদ আছে। Database একটা B-tree index দিয়ে সাধারণত একটাই range ভালোভাবে কাটতে পারে। ছবিতে দেখুন:

lat এর index নিলে database তৃষার latitude এর আশেপাশের সব driver বের করে, পূর্ব থেকে পশ্চিমে পুরো ঢাকা জুড়ে। প্রায় 4,500 row। তারপর একটা একটা করে lng মিলিয়ে দেখে, আর বেশিরভাগ row ফেলে দেয়। কাজে লাগে মাত্র 270 টা। (lat, lng) দিয়ে composite index বানালেও একই অবস্থা হয়। প্রথম column এ range থাকলে দ্বিতীয় column টা আর সাজানো অবস্থায় পাওয়া যায় না।

এবার এর সাথে আগের হিসাব মেলান। প্রতি সেকেন্ডে 60,000 query, প্রতিটায় হাজার হাজার row পড়া। সাথে প্রতি সেকেন্ডে 25,000 write, আর প্রতিটা write এ index এর B-tree ও আপডেট করতে হয়। Database এর CPU আর disk দুটোই তখন হাঁপিয়ে ওঠে।

০৫ Geohash কীভাবে কাছের driver খুঁজে দেয়?

Map কে খোপে ভাগ করা

একটা বড় দাবার বোর্ডের কথা ভাবুন, যেটা পুরো পৃথিবী ঢেকে রেখেছে। বোর্ডের প্রতিটা ঘরের একটা নাম আছে। এখন প্রতিটা ঘরকে আবার ৩২টা ছোট ঘরে ভাগ করুন। সেই ছোট ঘরগুলোকেও আবার ৩২ ভাগ করুন। এভাবে যত ভাগ করবেন, ঘর তত ছোট হবে।

Geohash ঠিক এই কাজটাই করে। প্রতিটা ভাগের নাম একটা অক্ষর, যা আসে ৩২টা চিহ্নের একটা তালিকা থেকে (0-9 আর কয়েকটা ইংরেজি অক্ষর)। এই তালিকাকে বলে base32। প্রতি ধাপে নামের শেষে একটা করে অক্ষর যোগ হয়। তৃষার Banani র ঘরের আসল geohash হলো wh0r35:

এর সবচেয়ে সুন্দর দিকটা হলো, নামের শুরুর অংশ এক হলে জায়গাও কাছাকাছি। wh0r35 (Banani) আর wh0r37 (Gulshan) দুটোই wh0r3 দিয়ে শুরু, কারণ দুটোই একই বড় ঘরের ভেতরে। মিরপুরের geohash wh0r2m, তাই সেটা wh0r2 এর ঘরে পড়ে।

এখন দুই মাত্রার location একটা সাধারণ string হয়ে গেলো। আর string সাজানোর কাজ যেকোনো সাধারণ index ভালোই পারে। wh0r35 দিয়ে শুরু হওয়া সব driver খুঁজে বের করা তখন একটা সাধারণ prefix search, যা খুব দ্রুত হয়।

ঘরের সীমানার সমস্যা

এবার একটা ফাঁদ। তৃষা দাঁড়িয়ে আছে Banani ঘরের একদম পূর্ব সীমানার কাছে। ঠিক ওপাশে, Gulshan এর ঘরে, জামালের গাড়ি:

শুধু wh0r35 দিয়ে খুঁজলে জামাল বাদ পড়ে যায়, যদিও সে মাত্র 300 m দূরে। দুইটা কাছের বিন্দু সীমানার দুই পাশে পড়লে তাদের নাম আলাদা হয়ে যায়। তাই geohash দিয়ে খোঁজার নিয়ম হলো: নিজের ঘর আর চারপাশের ৮টা ঘর, মোট ৯টা ঘর একসাথে খোঁজা। তারপর পাওয়া driver দের আসল দূরত্ব মেপে ছেঁকে নেওয়া।

বাস্তবে: Redis GEO

এই পুরো কাজটা নিজে লিখতে হয় না। Redis GEO ভেতরে geohash ব্যবহার করে, আর কাজটা দুইটা command এ সেরে দেয়:

# Driver এর ping এলে latest location overwrite হয় (আগে longitude, পরে latitude)
GEOADD drivers:dhaka 90.3960 23.7940 "D-7731"     # রফিক
GEOADD drivers:dhaka 90.4072 23.7940 "D-5120"     # জামাল

# তৃষা গাড়ি খুঁজলে: 2 km এর মধ্যে সবচেয়ে কাছের 10 জন
GEOSEARCH drivers:dhaka FROMLONLAT 90.4043 23.7937 BYRADIUS 2 km ASC COUNT 10 WITHDIST

1) "D-5120"  0.2955     # জামাল, ~300 m (লেকের ওপারে)
2) "D-7731"  0.8452     # রফিক, ~850 m (একই রাস্তায়)
...                     # আরো 8 জন, সব মিলিয়ে কয়েক ms

GEOADD একজন driver এর location বসায়। একই driver এর নতুন ping এলে পুরোনোটা মুছে নতুনটা বসে। GEOSEARCH তৃষার চারপাশে 2 km এর মধ্যে সবচেয়ে কাছের ১০ জনকে দূরত্ব সহ এনে দেয়। পুরো data memory তে থাকায় এটা কয়েক millisecond এ হয়ে যায়।

০৬ Quadtree কী, আর geospatial index হিসেবে কখন এটা ভালো?

Geohash এর একটা দুর্বলতা আছে। সব ঘরের মাপ সমান। Gulshan এ সন্ধ্যা ৬টায় একটা ঘরে ৪০০ জন driver থাকতে পারে, আর পূর্বাচলের একটা ঘরে হয়তো ২ জন। ভিড়ের ঘরে খুঁজলে অনেক বেশি driver আসে, আর ফাঁকা ঘরে খুঁজলে কেউই আসে না।

Quadtree এই সমস্যার সমাধান করে ভিন্নভাবে। এর নিয়ম একটাই: একটা ঘরে driver একটা সীমার বেশি হলে ঘরটা সমান ৪ ভাগ হয়। (“Quad” মানে চার।) ভাগ হওয়া ঘরেও ভিড় বেশি থাকলে সেটা আবার ৪ ভাগ হয়। ছবিতে সীমা ধরা হয়েছে ৪ জন, যাতে সহজে দেখা যায়:

ফলাফলটা দেখুন। Gulshan এর মতো ভিড়ের জায়গায় ঘরগুলো ছোট ছোট হয়ে গেছে। ফাঁকা এলাকা একটা বড় ঘরেই রয়ে গেছে। ফলে প্রতিটা ঘরে driver এর সংখ্যা মোটামুটি সমান থাকে। কাছের driver খুঁজতে tree এর উপর থেকে নিচে নামতে হয়: শহর থেকে ভাগ, ভাগ থেকে উপভাগ, যতক্ষণ না তৃষার ঘরে পৌঁছানো যায়।

০৭ Matching কীভাবে হয়, আর ETA কেন দূরত্বের চেয়ে জরুরি?

তৃষা request পাঠালো। এখন কাছের driver দের মধ্য থেকে একজনকে বেছে trip টা তাকে দিতে হবে। এই কাজের নাম matching। পুরো কাজটা চারটা ধাপে হয়:

কেন দূরত্ব দিয়ে নয়, ETA দিয়ে

ধাপ ২ এ Redis বললো জামাল সবচেয়ে কাছে, মাত্র 300 m। তাহলে জামালকেই offer দিই না কেন? কারণ মাঝখানে একটা লেক:

ETA (Estimated Time of Arrival) মানে driver কত মিনিটে pickup এ পৌঁছাবে। এটা হিসাব করতে system ঢাকার রাস্তাগুলোকে একটা graph হিসেবে দেখে। প্রতিটা মোড় একটা node, আর দুই মোড়ের মাঝের রাস্তা একটা edge। প্রতিটা edge এর ওজন হলো ঐ রাস্তা পার হতে এই মুহূর্তে কত সময় লাগে।

এই সময়টা আসে driver দেরই ping থেকে। Kafka তে জমা ping দেখে বোঝা যায়, Banani র কোন রাস্তায় গাড়িগুলো এখন ঘণ্টায় মাত্র ৮ km বেগে চলছে। তারপর graph এ সবচেয়ে কম সময়ের পথ খোঁজা হয় (Dijkstra এর মতো shortest path algorithm দিয়ে, যেটা algorithm ক্লাসে পড়েছেন)। প্রতিটা request এ পুরো শহরের graph ঘাঁটা ধীর, তাই বাস্তবে বড় রাস্তাগুলোর পথ আগে থেকে হিসাব করে রাখা হয়।

একই driver যেন দুইজনকে না পায়

ধাপ ৪ এর “lock” অংশটা খুব জরুরি। ঠিক একই সময়ে Banani র আরেকজন rider ও রফিককে খুঁজে পেতে পারে। দুইজনকেই রফিকের কাছে offer পাঠালে একজন নিশ্চিতভাবে হতাশ হবে।

তাই offer পাঠানোর আগে matching service রফিকের নামে Redis এ একটা lock বসায়: SET lock:driver:D-7731 T-90412 NX EX 15। NX মানে key টা আগে না থাকলেই বসবে। তাই দুইজন একসাথে চেষ্টা করলে শুধু একজন সফল হয়। EX 15 মানে ১৫ সেকেন্ড পর lock নিজে থেকেই মুছে যাবে। রফিক সাড়া না দিলে সে আটকে থাকবে না। আরেকটা উপায় হলো প্রতিটা এলাকার matching এর দায়িত্ব একটাই server কে দেওয়া, যাকে বলে leader। Leader কীভাবে বাছা হয়, সেটা সেশন ১৬ এ দেখবো।

০৮ Trip state machine কেন দরকার?

রফিক accept করলো। তৃষার screen এ রফিকের নাম, গাড়ির নম্বর আর “৪ মিনিটে আসছে” দেখাচ্ছে। এখান থেকে trip টা অনেকগুলো ধাপ পার হবে। প্রতিটা ধাপে তৃষা, রফিক বা system নিজে কিছু একটা করতে পারে। কোন অবস্থায় কোন কাজ চলবে, সেটা একটা নিয়মে বাঁধা না থাকলে গোলমাল হবেই।

এই নিয়মকে বলে trip state machine। Trip সবসময় নির্দিষ্ট কয়েকটা অবস্থার (state) একটায় থাকে। আর এক state থেকে অন্য state এ যাওয়ার পথগুলো আগে থেকে ঠিক করা:

State machine কয়েকটা বিপদ সরাসরি আটকে দেয়:

• অসম্ভব ধাপ আটকানো: COMPLETED trip আবার cancel করা যায় না। ON_TRIP অবস্থায় আরেকজন driver accept করতে পারে না। কারণ ছবিতে এমন কোনো পথই নেই।
• একই মুহূর্তের দুইটা কাজ সামলানো: ধরুন রফিক যে মুহূর্তে accept চাপলো, ঠিক সেই মুহূর্তে বিরক্ত হয়ে তৃষা cancel চাপলো। দুইটা কাজই trip এর state বদলাতে চায়।

দ্বিতীয় সমস্যার সমাধান একটা শর্তসহ update। Trip service লেখে: UPDATE trip SET state = 'ACCEPTED', driver_id = 'D-7731' WHERE trip_id = 'T-90412' AND state = 'MATCHING'। Database এই কাজটা একবারে করে। তাই দুইটা update এর মধ্যে যে আগে পৌঁছায়, সেটাই সফল হয়। পরেরটা দেখে state আর MATCHING নেই, তাই ০টা row বদলায়। Service তখন বুঝে নেয় যে সে দেরি করে ফেলেছে, আর রফিককে জানায় “trip টা cancel হয়ে গেছে”।

প্রতিবার state বদলালে trip service একটা event পাঠায়, যেমন trip.accepted বা trip.completed। Notification service সেটা দেখে তৃষাকে push পাঠায়। Payment service ভাড়া কাটে। Analytics সংখ্যা গোনে। কেউ কাউকে সরাসরি ডাকে না, সবাই event শোনে। (Event-driven ধারণাটা সেশন ১০ এ বিস্তারিত আছে।)

০৯ Hot area (Gulshan, সন্ধ্যা ৬টা) আর surge pricing কীভাবে সামলাবো?

Hot area: এক জায়গায় সব ভিড়

“চলো” যখন সারা দেশে ছড়ালো, তখন একটা Redis আর সব query সামলাতে পারলো না। Data মাপে ছোট, কিন্তু প্রতি সেকেন্ডে লাখো GEOSEARCH এক machine এর CPU র জন্য বেশি। তখন data কে এলাকা অনুযায়ী ভাগ করা হলো: wh0r3 এর সব driver এক shard এ, wh0r2 এর সব driver আরেক shard এ। (Shard আর shard key এর ধারণা সেশন ০৫ এ আছে।) এলাকা দিয়ে ভাগ করা যুক্তিসঙ্গত, কারণ nearby query প্রায় সবসময় একটা এলাকার ভেতরেই থাকে।

কিন্তু শুক্রবার সন্ধ্যা ৬টায় পুরো ঢাকার ভিড় এসে জমে Banani আর Gulshan এ। অফিস ছুটি, বৃষ্টি, সবাই একসাথে গাড়ি খুঁজছে। ঐ একটা shard এর উপর তখন সব চাপ। একেই সেশন ০৫ এ hot key বলেছিলাম। এখানে key টা একটা এলাকা, তাই একে hot area বলা যায়।

এর তিনটা প্রতিকার একসাথে কাজ করে:

1. Hot ঘরকে ভেঙে দেওয়া: wh0r3 কে ছোট ঘরে (wh0r35, wh0r37) ভেঙে আলাদা shard এ পাঠানো। Quadtree ঠিক এই কাজটাই নিজে থেকে করে।
2. Nearby result cache করা: Banani র একই ঘর থেকে প্রতি সেকেন্ডে শত শত মানুষ “আশেপাশে কে আছে?” জিজ্ঞেস করে। প্রত্যেকের জন্য আলাদা করে খোঁজার দরকার নেই। এক ঘরের result ২ সেকেন্ডের জন্য cache করলে বেশিরভাগ query সেখান থেকেই উত্তর পায় (cache এর TTL সেশন ০৪ এ আছে)।
3. Read আর write আলাদা রাখা: Location write যায় primary তে, map দেখানোর read যায় replica তে (সেশন ০৩)। Map এর গাড়ি এক সেকেন্ড পিছিয়ে থাকলেও তৃষার কিছু যায় আসে না।

Surge pricing: চাহিদা আর জোগানের হিসাব

Server এর সমস্যা মিটলো, কিন্তু আসল সমস্যা রয়ে গেলো। ৬টা ১০ এ Banani র ঘরে গত ৫ মিনিটে request এসেছে ২৪০টা। খালি driver আছে মাত্র ৪০ জন। Server যত দ্রুতই হোক, ২০০ জন মানুষ গাড়ি পাবে না।

Surge pricing এই অসমতা কমানোর চেষ্টা করে। প্রতি মিনিটে, প্রতিটা ঘরের জন্য, system চাহিদা আর জোগানের অনুপাত হিসাব করে। অনুপাত বেশি হলে ঐ ঘরে ভাড়া কিছুটা বাড়ে:

বাড়তি ভাড়া দুই দিক থেকে কাজ করে। আশেপাশের এলাকার driver রা Banani র দিকে আসতে আগ্রহী হয়, তাই জোগান বাড়ে। আর যার যাওয়াটা অতটা জরুরি নয়, সে আধা ঘণ্টা অপেক্ষা করে, তাই চাহিদা কিছুটা কমে। তৃষার জন্য ভাড়াটা গায়ে লাগে। কিন্তু মা অপেক্ষা করছেন, তাই সে ৫৭৬ টাকাতেই রাজি হয়। Surge না থাকলে হয়তো গাড়িই পেতো না।

Surge এর হিসাবও আসে সেই Kafka stream থেকে। একটা service প্রতিটা ঘরের request আর খালি driver গুনতে থাকে, আর প্রতি মিনিটে গুণক আপডেট করে।

১০ মগজে প্রেশার দিন

আগে নিজে ভাবুন। তারপর উত্তর খুলে দেখুন: বেশিরভাগ মানুষ কীভাবে ভাবে, সেই চিন্তায় কী বাদ পড়ে, আর আসল কথাটা কোথায়।

১১ যে টার্মগুলো শিখলাম

১২ শর্ট সামারি

১৩ মনে রাখুন

• আগে হিসাব, পরে design। Write load এর হিসাবটাই বলে দিলো location কোথায় রাখতে হবে।
• দ্রুত বদলানো data আর টাকার data আলাদা রাখুন। Location memory তে, trip SQL database এ।
• Location এর জন্য geospatial index লাগে। lat আর lng এর আলাদা index পুরো শহর ঘাঁটে।
• Geohash এ সবসময় ৯টা ঘর খুঁজুন। সবচেয়ে কাছের driver সীমানার ওপারে থাকতে পারে।
• দূরত্ব নয়, ETA দিয়ে বাছুন। লেক আর জ্যাম সোজা দূরত্বের হিসাব উল্টে দেয়।
• Trip এর প্রতিটা ধাপ state machine আর শর্তসহ update দিয়ে বাঁধুন। তাহলে একই মুহূর্তের দুইটা কাজের একটাই সফল হয়।
• Hot area তে শুধু server বাড়ানো যথেষ্ট নয়। ঘর ভাঙুন, cache করুন, আর surge দিয়ে চাহিদা ও জোগান মেলান।

১৪ যাত্রার শেষে

আজকের design এ একটু খেয়াল করলে দেখবেন, সত্যিকারের নতুন জিনিস খুব কম ছিলো। Geohash আর quadtree নতুন। কিন্তু driver এর location রাখা হয়েছে Redis এ (সেশন ০৪), শহর ভাগ হয়েছে region ধরে shard করে (সেশন ০৫), Gulshan এর ভিড় সামলানো হয়েছে hot key এর কৌশলে (সেশন ০৫), আর trip এর প্রতিটা ধাপ event হয়ে অন্য service এ গেছে (সেশন ১০)। নতুন design মানে বেশিরভাগ সময় পুরোনো টুকরোগুলোকে নতুনভাবে জোড়া দেওয়া।

সেশন ০১ এ আমরা শুরু করেছিলাম একটা ছোট প্রশ্ন দিয়ে: একটা server এ আর না কুলালে কী করবো? সেখান থেকে load balancer, replica, cache, shard, queue পার হয়ে আমরা consensus, saga আর chaos engineering পর্যন্ত এসেছি। তারপর একটা ছোট URL shortener দিয়ে শুরু করে feed, chat আর YouTube পেরিয়ে আজ এলাম বৃষ্টির সন্ধ্যায় তৃষার জন্য কাছের গাড়ি খোঁজায়।

এই কোর্স শেষ করে আপনি হয়তো এখনো রাত তিনটায় কোনো alert পাননি। কোনো দিন পাবেন। সেদিন আপনিও log খুলে বসবেন, একটু ভয় পাবেন, তারপর মনে পড়বে: “এটা তো আগে দেখেছি। এটা একটা bottleneck। এর জন্য cache আছে, queue আছে, rate limiter আছে।” প্রতিটা system design আসলে একটাই প্রশ্নের উত্তর: কোথায় চাপ পড়বে, আর সেই চাপ কে সামলাবে। প্রশ্নটা আপনি এখন জানেন।

Interview এর টেবিলে বা প্রথম চাকরির প্রথম on-call রাতে এই সেশনগুলো আপনার পাশে থাকুক। এত দূর সাথে থাকার জন্য অনেক ধন্যবাদ। শুভ যাত্রা।