Wawancara Koding: Bagaimana Cara Mendesain Resumable Batched Iterator?

Perintah dan konteks

Rancang sebuah iterator yang menelusuri API jarak jauh terpaginasi satu per satu item. Setiap halaman memiliki paling banyak 100 item dan menggunakan pageToken; permintaan mungkin gagal atau mengembalikan duplikat, dan pemanggil menyimpan kursor pada titik arbitrer untuk dilanjutkan nanti. Jelaskan antarmuka, invarian, buffering, deduplikasi, semantik pemulihan, kompleksitas, dan pengujian.

Desain iterator muncul dalam materi wawancara publik; Java API mendefinisikan hasNext() sebagai pemeriksaan elemen berikutnya dan next() untuk mengembalikannya atau melempar pengecualian jika tidak ada yang tersisa. Pertanyaan ini memperluas pola in-memory yang sudah dikenal menjadi iterator jarak jauh berbasis batch yang dapat dilanjutkan (resumable), serta berfokus pada batas-batas status (state boundaries).

Apa yang dinilai oleh pewawancara

Jawaban rata-rata hanya menulis satu indeks array. Jawaban yang kuat memisahkan token halaman, indeks di dalam halaman, item yang terkirim, dan checkpoint yang diakui oleh pemanggil, lalu menjelaskan mengapa percobaan ulang (retry) tidak boleh melewati atau menduplikasi data secara diam-diam. Pertanyaan lanjutan mencakup halaman duplikat, perubahan data selama paginasi, crash setelah hasNext(), dan panggilan konkuren.

Sinyal utamanya adalah penggunaan invarian untuk mengontrol efek samping eksternal alih-alih memperlakukan paginasi jarak jauh seperti array lokal.

Pertanyaan klarifikasi

• Apakah pengurutannya stabil? Asumsikan urutan (createdAt, id) yang tidak dapat diubah (immutable); tanpanya, pemulihan yang tepat tidak dapat dijanjikan.
• Apakah pemulihannya at-least-once atau exactly-once? Pilih pembacaan at-least-once dan biarkan pemanggil melakukan deduplikasi berdasarkan ID yang stabil; layanan jarak jauh tidak memiliki transaksi lintas permintaan.
• Bisakah baris disisipkan atau dihapus? Asumsikan snapshot atau token konsistensi menetapkan kumpulan hasil; jika tidak, janjikan penelusuran yang lemah saja.
• Apakah panggilan konkuren diizinkan? Standarnya adalah penggunaan single-threaded; panggilan konkuren memerlukan kunci (lock) atau kesalahan status eksplisit.
• Bisakah iterasi berlanjut setelah kegagalan? Coba lagi kesalahan jaringan sementara dalam batas tertentu; teruskan kesalahan autentikasi, parameter, dan snapshot kedaluwarsa secara langsung.

Jawaban 30 detik

“Saya membagi kursor menjadi versi snapshot, token halaman berikutnya, dan indeks di dalam halaman. Iterator meng-cache satu halaman; hasNext() tidak memajukan status pengiriman, sedangkan next() menggunakan satu item dan memajukan indeks. Kursor yang dipersistensikan mewakili item terkirim terakhir yang diakui oleh pemanggil, sehingga pemulihan dapat mengulangi batas dan bersifat at-least-once; kode hilir mendeduplikasi berdasarkan ID yang stabil. API memerlukan pengurutan yang stabil dan snapshot, jika tidak, saya menyatakan konsistensi yang lebih lemah. Kegagalan jaringan memiliki batas percobaan ulang dan kesalahan permanen diteruskan.”

Jawaban langkah demi langkah

Langkah 1: Tentukan status dan kontrak antarmuka

Antarmuka dapat mengekspos hasNext(), next(), checkpoint(), dan close(). hasNext() dapat memeriksa buffer atau melakukan prefetch satu halaman, tetapi tidak boleh menandai item sebagai telah terkirim. next() mengembalikan satu item dan memajukan index. checkpoint() membuat token yang dapat diserialisasi; pemanggil memutuskan kapan kemajuan tersebut diakui.

Langkah 2: Tetapkan invarian

0 <= index <= len(buffer)
next() returns buffer[index], then increments index
replace buffer and pageToken only after a whole page succeeds
the recovery token represents only the caller-acknowledged prefix
permanent errors are never swallowed by a retry loop

Jika permintaan halaman berikutnya gagal, pertahankan buffer lama dan posisi pengiriman. Jika halaman baru berhasil tetapi proses crash sebelum menyimpan checkpoint, pemulihan akan mengulangi akhiran (suffix), yang bersifat at-least-once. Menyimpan checkpoint sebelum pengiriman dapat menyebabkan item terlewat, jadi urutannya sangat penting.

Langkah 3: Terapkan pembacaan halaman dan percobaan ulang terbatas

class ResumableIterator:
    def __init__(self, client, checkpoint=None, page_size=100):
        self.client = client
        self.page_size = page_size
        self.snapshot = checkpoint.snapshot if checkpoint else None
        self.token = checkpoint.page_token if checkpoint else None
        self.index = checkpoint.index if checkpoint else 0
        self.buffer = []
        self.done = False

    def has_next(self):
        self._ensure_buffer()
        return self.index < len(self.buffer)

    def next(self):
        self._ensure_buffer()
        if self.index == len(self.buffer):
            raise StopIteration
        item = self.buffer[self.index]
        self.index += 1
        return item

    def checkpoint(self):
        return Checkpoint(self.snapshot, self.token, self.index)

_ensure_buffer() meminta halaman berikutnya ketika halaman saat ini habis, menggunakan exponential backoff dan jumlah percobaan maksimum. Batas waktu (timeout) mungkin terjadi setelah permintaan sisi server berhasil, jadi percobaan ulang harus menggunakan snapshot/token yang sama dan server harus mengembalikan halaman yang stabil atau batas duplikat yang dapat diamati.

Langkah 4: Tangani duplikat, penyisipan, dan penghapusan

Token halaman saja mungkin tidak mencegah data duplikat setelah percobaan ulang. Jika API mengembalikan id yang stabil, buang awalan pada batas pemulihan tempat id <= lastId; untuk pengurutan gabungan, bandingkan kursor (createdAt, id) lengkap. Jangan menumbuhkan kumpulan deduplikasi tanpa batas; snapshot server dan token batas menjaga deduplikasi tetap lokal pada jendela pemulihan.

Tanpa snapshot, baris baru dapat muncul sebelum halaman saat ini dan penghapusan dapat membuat halaman berikutnya melewati sebuah item. Janjikan hanya penelusuran best-effort dari hasil yang terlihat, bukan exactly-once atau konsistensi yang kuat. Dalam wawancara, turunkan garansinya secara eksplisit atau minta versi snapshot.

Langkah 5: Tentukan semantik checkpoint dan pemulihan

Checkpoint harus berisi versi, snapshot, token, indeks di dalam halaman, ID stabil terakhir, digest filter, dan waktu kedaluwarsa. Digest filter mencegah pemulihan kursor dari satu kueri ke kueri lainnya; kedaluwarsa mencegah pembacaan hasil yang berbeda secara diam-diam setelah server mereklamasi snapshot.

Bangun kembali iterator dari checkpoint. Jika pemanggil menyimpan segera setelah mengonsumsi item, pemulihan dapat mengulangi item tersebut, sehingga penulisan di tingkat hilir harus idempoten berdasarkan ID yang stabil. Jika bisnis tidak memperbolehkan duplikat, kemajuan dan hasil bisnis harus berbagi transaksi atau penyimpanan hilir harus menyediakan tabel deduplikasi; iterator tidak dapat menciptakan exactly-once dengan sendirinya.

Langkah 6: Kompleksitas, backpressure, dan penutupan

Ruang buffer adalah O(page_size) dan pemajuan lokal adalah O(1) per item. Pembacaan jarak jauh sekitar ceil(N / page_size), tidak termasuk percobaan ulang. hasNext() dapat mengeluarkan permintaan jaringan, sehingga pemanggil tidak boleh menganggapnya bebas biaya. Prefetch dapat menyembunyikan latensi tetapi harus membatasi dirinya pada satu halaman atau anggaran byte tertentu.

close() membatalkan pekerjaan yang tertunda dan melepaskan koneksi; snapshot server memerlukan TTL. Jika konsumen lebih lambat dari produsen, API harus menerapkan rate-limit atau mengembalikan kesalahan snapshot-kedaluwarsa daripada memperpanjang snapshot selamanya. Panggilan konkuren harus ditolak atau diserialisasi, jika tidak dua panggilan next() dapat mengamati indeks yang sama.

Contoh jawaban berkualitas tinggi

“Saya akan memodelkan iterator jarak jauh sebagai state machine kecil dengan snapshot, pageToken, buffer, index, dan lastId. hasNext() hanya memastikan bahwa item buffer ada; next() memajukan index; checkpoint() menyimpan awalan yang diakui pemanggil. Ganti buffer hanya setelah seluruh halaman berhasil, coba lagi batas waktu sementara dengan batasan tertentu, dan teruskan kesalahan permanen.

“Untuk pemulihan, saya memerlukan pengurutan yang stabil dan token snapshot. Checkpoint juga berisi digest kueri, indeks di dalam halaman, ID stabil terakhir, dan kedaluwarsa. Pemulihan dapat mengulangi batas, jadi saya menjanjikan at-least-once dan membuat penulisan hilir idempoten berdasarkan ID. Tanpa snapshot, penyisipan dan penghapusan melemahkan jaminan.

“Buffer berukuran O(pagesize), setiap next bernilai O(1), dan halaman jarak jauh sekitar ceil(N/pagesize). Pengujian mencakup halaman kosong, halaman duplikat, token kedaluwarsa, batas waktu setelah keberhasilan server, crash saat checkpoint, mutasi, pemulihan berulang, next konkuren, backpressure, dan penutupan. Exactly-once memerlukan transaksi bersama atau penyimpanan deduplikasi.”

Kesalahan umum

• Gejala → Memperlakukan API jarak jauh sebagai array dan memulihkan satu indeks bilangan bulat → Mengapa gagal → Batas halaman dan mutasi mengarahkan indeks tersebut ke item yang berbeda → Solusi → Persistensikan snapshot, token, indeks di dalam halaman, dan ID yang stabil.
• Gejala → Memajukan token di hasNext() → Mengapa gagal → Pemanggil dapat memeriksa tanpa mengonsumsi lalu mengalami crash, sehingga melewatkan data → Solusi → Majukan status pengiriman hanya setelah next() mengembalikan item.
• Gejala → Pindah ke halaman berikutnya setelah batas waktu habis → Mengapa gagal → Seluruh halaman mungkin hilang atau permintaan yang berhasil dapat diduplikasi → Solusi → Coba lagi token yang sama dan lakukan deduplikasi berdasarkan ID yang stabil.
• Gejala → Mengklaim exactly-once dari iterator → Mengapa gagal → Persistensi checkpoint dan efek samping bisnis bukan satu transaksi atomik → Solusi → Janjikan at-least-once dan buat sink menjadi idempoten atau transaksional.
• Gejala → Prefetch dan percobaan ulang tanpa batas → Mengapa gagal → Konsumen yang lambat menghabiskan memori dan pemadaman memblokir selamanya → Solusi → Batasi buffer, percobaan, batas waktu, dan TTL snapshot.

Pertanyaan lanjutan dan tanggapan

Bagaimana jika server hanya menyediakan nomor halaman, bukan token snapshot?

Wajibkan kursor kunci gabungan yang stabil atau nyatakan bahwa hanya penelusuran konsistensi lemah yang dimungkinkan. Nomor halaman bergeser setelah penyisipan dan penghapusan, sehingga tidak dapat menjamin tidak adanya item yang terlewat atau duplikat.

Bagaimana jika sink hanya menerima setiap item satu kali dan tidak dapat mendeduplikasi?

Iterator tidak dapat menjamin exactly-once sendirian. Tempatkan kemajuan, penulisan bisnis, dan checkpoint dalam satu transaksi, atau wajibkan sink yang idempoten; jika tidak, cantumkan kemungkinan duplikat ke dalam kontrak.

Bagaimana jika satu halaman terus-menerus mengalami timeout?

Pertahankan buffer lama dan jangan memajukan token. Setelah batas percobaan ulang tercapai, munculkan kesalahan terklasifikasi sehingga pemanggil dapat memilih untuk menjeda, melewati, atau memulai ulang. Tindakan melewati harus mencatat celah (gap) dan tidak dapat berpindah ke halaman berikutnya secara diam-diam.