240 Million Domenda Autocomplete: Tezlik Qanday Qilib "Jodu" Kabi Ko'rinadi

Siz biron nima yozayotganingizda, taklif tugashidan oldin paydo bo'lib qolganmisiz? Bu sehr emas — bu muhandislik. Va 240 million domen bilan ishlayotganda bu juda qiziq muammo bo'ladi.

Tezlik Nima Uchun Muhim

Foydalanuvchi qidiruv maydoniga nima yozishi bilan natija kutmoqda. Nielsen Norman Group tadqiqotiga ko'ra, 0.1 soniya — bu foydalanuvchiga "darhol bo'ldi" hissini beradigan chegara. Bundan sekinroq bo'lsa, interfeys "qotib qolgan" kabi tuyuladi — va foydalanuvchi o'z izlanishidan uziladi.

Wirewiki kabi domen tekshirish vositasi uchun autocomplete — bu asosiy kirish nuqtasi. DNS yozuvlarini tezda qidirayotganda har bir millisoniya muhim. Foydalanuvchi vositaning "miyagini o'qiyotganini" his qilishi kerak, serverni kutmasligi kerak.

Vaqtni O'g'irlash

Bu yerda asosiy g'oyani tushunishingiz kerak: muammo faqat API'ni tezlashtirish emas (garchi bu ham yordam beradi). Asosiy yondashuv — foydalanuvchi kiritayotgan vaqtni o'z foydangizga ishlatish.

Foydalanuvchi tugmani bosganda (keyDown), siz kiritayotgan narsa va keyingi ehtimoliy belgi uchun takliflarni oldindan yuklaysiz. Tugmani qo'yganda (keyUp), tayyor bo'lgan narsani ekranga chiqarasiz. Bu degani — sizning vaqt byudjetingiz API kechikishi emas, balki ikkita tugma bosish va ular orasidagi tanaffus.

60Hz displeyda har bir kadra 16.7ms bor. Hisob-kitob bo'yicha tez yozuvchilar uchun p99 da 121ms — bu sizning byudjetingiz. Natijalarni ikkinchi tugma bosish tugagunga tayyor qiling — va foydalanuvchiga bu "darhol" kabi his qilinadi.

Masshtabda Tezlikni Loyihalash

API 240 million domenni osongina qayta ishlashi kerak. Bu yerda yondashuv — mashhur domenlarni va kam qo'llaniladiganlarni turlicha qilish:

Birinchi qism (Head): Eng mashhur domenlar xotirada saqlanadigan belgi trie'sida turadi. Prefix bo'yicha qidiruv — bu oddiy ko'rsatkich yurishlari. Har bir mumkin bo'lgan prefix uchun 8 ta eng yaxshi taklif oldindan hisoblangan. Eng yomon holatda ham murakkablik — kiritma uzunligiga bog'liq. Bu juda kichik.

Ikkinchi qism (Tail): Qolgan hamma narsa SSD'da, xotira bilan bog'langan block index yordamida saqlanadi. Domenlar tartiblangan, delta-compressed, va qat'iy o'lchamdagi block'larga ajratilgan. Binary search uchun kichik xotiradagi directory bor. 240M domen taxminan 2.5GB joy oladi, va OS avtomatik ravishda tez-tez ishlatiladigan sahifalarni cache'da saqlaydi.

Ikkala struktura ham cheklangan kiritmalarga ega — domenlar soni va so'rov uzunligi cheksiz o'smaydi. Bu amalda murakkablikni deyarli O(1) qiladi va p99 kechikishni doimiy past tutadi.

Raqamlar Qanday?

Stress testlari qiziq natijani ko'rsatdi. API'ning o'zi ko'p so'rovlarni 2ms dan kam vaqtda javoblaydi. 1,600 so'rov/soniya yuk ostida ham Nginx va API p99 da 15ms javob beradi. Yaxshi ko'rsatkich.

Ammo bu yerda haqiqat kirib keladi: tarmoq. Amalda, oxirgi kechikish — bu brauzerdan Cloudflare orqali serveringizga va qaytib kelgunga qadar ketgan vaqt, plus 10ms qo'shimcha. Server bilan bir xil hududda bo'lgan foydalanuvchilar uchun byudjet ichida bo'lasiz. Qolganlari uchun? Bu yerda muammo boshlanadi.

Yulduzcha

p99 0ms* degani — 99% so'rovlar foydalanuvchi tugmani bosishini tugatgunga qadar javob oladi, agar u server yaqinida bo'lsa. 100-200ms transatlantik kechikish qo'shing — va byudjetdan oshdingiz.

Yechim — geo-taqsimlangan serverlar va load balancing. Ammo side project uchun bu juda ko'p infratuzilma. Ba'zan "yetarli" — bu haqiqatan ham yetarli. Ayniqsa, maqsadli foydalanuvchilar Yevropalik dasturchilar bo'lsa.

Bu Sizning Keyingi Loyihangiz Uchun Nimani Anglatadi

Bu yerda domen qidiruvdan tashqari ham qo'llaniladigan saboq bor: oldindan yuklashni (prefetch) aqlli qiling. Agar foydalanuvchilar keyin nima so'ramoqchi ekanini bilsangiz, ular so'ramasdan oldin yuklab oling. UI'ga aniq javob kelishini kutmasdan, tayyor bo'lgan narsaga react qiling.

Ikkinchi saboq — ma'lumot tuzilmasini tanlash haqida. Issiq ma'lumotlar uchun trie, hamma qolgan uchun yaxshi indekslangan tartiblangan struktura. 240 million elementni RAM'da saqlamasdan ham ishlamoqchi bo'lsangiz — qidiruv sxemangizni haqiqatan ham so'ralishi ehtimoli atrofida loyihalash kifoya.

Va nihoyat, o'zingizning haqiqiy byudjetingizni o'lchang. Bu holda — ikkita tugma bosish va oradagi tanaffus. Sizning analogiyangiz nima? Uni toping, unga qarab optimallashtiring, va undan tashqariga optimallashtirishni to'xtating.

Natija sehr kabi his qilinadi. Ammo barchasi aniq qancha vaqtingiz borligini tushunganingizdan boshlanadi.