Case study: ride-sharing — location update, geohash আর matching

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

ধরা যাক আমরা “পথিক” নামের একটি কাল্পনিক ride-sharing অ্যাপ বানাচ্ছি। ঢাকার মতো একটি ঘনবসতির শহরে যাত্রী অ্যাপ খুলে গন্তব্য দেন, ভাড়ার অনুমান দেখেন, “অনুরোধ” চাপেন। কয়েক সেকেন্ডে কাছের একজন চালক — বাইক, গাড়ি বা CNG — গ্রহণ করেন, আর যাত্রী মানচিত্রে তাঁকে এগিয়ে আসতে দেখেন। আমরা পর্ব ৬ — একটি নকশা কীভাবে এগোয়-এর আট ধাপ ধরে এগোব; আগের ধারণাগুলোর শুধু প্রয়োগ আর মূল পর্বের লিংক থাকবে।

Functional requirement — যা করতেই হবে

• যাত্রী: ভাড়ার অনুমান দেখা, গাড়ির ধরন বেছে অনুরোধ বা বাতিল, চালকের চলমান অবস্থান আর ETA দেখা।
• চালক: অনলাইন হওয়া, কয়েক সেকেন্ড পরপর অবস্থান পাঠানো, offer গ্রহণ বা প্রত্যাখ্যান, trip শুরু ও শেষ।
• সিস্টেম: কাছের চালক খুঁজে একজনকে offer (dispatch), trip-এর জীবনচক্র, পথ ধরে ভাড়া, পরিশোধ শুরু — পরিশোধের নকশা পর্ব ৬০ — Case study: ticket booking আর payment-এ।

Non-functional requirement — কতটা ভালোভাবে

• সতেজতা আর গতি: matching-এর দেখা অবস্থান ধরা যাক ১০ সেকেন্ডের মধ্যে; প্রথম offer কয়েক সেকেন্ডে, খোঁজার p99 শ-খানেক ms-এর ঘরে (লক্ষ্য)।
• সঠিকতা: একজন চালক একসাথে দুটি trip নয়, একটি trip দুজন চালক নয়, একবার চাপলে একটিই trip — কঠোর consistency; অবস্থানে eventual যথেষ্ট — পর্ব ৪০ — CAP, PACELC আর consistency model.
• Availability: অনুরোধ আর চলমান trip সবসময়; বিশ্লেষণ পিছিয়ে থাকলেও চলে — পর্ব ৫ — Availability আর reliability.
• গোপনীয়তা: অবস্থান থেকে কে কোথায় থাকেন, কোথায় কাজ করেন — সব বোঝা যায় (অংশ ৯)।
• বাংলাদেশের বাস্তবতা (ধরা যাক): সবাই মোবাইলে; চলন্ত অবস্থায় ডেটা মাঝে মাঝে কাটে; ব্যাটারি আর ডেটা খরচ গুরুত্বপূর্ণ।

ইন্টারভিউয়ার যে প্রশ্নগুলো আশা করেন

২ · হিসাব — লেখার ঢেউ বড়, memory ছোট

পর্ব ৩ — Back-of-the-envelope হিসাব-এর নিয়মে আগে অনুমানগুলো লিখে নিই। সংখ্যাগুলো কোনো আসল কোম্পানির নয় — সবই “ধরা যাক”, আর নিচের প্রোগ্রামে বদলে দেখা যায়।

// Ride-sharing estimator. Every input is an ASSUMPTION (dhora jak) - change them and re-run.
const A = {
  peakDrivers: 100000,      // online drivers at the busiest hour, all cities
  bigCity: 50000,           // of them, in the largest city
  everySec: 4,              // a driver app sends GPS every 4 s
  wireBytes: 150,           // one location message on the wire (payload + framing + TLS)
  memBytes: 200,            // one "latest location" entry incl. index overhead
  avgDrivers: 40000,        // online drivers averaged over 24 h
  tripsPerDay: 1000000,     // completed trips per day
  peakFactor: 3,            // busiest hour vs daily average
  tripMin: 20,              // average trip length (minutes)
  pointBytes: 50,           // one stored trace point, compact binary
  eventsPerTrip: 8,         // requested, offered, accepted, arrived, started, ended, paid, rated
  copies: 3,                // replication factor for stored traces
};
const fmt = (x) => Math.round(x).toLocaleString("en-US");
const writes = A.peakDrivers / A.everySec, city = A.bigCity / A.everySec;
console.log("location writes/s at peak : " + fmt(writes) + "  (largest city " + fmt(city) + ")");
console.log("ingest bandwidth          : " + (writes * A.wireBytes * 8 / 1e6).toFixed(0) + " Mbit/s");
console.log("memory, latest locations  : " + (A.peakDrivers * A.memBytes / 1e6).toFixed(0) + " MB");
const reqAvg = A.tripsPerDay / 86400;
console.log("ride requests/s avg, peak : " + reqAvg.toFixed(1) + ", " + (reqAvg * A.peakFactor).toFixed(0));
console.log("write : request at peak   : " + fmt(writes / (reqAvg * A.peakFactor)) + " : 1");
const allPts = A.avgDrivers * 86400 / A.everySec;
const tripPts = A.tripsPerDay * A.tripMin * 60 / A.everySec;
console.log("location events/day, all  : " + fmt(allPts));
console.log("trace points/day, on trip : " + fmt(tripPts) + "  (" + fmt(A.tripMin * 60 / A.everySec) + " per trip)");
console.log("trip state events/day     : " + fmt(A.tripsPerDay * A.eventsPerTrip));
const day = tripPts * A.pointBytes, year = day * 365;
console.log("trip traces: " + (day / 1e9).toFixed(1) + " GB/day, " + (year / 1e12).toFixed(2) +
  " TB/year, x" + A.copies + " copies = " + (year * A.copies / 1e12).toFixed(1) + " TB");
console.log("all pings for 1 year (x" + A.copies + ")  : " + (allPts * A.pointBytes * 365 * A.copies / 1e12).toFixed(1) + " TB");

location writes/s at peak : 25,000  (largest city 12,500)
ingest bandwidth          : 30 Mbit/s
memory, latest locations  : 20 MB
ride requests/s avg, peak : 11.6, 35
write : request at peak   : 720 : 1
location events/day, all  : 864,000,000
trace points/day, on trip : 300,000,000  (300 per trip)
trip state events/day     : 8,000,000
trip traces: 15.0 GB/day, 5.47 TB/year, x3 copies = 16.4 TB
all pings for 1 year (x3)  : 47.3 TB

৩ · API — যাত্রী, চালক আর অবস্থানের বার্তা

যাত্রীর কাজগুলো সাধারণ অনুরোধ-উত্তর, তাই REST (পর্ব ৮ — REST API নকশা)। চালকের অ্যাপ সারাক্ষণ অবস্থান পাঠায় আর যেকোনো মুহূর্তে offer পেতে পারে — তাই একটি স্থায়ী সংযোগ, যেমন WebSocket বা MQTT-ধাঁচের protocol (পর্ব ১০ — Real-time যোগাযোগ)। প্রতিটি অনুরোধ আগে API gateway-তে পরিচয় যাচাই আর rate limiter পার হয় (পর্ব ১১ — Reverse proxy, API gateway আর BFF).

POST /v1/fare-quotes
{ "pickup": {"lat": 23.7801, "lon": 90.4003},
  "dropoff": {"lat": 23.8103, "lon": 90.4125}, "vehicle": "car" }

200 OK
{ "quote_id": "q_8f21", "fare_min": 310, "fare_max": 360, "currency": "BDT",
  "surge": 1.0, "pickup_eta_min": 6, "expires_in_s": 120 }

POST /v1/rides
Idempotency-Key: 5b0e-77c1
{ "quote_id": "q_8f21", "payment": "cash" }

201 Created
{ "ride_id": "r_90412", "status": "MATCHING" }

Quote-এর মেয়াদ: ভাড়া দুই মিনিট বৈধ, অনুরোধে শুধু quote_id — app ভাড়া বদলাতে পারে না, যাত্রী যা দেখেছেন তা-ই পান। Idempotency key: উত্তর হারালে app একই key-তে আবার পাঠায়; সার্ভার আগের ride_id-ই ফেরত দেয়।

→ {"t":"loc","seq":1842,"pts":[
     {"ts":1793170802,"lat":23.78112,"lon":90.40261,"acc":6,"spd":7.9,"hdg":84},
     {"ts":1793170806,"lat":23.78118,"lon":90.40292,"acc":7,"spd":8.1,"hdg":86}]}
← {"t":"offer","offer_id":"of_771","ride_id":"r_90412","pickup_eta_min":4,
   "expires_in_s":15}
→ {"t":"accept","offer_id":"of_771"}
← {"t":"assigned","ride_id":"r_90412"}          (or {"t":"offer_gone"} if too late)

অবস্থানের বার্তায় ক্রমিক sequence number, ফোনের সময় (ts), নির্ভুলতা (acc, মিটারে), গতি আর দিক; নেটওয়ার্ক খারাপ হলে কয়েকটি বিন্দু একসাথে। বাস্তবে সাধারণত Protobuf-এর মতো binary format-এ — পর্ব ১২ — Data format আর serialization. accept offer_id দিয়ে idempotent; দেরিতে এলে offer_gone. Trip চলাকালে যাত্রীর app একটি subscription খোলে, যাতে সার্ভার নিজেই অবস্থান পাঠায়।

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

সবচেয়ে বড় সিদ্ধান্ত: ডেটাকে চরিত্র অনুযায়ী আলাদা করা। সর্বশেষ অবস্থান প্রতি ৪ সেকেন্ডে বদলায়, হারালেও পরের বার্তায় ভরে যায় — soft state. Trip-এর অবস্থা আর ভাড়া হারানো চলে না। এক database-এ দুটো চালালে হয় অবস্থান-লেখায় সেটি ডোবে, নয়তো trip-এর নিয়ম ঢিলা হয় (পর্ব ২০ — SQL বনাম NoSQL).

Trip DB-র partition key কেন শহর? যাত্রী, চালক আর পথ প্রায় সবসময় একই শহরে, তাই চালকের অবস্থা আর trip একই shard-এ — “চালক রাজি, trip গৃহীত” এক local transaction-এ (অংশ ৮), shard-জোড়া transaction ছাড়াই (পর্ব ২৫ — Distributed transaction). দাম: খুব বড় শহর একাই বড় shard — তখন এলাকা বা trip_id ধরে আরও ভাগ (পর্ব ২৩ — Partitioning আর sharding). rider_id-এ ইতিহাস খুঁজতে scatter-gather-এর বদলে আলাদা read model — পর্ব ৩৫ — Event sourcing আর CQRS; index-এর বাছাই পর্ব ২১ — Index আর query performance-এর অনুশীলনে।

CREATE TABLE trips (
  trip_id     BIGINT PRIMARY KEY,          -- Snowflake-style id (পর্ব ২৩)
  city_id     INT    NOT NULL,             -- partition key
  rider_id    BIGINT NOT NULL,
  driver_id   BIGINT,
  state       TEXT   NOT NULL,             -- REQUESTED, MATCHING, ACCEPTED, ...
  version     INT    NOT NULL DEFAULT 1,   -- every change: WHERE version = old
  quote_id    TEXT   NOT NULL,
  client_key  TEXT   NOT NULL,             -- the Idempotency-Key
  UNIQUE (rider_id, client_key)
);
CREATE TABLE driver_dispatch (
  driver_id   BIGINT PRIMARY KEY,
  city_id     INT    NOT NULL,
  state       TEXT   NOT NULL,             -- offline, available, offered, en_route, on_trip
  trip_id     BIGINT,
  offer_until TIMESTAMPTZ,                 -- an offer is a lease: it expires
  version     INT    NOT NULL
);

৫ · High-level design — অনুরোধ থেকে trip শুরু

বাঁ দিকে লেখার পথ: অবস্থান যায় একটি connection gateway-এ (শুধু লাখো স্থায়ী সংযোগ ধরে রাখে), তারপর location service-এ — memory-র geo index আর trace stream. ডান দিকে অনুরোধের পথ: যাত্রীর app → API gateway → ride service → matching, যে location service-এ কাছের চালক খুঁজে gateway দিয়ে offer পাঠায়।

লেখার পথ: সংযোগ খোলার সময় gateway একবার token যাচাই করে, তারপর প্রতিটি বার্তা চালকের cell-এর shard-এ পাঠায়; shard অবস্থান overwrite করে, cell বদলালে চালককে নতুন cell-এ সরায়, আর বিন্দুটি trace stream-এ append করে। প্রতিটি সংযোগ একটি নির্দিষ্ট gateway-তে, তাই কোন চালক কোথায়, তা একটি ছোট registry-তে থাকে, যাতে offer ঠিক জায়গায় যায় (পর্ব ১৫ — Stateless বনাম stateful; একই নকশা চ্যাটের জন্য পর্ব ৫৫ — Case study: chat আর messaging system-এ)।

অনুরোধের পথ: নিচের stepper-এ একটি অনুরোধের পুরো যাত্রা, নির্দিষ্ট সংখ্যাসহ। “পরে” চাপুন।

Idempotency-Key 5b0e-77c1 → নতুন
quote q_8f21 → বৈধ (আরও 74 s)
INSERT trips (r_90412, state = MATCHING, version 1)
→ যাত্রী: 201 Created · matching queue-তে কাজ

pickup → geohash-6 wh0r31, সাথে ৮টি পাশের cell
পাওয়া গেল ১৪ জন চালক (ধরন: bike)
বাদ: ৩ জন trip-এ, ১ জনের অবস্থান ২১ s পুরোনো, ১ জন ভুল দিকে
প্রার্থী ৯ জন → সবচেয়ে কাছের ৫ জনের ETA চাওয়া হলো

D-17  সোজা দূরত্ব 0.4 km   ETA 11 min (রেললাইনের ওপারে)
D-23  সোজা দূরত্ব 0.9 km   ETA 4 min
D-08  সোজা দূরত্ব 1.1 km   ETA 5 min
CAS: D-23 available v3 → offered(r_90412) v4 ✔
offer of_771 → D-23-এর gateway, মেয়াদ 15 s

accept of_771 (6 s পরে, মেয়াদের ভেতরে)
trips  r_90412: MATCHING v1 → ACCEPTED v2, driver D-23
driver D-23  : offered v4 → en_route v5
→ যাত্রীকে push: চালক D-23, বাইক, ETA 4 min

ARRIVED → যাত্রী উঠলেন → ON_TRIP v4
D-23-এর প্রতিটি বিন্দু: trace stream (key D-23, trip r_90412)
যাত্রীর app: চালকের অবস্থান প্রতি ~4 s, সার্ভার নিজেই পাঠায়

৬ · Deep dive ১ — প্রতি ৪ সেকেন্ডে লাখো অবস্থান

কত ঘনঘন পাঠাবেন — তিনটি দাম একসাথে

ব্যবধান কমালে অবস্থান তাজা, কিন্তু লেখা, ফোনের ব্যাটারি আর মোবাইল ডেটা — তিনটিই বাড়ে। ঘণ্টায় ৩০ km গতিতে (প্রায় ৮.৩ m/s) চলা একটি গাড়ির হিসাব দেখুন; বার্তার আকার অংশ ২-এর মতো ১৫০ B ধরা।

৪ সেকেন্ডে চালক বড়জোর প্রায় ৩৩ মিটার সরেন — খোঁজার জন্য যথেষ্ট। অনেক নকশায় হার বদলায় (ধরা যাক): দাঁড়িয়ে থাকা চালক কম ঘনঘন, pickup-এর পথে বা trip-এ বেশি ঘনঘন।

সার্ভারে একটি বার্তার পথ

• Overwrite, append নয়: memory-তে প্রতি চালকের একটিই এন্ট্রি — অবস্থান, সময়, অবস্থা, গাড়ির ধরন, cell; নতুন বার্তা আগেরটিকে মুছে বসে।
• পুরোনো বার্তা উপেক্ষা: পুনঃসংযোগের পর জমা বার্তা দেরিতে আসতে পারে। Sequence number আগেরটির চেয়ে ছোট হলে latest-এ বসানো হয় না, শুধু trace-এ যায়। এটি last-write-wins, তবে “শেষ” ঠিক হয় ফোনের ক্রমিক নম্বরে, সার্ভারে পৌঁছানোর সময়ে নয় (পর্ব ৩৯ — সময় আর ক্রম)।
• নীরব চালক নিজে থেকে মুছে যান: এন্ট্রিতে TTL প্রায় ৩০ সেকেন্ড; বার্তা না এলে চালক তালিকা থেকে সরে যান — অবস্থানের বার্তাই একরকম heartbeat (পর্ব ৪৪ — Membership আর failure detection).
• Trace stream-এ append: key হিসেবে driver_id, তাই একজন চালকের সব বিন্দু একটি partition-এ ক্রম ধরে থাকে (পর্ব ৩৩ — Log-ভিত্তিক streaming). গ্রাহক: trace store, ভাড়া, রাস্তার গতি, surge-এর গণনা। Shard ধীর হলে gateway পুরোনো বার্তা ফেলে নতুনটি রাখে — এক ধরনের load shedding (পর্ব ১৮ — Overload সামলানো)।

GPS-এর ভুল আর map-matching

ফোনের GPS খোলা আকাশে সাধারণত কয়েক মিটারে নির্ভুল, কিন্তু উঁচু দালানের সারি বা উড়ালসড়কের নিচে সংকেত প্রতিফলিত হয়ে কয়েক দশ মিটার বা আরও সরে যেতে পারে। তাই:

• ছাঁকা: acc খুব বড়, বা অসম্ভব গতি (৪ সেকেন্ডে ৫০০ m) হলে বিন্দুটি সন্দেহজনক — ভুয়া অবস্থানেরও লক্ষণ হতে পারে।
• Map-matching: এলোমেলো বিন্দুগুলোকে আসল রাস্তার ওপর বসানো — কোন রাস্তা দিয়ে গাড়িটি সত্যিই গেছে। ভাড়া, ETA আর রাস্তার গতি এর ওপর দাঁড়ায়; দামি বলে চলে stream processor-এ (পর্ব ৩৬ — Batch আর stream processing).
• ফাঁক পূরণ: সংকেত কিছুক্ষণ না থাকলে শেষ জানা গতি আর দিক থেকে অবস্থানের অনুমান — dead reckoning — শুধু যাত্রীর মানচিত্রে মসৃণ দেখানোর জন্য; ভাড়ার হিসাবে পরে আসল বিন্দু দিয়ে ঠিক করা হয়।

নেটওয়ার্ক কেটে গেলে

চলন্ত অবস্থায় ডেটা কয়েক সেকেন্ড থেকে কয়েক মিনিট কেটে যেতে পারে (Computer Networks কোর্সের মোবাইল নেটওয়ার্ক — cell আর handover). তিনটি নিয়ম: (১) অ্যাপ বিন্দু জমিয়ে রাখে, সংযোগ ফিরলে সময় আর sequence-সহ পাঠায়। (২) Trip-এর অবস্থা সার্ভারে; ping না এলে trip বাতিল হয় না। (৩) যাত্রী দেখেন “শেষ জানা অবস্থান · ৪০ সেকেন্ড আগে” — পুরো সেবা ভেঙে না পড়ে মান একটু কমে, পর্ব ৪৮ — Resilience pattern-এর graceful degradation. অ্যাপের এই আচরণ offline-first নকশার একটি ছোট রূপ।

৭ · Deep dive ২ — spatial index: geohash, quadtree আর hexagon

“এই বিন্দুর ১ km-এর মধ্যে খালি চালক কারা?” — সাধারণ B-tree এতে ভালো নয়: (lat, lon) index-এ lat-এর পরিসর দেয় পুরো শহর জুড়ে একটি সরু ফালি, lon প্রতিটি সারিতে আলাদা মেলাতে হয়। লাগে দুই মাত্রাকে এক মাত্রায় আনার কৌশল, বা মাত্রা ধরে ভাগ করা গাছ।

Geohash — পৃথিবীকে নামওয়ালা ঘরে ভাগ

পৃথিবীকে বারবার দুই ভাগ করুন — পালা করে দ্রাঘিমা (longitude) আর অক্ষাংশ (latitude) ধরে — আর প্রতিবার বিন্দুটি কোন অর্ধেকে পড়ল তার একটি bit লিখুন (১ = বড় অর্ধেক)। দুই মাত্রার bit একটির পর একটি বসানো — এই interleaving-ই Z-order curve. প্রতি ৫টি bit মিলে একটি অক্ষর, ৩২টি অক্ষরের বর্ণমালা থেকে — base32 (0–9 আর a থেকে z, কিন্তু a, i, l, o বাদ)। অক্ষর যত বেশি, ঘর তত ছোট; একই prefix মানে একই বড় ঘর। নিচে একটি কাল্পনিক বিন্দু (অক্ষাংশ ২৩.৭৮, দ্রাঘিমা ৯০.৪০):

সীমানার ফাঁদ — কেন ৯টি ঘর

একই prefix মানে কাছাকাছি, কিন্তু উল্টোটি সত্য নয়: সীমানার দুই পাশের দুটি বিন্দু কয়েক মিটার দূরে থেকেও আলাদা prefix পায়। তাই খোঁজা হয় নিজের ঘর আর চারপাশের ৮টি — একটি ৩ × ৩ block. নিচের প্রোগ্রাম geohash বানায়, ঘরের সীমা ফিরিয়ে আনে, প্রতিবেশী খোঁজে, তারপর seed দেওয়া ২,০০০ জন চালকের মধ্যে কাছের জনকে দুইভাবে খোঁজে — ৯টি ঘরে, আর সবাইকে মেপে (brute force).

// Geohash: bits alternate lon, lat; every 5 bits -> one base32 char. Then a nearest-driver query.
const B32 = "0123456789bcdefghjkmnpqrstuvwxyz", KM = 111.32, rad = Math.PI / 180;
const LAT = 23.78, LON = 90.40;          // a made-up point in a dense city
function encode(lat, lon, p) {           // k = 1 halves longitude, k = 0 latitude; lon goes first
  const lo = [-90, -180], hi = [90, 180], v = [lat, lon]; let s = "", ch = 0, k = 1;
  for (let i = 0; i < 5 * p; i++, k ^= 1) {
    const mid = (lo[k] + hi[k]) / 2, bit = v[k] >= mid ? 1 : 0;
    if (bit) lo[k] = mid; else hi[k] = mid;
    ch = ch * 2 + bit; if (i % 5 === 4) { s += B32[ch]; ch = 0; }
  } return s; }
function cell(g) {                       // decode: the cell's [lat, lon] lower and upper bounds
  const lo = [-90, -180], hi = [90, 180]; let k = 1;
  for (const c of g) for (let b = 4; b >= 0; b--, k ^= 1) {
    const mid = (lo[k] + hi[k]) / 2; if ((B32.indexOf(c) >> b) & 1) lo[k] = mid; else hi[k] = mid; }
  return { lo, hi }; }
function block3x3(g) {                   // g and its 8 neighbours: re-encode the centres around it
  const { lo, hi } = cell(g), out = [];
  for (const i of [1, 0, -1]) for (const j of [-1, 0, 1]) out.push(encode((lo[0] + hi[0]) / 2 +
    i * (hi[0] - lo[0]), (lo[1] + hi[1]) / 2 + j * (hi[1] - lo[1]), g.length));
  return out; }
for (const p of [5, 6, 7]) { const g = encode(LAT, LON, p), { lo, hi } = cell(g);
  console.log("p=" + p + " " + g.padEnd(8) + ((hi[1] - lo[1]) * KM * Math.cos(LAT * rad)).toFixed(3) + " km wide x " + ((hi[0] - lo[0]) * KM).toFixed(3) + " km tall"); }
console.log("3x3 around " + encode(LAT, LON, 6) + ": " + block3x3(encode(LAT, LON, 6)).join(" "));
let seed = 58; const rand = () => { seed = (seed + 0x6D2B79F5) | 0; let t = Math.imul(seed ^ (seed >>> 15), 1 | seed);
  t = (t + Math.imul(t ^ (t >>> 7), 61 | t)) ^ t; return ((t ^ (t >>> 14)) >>> 0) / 4294967296; };   // mulberry32
const index = new Map(), drivers = [];   // in-memory geo index: geohash-6 cell -> drivers in it
for (let i = 0; i < 2000; i++) { const d = { id: "d" + i, lat: 23.68 + 0.2 * rand(), lon: 90.30 + 0.2 * rand() };
  drivers.push(d); const g = encode(d.lat, d.lon, 6); index.set(g, (index.get(g) || []).concat(d)); }
const dist = (a, b) => KM * Math.hypot(a.lat - b.lat, (a.lon - b.lon) * Math.cos(a.lat * rad));
const me = { lat: LAT, lon: LON }; let ops = 0, best = null;
for (const g of block3x3(encode(LAT, LON, 6))) for (const d of index.get(g) || []) { ops++; if (!best || dist(me, d) < dist(me, best)) best = d; }
const brute = drivers.reduce((m, d) => dist(me, d) < dist(me, m) ? d : m);
console.log("3x3 cells: " + best.id + " at " + (dist(me, best) * 1000).toFixed(0) + " m after " + ops + " checks");
console.log("brute    : " + brute.id + " at " + (dist(me, brute) * 1000).toFixed(0) + " m after " + drivers.length + " checks");

p=5 wh0r3   4.477 km wide x 4.892 km tall
p=6 wh0r31  1.119 km wide x 0.611 km tall
p=7 wh0r315 0.140 km wide x 0.153 km tall
3x3 around wh0r31: wh0r2f wh0r34 wh0r36 wh0r2c wh0r31 wh0r33 wh0r2b wh0r30 wh0r32
3x3 cells: d314 at 15 m after 32 checks
brute    : d314 at 15 m after 2000 checks

Quadtree, hexagon আর অন্যান্য

লেখার সময়ের documentation অনুযায়ী Redis-এর GEO কমান্ড অবস্থানকে 52-bit geohash-এ বদলে sorted set-এর score হিসেবে রাখে, আর ৬.২ সংস্করণ থেকে GEOSEARCH দিয়ে ব্যাসার্ধে খোঁজা যায় (পুরোনো GEORADIUS deprecated). আচরণ সংস্করণভেদে আলাদা।

GEOADD drivers:city7:bike 90.40261 23.78112 D-23 90.3975 23.7832 D-08
GEOSEARCH drivers:city7:bike FROMLONLAT 90.4003 23.7801 BYRADIUS 1.5 km ASC COUNT 20 WITHDIST
1) 1) "D-23"   2) "0.2611"
2) 1) "D-08"   2) "0.4473"

Geo index ভাগ করা — আর গরম ঘর

আকার ২০ MB, তবু ভাগ লাগে লেখার হার আর availability-র জন্য। Shard key কী হবে (পর্ব ২৩)?

• driver_id ধরে ভাগ: লেখা সমান ছড়ায়, চালক সরলেও shard বদলায় না। কিন্তু “কাছের চালক” প্রশ্নে সব shard জিজ্ঞেস করতে হয় — scatter-gather, প্রতিটি অনুরোধে।
• এলাকা (geohash-৪ বা ৫ prefix) ধরে ভাগ: কাছের চালকেরা একই shard-এ, তাই খোঁজা সাধারণত এক shard-এ, সীমানায় ২–৪টিতে। দাম: এলাকা পার হলে চালককে shard বদলাতে হয় (মোছা হারালেও TTL সাফ করে), আর কিছু এলাকা খুব ব্যস্ত। এলাকা থেকে shard-এ বসাতে consistent hashing (পর্ব ১৬) বা একটি এলাকা-মানচিত্র। পড়ার প্রশ্নটি ভৌগোলিক বলে এটিই সাধারণ পছন্দ।

গরম ঘর: খেলা শেষে স্টেডিয়ামে বা ঈদের আগে বড় স্টেশনে একটি-দুটি cell-এ হাজারো অনুরোধ — একটি hot spot (পর্ব ৩০ — Distributed cache-এর hot key-র মতো)। প্রতিকার: (১) গরম এলাকাকে ছোট cell-এ ভেঙে আলাদা shard-এ; (২) একটি জানালার সব অনুরোধের জন্য একবার খোঁজা (অংশ ৮); (৩) pickup এলাকা ঘিরে geofence আর চালকের সারি — ফেরিঘাটের সিরিয়ালের মতো; (৪) সীমা ছাড়ালে নতুন অনুরোধকে “কয়েক মিনিট অপেক্ষা”।

৮ · Deep dive ৩ — matching, dispatch আর trip-এর অবস্থা

দূরত্ব নয়, পৌঁছানোর সময়

ঢাকার একমুখী রাস্তায় মানচিত্রে ৪০০ m দূরের গাড়ি রেললাইনের ওপারে থাকলে ঘুরে আসতে দশ মিনিট। তাই matching দুই ধাপে: (১) geo index থেকে সোজা দূরত্বে কয়েক ডজন প্রার্থী — সস্তা; (২) প্রথম কয়েকজনের routing engine থেকে ETA — দামি, রাস্তার graph-এ সবচেয়ে ছোট পথ (DSA কোর্সের Dijkstra — সবচেয়ে ছোট পথ)। রাস্তার গতি আসে trace stream থেকে, কয়েক মিনিটের tumbling window-এ গড় করে।

একজন একজন করে, নাকি একসাথে — batch matching

সহজ নিয়ম: অনুরোধ আসামাত্র সবচেয়ে কাছের খালি চালক (greedy). কিন্তু প্রথম যাত্রীর নেওয়া চালক হয়তো পরের যাত্রীর একমাত্র ভালো বিকল্প ছিলেন। একটি রাস্তায় — R1 ২ km চিহ্নে (আগে এলেন), R2 ০ km-এ; চালক D1 ১ km-এ, D2 ৪ km-এ:

একসাথে দেখলে মোট ৫ থেকে ৩ km — ৪ মিনিট/km ধরলে গড় অপেক্ষা ১০ থেকে ৬ মিনিট। এটিই batch matching: ১–২ সেকেন্ডের একটি জানালায় আসা সব অনুরোধ আর খালি চালক মিলিয়ে এমন জোড়া খোঁজা, যাতে মোট খরচ সবচেয়ে কম — গণিতে assignment problem, যার ক্লাসিক সমাধান Hungarian অ্যালগরিদম (DSA কোর্সের Network flow, min cut আর bipartite matching পর্বে)। নিচের simulator ৬ × ৬ km এলাকায় ৪০০টি জানালা চালায়, প্রতিটিতে ৮টি অনুরোধ আর ১১ জন চালক; ছোট বলে সঠিক সমাধান bitmask DP দিয়েই।

// Greedy-immediate vs batched matching. 400 rounds; each round = a 2 s window in one area:
// 8 requests arrive, 11 free drivers. Distance = |dx| + |dy| km (a grid of roads), 6 x 6 km area.
let seed = 58; const rand = () => { seed = (seed + 0x6D2B79F5) | 0; let t = Math.imul(seed ^ (seed >>> 15), 1 | seed);
  t = (t + Math.imul(t ^ (t >>> 7), 61 | t)) ^ t; return ((t ^ (t >>> 14)) >>> 0) / 4294967296; };   // mulberry32
const R = 8, D = 11, MIN_PER_KM = 4;     // assume ~15 km/h in dense traffic = 4 min per km
const pt = () => ({ x: 6 * rand(), y: 6 * rand() }), km = (a, b) => Math.abs(a.x - b.x) + Math.abs(a.y - b.y);
const greedy = [], batched = [];
for (let round = 0; round < 400; round++) {
  const req = Array.from({ length: R }, pt), drv = Array.from({ length: D }, pt);
  const c = req.map((r) => drv.map((d) => km(r, d)));
  const used = new Array(D).fill(false);  // (1) greedy: in arrival order, take the nearest free driver
  for (let i = 0; i < R; i++) {
    let j = -1; for (let k = 0; k < D; k++) if (!used[k] && (j < 0 || c[i][k] < c[i][j])) j = k;
    used[j] = true; greedy.push(c[i][j]);
  }
  // (2) batched: minimum total distance over the whole window (bitmask DP = exact assignment)
  const N = 1 << D, best = new Float64Array(N).fill(Infinity), from = new Int32Array(N); best[0] = 0;
  let end = -1;
  for (let m = 0; m < N; m++) {
    if (best[m] === Infinity) continue;
    let i = 0; for (let x = m; x; x &= x - 1) i++;        // i = requests already placed
    if (i === R) { if (end < 0 || best[m] < best[end]) end = m; continue; }
    for (let k = 0; k < D; k++) if (!(m >> k & 1) && best[m] + c[i][k] < best[m | 1 << k]) {
      best[m | 1 << k] = best[m] + c[i][k]; from[m | 1 << k] = k; }
  }
  for (let m = end, i = R - 1; m; i--) { const k = from[m]; batched.push(c[i][k]); m ^= 1 << k; }
}
function show(name, a) {
  const s = [...a].sort((x, y) => x - y), avg = a.reduce((x, y) => x + y, 0) / a.length;
  const p90 = s[Math.ceil(0.9 * s.length) - 1];   // nearest-rank p90
  console.log(name.padEnd(9) + "avg " + avg.toFixed(2) + " km (" + (avg * MIN_PER_KM).toFixed(1) + " min)   p90 " +
    p90.toFixed(2) + " km (" + (p90 * MIN_PER_KM).toFixed(1) + " min)   max " + s[s.length - 1].toFixed(2) + " km");
}
show("greedy", greedy); show("batched", batched);
console.log("pickups: " + greedy.length + " each; extra wait for batching: about 1 s on average (half the window)");

greedy   avg 1.72 km (6.9 min)   p90 3.22 km (12.9 min)   max 8.71 km
batched  avg 1.55 km (6.2 min)   p90 2.87 km (11.5 min)   max 5.95 km
pickups: 3200 each; extra wait for batching: about 1 s on average (half the window)

Offer — একজনকে, মেয়াদসহ

কয়েকজনকে একসাথে একই offer দিলে দ্রুত, কিন্তু বাকিরা বিরক্ত হন আর একই চালক কয়েকটি offer-এ জড়ান। তাই সাধারণত একবারে একজন, ১০–১৫ সেকেন্ডের মেয়াদ (ধরা যাক)। গ্রহণের সম্ভাবনা ০.৬ ধরলে পরপর তিনজনই না নেওয়ার সম্ভাবনা ০.৪³ = ০.০৬৪ — প্রায় ৬.৪% অনুরোধে তিন চেষ্টাতেও চালক নেই, আর প্রতিটি ব্যর্থতায় অপেক্ষা বাড়ে। মেয়াদের টাইমার থাকে টেকসই scheduler-এ, matcher-এর memory-তে নয় (পর্ব ৩৭ — Background job, scheduler আর workflow engine).

একই চালক, দুই dispatcher — double assignment

পাশাপাশি দুটি অনুরোধে দুটি dispatcher একই চালককে বাছতে পারে; দুজনই পড়ে “available”, দুজনই লেখে “আমার” — একটি ক্লাসিক race condition. নিচের simulator দুটি dispatcher-এর পড়া একটি ১০০ ms জানালার যেকোনো সময়ে রাখে; পড়া আর লেখার মাঝে ২০ ms (হিসাব আর একটি network hop).

// Two dispatchers both pick the same nearest driver. Each READS the driver's state, spends
// GAP ms (scoring, a network hop), then WRITES "offered to my trip". 10,000 trials per mode.
let seed = 58; const rand = () => { seed = (seed + 0x6D2B79F5) | 0; let t = Math.imul(seed ^ (seed >>> 15), 1 | seed);
  t = (t + Math.imul(t ^ (t >>> 7), 61 | t)) ^ t; return ((t ^ (t >>> 14)) >>> 0) / 4294967296; };   // mulberry32
const WINDOW = 100, GAP = 20, TRIALS = 10000;   // both reads land somewhere in the same 100 ms
function trial(useCas) {
  const driver = { state: "available", version: 7, offeredTo: [] };
  const ev = [];
  for (const who of ["A", "B"]) { const t = WINDOW * rand(); ev.push([t, "read", who], [t + GAP, "write", who]); }
  ev.sort((x, y) => x[0] - y[0]);
  const seen = {}; let retries = 0;
  for (const [, op, who] of ev) {
    if (op === "read") { seen[who] = { state: driver.state, version: driver.version }; continue; }
    if (seen[who].state !== "available") continue;   // saw it busy: go to the next driver
    if (!useCas) { driver.state = "offered"; driver.offeredTo.push(who); }   // naive: "it is mine"
    else if (driver.version === seen[who].version) {   // CAS: write only if nobody changed it
      driver.state = "offered"; driver.version++; driver.offeredTo.push(who);
    } else retries++;                    // lost the race: pick the next-best driver instead
  }
  return { double: driver.offeredTo.length > 1, retries };
}
for (const useCas of [false, true]) {
  let doubles = 0, retries = 0; seed = 58;   // same 10,000 timings for both modes
  for (let i = 0; i < TRIALS; i++) { const r = trial(useCas); doubles += r.double; retries += r.retries; }
  console.log((useCas ? "CAS on version" : "naive read-then-write").padEnd(22) + "double offers: " +
    String(doubles).padStart(5) + "   losers who retried: " + retries);
}
const p = 1 - (1 - GAP / WINDOW) ** 2;  // P(|tA - tB| < GAP) for two uniform times
console.log("theory for naive: 1 - (1 - " + GAP + "/" + WINDOW + ")^2 = " + p.toFixed(2) + " -> about " + Math.round(p * TRIALS));

naive read-then-write double offers:  3603   losers who retried: 0
CAS on version        double offers:     0   losers who retried: 3603
theory for naive: 1 - (1 - 20/100)^2 = 0.36 -> about 3600

একই নিয়ম SQLite-এ চালিয়ে দেখুন: কয়টি সারি বদলাল, সেটিই dispatcher-এর উত্তর — ১ মানে জিত, ০ মানে হার। শেষে trip আর চালক একই transaction-এ বদলায়, কারণ দুটি সারি একই শহরের shard-এ (অংশ ৪)। SQLite একটি মেশিনের database; এটি শুধু শর্তসাপেক্ষ লেখার যুক্তি দেখায়, বিতরণ করা সিস্টেমের ব্যর্থতা নয়।

CREATE TABLE drivers (id INTEGER PRIMARY KEY, state TEXT NOT NULL, trip_id INTEGER, version INTEGER NOT NULL);
CREATE TABLE trips (id INTEGER PRIMARY KEY, state TEXT NOT NULL, driver_id INTEGER, version INTEGER NOT NULL);
INSERT INTO drivers VALUES (17, 'available', NULL, 7), (23, 'available', NULL, 3);
INSERT INTO trips VALUES (501, 'MATCHING', NULL, 1), (502, 'MATCHING', NULL, 1);
-- A and B both read driver 17: available, version 7. A writes first:
UPDATE drivers SET state = 'offered', trip_id = 501, version = version + 1
 WHERE id = 17 AND state = 'available' AND version = 7;
-- B writes with the same old read:
UPDATE drivers SET state = 'offered', trip_id = 502, version = version + 1
 WHERE id = 17 AND state = 'available' AND version = 7;
-- 0 rows for B, so B offers driver 23 instead:
UPDATE drivers SET state = 'offered', trip_id = 502, version = version + 1
 WHERE id = 23 AND state = 'available' AND version = 3;
-- Driver 17 accepts: the trip and the driver change together
BEGIN;
UPDATE trips SET state = 'ACCEPTED', driver_id = 17, version = version + 1
 WHERE id = 501 AND state = 'MATCHING' AND version = 1;
UPDATE drivers SET state = 'en_route', version = version + 1
 WHERE id = 17 AND state = 'offered' AND trip_id = 501;
COMMIT;
-- An illegal jump (MATCHING to COMPLETED) matches no row:
UPDATE trips SET state = 'COMPLETED' WHERE id = 502 AND state = 'ON_TRIP';
SELECT id, state, trip_id, version FROM drivers ORDER BY id;
SELECT id, state, driver_id, version FROM trips ORDER BY id;

অন্য পথ: প্রতিটি চালকের সব offer driver_id ধরে একটি নির্দিষ্ট matcher দিয়ে পাঠালে দুজন লেখকই থাকে না — single-writer principle. Distributed lock-ও সম্ভব, তবে fencing token ছাড়া বিপদ — পর্ব ৪৩ — Coordination — distributed lock, lease আর fencing token.

Trip-এর state machine

প্রতিটি বদল একটি শর্তসাপেক্ষ UPDATE (“অবস্থা X আর version v হলে”), আর একই transaction-এ একটি event — outbox pattern (পর্ব ২৫); notification, ভাড়া, বিশ্লেষণ কোনো ঘটনা হারায় না, অবৈধ লাফ database নিজেই আটকায়। Consistency-র ভাগ: trip আর dispatch-অবস্থায় strong consistency, অবস্থানে eventual consistency — ডেটার চরিত্র অনুযায়ী।

ETA, ভাড়ার অনুমান আর surge-এর ধারণা

ভাড়ার অনুমান সাধারণত: ভিত্তি + প্রতি km-এর হার × দূরত্ব + প্রতি মিনিটের হার × সময়, তারপর একটি গুণক; দূরত্ব-সময় routing-এর আনুমানিক পথ থেকে, trip শেষে map-matched পথ থেকে (upfront ভাড়ায় quote-এর মানই থাকে)। Surge বা dynamic pricing-এর ধারণা: একটি এলাকায় (geohash-৫ বা hexagon ঘর) কয়েক মিনিটে অনুরোধ : খালি চালকের অনুপাত বাড়লে গুণক একটু বাড়ে, যাতে কিছু যাত্রী অপেক্ষা করেন আর চালক সেখানে আসেন। ভালো নকশায় মসৃণ বদল, ঊর্ধ্বসীমা, স্পষ্ট দেখানো আর জরুরি অবস্থায় বন্ধের নিয়ম। কত গুণক ন্যায্য, তা ব্যবসা, আইন আর নৈতিকতার প্রশ্ন — কোথাও নিয়ন্ত্রক সীমা দিতে পারে; এখানে শুধু ধারণা।

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

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

শহর = cell

প্রায় সব trip একটি শহরের ভেতরে। তাই প্রতিটি শহর একটি পূর্ণ, স্বাধীন কপি চালাতে পারে — নিজের gateway, geo index, matcher আর trip DB-র shard: cell-based architecture (পর্ব ৪৮)। এক শহরের সমস্যা বা ভুল deploy বাকিদের ছোঁয় না, আর নতুন সংস্করণ আগে একটি ছোট শহরে (পর্ব ৫৩ — Deployment আর release). শহর পেরোনো trip-এর মালিক যে শহরে শুরু; অ্যাকাউন্ট আর পরিশোধ cell-এর বাইরে।

১০ গুণ বড় হলে

• লেখা ২,৫০,০০০/সেকেন্ড: আরও এলাকাভিত্তিক shard, gateway-তে বার্তা একসাথে পাঠানো; memory তখনো কয়েকশো MB.
• সংযোগ ১০ লাখ: gateway-র memory আর file descriptor-এর সীমা — চ্যাটের মতোই (পর্ব ৫৫)।
• ETA: routing প্রায়ই সবচেয়ে বেশি CPU খায় — প্রাক-হিসাব করা রাস্তার graph আর এলাকা-জোড়ার ETA cache.

নিরাপত্তা আর গোপনীয়তা (প্রতিরক্ষার দিক থেকে)

• অবস্থান = PII: পথ থেকে বাসা আর কর্মস্থল বোঝা যায়। Data minimisation — সঠিক অবস্থান শুধু চলমান trip-এ, বিশ্লেষণে এলাকাভিত্তিক গড়, নাম ছাড়া।
• প্রবেশাধিকার: কর্মীরা trace দেখেন শুধু নির্দিষ্ট কারণে, role অনুযায়ী, প্রতিটি দেখা audit log-এ। Transit-এ TLS, জমা ডেটায় encryption at rest — পর্ব ৫২ — নকশায় নিরাপত্তা; শুরু থেকে privacy by design.
• যোগাযোগ আর অপব্যবহার: আসল ফোন নম্বরের বদলে মাঝের নম্বর; অস্বাভাবিক অবস্থান-ধারা পর্যালোচনায়; অনুরোধ আর বাতিলে rate limiting (পর্ব ৪৯)।

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

পর্ব ৫০ — Observability-এর SLI, প্রতি শহরে আলাদা: অবস্থান পৌঁছানোর দেরি (p99); পুরোনো এন্ট্রির অনুপাত; চালক মেলার সময় (p50, p90) আর হার; offer গ্রহণের হার; ETA-র ভুল; double assignment — সবসময় শূন্য, একটিও হলে alert.

খরচ কোথায়

Memory প্রায় নগণ্য। খরচ মূলত: লাখো সংযোগের gateway, routing-এর CPU, trace-এর storage (retention-এ নিয়ন্ত্রণযোগ্য), আর ব্যবহারকারীর মোবাইল ডেটা।

১০ · AI-এর যুগে — ride-sharing-এর নকশা AI দিয়ে, কিন্তু যাচাই করে

AI-কে শুধু “একটি ride-sharing অ্যাপের নকশা চাই” বললে আসে microservices, Kafka, Redis, Kubernetes-এর একটি সুন্দর ছবি — কিন্তু এই case-এর আসল প্রশ্নগুলো প্রায়ই বাদ বা ভুল:

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

• লেখার হার, memory আর storage নিজে আবার হিসাব করেছি — একক আর peak ঠিক আছে
• সর্বশেষ অবস্থান, ইতিহাস আর trip-এর অবস্থা আলাদা ঘরে, আর প্রতিটির consistency স্পষ্ট
• কাছের চালক খোঁজায় প্রতিবেশী cell আর বলয় বাড়ানোর নিয়ম আছে; একটি সীমানার উদাহরণে পরীক্ষা করেছি
• Double assignment, offer-এর মেয়াদ আর matcher মরে যাওয়ার ক্ষেত্র নকশায় আছে
• পণ্যের সীমা বা দাম official documentation-এ মিলিয়েছি, আর একটি ছোট simulation বা load test চালিয়েছি
• অবস্থান-ডেটার গোপনীয়তা, retention আর প্রবেশাধিকারের নিয়ম আছে; প্রয়োজনের চেয়ে বড় ব্যবস্থা নেই