Jawaban singkat untuk pertanyaan yang paling sering diajukan pembaca tentang topik ini.
Cara mendesain search autocomplete skala besar: hitungan kapasitas, latency budget 100 ms, trie vs Postgres dan Redis, ranking dengan decay, agregasi log offline, caching top-K, dan client dengan debounce.
Matthews Wong
Software Engineer
Ringkasan Utama
Desain search autocomplete dengan menghitung di muka sepuluh suggestion teratas untuk setiap prefix query secara offline dari log query yang diagregasi, diurutkan berdasarkan frekuensi dengan time decay, lalu disajikan dari Redis atau CDN memakai key prefix yang persis. Client melakukan debounce dan membatalkan request usang, dengan target round trip sekitar 100 milidetik.
Product picker di layar point-of-sale adalah autocomplete terkecil yang dibuat kebanyakan developer: ketik tiga huruf, muncul item yang cocok. Ini jalan dengan query LIKE pada beberapa ribu baris, dan terus jalan sampai daftar, traffic, atau kecepatan mengetik tumbuh sehingga setiap keystroke menjadi query ke database.
Tulisan ini adalah latihan desain, bukan case study. Setiap angka berasal dari asumsi yang disebutkan dengan hitungan yang ditunjukkan, atau dari sumber yang dikutip, dan tidak ada yang berupa benchmark. Cakupannya: kapasitas, latency, struktur data, ranking, agregasi offline, caching, dan client, ditutup dengan decision checklist. Full-text search biasa dibahas di post PostgreSQL full-text search, dan dasar hook debounce di panduan debouncing React, jadi keduanya hanya singkat di sini.
Jauh lebih banyak daripada search yang dilayaninya. Search adalah satu request per query yang disubmit, sedangkan typeahead bisa mengirim satu per keystroke. Mulai dari asumsi yang bisa dipertanggungjawabkan, lalu turunkan sisanya. Blok di bawah mengasumsikan 5 juta daily active users dan menunjukkan bahwa debounce saja memangkas volume request 4,75 kali.
Assumed inputs (a design exercise, not a measurement):
daily active users = 5,000,000
submitted searches per user = 10 per day
average query length = 20 characters, suggestions start at 2
debounced requests / search = 4 (assumed)
peak vs average = 3x
suggestion response = 10 items x 25 B + 300 B headers = 550 B
Searches and requests
searches per day = 5,000,000 x 10 = 50,000,000
requests per day, debounced = 50,000,000 x 4 = 200,000,000
average requests / s = 200,000,000 / 86,400 = 2,315
peak requests / s = 2,315 x 3 = 6,944
The same traffic with no debounce (one request per keystroke from char 2)
requests per search = 20 - 1 = 19
requests per day = 50,000,000 x 19 = 950,000,000
average requests / s = 950,000,000 / 86,400 = 10,995
reduction from debouncing = 950 / 200 = 4.75x fewer requests
Logging and bandwidth
search log writes / s = 50,000,000 / 86,400 = 579 (submitted searches only)
peak response bandwidth = 6,944 x 550 B = 3.8 MB/s
Cache effect (assumed 80% of requests answered by browser or CDN cache)
requests reaching the app = 6,944 x 0.20 = 1,389 / s at peakDua kesimpulan muncul. Jalur baca harus berupa key lookup yang murah, karena pekerjaan ranking pada 6.944 request per detik di puncak itu tidak masuk akal, sedangkan log search hanya 579 write per detik yang mudah diserap batch insert. Angka cache hit 80 persen adalah asumsi, tetapi hanya masuk akal karena URL tidak membawa apa pun yang spesifik per user, sifat yang dijaga di bagian caching.
Suggestion yang tiba setelah user selesai mengetik hanyalah noise, jadi budget-nya ketat. Nielsen Norman Group menyebut 0,1 detik sebagai batas respons yang terasa instan, sehingga 100 ms adalah target yang wajar. Bagi budget itu ke tahap yang bisa Anda kontrol dan lihat sisanya.
Target: about 100 ms, the figure Nielsen Norman Group cites for "feels instant".
Budget per request (network and server numbers are assumptions, measure your own)
network round trip, warm connection = 40 ms
app + one Redis read = 5 ms
render one frame at 60 Hz = 1000 / 60 = 16.7 ms
total = 61.7 ms
slack = 100 - 61.7 = 38.3 ms
What the user feels is measured from the LAST keystroke:
debounce 100 ms + 61.7 ms = 161.7 ms
debounce 50 ms + 61.7 ms = 111.7 ms
A shorter debounce feels faster but sends more requests. It is a dial, not a constant.Slack-nya kecil, dan delay debounce tidak termasuk di dalamnya karena berlalu sebelum request keluar dari browser. Itulah ketegangan desain yang sebenarnya: setiap milidetik kerja server bersaing dengan debounce yang ingin Anda pakai untuk menghemat request. Ini juga alasan untuk precomputation, karena satu key lookup menyisakan ruang untuk keduanya.
Trie menyimpan string berdasarkan prefix yang sama, jadi mencari node untuk sebuah prefix membutuhkan waktu sebanding panjang prefix, bukan jumlah string. Simpan sepuluh suggestion teratas di setiap node dan lookup hanya berupa penelusuran plus salinan. Kekurangannya, ia hidup di satu proses, jadi setiap instance butuh build yang sama dan cara menggantinya. Bandingkan dengan opsi berbasis database.
| Pendekatan | Yang dicocokkan | Ranking | Kelemahan utama |
|---|---|---|---|
| Trie in-memory dengan top-K di setiap node | Prefix persis, biaya naik sesuai panjang prefix | Dihitung di muka per node | Memori per proses; setiap instance butuh build yang sama |
| B-tree Postgres dengan text_pattern_ops | LIKE berjangkar kiri seperti ca% | ORDER BY score atas semua yang cocok | Prefix pendek cocok dengan banyak baris yang harus diurutkan |
| Postgres pg_trgm dengan index GIN | Di mana saja dalam string, plus typo lewat similarity | ORDER BY similarity, lalu score | Index lebih besar; pola tanpa trigram yang bisa diekstrak memindai seluruh index |
| Sorted set Redis per prefix | Lookup key prefix yang persis | Score adalah rank-nya | Job offline harus mengisinya; memori tumbuh sesuai jumlah prefix |
| Redis ZRANGE BYLEX pada satu set | Rentang leksikografis berjangkar kiri | Hanya alfabetis, bukan berdasarkan popularitas | Tidak bisa melakukan ranking, dan semua score harus sama |
Di satu VPS saya akan mulai dari Postgres, karena sudah berjalan dan beberapa ratus ribu query muat dengan nyaman. Dokumentasi PostgreSQL menyatakan index text_pattern_ops mendukung LIKE ketika database tidak memakai locale C, dan index pg_trgm mendukung pencarian LIKE, ILIKE, dan similarity yang tidak harus berjangkar kiri. Pakai B-tree untuk prefix biasa dan pg_trgm bila ingin toleransi typo.
-- Left-anchored prefix match on a B-tree. In a non-C locale the default operator
-- class cannot serve LIKE 'ca%', which is why text_pattern_ops exists.
CREATE INDEX popular_queries_prefix_idx ON popular_queries (q text_pattern_ops);
-- Works, but 'c%' matches a large share of the table, and ORDER BY score then
-- has to sort every match. This is why the production shape is precomputed.
SELECT q FROM popular_queries WHERE q LIKE 'ca%' ORDER BY score DESC LIMIT 10;
-- pg_trgm: typo tolerance and match-anywhere, at the price of a bigger index.
CREATE EXTENSION IF NOT EXISTS pg_trgm;
CREATE INDEX popular_queries_trgm_idx ON popular_queries USING gin (q gin_trgm_ops);
SELECT q
FROM popular_queries
WHERE q % 'cofee' -- similarity operator, uses the GIN index
ORDER BY similarity(q, 'cofee') DESC, score DESC
LIMIT 10;Langkah untuk skala adalah berhenti melakukan query dan mulai melakukan lookup. Redis mendokumentasikan ZRANGE dengan BYLEX untuk rentang leksikografis, tetapi hanya untuk member dengan score yang sama, yang menghasilkan urutan alfabetis. Ranking popularitas butuh bentuk lain: satu sorted set per prefix dengan score sebagai rank, ditulis oleh job offline dan dibaca dengan satu ZREVRANGE.
# Precomputed top-K per prefix: a sorted set whose score IS the rank.
ZADD sg:v43:ca 362.3 "cat food" 300 "car insurance" 250 "calendar app"
ZREVRANGE sg:v43:ca 0 9 # top 10, highest score first
ZREVRANGE sg:v43:ca 0 9 WITHSCORES # same, with the scores
# Lexicographic range works only when every member has the SAME score (use 0).
# It gives alphabetical order, not popularity, so it filters but cannot rank.
ZADD sg:lex 0 "cat food" 0 "car insurance" 0 "calendar app"
ZRANGE sg:lex "[ca" "[ca\xff" BYLEX LIMIT 0 10
# Publish a new build atomically: write sg:v44:* in the background, then flip.
SET sg:version 44Batasi panjang prefix, misalnya 8 karakter. Setelah itu user hanya mempersempit daftar yang sudah terlihat, jadi pakai ulang daftar 8 karakter dan filter di aplikasi. Ruang key tetap terbatas sepanjang apa pun query yang diketik.
Hitungan mentah menguntungkan raksasa lama: query yang dicari 1.000 kali bulan lalu mengalahkan yang sedang melonjak hari ini. Bobotkan hitungan tiap hari dengan exponential decay dengan half-life pilihan Anda, lalu jumlahkan. Contoh di bawah memakai half-life 7 hari dan menunjukkan urutan berbalik.
score = sum over days of count(day) x 0.5 ^ (age_in_days / half_life)
half_life = 7 days (a choice: shorter reacts to trends faster, longer is steadier)
query A: 1,000 searches, all 14 days ago 1,000 x 0.5 ^ (14 / 7) = 1,000 x 0.25 = 250.0
query B: 400 searches, all 1 day ago 400 x 0.5 ^ (1 / 7) = 400 x 0.906 = 362.3
query C: 300 searches, all today 300 x 0.5 ^ 0 = 300.0
Raw count order: A (1,000), B (400), C (300)
Decayed order: B (362.3), C (300), A (250)Half-life adalah keputusan produk, bukan konstanta. Yang pendek membuat topik tren cepat muncul tetapi juga membiarkan lonjakan satu hari menggeser favorit yang stabil, sedangkan yang panjang stabil tetapi lambat. Tambahkan jumlah minimum sebelum sebuah query layak masuk, yang sekaligus menyingkirkan typo sekali pakai dan query pribadi yang langka.
Jangan pernah melakukan ranking di jalur request. Catat search yang disubmit, agregasi menjadi hitungan harian per query yang dinormalisasi, lalu jalankan job malam yang memberi skor tiap query, memecahnya menjadi prefix, dan menyimpan sepuluh teratas per prefix. Di Postgres seluruh job-nya satu statement dengan generate_series dan row_number.
-- Nightly job. Input: daily_query_counts(day date, q text, cnt bigint),
-- itself an aggregate of the raw search log. Output: top 10 per prefix.
WITH scored AS (
SELECT lower(trim(q)) AS q,
sum(cnt * power(0.5, (current_date - day) / 7.0)) AS score
FROM daily_query_counts
WHERE day >= current_date - 28
GROUP BY 1
HAVING sum(cnt) >= 5 -- privacy and noise floor
),
prefixes AS (
SELECT left(s.q, n) AS prefix, s.q, s.score
FROM scored s, generate_series(1, 8) AS n
WHERE length(s.q) >= n -- prefixes capped at 8 characters
),
ranked AS (
SELECT prefix, q, score,
row_number() OVER (PARTITION BY prefix ORDER BY score DESC, q) AS rn
FROM prefixes
)
SELECT prefix, q, score FROM ranked WHERE rn <= 10;Hasilnya mengisi set Redis di bawah nomor versi baru, dan satu SET membalik pointer versi setelah build selesai, sehingga pembaca tidak pernah melihat index yang setengah jadi. Siklus malam berarti suggestion tertinggal hingga sehari, yang dapat diterima untuk kebanyakan produk. Bila tidak, tambahkan lapisan online kecil yang menaikkan score query baru dan gabungkan nanti.
Log query berisi apa yang diketik orang, termasuk nama, nomor telepon, dan hal yang tidak ingin mereka lihat disarankan ke orang asing. Normalisasi, terapkan jumlah minimum di atas, saring dengan blocklist sebelum dipublikasikan, dan tetapkan masa retensi untuk log mentah. Suggestion yang tampil ke semua orang adalah publikasi, bukan metrik internal.
Jadikan endpoint fungsi murni dari prefix, sehingga jawabannya identik untuk setiap user. Maka URL itu sendiri menjadi cache key, dan browser, CDN, serta Redis semuanya bisa menyimpannya. Handler di bawah melakukan satu pembacaan Redis, membatasi input, dan mengatur header Cache-Control publik.
@Get("suggest")
async suggest(
@Query("q") raw: string,
@Res({ passthrough: true }) res: Response,
): Promise<string[]> {
const q = (raw ?? "").trim().toLowerCase();
if (q.length < 2 || q.length > 64) return []; // reject junk before any I/O
const version = (await this.redis.get("sg:version")) ?? "1";
const key = "sg:v" + version + ":" + q.slice(0, 8); // keys stop at 8 characters
const top = await this.redis.zrevrange(key, 0, 9);
// Past 8 characters we reuse the 8-character list and filter it. This can
// return fewer than 10 items; that is the price of a bounded key space.
const out = q.length > 8 ? top.filter((s) => s.startsWith(q)) : top;
// The URL is the cache key: /suggest?q=ca is identical for every user.
res.setHeader("Cache-Control", "public, max-age=300");
return out;
}Periksa memori yang akan Anda tanggung sebelum membangunnya. Hitungannya memberi batas atas, karena prefix nyata saling tumpang tindih, dan batas itu muat di instance Redis kecil. Ukur satu sample key daripada memercayai estimasi per entry.
Assumed: 2,000,000 retained queries, prefixes capped at 8 characters.
Upper bound on prefix keys = 2,000,000 x 8 = 16,000,000
(real count is lower: queries share prefixes, e.g. every "cat food" shares "c", "ca", "cat")
Value size = 10 suggestions x 25 B = 250 B, plus about 50 B overhead = 300 B
Upper bound = 16,000,000 x 300 B = 4.8 GB
Smaller option: only materialise prefixes that at least 2 retained queries share
beyond length 3, and serve the rest from the filtered 8-character list.
Check the real footprint with MEMORY USAGE on a sample key, then extrapolate.Anggap max-age lima menit sebagai keputusan freshness. Karena job malam sudah membuat data berusia hingga sehari, lima menit staleness tambahan tidak merugikan apa pun yang terlihat user, dan itulah yang membuat asumsi hit 80 persen masuk akal.
Lakukan debounce agar rentetan keystroke mengirim satu request, dan batalkan agar respons lambat tidak pernah menimpa yang lebih baru. AbortController adalah cara standar membatalkan fetch, dan cleanup effect adalah tempat yang wajar untuk memanggilnya. Hook di bawah juga menyimpan map di memori, jadi menghapus karakter lalu mengetiknya lagi tidak butuh request.
import { useEffect, useRef, useState } from "react";
const DEBOUNCE_MS = 100;
const MIN_CHARS = 2;
export function useSuggestions(input: string): string[] {
const [items, setItems] = useState<string[]>([]);
const memo = useRef(new Map<string, string[]>()); // same prefix twice = zero requests
useEffect(() => {
const q = input.trim().toLowerCase();
if (q.length < MIN_CHARS) {
setItems([]);
return;
}
const hit = memo.current.get(q);
if (hit) {
setItems(hit);
return;
}
const controller = new AbortController();
const timer = setTimeout(async () => {
try {
const res = await fetch("/api/suggest?q=" + encodeURIComponent(q), {
signal: controller.signal,
});
if (!res.ok) return;
const data: string[] = await res.json();
memo.current.set(q, data);
setItems(data);
} catch (err) {
if ((err as Error).name !== "AbortError") setItems([]);
}
}, DEBOUNCE_MS);
// Runs on the next keystroke: drop the pending timer AND cancel the
// in-flight request, so a slow answer for "ca" can never overwrite "cat".
return () => {
clearTimeout(timer);
controller.abort();
};
}, [input]);
return items;
}Pembatalan hanya membuat browser berhenti menunggu; server mungkin tetap menyelesaikan pekerjaan, yang murah di sini karena jawabannya satu lookup yang di-cache. Delay 100 ms adalah nilai yang bisa disetel dari latency budget, bukan aturan, jadi pilih sesuai kecepatan mengetik user Anda yang sebenarnya.
Pilih desain paling ringan yang bertahan terhadap angka Anda, dan naik hanya ketika pengukuran memaksa. Jawab berurutan.
Apa pun pilihan Anda, tuliskan asumsi di balik blok kapasitas dan tinjau ulang ketika traffic nyata tiba. Hitungannya adalah bagian yang bisa diperiksa, dan asumsi yang salah murah dikoreksi selama masih di atas kertas.
Autocomplete adalah lookup read-heavy yang menyamar sebagai masalah search. Lakukan ranking yang mahal secara offline, kunci hasilnya per prefix, cache secara publik, dan buat client mengirim request sesedikit mungkin. Mulai dari database yang sudah Anda jalankan, dan biarkan beban terukur, bukan tren, yang memindahkan Anda ke trie atau Redis.
Sumber dan bacaan lanjutan