Business Systems১৩ মিনিট পাঠ

রাইড শেয়ারিং সার্ভিস ডিজাইন

যাত্রীদের রিয়েল-টাইমে কাছাকাছি চালকদের সাথে ম্যাচ করানো — বিশাল স্কেলে

scope:রিয়েল-ওয়ার্ল্ড সিস্টেম (Real-World System)difficulty:অ্যাডভান্সড (Advanced)

সমস্যাটি বোঝা (Understanding the Problem)

উবার (Uber) বা লিফটের (Lyft) কথা চিন্তা করুন — একজন রাইডার বা যাত্রী অ্যাপ খোলেন, রাইডের জন্য রিকোয়েস্ট করেন এবং কয়েক সেকেন্ডের মধ্যেই কাছাকাছি থাকা একজন ড্রাইভার ম্যাচ হয়ে যান এবং রওনা দেন। চলুন এর ব্যাকএন্ড (Backend) ডিজাইন করি যা এত দ্রুত এই কাজটি সম্পন্ন করে।

ফাংশনাল প্রয়োজনীয়তা (Functional Requirements):

রাইড রিকোয়েস্ট করা (Request a ride): রাইডার পিকআপ (Pickup) এবং ড্রপঅফ (Dropoff) লোকেশন নির্দিষ্ট করবেন।
ড্রাইভার ম্যাচ করা (Match a driver): কাছাকাছি থাকা সহজলভ্য ড্রাইভার খুঁজে বের করা এবং এই রাইডের জন্য তাকে বরাদ্দ করা।
রাইড ট্র্যাক করা (Track the ride): ট্রিপ চলাকালীন রাইডার এবং ড্রাইভার উভয়ের জন্যই রিয়েল-টাইম লোকেশন ট্র্যাকিং।
পেমেন্ট প্রসেস করা (Process payment): ট্রিপ শেষ হওয়ার পর ভাড়া হিসাব করা এবং রাইডারের কাছ থেকে পেমেন্ট নেওয়া।

নন-ফাংশনাল প্রয়োজনীয়তা (Non-Functional Requirements):

লো ম্যাচিং ল্যাটেন্সি (Low matching latency): রিকোয়েস্ট করার ৫ সেকেন্ডের চেয়ে কম সময়ের মধ্যে ড্রাইভার ম্যাচ হতে হবে। রাইডাররা অপেক্ষা করতে পছন্দ করেন না।
রিয়েল-টাইম লোকেশন ট্র্যাকিং (Real-time location tracking): ড্রাইভাররা প্রতি ৪ সেকেন্ডে জিপিএস (GPS) রিপোর্ট করবেন। রাইডারের ম্যাপে আপডেটগুলো তাৎক্ষণিকভাবে প্রতিফলিত হতে হবে।
পিক ডিমান্ড সামলানো (Handle peak demand): শুক্রবার রাত, কনসার্টের সময়, বা বৃষ্টির দিন — চাহিদা ৫-১০ গুণ বেড়ে যেতে পারে। সিস্টেমকে অবশ্যই এই সার্জ (Surge) বা হুট করে বেড়ে যাওয়া চাহিদা সুন্দরভাবে সামলাতে হবে।
উচ্চ প্রাপ্যতা (High availability): ৯৯.৯৯% আপটাইম (Uptime)। রাইড সার্ভিসের ডাউনটাইম মানে রাইডার আটকে পড়া এবং ব্যবসার ক্ষতি।

▸ মূল ধারণা: রাইডারের রিকোয়েস্ট → কাছাকাছি ড্রাইভারের সাথে ম্যাচ → রাইড

অ্যাস্টিমেশন (Estimation)

চলুন উবারের (Uber) মতো স্কেলের নাম্বার দিয়ে এই সিস্টেমের সাইজ অনুমান করি:

প্রতিদিন ২০ মিলিয়ন রাইড → গড়ে ~২৩০ রাইড/সেকেন্ড, পিকে (Peak) ~১,০০০/সেকেন্ড
৫ মিলিয়ন কনকারেন্ট (Concurrent) বা অ্যাক্টিভ ড্রাইভার যারা প্রতি ৪ সেকেন্ডে লোকেশন রিপোর্ট করেন
লোকেশন அபডেট থ্রুপুট (Location update throughput): ৫ মিলিয়ন / ৪ = প্রতি সেকেন্ডে ১.২৫ মিলিয়ন লোকেশন আপডেট
ম্যাচিং ল্যাটেন্সি টার্গেট (Matching latency target): ৫ সেকেন্ডের মধ্যে একজন ড্রাইভার খুঁজে বের করা এবং অ্যাসাইন করা
প্রতি আপডেটে লোকেশন ডেটা: driver_id (8B) + lat/lng (16B) + timestamp (8B) + metadata (32B) ≈ ৬৪ বাইট
লোকেশন ব্যান্ডউইথ (Location bandwidth): ১.২৫ মিলিয়ন × ৬৪ বাইট = র (Raw) লোকেশন ডেটার জন্য ~৮০ MB/সেকেন্ড

এখানকার সবচেয়ে বড় চ্যালেঞ্জটি হলো জিওম্প্যাশিয়াল ইনডেক্সিং (Geospatial indexing) — মিলিয়ন মিলিয়ন চলন্ত বস্তুর মধ্যে প্রদত্ত একটি পিকআপ পয়েন্টের কাছে কোন ড্রাইভার অবস্থান করছেন, তা দক্ষতার সাথে খুঁজে বের করা।

এপিআই ডিজাইন (API Design)

রাইড রিকোয়েস্ট করা (Request a Ride)

Endpoint	`POST /api/v1/rides`
Request	`{"rider_id": "r123", "pickup": {"lat": 37.77, "lng": -122.42}, "dropoff": {"lat": 37.79, "lng": -122.40}, "ride_type": "standard"}`
Response	`{"ride_id": "ride_456", "status": "matching", "eta": 180}`

ড্রাইভারের লোকেশন আপডেট করা (Update Driver Location)

Endpoint	`PUT /api/v1/drivers/:id/location`
Request	`{"lat": 37.78, "lng": -122.41, "heading": 90, "speed": 25}`
Note	অ্যাক্টিভ ড্রাইভারদের থেকে প্রতি ৪ সেকেন্ডে ওয়েবসকেটের (WebSocket) মাধ্যমে পাঠানো হয়

রাইড ট্র্যাক করা (Track a Ride)

Endpoint	`GET /api/v1/rides/:id`
Response	`{"ride_id": "ride_456", "status": "in_progress", "driver_location": {"lat": 37.78, "lng": -122.41}, "eta": 120}`

রাইড কমপ্লিট করা (Complete a Ride)

Endpoint	`POST /api/v1/rides/:id/complete`
Response	`{"ride_id": "ride_456", "fare": 24.50, "distance_km": 8.2, "duration_min": 18}`

▸ ড্রাইভার ম্যাচ করা: জিওস্প্যাশিয়াল সার্চ (Geospatial search)

Click chart to zoom

রাইড রিকোয়েস্ট ফ্লো: রাইড সার্ভিস লোকেশন সার্ভিসের কাছে কাছাকাছি ড্রাইভারদের ব্যাপারে জিজ্ঞাসা করে, এরপর সবচেয়ে ভালো ম্যাচ খুঁজে বের করে এবং ড্রাইভারকে নোটিফাই করে

▸ লোকেশন ট্র্যাকিং: রিয়েল-টাইম জিপিএস আপডেট

জিওস্প্যাশিয়াল ইনডেক্সিং (Geospatial Indexing)

এটি সিস্টেমের প্রাণকেন্দ্র। আপনি কীভাবে খুঁজে বের করবেন যে ৫ মিলিয়ন ড্রাইভারের মধ্যে কারা পিকআপ পয়েন্টের ৩ কিলোমিটারের মধ্যে আছেন?

অ্যাপ্রোচ বা পদ্ধতি: জিওহ্যাশ (Geohash) / কোয়াডট্রি (QuadTree)

ভিওহ্যাশ এনকোডিং (geohash encoding) ব্যবহার করে পৃথিবীর পৃষ্ঠকে সেল (Cell) বা কোষের একটি গ্রিডে (Grid) ভাগ করুন। প্রতিটি সেল একটি স্ট্রিং প্রিফিক্স (String prefix) পায় (যেমন, সান ফ্রান্সিসকোর জন্য 9q8yy)।
ড্রাইভারদের তাদের জিওহ্যাশ প্রিফিক্স অনুযায়ী ইনডেক্স করা হয়। কাছাকাছি ড্রাইভার খুঁজে বের করা = বর্তমান সেলটি + আশপাশের আটটি সেল অনুসন্ধান করা (সেল বর্ডারের আশেপাশের সমস্যা সামলাতে)।
একটি কোয়াডট্রি (QuadTree) হলো এর বিকল্প: ম্যাপটি বারবার ভাগ করে চতুর্ভুজ বা কোয়াড্রেন্ট (quadrants) অংশে ভাগ করুন। ঘনবসতিপূর্ণ জায়গা (শহর)-কে বেশি ভাগ করা হয় এবং গ্রাম্য জায়গাগুলোতে কম ভাগ করা হয়। ড্রাইভারের অসম বণ্টনের ক্ষেত্রে এটি অত্যন্ত কার্যকরী।

লোকেশন আপডেট (Location Updates):

ড্রাইভাররা অবিচ্ছিন্ন ওয়েবসকেট (WebSocket) সংযোগের মাধ্যমে প্রতি ৪ সেকেন্ডে জিপিএস কোঅর্ডিনেটগুলো (GPS coordinates) পাঠান।
প্রতিটি আপডেট ড্রাইভারের জিওহ্যাশ পুনরায় ক্যালকুলেট করে। যদি জিওহ্যাশ পরিবর্তিত হয়, তবে ড্রাইভারকে ইনডেক্সের নতুন সেলে সরানো হয়।
লোকেশন ইনডেক্সটি ইন-মেমোরিতে (in-memory) (যেমন Redis অথবা একটি কাস্টম ইন-মেমোরি স্টোর) অবস্থান করে যাতে এক মিলিসেকেন্ডেরও কম সময়ে খোঁজার কাজ সম্পন্ন করা যায়। হট পাথ (Hot path)-এর ওপর কোনো ডিস্ক ইনপুট/আউটপুট (Disk I/O) নেই।

কেন একটি ট্র্যাডিশনাল ডেটাবেস কোয়েরি নয়? প্রতি সেকেন্ডে ৫ মিলিয়ন সারির ওপর SELECT * WHERE distance(lat, lng, pickup_lat, pickup_lng) < 3km চালানো হলে যেকোনো ডেটাবেস থমকে যাবে বা কাজ করা বন্ধ করে দেবে। জিওহ্যাশ একটি ব্যাসার্ধ (Radius) কোয়েরিকে সাধারণ প্রিফিক্স লুকআপে (Prefix lookup) রূপান্তর করে — যা কয়েক গুণ দ্রুত।

▸ পূর্ণাঙ্গ আর্কিটেকচার (Full architecture)

সার্জ প্রাইসিং, ইটিএ এবং অ্যানালিটিক্স (Surge Pricing, ETA, and Analytics)

সার্জ প্রাইসিং (Surge Pricing):

শহরটিকে বিভিন্ন জোনে বা অংশে ভাগ করুন। রিয়েল-টাইমে প্রতিটি জোনের চাহিদা বা সাপ্লাই রেশিও (supply/demand ratio) ট্র্যাক করুন।
যখন একটি জোনে চাহিদা (রাইড রিকোয়েস্ট) সাপ্লাইয়ের (সহজলভ্য ড্রাইভার) চেয়ে বেশি হয়, তখন একটি সার্জ মাল্টিপ্লায়ার (Surge multiplier) প্রয়োগ করুন (১.৫x, ২x, ইত্যাদি)।
এটি দুইটি কাজ করে: কম-অগ্রাধিকারের (low-priority) রাইডগুলোকে নিরুৎসাহিত করে এবং ড্রাইভারদের বেশি চাহিদাসম্পন্ন জোনে বা অংশে যেতে অনুপ্রাণিত করে।

ইটিএ অ্যাস্টিমেশন বা আগমনের সম্ভাব্য সময় অনুমান (ETA Estimation):

রাস্তার নেটওয়ার্কটিকে একটি ওয়েটেড গ্রাফ (weighted graph) হিসেবে মডেল করুন (ছেদগুলো বা মোড়গুলো (intersections) = নোড, রাস্তা = এজ (edges), ওজন = যাতায়াতের সময়)।
সবচেয়ে ছোট পথ নির্ণয় করার জন্য ডাইকস্ট্রা (Dijkstra) অ্যালগরিদম বা A* (A-স্টার) ব্যবহার করুন। সাধারণ রুটগুলো আগ থেকেই ক্যালকুলেট বা প্রি-কম্পিউট (Pre-compute) করে রাখুন।
গতিশীলভাবে এজের (Edge) ওজন অ্যাডজাস্ট বা পরিবর্তন করার জন্য রিয়েল-টাইম ট্রাফিক ডেটা ইনক্লুড করুন।

ট্রিপ স্টোর (Trip Store):

প্রতিটি কমপ্লিট হওয়া ট্রিপ বিলিং (Billing), অভিযোগ সমাধান, ড্রাইভার রেটিং এবং অ্যানালিটিক্সের (Analytics) জন্য পারসিস্ট (Persist) বা সংরক্ষণ করা হয়।
উচ্চ রাইট (Write) থ্রুপুট থাকার কারণে — একটি রাইট-অপ্টিমাইজড স্টোর (write-optimized store) (যেমব Cassandra, DynamoDB) ব্যবহার করুন যা শহর এবং তারিখ অনুযায়ী ভাগ করা থাকে।

Note: ইন্টারভিউ টিপস: রাইড-শেয়ারিং সিস্টেমে জিওস্প্যাশিয়াল ইনডেক্সিং (Geospatial indexing) (জিওহ্যাশ বা কোয়াডট্রি) মূল চ্যালেঞ্জ। সাধারণ দূরত্বের কোয়েরিগুলো (Naive distance queries) কেন স্কেলিং-এ বাধা দেয় এবং কীভাবে স্প্যাশিয়াল পার্টিশনিং (Spatial partitioning) একটি O(n) স্ক্যানকে O(1) প্রিফিক্স লুকআপে রূপান্তর করে, তা আপনি বোঝেন কিনা ইন্টারভিউয়াররা সেটাই দেখতে চান। জিওহ্যাশ সীমানার আট-প্রতিবেশী (8-neighbor) সমস্যার কথাও উল্লেখ করুন — যা আপনার গভীর জ্ঞানের পরিচয় দেয়।