Case Study: Ride Sharing (Pathao ধরনের)

কাছের driver খোঁজা, matching, ভাড়া

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

Pathao বা Uber এর মতো ride sharing এর মূল চ্যালেঞ্জ: শহরজুড়ে হাজার হাজার চলমান driver এর অবস্থান প্রতি কয়েক সেকেন্ডে আপডেট হচ্ছে, আর একজন rider ride চাইলে কয়েক সেকেন্ডের মধ্যে কাছের উপযুক্ত driver খুঁজে মেলাতে হবে, এমনভাবে যাতে একজন driver দুইজন rider কে না পায়। Food delivery এর dispatch এর সাথে অনেক মিল, কিন্তু এখানে সময়ের চাপ আরও বেশি আর location এর ব্যবহার আরও ঘন। (শেখার জন্য design, কোনো company র আসল ব্যবস্থা না।)

#ধাপ ১: Requirement

Functional:

  • Rider: pickup আর destination দিয়ে ভাড়ার অনুমান, ride চাওয়া, driver আসছে live দেখা, ভাড়া পরিশোধ, rating
  • Driver: online/offline, ride এর অফার পাওয়া, accept, pickup, শেষ, আয়
  • System: matching, ভাড়া (চাহিদা অনুযায়ী surge), trip এর রেকর্ড

Non-functional:

  • Matching এর ফল কয়েক সেকেন্ডের মধ্যে (৫-১০ সেকেন্ডে অফার)
  • Driver এর location আপডেট ৪ সেকেন্ডে একবার, rider এর map এ মসৃণ
  • একজন driver একসাথে একটাই ride
  • Trip আর ভাড়ার রেকর্ড কখনো হারাবে না

#ধাপ ২: Estimation

  • সক্রিয় driver (একসাথে online) ৫০,০০০; প্রতি ৪ সেকেন্ডে location → ১২,৫০০ write/সেকেন্ড
  • দিনে ১০ লাখ ride → গড় ~১২ ride request/সেকেন্ড, peak (অফিস শুরু-শেষ, বৃষ্টি) ৫০-১০০
  • প্রতিটা ride request এ "কাছের driver" খোঁজা; প্রতিটা চলমান trip এ rider এর map এ driver এর আপডেট

সিদ্ধান্ত: Location এর write সবচেয়ে বড় চাপ, আর geo-query সবচেয়ে ঘন read। Trip এর data তুলনায় ছোট কিন্তু সঠিক হতে হবে।

#ধাপ ৩: API

HTTP
POST /v1/fare-estimate        {pickup, dropoff, ride_type}  → {fare_range, eta, surge}
POST /v1/rides                (Idempotency-Key) {pickup, dropoff, ride_type, fare_quote_id}
GET  /v1/rides/{id}/events    (SSE/WebSocket: matched, driver location, arrived, started, completed)
POST /v1/driver/location      {lat, lng, heading, speed, ts}   (WebSocket দিয়েও)
POST /v1/driver/offers/{id}/accept
POST /v1/rides/{id}/start | /complete

fare_quote_id: rider যে ভাড়া দেখে ride চাইলো, সেটা কিছুক্ষণের জন্য "লক" (quote এর মেয়াদ ২ মিনিট), যাতে মাঝে surge বাড়লেও প্রতিশ্রুত দাম থাকে।

#ধাপ ৪: Data

Data কোথায়
Driver এর সর্বশেষ location আর অবস্থা (free/on-trip) Redis (geo-index), city অনুযায়ী ভাগ
Ride/trip, ভাড়া, payment PostgreSQL (city/region দিয়ে partition)
Location এর ইতিহাস (trip এর পথ) Kafka → time-series/columnar store; trip শেষে পথ সারাংশ করে trip এর সাথে
Surge এর হিসাব Stream processing → Redis এ এলাকা অনুযায়ী মান

#ধাপ ৫: High-level design

Driver app Rider app Location ingest WebSocket, হালকা Geo index Redis / H3 cell Kafka location stream Ride service request, ভাড়া, trip Matching service কাছের driver, অফার Surge service চাহিদা ÷ যোগান Trip DB PostgreSQL
Location এর বিশাল প্রবাহ আলাদা হালকা পথে (ingest → geo index, আর stream এ ইতিহাস)। Matching শুধু geo index পড়ে; trip এর সঠিক রেকর্ড আলাদা database এ।

#ধাপ ৬: Deep dive

#Geo index: শহরকে ঘরে ভাগ

প্রতিবার ৫০,০০০ driver এর দূরত্ব হিসাব করা চলে না। শহরকে ছোট ছোট ঘরে ভাগ করো:

  • Geohash: আয়তাকার ঘর, code এর শুরু মিললে কাছাকাছি (সীমানায় সাবধানতা লাগে)
  • H3 (Uber এর বানানো): ষড়ভুজ ঘর, প্রতিটা প্রতিবেশী সমান দূরত্বে; প্রতিটা ঘরের পাশের ঘর খোঁজা সহজ
  • Quadtree: যেখানে driver বেশি সেখানে ঘর ছোট, যেখানে কম সেখানে বড়
  • Redis GEO: ভেতরে geohash, GEOSEARCH দিয়ে সরাসরি "৩ km এর মধ্যে"

Driver এর location আপডেট মানে শুধু তার ঘর বদলানো (আগের ঘর থেকে সরিয়ে নতুন ঘরে)। খোঁজা মানে rider এর ঘর আর তার চারপাশের কয়েকটা ঘর দেখা। শহর অনুযায়ী (ঢাকা, চট্টগ্রাম) আলাদা index, scale সহজ।

#Matching আর race condition

  1. Rider এর চারপাশের ঘরে free driver খোঁজো, রাস্তার দূরত্ব/সময় অনুযায়ী সাজাও (সরলরেখার দূরত্ব না; নদী আর একমুখী রাস্তা আছে)
  2. সেরা driver কে অফার, ১৫ সেকেন্ডের সময়সীমা
  3. অফার পাঠানোর সময় driver কে "অফার চলছে" অবস্থায় রাখো, যাতে একসাথে দুইটা অফার না পায়
  4. Accept এ atomic অবস্থা বদল (free/offered → on_trip, শর্তসহ); ব্যর্থ হলে পরের driver
  5. কেউ না নিলে পরিসর বাড়াও, বা rider কে জানাও

একসাথে অনেক request এলে "প্রতিটা request এর জন্য আলাদাভাবে সেরা driver" না করে কয়েক সেকেন্ডের request গুলো একসাথে মিলিয়ে (batch matching) সামগ্রিকভাবে ভালো মিল খোঁজা যায়: মোট অপেক্ষার সময় কম হয়।

#Surge pricing

প্রতিটা ঘরে (বা এলাকায়) কয়েক মিনিট পর পর হিসাব: অপেক্ষমান request ÷ free driver। অনুপাত বেশি হলে ভাড়ার গুণক বাড়ে, যা দুইভাবে কাজ করে: কিছু rider অপেক্ষা করে (চাহিদা কমে) আর আশেপাশের driver সেই এলাকায় আসে (যোগান বাড়ে)। Stream processing (Kafka + Flink ধরনের) দিয়ে প্রায় real-time। স্বচ্ছতা জরুরি: rider আগেই গুণক দেখবে আর quote লক থাকবে।

#Driver এর location: খরচ আর মসৃণতা

  • Driver app GPS নেয় কিন্তু প্রতিটা পাঠায় না: স্থির থাকলে কম, চললে বেশি (battery আর data বাঁচে)
  • WebSocket এ পাঠানো, HTTP এর overhead নেই
  • Rider এর map এ দুই আপডেটের মাঝে অ্যানিমেশন (interpolation), যাতে গাড়ি "লাফায়" না
  • GPS এর ভুল (বিল্ডিং এর মাঝে) সংশোধন করে রাস্তার উপর বসানো (map matching)

#Trip এর সঠিকতা

  • Trip এর অবস্থা state machine: requested → matched → arrived → started → completed / cancelled
  • প্রতিটা বদল event সহ, idempotent
  • ভাড়ার চূড়ান্ত হিসাব trip এর পথের দূরত্ব আর সময় থেকে (location এর ইতিহাস), quote এর সীমার সাথে মিলিয়ে
  • Payment এর ব্যর্থতা trip এর সফলতাকে আটকাবে না; বকেয়া হিসেবে রেখে পরে আদায়

#অনুশীলন

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

প্রতিটা ride request এ সব driver এর দূরত্ব হিসাব না করে কী করা হয়?

শহরকে ঘরে (geohash, H3, quadtree) ভাগ করে প্রতিটা driver কে তার ঘরে রাখা হয়। খোঁজার সময় শুধু rider এর ঘর আর আশেপাশের কয়েকটা ঘরের driver দেখা হয়।

Fare quote লক করার কারণ কী?

Rider যে ভাড়া দেখে ride চাইলো, মাঝে surge বাড়লেও যেন সেই প্রতিশ্রুত ভাড়া থাকে। এতে স্বচ্ছতা আর বিশ্বাস থাকে।

Surge pricing কীভাবে চাহিদা আর যোগান মেলায়?

দাম বাড়লে কিছু rider অপেক্ষা করে বা বিকল্প নেয় (চাহিদা কমে), আর বেশি আয়ের আশায় আশেপাশের driver সেই এলাকায় আসে বা online হয় (যোগান বাড়ে)।

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