Proximity Service (Yelp/Nearby) ডিজাইন

ধরো তুমি Yelp বা Google Maps-এর "nearby restaurants" ফিচারটা বানাচ্ছো। ইউজার তার বর্তমান লোকেশন থেকে ৫ কিমির মধ্যে সব রেস্টুরেন্ট দেখতে চায়। শুনতে সহজ, কিন্তু এর পিছনের geospatial indexing-টাই এই সিস্টেমের আসল মজা। চলো ধাপে ধাপে interview framework মেনে ডিজাইন করি।

১. সমস্যা বোঝা (Requirements)

প্রথমে scope ঠিক করি। বড় সিস্টেম তিনটা ভাগে ভাবা যায় — places খোঁজা, places-এর তথ্য দেখা, এবং business owner দ্বারা places যোগ/আপডেট করা।

Functional requirements:

• ইউজারের (latitude, longitude) এবং একটি radius (যেমন ২ কিমি, ৫ কিমি) দিলে সেই radius-এর ভিতরের সব places ফেরত দিতে হবে।
• প্রতিটি place-এর details (নাম, রেটিং, ছবি, ঠিকানা) দেখা যাবে।
• Business owner নতুন place যোগ, আপডেট, ডিলিট করতে পারবে।
• ফলাফল distance এবং rating অনুযায়ী ranked হবে।

Non-functional requirements:

• Low latency — nearby search ১০০ ms-এর কম হওয়া উচিত।
• High availability — read পথ সবসময় চালু থাকবে।
• Read-heavy — search query অনেক বেশি, place update কম।
• Eventual consistency চলবে — নতুন রেস্টুরেন্ট সার্চে আসতে কয়েক মিনিট দেরি হলে সমস্যা নেই।

২. স্কেল আন্দাজ (Estimation)

ধরা যাক বিশ্বব্যাপী জনপ্রিয় একটা সার্ভিস।

places (business) সংখ্যা      = 200 million
দৈনিক active user            = 100 million
গড়ে প্রতি user/দিন search     = 5
দৈনিক search query           = 100M × 5 = 500 million
search QPS (গড়)             = 500M / 86,400 ≈ 5,800 QPS
peak QPS (≈ 5x)             ≈ 30,000 QPS

place update (write) QPS    ≈ 200/sec (search-এর তুলনায় নগণ্য)
=> read : write ≈ 100,000 : 1  → চরম read-heavy

storage:
  per place ≈ 1 KB (metadata) + geo-index entry
  200M × 1 KB = 200 GB metadata (একটি cluster-এ সহজেই আঁটে)
  geo-index (place_id + geohash) ≈ 200M × ~30 B = ~6 GB → মেমোরিতে রাখা সম্ভব

মূল শিক্ষা: storage সমস্যা না, QPS ও latency-ই আসল challenge। তাই caching আর read replica-তে জোর দিতে হবে।

৩. API ডিজাইন

GET /v1/search/nearby
    ?lat=23.7461
    &lng=90.3742
    &radius=5000          # মিটারে
    &category=restaurant
    &limit=20
    &page_token=...
→ 200 OK
  {
    "places": [
      { "id": "p_123", "name": "Star Kabab",
        "lat": 23.74, "lng": 90.37,
        "distance_m": 420, "rating": 4.3 }
    ],
    "next_page_token": "..."
  }

GET  /v1/places/{id}                 # details
POST /v1/places        { name, lat, lng, category, ... }   # owner add
PUT  /v1/places/{id}   { ... }       # update
DELETE /v1/places/{id}

লক্ষ করো — radius মিটারে নিচ্ছি যাতে frontend-এর সাথে confusion না হয়, আর pagination-এ page_token ব্যবহার করছি offset-এর বদলে (বড় ডেটাসেটে বেশি স্থিতিশীল)।

৪. ডেটা মডেল

দুটো আলাদা জিনিস লাগবে — place-এর metadata আর geospatial index।

টেবিল/স্টোর	মূল কলাম	উদ্দেশ্য
places	id (PK), name, lat, lng, category, rating, address	place-এর পূর্ণ তথ্য
geo_index	geohash (prefix), place_id	কোন cell-এ কোন place

Choice — কোন database?

• places metadata-র জন্য একটি relational DB (PostgreSQL) বা document store ভালো — read-heavy বলে অনেক read replica যোগ করা যাবে।
• geo_index দুইভাবে রাখা যায়: (১) geohash কলামে সাধারণ B-tree index দিয়ে relational DB-তেই, অথবা (২) PostgreSQL-এর PostGIS extension যা GiST index দিয়ে নেটিভ geo-query দেয়।

আমরা শুরুতে geohash-ভিত্তিক approach নেব কারণ এটা যেকোনো DB ও cache-এ সহজে কাজ করে এবং shard করা সোজা।

৫. হাই-লেভেল ডিজাইন

মূল components:

• Load Balancer → API Gateway
• Search Service (stateless, geo-index query করে)
• Place Service (CRUD, metadata সামলায়)
• Geo-Index Store (geohash → place_ids)
• Metadata DB (primary + অনেক read replica)
• Cache layer (Redis) — hot cell ও popular place

Nearby search flow:

1. ইউজার (lat, lng, radius) পাঠায়।
2. Search Service (lat, lng) থেকে geohash বের করে। radius অনুযায়ী উপযুক্ত precision (prefix length) বেছে নেয় — বড় radius হলে ছোট prefix (বড় cell)।
3. সেই geohash cell + আশেপাশের ৮টি neighbor cell-এর place_id-গুলো index থেকে আনে। (neighbor নেওয়া জরুরি, নইলে cell-এর কিনারায় থাকা ইউজার boundary problem-এ পড়ে।)
4. candidate place-গুলোর precise distance Haversine formula দিয়ে হিসাব করে radius-এর বাইরেরগুলো বাদ দেয়।
5. distance + rating দিয়ে rank করে metadata যোগ করে ফেরত দেয়।

৬. গভীরে (Deep Dive)

Geohash কীভাবে কাজ করে

Geohash পৃথিবীকে recursively চারভাগ করে এবং প্রতিটি cell-কে একটি ছোট string দেয় (base32 encoding)। মূল idea — common prefix মানে কাছাকাছি অবস্থান।

precision 4  → cell ≈ 39 km × 19 km   (city scale)
precision 5  → cell ≈ 4.9 km × 4.9 km (neighborhood)
precision 6  → cell ≈ 1.2 km × 0.6 km (block)
precision 7  → cell ≈ 153 m × 153 m   (street)

৫ কিমি radius হলে precision 5 বা 6 ভালো। query-তে আমরা প্রথমে geohash বের করি, তারপর WHERE geohash LIKE 'wh0r%' জাতীয় prefix lookup করি — যা index-এ অত্যন্ত দ্রুত।

সীমাবদ্ধতা: geohash গ্রিড সমান নয় (cell-এর ভিতর place অসমভাবে বণ্টিত)। ঘন এলাকায় (নিউইয়র্ক) এক cell-এ হাজার হাজার place, ফাঁকা এলাকায় শূন্য। এর সমাধান করে Quadtree ও S2।

Quadtree বনাম S2

• Quadtree একটি ট্রি যেখানে প্রতিটি node চারটি child-এ ভাগ হয়, কিন্তু শুধু তখনই ভাগ হয় যখন একটি cell-এ একটি threshold-এর বেশি place জমে (যেমন ১০০টির বেশি)। ফলে ঘন এলাকায় ছোট cell, ফাঁকা এলাকায় বড় cell — adaptive। সমস্যা: এটি সাধারণত in-memory রাখতে হয় এবং place যোগ হলে rebuild/rebalance লাগে।

• S2 (Google-এর library) পৃথিবীকে একটি cube-এ project করে Hilbert curve দিয়ে cell-এ ভাগ করে। এর সুবিধা — cell-গুলো 64-bit integer, range query করা সহজ, এবং Hilbert curve কাছাকাছি জায়গাগুলোকে কাছাকাছি number দেয়। distance ও coverage হিসাবে geohash-এর চেয়ে accurate।

পদ্ধতি	adaptive density?	সহজতা	ব্যবহার
Geohash	না (fixed grid)	খুব সহজ	দ্রুত prototype, prefix search
Quadtree	হ্যাঁ	মাঝারি	uneven density, in-memory
S2	আংশিক (level বেছে)	জটিল	Google Maps, precise

Caching strategy

read-heavy বলে caching-ই asset। তিন স্তর:

1. Hot cell cache: জনপ্রিয় geohash cell-এর place list Redis-এ TTL সহ রাখি (যেমন গুলশান এলাকা)।
2. Place metadata cache: popular place-এর details cache করি।
3. CDN: ছবি ও static content।

যেহেতু place খুব কম change হয়, cache hit rate স্বাভাবিকভাবেই অনেক উঁচু (৯০%+) থাকে।

৭. বটলনেক ও স্কেলিং

• Read scaling: metadata DB-তে অনেক read replica; primary শুধু write নেয়। search QPS replica + cache মিলে সামলায়।
• Geo-index sharding: geohash prefix দিয়ে shard করা যায়, কিন্তু density skew-এর কারণে কিছু shard (ঘন শহর) hot হবে। সমাধান — hot prefix আলাদা shard-এ ভাঙা, বা Quadtree-র adaptive ভাগ ব্যবহার।
• Boundary edge cases: সবসময় neighbor cell অন্তর্ভুক্ত করা; খুব বড় radius হলে কম precision বেছে কম cell scan।
• Write path: place add হলে metadata DB + geo-index দুটোতেই update; eventual consistency বলে index async আপডেট হলেও চলে।
• Hot spot: কোনো বিখ্যাত এলাকার search burst হলে cell cache + rate limiting বাঁচায়।

৮. সারসংক্ষেপ

Proximity service-এর হৃদয় হলো 2D location-কে 1D searchable key-তে নামিয়ে আনা — geohash/quadtree/S2 ঠিক এই কাজটাই করে, যাতে একটি সাধারণ index দিয়ে দ্রুত খোঁজা যায়। সিস্টেমটা চরম read-heavy, তাই read replica ও multi-layer caching দিয়ে latency কম রাখা হয়। boundary problem মনে রেখে neighbor cell নেওয়া, density skew সামলাতে adaptive index বাছা, আর precise distance-এর জন্য Haversine — এই কয়টা detail interview-এ আলাদা নম্বর এনে দেয়।