Pendalaman dan Tradeoff

Desain tingkat tinggi menunda satu keputusan, yaitu bagaimana pencarian catatan dijalankan. Topik ini memperdalam komponen tersebut sampai ke mekanismenya, mode kegagalannya, dan tradeoff yang diakuinya, sehingga proyek ditutup dengan satu komponen yang dipahami sampai ke ujungnya, bukan sekali digambar lalu dilewati. Komponen yang dipilih adalah pencarian, dan alasan pemilihannya dibahas lebih dahulu.

Mengapa pencarian yang diperdalam#

Pencarian dipilih karena tiga alasan. Pertama, ia menyentuh hampir semua komponen pada diagram desain, yaitu basis data sebagai tempat indeksnya, queue sebagai pembawa tugasnya, worker sebagai pelaksananya, dan cache sebagai penyimpan hasil kueri yang berulang. Kedua, perilakunya tidak ketat, artinya hasil boleh sedikit terlambat tanpa merusak produk, sehingga ruang tradeoff-nya nyata dan dapat dinyatakan secara terbuka. Ketiga, pendalaman ini menindaklanjuti keputusan yang ditunda pada desain, yaitu mesin pencarian terpisah yang belum dimasukkan.

Keputusan yang diperdalam adalah membangun indeks di dalam basis data. Konsep indeks terbalik (inverted index) beserta posting list-nya sudah dibahas pada topik Pencarian, sehingga di sini hanya tempat penyimpanannya yang berbeda, yaitu dua tabel relasional alih-alih mesin pencarian terpisah. Alasannya mengikuti angka estimasi, yaitu sekitar 18 juta catatan pada tahun pertama masih dalam jangkauan indeks berbasis basis data, dan mengoperasikan satu sistem lebih sederhana daripada dua sistem yang harus disinkronkan. Angka itu juga menetapkan bentuk indeksnya, karena indeks di basis data dapat dibangun ulang dari catatan kapan pun keputusannya berubah.

Mekanisme indeks dan alur tugasnya#

Struktur indeksnya terdiri atas dua tabel. Tabel kata menyimpan setiap kata unik, sedangkan tabel kecocokan menyimpan pasangan kata dan catatan beserta jumlah kemunculannya, dan pasangan itulah posting list versi relasional. Tokenisasinya dibuat sederhana, yaitu huruf dikecilkan, pemisahan pada spasi dan tanda baca, tanpa stemming, dan pilihan ini dinyatakan kembali sebagai tradeoff pada bagian akhir topik.

Alur kerjanya asinkron. Respons tulis selesai begitu basis data menyimpan catatan, kemudian tugas indeks masuk ke queue tugas latar, lalu worker pengindeks menarik tugasnya, memecah teks menjadi token, dan memperbarui tabel kecocokan. Kueri pencarian tidak menyentuh jalur tulis, melainkan membaca tabel kecocokan langsung. Diagram berikut memisahkan kedua jalur tersebut.

Kebenaran tulis tidak bergantung pada indeks. Catatan tetap tersimpan dan dapat dibuka berdasarkan pengenalnya walaupun tugas indeksnya belum dikerjakan, dan bila tabel indeks rusak, seluruhnya dapat dibangun ulang dari catatan yang tersimpan. Pemisahan peran inilah yang membuat jeda indeks dapat diterima, karena yang terlambat hanya keterlihatan pada pencarian, bukan keutuhan data.

Mengukur jeda indeks dengan simulasi#

Jeda antara penulisan catatan dan keterlihatannya pada pencarian dapat diestimasi dengan simulasi sederhana. Jadwal kedatangan tugas ditetapkan secara tetap agar hasilnya dapat diperiksa ulang, yaitu satu tugas per detik pada kondisi normal, lima tugas per detik selama sepuluh detik puncak, lalu satu tugas per detik selama empat puluh detik berikutnya. Satu worker menyelesaikan satu tugas per detik, dan simulasi mengukur antrean maksimum, jeda maksimum tugas yang selesai, serta sisa tugas di akhir.

# Simulasi jeda indeks pencarian aplikasi catatan.
# Satu tick mewakili satu detik. Jadwal kedatangan tugas ditetapkan agar
# hasilnya dapat diperiksa ulang, yaitu 20 detik normal, 10 detik puncak,
# lalu 40 detik normal.

KEDATANGAN = [1] * 20 + [5] * 10 + [1] * 40


def simulasi(jumlah_worker):
    usia = []            # usia tiap tugas yang menunggu, tugas tertua di depan
    antrian_maks = 0
    lag_maks = 0
    for datang in KEDATANGAN:
        usia = [u + 1 for u in usia]
        usia += [0] * datang
        selesai = usia[:jumlah_worker]
        usia = usia[jumlah_worker:]
        antrian_maks = max(antrian_maks, len(usia))
        if selesai:
            lag_maks = max(lag_maks, max(selesai))
    return antrian_maks, lag_maks, len(usia)


print(f"Total tugas indeks : {sum(KEDATANGAN)}")
for jumlah_worker in (1, 2):
    antrian_maks, lag_maks, sisa = simulasi(jumlah_worker)
    print(f"Worker {jumlah_worker}: antrian maksimum {antrian_maks}, "
          f"lag maksimum {lag_maks} detik, tersisa {sisa} tugas")

Total tugas indeks : 110
Worker 1: antrian maksimum 40, lag maksimum 40 detik, tersisa 40 tugas
Worker 2: antrian maksimum 30, lag maksimum 15 detik, tersisa 0 tugas

Dengan satu worker, antrean mencapai 40 tugas dan masih menyisakan 40 tugas di akhir simulasi, artinya laju pengerjaannya tidak pernah mengejar laju kedatangan dan jeda indeksnya bertumbuh tanpa batas. Dengan dua worker, antrean maksimumnya 30 tugas, tugas yang paling lama menunggu 15 detik, dan antrean habis sekitar 30 detik setelah puncak berakhir. Kesimpulannya, jumlah worker ditentukan dari laju tulis puncak, bukan dari rata-ratanya, dan pada desain ini satu worker sudah terbukti tidak mencukupi bahkan sebelum puncak datang. Angka jeda maksimum dari konfigurasi yang layak inilah yang dinyatakan sebagai batas keterlihatan pencarian pada desain.

Mode kegagalan dan penanggulangannya#

Pendalaman sebuah komponen belum lengkap tanpa memikirkan kegagalannya. Empat mode kegagalan berikut diturunkan dari sifat queue yang dijamin at-least-once, yaitu tugas dijamin sampai di worker, tetapi boleh sampai lebih dari sekali.

Baris kedua pada tabel inilah yang paling mudah terlewat saat desain disusun, karena kejadiannya tidak tampak pada kasus normal. Tugas yang sama dapat tiba dua kali di worker ketika worker mati setelah memperbarui indeks tetapi sebelum mengakui tugasnya, dan duplikasi barulah muncul pada keadaan seperti ini.

Tradeoff yang diakui terbuka#

Pendalaman ditutup dengan menyatakan empat tradeoff yang diterima beserta alasannya, supaya keputusan ini dapat dinilai ulang dengan dasar yang sama oleh siapa pun.

1. Jeda indeks diterima alih-alih pembaruan indeks sinkron. Respons tulis tidak boleh gagal karena indeks, dan keterlihatan pencarian yang terlambat beberapa puluh detik tidak merusak produk catatan pribadi. Batasnya yang dinyatakan, bukan dihilangkan.
2. Stemming tidak digunakan, sehingga pencarian kata tidak menemukan catatan yang hanya memuat kata membuat. Pilihan ini diterima karena tokenisasinya sederhana dan kebutuhannya masih terlayani, sedangkan perbaikannya, yaitu normalisasi kata dasar, dicatat sebagai revisi berikutnya.
3. Relevansi hasil hanya dari jumlah kemunculan dan kebaruan, bukan dari peringkat penuh. Untuk catatan pribadi dengan satu pemilik, urutan sederhana sudah cukup, sedangkan sasaran relevansi lintas pengguna memang berada di luar lingkup.
4. Indeks tetap di basis data alih-alih pada mesin pencarian terpisah. Pemicu penggantiannya sudah dinyatakan pada desain, yaitu kueri yang melambat atau kebutuhan relevansi yang naik, dan bila saat itu tiba, basis data tetap menjadi sumber kebenaran sehingga perpindahan tidak memindahkan data utama.

Empat butir ini dituliskan secara terbuka karena tradeoff yang diterima diam-diam akan berubah menjadi kejutan pada saat produksi, sedangkan yang disertai alasan dan pemicu menjadi keputusan yang terjadwal.

Ringkasan#

• Pencarian diperdalam karena menyentuh hampir semua komponen desain dan tradeoff-nya nyata, yaitu keterlambatan yang dapat diterima dengan batas yang dinyatakan.
• Indeks terbalik disimpan sebagai dua tabel di basis data, diisi worker melalui queue tugas latar, dan seluruhnya dapat dibangun ulang dari catatan yang tersimpan.
• Simulasi menunjukkan satu worker tidak pernah mengejar laju tulis, sedangkan dua worker menghabiskan antrean sekitar 30 detik setelah puncak dengan jeda maksimum 15 detik.
• Mode kegagalan utamanya diturunkan dari jaminan at-least-once, dan penanggulangannya adalah idempotensi worker beserta batas jeda yang terukur.

Referensi#

• Elastic fundamentals — Elastic — Pengenalan resmi konsep inti Elasticsearch, termasuk indeks dan shard, yang menjadi pembanding keputusan indeks di basis data.
• Text Search — PostgreSQL Documentation — Kemampuan pencarian teks di dalam basis data yang menopang keputusan indeks pada topik ini.
• Amazon SQS standard queues — AWS Documentation — Jaminan pengiriman at-least-once yang menjadi dasar analisis mode kegagalan.