Rate Limiter / Search Design - এক উৎসবে দুইটা design

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

আগের সেশনে URL shortener দিয়ে case study এর সাতটা ধাপ শিখেছি। আজ সেই ধাপ মেনেই একটা online shop এর দুইটা ছোট অংশ design করবো। প্রথমটা একটা rate limiter, যেটা bot এর হাত থেকে login বাঁচায়। দ্বিতীয়টা search, যেটা “পাঞ্জাবি” লিখলেও খুঁজে পায়, “panjabi” লিখলেও খুঁজে পায়। দুইটাতেই আগের সেশনের Redis, index আর queue নতুন রূপে ফিরে আসবে।

০১ Login API তে bot এর ভিড়: প্রতিটা server এ আলাদা limit রাখলে কেন কাজ হয় না?

চৈত্রের শেষ সপ্তাহ। পহেলা বৈশাখের আর দশ দিন বাকি। রাত দুইটায় রিয়ার phone বেজে উঠলো। রিয়া “বাজারঘর” নামের একটা online shop এর backend engineer। Alert বলছে, login API তে মিনিটে ৪০,০০০ চেষ্টা আসছে, যেখানে স্বাভাবিক সময়ে আসে মিনিটে ৩,০০০। ঘুমঘুম চোখে log খুলে রিয়া বুঝলো, এগুলো মানুষ না। কেউ অন্য কোনো site থেকে ফাঁস হওয়া email আর password এর লম্বা list নিয়ে একটা একটা করে চেষ্টা করছে।

এই আক্রমণের নাম credential stuffing। অনেকেই একই password সব জায়গায় ব্যবহার করে। তাই অন্য site এর ফাঁস হওয়া list থেকে কিছু account এ ঢোকা যায়। Bot এর দরকার শুধু অনেক বেশি চেষ্টা করার সুযোগ। আমাদের কাজ সেই সুযোগটা কেড়ে নেওয়া।

সেশন ২১ এ আপনি rate limiting শিখেছেন: একজন client নির্দিষ্ট সময়ে কতগুলো request পাঠাতে পারবে, তার একটা সীমা। সীমা পার হলে server 429 Too Many Requests ফেরত দেয়। সেখানে প্রশ্ন ছিলো algorithm নিয়ে। আজকের প্রশ্ন অন্য: বাজারঘরের ২০টা API server আছে। এই ২০টা server মিলে একটাই limit কীভাবে মানবে?

Requirement

Functional requirement (system কী করবে):

• একই IP থেকে মিনিটে ১০টার বেশি login চেষ্টা হলে বাকিগুলো আটকাবে।
• একই account এ ১৫ মিনিটে ৫টা ভুল password এর পর সেই account এ login সাময়িক বন্ধ রাখবে। Bot ৩,০০০ আলাদা IP ব্যবহার করলেও এই নিয়ম তাকে ধরে।
• আটকানো request কে 429 আর Retry-After header দেবে, যাতে ভালো client জানে কতক্ষণ পরে আবার চেষ্টা করতে হবে।

Non-functional requirement (কতটা ভালোভাবে করবে):

• প্রতিটা check হবে ২-৩ ms এর মধ্যে, কারণ এটা প্রতিটা request এর পথে বসে আছে।
• ২০টা server মিলে limit টা একটাই থাকবে। কোন server request পেলো, তাতে হিসাব বদলাবে না।
• Limiter নিজে down হলে পুরো shop যেন বন্ধ না হয়ে যায় (সেকশন ০৪ এ দেখবো)।

প্রথম চেষ্টা: প্রতিটা server নিজের memory তে গুনবে

সবচেয়ে সহজ উপায় হলো প্রতিটা server নিজের memory তে একটা counter রাখবে। কিন্তু load balancer (সেশন ০২) request গুলো ২০টা server এ ভাগ করে দেয়। তাই প্রতিটা server bot এর মোট চেষ্টার মাত্র ২০ ভাগের এক ভাগ দেখে। প্রত্যেকে ভাবে “মাত্র ১০টা, ঠিক আছে”। অথচ bot আসলে মিনিটে ২০০টা চেষ্টা করে ফেলেছে।

সমাধান হলো counter টা সব server এর বাইরে, একটা shared জায়গায় রাখা। সেই জায়গাটা খুব দ্রুত হতে হবে, কারণ প্রতিটা request এর আগে তাকে জিজ্ঞেস করতে হবে। এখানে Redis (সেশন ০৪) একদম মানানসই: সব data memory তে থাকে, আর একটা call এ সাধারণত এক millisecond এর কম লাগে। সব server যখন একই shared counter দেখে limit মানে, তাকে বলে distributed rate limiter।

Back-of-envelope হিসাব

সেশন ২৩ এ দেখেছেন, design এর আগে মোটা দাগে একটা হিসাব করে নিতে হয়। বাজারঘরের বৈশাখী সপ্তাহের হিসাবটা এরকম:

বাজারঘর login API, বৈশাখী সপ্তাহ

স্বাভাবিক login: 3,000 / min ≈ 50 req/s
Bot attack এর সময়: 40,000 / min ≈ 670 req/s
সব API মিলে, sale এর peak এ: ~20,000 req/s

প্রতিটা request এ check: 1 টা Redis call, ~0.5 ms (একই data center)
এক Redis node এর ক্ষমতা: সহজ command এ ~100,000 ops/s
তাই 20,000 check/s এক node এই চলে, হাতে ~5 গুণ জায়গা থাকে

Memory:
  active key (user + IP): ~500,000
  প্রতিটা key: ~100 byte
  মোট: 500,000 × 100 byte ≈ 50 MB

হিসাব থেকে দুটো কথা পরিষ্কার। এক, একটা Redis node এই কাজের জন্য যথেষ্ট, আর হাতে অনেক জায়গা থাকে। দুই, memory প্রায় লাগেই না। তাই আসল চ্যালেঞ্জ speed বা size না। আসল চ্যালেঞ্জ হলো হিসাবটা সঠিক রাখা, যখন ২০টা server একই মুহূর্তে একই counter ছুঁতে চায়।

০২ Redis এ counter রাখলে race condition কোথায়?

রিয়ার team এর একজন junior প্রথম version টা লিখলো। প্রতিটা request এ server Redis থেকে counter পড়ে (GET)। ১০ এর কম হলে এক বাড়িয়ে লিখে দেয় (SET)। দেখতে একদম ঠিক। কিন্তু দুইটা server একদম একই সময়ে request পেলে কী হয়, দেখুন:

দুইটা server ই পড়লো ৯। দুজনেই ভাবলো “এখনো জায়গা আছে”। দুজনেই লিখলো ১০। ফলে দুটো request ই পার হলো, কিন্তু counter বাড়লো মাত্র একবার। দুই বা তার বেশি কাজ একই data একসাথে ছুঁলে, কে আগে আর কে পরে তার উপর result নির্ভর করলে, তাকে বলে race condition। Bot একসাথে শত শত request পাঠায়, তাই এই ফাঁকটা সে ঠিকই কাজে লাগাবে।

সমাধান ১: INCR, যেটা ভাগ হয় না

Redis এর INCR command পড়া আর বাড়ানো, দুটো কাজ একটা ধাপে করে। Redis একটা command শেষ না করে আরেকটা ধরে না। তাই মাঝখানে অন্য কোনো server ঢুকতে পারে না। যে কাজ পুরোটা একসাথে হয়, মাঝপথে ভাগ হয় না, তাকে বলে atomic operation। দুই server একসাথে INCR করলে একজন পায় ১০, আরেকজন পায় ১১। যে ১১ পেলো, সে request টা আটকে দেয়।

সমাধান ২: INCR আর EXPIRE কে এক সাথে বাঁধা

Counter টা চিরকাল থাকলে চলবে না। এক মিনিট পরে সেটা মুছে যেতে হবে। তাই প্রথম INCR এর পর EXPIRE দিয়ে ৬০ সেকেন্ডের TTL (সেশন ০৪) বসাতে হয়। কিন্তু এখানে দুইটা আলাদা command। প্রথমটার পর server crash করলে দ্বিতীয়টা আর চলে না। তখন counter টা কখনো মোছে না, আর সেই user চিরদিনের জন্য আটকে যায়।

এর উত্তর হলো Lua script। Redis এর ভেতরে ছোট একটা script পাঠানো যায়। Redis পুরো script টা একটানা চালায়, মাঝখানে অন্য কোনো command ঢুকতে দেয় না। তাই script এর ভেতরের সব কাজ মিলে একটা atomic কাজ হয়ে যায়:

-- KEYS[1] = "rl:login:ip:203.0.113.7:29012345"   (IP আর মিনিটের নম্বর)
-- ARGV[1] = 10 (limit)    ARGV[2] = 60 (window, সেকেন্ডে)

local count = redis.call('INCR', KEYS[1])

if count == 1 then
    -- এই মিনিটের প্রথম request: এখনই TTL বসানো হয়
    redis.call('EXPIRE', KEYS[1], ARGV[2])
end

if count > tonumber(ARGV[1]) then
    return 0    -- limit পার, server 429 পাঠাবে
end

return 1        -- request এগিয়ে যাবে

প্রতিটা API server request পেলে এই script টা একবার চালায়। উত্তর ১ হলে request এগিয়ে যায়। উত্তর ০ হলে server 429 ফেরত দেয়। একটাই network round trip, আর কোনো race condition নেই।

০৩ Sliding window log নাকি sliding window counter?

সেশন ২১ এ চারটা algorithm এর ছবি দেখেছেন। এক লাইনে মনে করিয়ে দিই:

• Fixed window: প্রতি মিনিটের জন্য একটা counter; মিনিট বদলালে শূন্য থেকে শুরু।
• Sliding window: ঠিক “গত ৬০ সেকেন্ড” ধরে গোনে, ঘড়ির মিনিট ধরে না।
• Token bucket: একটা বালতিতে নির্দিষ্ট হারে token জমে; প্রতিটা request একটা token খরচ করে।
• Leaky bucket: request গুলো একটা লাইনে দাঁড়ায় আর স্থির গতিতে বের হয়।

উপরের Lua script টা আসলে fixed window। এর একটা দুর্বলতা আছে। Bot ১০:০০:৫৯ এ ১০টা চেষ্টা করলো, আবার ১০:০১:০০ এ ১০টা। দুই সেকেন্ডে ২০টা চেষ্টা পার হয়ে গেলো, কারণ দুটো আলাদা মিনিটে পড়েছে। Login এর মতো জায়গায় এই ফাঁক বন্ধ করতে চাই। Sliding window এর দুটো রূপ আছে, আর এদের cost একেবারে আলাদা।

Sliding window log: প্রতিটা request এর সময় (timestamp) একটা তালিকায় রাখা হয়। Redis এ এর জন্য sorted set ব্যবহার হয়, যেটা প্রতিটা entry কে একটা সংখ্যা (এখানে সময়) ধরে সাজিয়ে রাখে। নতুন request এলে ৬০ সেকেন্ডের পুরোনো timestamp গুলো মুছে ফেলা হয়, তারপর বাকিগুলো গোনা হয়। হিসাব একদম নিখুঁত। কিন্তু limit যত, প্রতি user এর জন্য তত entry রাখতে হয়।

Sliding window counter: শুধু দুইটা সংখ্যা রাখা হয়: আগের মিনিটের count আর এই মিনিটের count। তারপর আগের মিনিটের যতটুকু অংশ এখনো “গত ৬০ সেকেন্ড” এর ভেতরে পড়ে, ততটুকু ধরে একটা আনুমানিক হিসাব করা হয়:

এটা ধরে নেয় যে আগের মিনিটের request গুলো পুরো মিনিট জুড়ে সমানভাবে ছড়ানো ছিলো। সব সময় তা হয় না, তাই হিসাবটা আনুমানিক। তবে Cloudflare নিজেদের traffic এ মেপে দেখেছিলো, মাত্র ০.০০৩% request এ এই আনুমানিক হিসাব ভুল সিদ্ধান্ত দিয়েছিলো।

রিয়া দুটোই ব্যবহার করলো। Login এ limit মাত্র ১০, তাই log রাখলেও memory খুব কম লাগে, আর হিসাব নিখুঁত হয়। Search আর product API তে limit বড়, সেখানে counter।

০৪ Redis নিজেই down হলে: fail open নাকি fail closed?

এখন প্রতিটা request এর পথে Redis বসে আছে। তাহলে Redis নিজেই একটা নতুন SPOF (সেশন ০১)। ধরুন বৈশাখের আগের সন্ধ্যায় Redis এর primary down হলো। Replica কে primary বানাতে (failover, সেশন ০৩) ২০ সেকেন্ড লাগবে। এই ২০ সেকেন্ড API server গুলো কী করবে? দুটো রাস্তা আছে।

• Fail open: limiter কাজ না করলে সব request কে যেতে দেওয়া হয়। Shop চালু থাকে, কিন্তু ঐ সময়টুকু bot ও বাধা পায় না।
• Fail closed: limiter কাজ না করলে সব request আটকে দেওয়া হয়। Bot পুরোপুরি আটকায়, কিন্তু সত্যিকারের customer ও আটকে যায়।

কোনোটাই সব জায়গায় ঠিক না। উত্তরটা নির্ভর করে endpoint টার উপর: এখানে ভুল হলে কোনটা বেশি ক্ষতি করে?

Product দেখা বা search এ কয়েক সেকেন্ড বেশি request গেলে তেমন ক্ষতি হয় না। তাই সেখানে fail open। কিন্তু login আর OTP (SMS এ পাঠানো এক বারের code) এ ক্ষতিটা বড়। OTP এর প্রতিটা SMS এ টাকা লাগে, আর bot মিনিটে হাজারটা SMS পাঠাতে পারলে এক রাতেই বড় একটা bill হয়ে যায়। সেখানে fail closed এর কাছাকাছি কিছু চাই।

রিয়ার team মাঝামাঝি একটা উপায় নিলো। Redis এর জবাব ৫ ms এর মধ্যে না এলে server টা timeout (সেশন ০১) ধরে নেয়। তারপর নিজের memory তে একটা ছোট local limit চালায়। ২০টা server, তাই প্রতিটা server মোট limit এর ২০ ভাগের এক ভাগ নিজে মানে। হিসাবটা নিখুঁত না, তবে পুরো খোলা দরজার চেয়ে অনেক ভালো।

০৫ ২০ লাখ product থেকে “পাঞ্জাবি” কীভাবে খুঁজবো?

এবার রিয়ার সামনে সবচেয়ে বড় কাজ। গত বছর বৈশাখে customer রা অভিযোগ করেছিলো: “panjabi” লিখলে কিছুই আসে না, “পাঞ্জাবী” লিখলে অর্ধেক আসে। এবার search ঠিক করতে হবে।

Requirement আর হিসাব

• User একটা বা কয়েকটা শব্দ লিখবে, Bangla বা English এ। মিল থাকা product গুলো ভালো থেকে কম ভালো ক্রমে আসবে।
• টাইপ করার সময়েই নিচে suggestion আসবে।
• নতুন product যোগ হলে কয়েক সেকেন্ডের মধ্যে search এ পাওয়া যাবে।
• Search এর p99 latency ২০০ ms এর নিচে থাকবে, suggestion এর ৫০ ms এর নিচে। p99 মানে ১০০টা request এর মধ্যে সবচেয়ে ধীর ১টা বাদে বাকি সব এর চেয়ে দ্রুত।

বাজারঘর search, বৈশাখী সপ্তাহ

Product: 2,000,000 (20 লাখ)
Search: 1,500,000 / দিন ≈ 17 / s গড়ে
Sale এর peak (গড়ের 10 গুণ): ~170 search / s
Typeahead (debounce সহ): প্রতি search এ ~3 request, peak এ ~510 / s

Index এর size:
  প্রতি product এ token: ~50 (title + description)
  মোট posting: 2,000,000 × 50 = 100,000,000
  প্রতি posting: ~8 byte (compress করার পর)
  মোট index: ≈ 800 MB, এক machine এর memory তেই আঁটে

SQL এর LIKE কেন চলবে না

প্রথমে মনে হতে পারে, WHERE title LIKE '%পাঞ্জাবি%' লিখলেই তো হয়। কিন্তু সেশন ০৭ এর B-tree index সাজানো থাকে title এর শুরু থেকে। শব্দটা title এর মাঝখানে থাকলে index কোনো কাজে আসে না। তখন database কে ২০ লাখ row একটা একটা করে পড়তে হয়। তাছাড়া LIKE জানে না যে “panjabi” আর “পাঞ্জাবি” একই জিনিস। কোন result আগে দেখাতে হবে, সেটাও জানে না।

Inverted index: বইয়ের শেষের সূচির মতো

একটা মোটা বইয়ে “photosynthesis” কোথায় আছে খুঁজতে আপনি প্রথম পাতা থেকে পড়া শুরু করেন না। বইয়ের শেষে যান। সেখানে প্রতিটা শব্দের পাশে লেখা থাকে কোন কোন পাতায় সেটা আছে। Search engine ঠিক এই কাজটাই করে।

সাধারণ table এ প্রতিটা product এর পাশে তার শব্দগুলো থাকে। উল্টো দিক থেকে সাজালে প্রতিটা শব্দের পাশে থাকে সেই শব্দ যে যে product এ আছে তাদের তালিকা। এই উল্টো করে সাজানো কাঠামোর নাম inverted index। প্রতিটা শব্দের পাশের product তালিকাটাকে বলে posting list।

“লাল পাঞ্জাবি” খুঁজলে engine দুইটা শব্দের posting list বের করে। তারপর দুই তালিকার মিল খোঁজে। এই তালিকাগুলো product id ধরে সাজানো থাকে, তাই দুইটা সাজানো তালিকার মিল বের করা খুব দ্রুত হয়। ২০ লাখ product পড়তে হয় না, শুধু দুইটা ছোট তালিকা পড়লেই চলে।

Catalog অনেক বড় হলে index টাকে কয়েকটা shard এ ভাগ করা হয় (সেশন ০৫)। Query সব shard এ একসাথে যায়, প্রতিটা shard নিজের সেরা result ফেরত দেয়, তারপর সেগুলো এক করে চূড়ান্ত তালিকা বানানো হয়। বাস্তবে এই কাজের জন্য সাধারণত Elasticsearch বা OpenSearch ব্যবহার হয়। দুটোই ভেতরে Lucene নামের একটা inverted index library দিয়ে বানানো।

০৬ Bangla আর English text কে token এ ভাঙবো কীভাবে, আর index কখন update হয়?

Inverted index বানানোর আগে একটা প্রশ্নের উত্তর দিতে হয়: “শব্দ” বলতে আসলে কী বোঝাবো? একজন seller title লিখলো “লাল সুতি পাঞ্জাবীগুলো”। আরেকজন লিখলো “Red Cotton PANJABI”। Customer খুঁজছে “পাঞ্জাবি”। তিনটা আলাদা বানান, অথচ জিনিস একই।

Text কে ছোট ছোট খোঁজার যোগ্য টুকরায় ভাঙা আর প্রতিটা টুকরাকে একটা নিয়মিত রূপে আনার কাজকে বলে tokenization। প্রতিটা টুকরাকে বলে token। Index এ শব্দ নয়, এই token গুলোই জমা হয়।

ধাপগুলো এক এক করে দেখি:

1. Unicode normalization: Bangla তে একই দেখতে অক্ষর computer এ দুইভাবে লেখা যায়। যেমন “য়” একটা অক্ষর হিসেবেও লেখা যায়, আবার “য” এর সাথে নিচের ফোঁটা জুড়েও লেখা যায়। চোখে একই, কিন্তু computer এর কাছে আলাদা। তাই প্রথমেই সবকিছু একটা নিয়মিত রূপে আনা হয়।
2. ভাঙা: space, কমা আর দাঁড়ি (।) দেখে text কে শব্দে ভাগ করা হয়। English এ বড় হাতের অক্ষর ছোট হাতের করা হয়, তাই “PANJABI” হয়ে যায় “panjabi”।
3. বানান মেলানো: “পাঞ্জাবী” আর “পাঞ্জাবি”, “শাড়ী” আর “শাড়ি”, দুই বানানই খুব চলে। ঈ-কার কে ই-কার এ আনার মতো কয়েকটা নিয়ম দিয়ে এগুলোকে এক করা হয়।
4. শব্দের মূল বের করা: “পাঞ্জাবীগুলো”, “পাঞ্জাবির”, “পাঞ্জাবিটা” থেকে “গুলো”, “র”, “টা” এর মতো শেষাংশ কেটে মূল শব্দ “পাঞ্জাবি” বের করা হয়। English এ “shirts” থেকে “shirt”। এই কাজের নাম stemming।
5. প্রতিশব্দ মেলানো: “panjabi”, “punjabi” আর “পাঞ্জাবি” কে একই token এ আনা হয়, একটা ছোট synonym তালিকা দিয়ে। “red” আর “লাল” ও এভাবে মেলে।

নতুন product index এ কখন ঢোকে?

বৈশাখের আগে seller রা দিনে প্রায় ৩০,০০০ নতুন product যোগ করে, আর লাখো product এর দাম ও stock বদলায়। প্রতিটা save এর সাথে সাথে index update করতে গেলে seller এর “Save” button ধীর হয়ে যাবে। Search cluster একটু ধীর হলে product save ও আটকে যাবে।

তাই কাজটা আলাদা করা হয়। Product আগে main database এ save হয়, seller সাথে সাথে “সফল” দেখে। তারপর একটা product.updated event (সেশন ১০) queue তে যায়। একটা indexer worker সেটা তুলে tokenize করে index update করে। একে বলে async indexing।

এর মানে, নতুন product search এ আসতে কয়েক সেকেন্ড দেরি হয়। Elasticsearch নিজেও default ভাবে প্রতি ১ সেকেন্ডে নতুন লেখাগুলো search এর জন্য খুলে দেয়। এভাবে কয়েক সেকেন্ডের মধ্যে খুঁজে পাওয়াকে বলে near real-time search। এটা eventual consistency (সেশন ০৩) এর আরেকটা চেহারা। মনে রাখবেন, সত্যিকারের data থাকে main database এ। Index হারিয়ে গেলেও database থেকে আবার পুরোটা বানানো যায়।

০৭ মিল পাওয়া ৩,০০০ product এর কোনটা আগে দেখাবো?

“লাল পাঞ্জাবি” লিখলে মিল পাওয়া যায় ৩,০০০ product। Customer প্রথম পাতার ২০টার বেশি সাধারণত দেখে না। তাই কোন ২০টা আগে আসবে, সেটাই search এর আসল মান ঠিক করে। দুই ধরনের হিসাব মিলিয়ে এটা ঠিক হয়।

লেখার সাথে মিল (relevance):

• যে product এ খোঁজা শব্দটা বেশিবার আছে, সেটা বেশি প্রাসঙ্গিক।
• কিন্তু যে শব্দ প্রায় সব product এ আছে (“নতুন”, “অফার”), তার দাম কম। যে শব্দ অল্প product এ আছে (“জামদানি”), তার দাম বেশি। এই দুই ধারণা মিলিয়ে বানানো হিসাবের নাম TF-IDF। এর একটা উন্নত রূপ BM25, যেটা Elasticsearch default ভাবে ব্যবহার করে।
• শব্দটা title এ থাকলে description এ থাকার চেয়ে বেশি নম্বর পায়।

ব্যবসার signal: কতজন কিনেছে, rating কত, stock আছে কি না, কতজন result এ click করে কিনেছে। Relevance দিয়ে প্রথম ১,০০০টা বাছাই হয়। তারপর এই signal গুলো মিলিয়ে চূড়ান্ত ক্রম হয়। Feed এর two-stage ranking এর সাথে মিলটা খেয়াল করুন।

তৃতীয়টার বিক্রি আর rating ভালো, কিন্তু stock শেষ। Customer click করে “stock নেই” দেখলে হতাশ হয়। তাই সেটা নিচে নামে।

০৮ “pan” লিখতেই suggestion আসে কীভাবে?

Customer “p”, “a”, “n” লিখতেই নিচে ভেসে ওঠে “panjabi” আর “pant”। টাইপ করার সাথে সাথে সম্ভাব্য পুরো query দেখানোকে বলে typeahead (বা autocomplete)। মানুষ সাধারণত প্রতি ১৫০-২০০ ms এ একটা অক্ষর টাইপ করে। তাই suggestion কে এর চেয়েও দ্রুত আসতে হয়, নইলে পরের অক্ষর টাইপ হয়ে যায় আর পুরোনো suggestion অর্থহীন হয়ে পড়ে।

Trie: অক্ষর ধরে সাজানো গাছ

Trie একটা গাছের মতো data structure। এর প্রতিটা ধাপে একটা করে অক্ষর থাকে। Root থেকে নিচে নামতে নামতে অক্ষরগুলো জুড়লে একটা prefix (শব্দের শুরুর অংশ) তৈরি হয়। “pan” খুঁজতে root থেকে p, তারপর a, তারপর n, মাত্র তিন ধাপ। Dictionary তে লাখটা query থাকলেও ধাপ তিনটাই।

শুধু prefix এর node এ পৌঁছানো যথেষ্ট না। এর নিচে হাজারটা query থাকতে পারে। প্রতিবার পুরো উপগাছ ঘুরে সবচেয়ে জনপ্রিয় ৫টা বের করতে গেলে সময় লাগে। তাই প্রতিটা node এ আগে থেকেই তার নিচের সেরা ৫টা query হিসাব করে রেখে দেওয়া হয়। Request এলে শুধু prefix ধরে node এ যাওয়া আর সেখানে রাখা তালিকাটা ফেরত দেওয়া। একে বলে top-k রাখা।

Bangla তেও একই trie কাজ করে, শুধু অক্ষরগুলো Bangla। “পাঞ্” লেখা মানে computer এর কাছে চারটা অক্ষর: প, া, ঞ, ্। Tokenization এর synonym তালিকা ব্যবহার করে “panj” লিখলেও “পাঞ্জাবি” suggestion দেখানো যায়।

Trie প্রতিটা search এ বদলায় না। Search এর log থেকে প্রতি ঘণ্টায় একটা job নতুন trie বানায়, তারপর পুরোনোটার জায়গায় বসিয়ে দেয়। এটা আরেকটা async কাজ। এক ঘণ্টা পুরোনো জনপ্রিয়তার হিসাব suggestion এর জন্য যথেষ্ট ভালো।

জনপ্রিয় prefix cache করা, আর অপ্রয়োজনীয় request কমানো

বৈশাখের সপ্তাহে হাজার হাজার মানুষ ঠিক একই জিনিস লেখে: “p”, “pa”, “pan”, “পা”, “পাঞ”। এই ছোট prefix গুলোর উত্তর সবার জন্য একই। তাই এগুলোর উত্তর Redis (সেশন ০৪) বা CDN edge এ (সেশন ০৬) ১০ মিনিটের TTL দিয়ে cache করা হয়। বেশিরভাগ request trie service পর্যন্ত পৌঁছায়ই না।

App এর দিক থেকেও request কমানো যায়। প্রতিটা অক্ষরে request না পাঠিয়ে, শেষ অক্ষর টাইপ করার পর ১০০ ms অপেক্ষা করা হয়। এর মধ্যে আরেকটা অক্ষর এলে আগের request বাতিল। এই কৌশলের নাম debounce। দ্রুত টাইপ করা মানুষের জন্য এতে request প্রায় অর্ধেক হয়ে যায়।

বৈশাখের আগের রাতে রিয়া নিজের phone এ “panj” লিখলো। চোখের পলকে নিচে এলো “পাঞ্জাবি”। সে হাসলো, laptop বন্ধ করলো, আর এবার শান্তিতে ঘুমাতে গেলো।

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

আগে নিজে ভাবুন। তারপর দেখুন: সবাই যেভাবে ভাবে, কেন সেটা অসম্পূর্ণ, আর আসল কথাটা কোথায়।

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

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

১২ মনে রাখুন

• প্রতিটা server এর নিজের counter মানে কোনো limit নেই: ২০টা server থাকলে bot ২০ গুণ সুযোগ পায়, তাই counter রাখুন shared Redis এ।
• পড়া আর লেখা এক ধাপে করুন: GET এর পর SET করলে race condition হয়, তাই INCR বা Lua script ব্যবহার করুন।
• TTL বসানো আর counter বাড়ানো একসাথে বাঁধুন: মাঝখানে crash হলে TTL ছাড়া counter থেকে যায় আর user চিরদিন আটকে থাকে।
• Fail open নাকি fail closed, endpoint দেখে ঠিক করুন: browse এ খোলা, login আর OTP এ সাবধান।
• Search মানে শব্দ থেকে document: LIKE '%...%' না, inverted index ব্যবহার করুন।
• Index আর query এ একই tokenizer চালান: নিয়ম বদলালে পুরো catalog আবার index করুন।
• Typeahead এ প্রতিটা অক্ষরের জন্য কাজ করবেন না: top-k আগে থেকে রাখুন, জনপ্রিয় prefix cache করুন, app এ debounce দিন।