Temu Duga Pengekodan: Bagaimanakah Anda Mereka Bentuk Resumable Batched Iterator?

Gesaan dan konteks

Reka bentuk iterator yang menyusuri API jauh berhalaman satu item pada satu masa. Setiap halaman mempunyai paling banyak 100 item dan menggunakan pageToken; permintaan mungkin gagal atau mengembalikan duplikasi, dan pemanggil menyimpan kursor pada titik arbitrari untuk disambung semula kemudian. Terangkan antara muka, invarian, penimbalan, penyahduplikasian, semantik pemulihan, kerumitan, dan ujian.

Reka bentuk iterator sering muncul dalam bahan temu duga awam; Java API mentakrifkan hasNext() sebagai menyemak kewujudan elemen lain dan next() sebagai mengembalikannya atau melempar ralat apabila tiada lagi yang tinggal. Soalan ini memperluaskan corak dalam memori yang lazim kepada iterator jauh berkelompok yang boleh disambung semula (resumable) dan memberi tumpuan kepada sempadan keadaan.

Perkara yang dinilai oleh penemu duga

Jawapan purata hanya menulis satu indeks tatasusunan. Jawapan yang mantap memisahkan token halaman, indeks dalam halaman, item yang dihantar, dan titik semak yang diperakui oleh pemanggil, kemudian menjelaskan sebab percubaan semula tidak boleh melangkau atau menduplikasi data secara senyap. Soalan susulan meliputi halaman pendua, data yang berubah semasa penomboran halaman, kerosakan (crash) selepas hasNext(), dan panggilan serentak.

Isyarat teras adalah menggunakan invarian untuk mengawal kesan sampingan luaran dan bukannya menganggap penomboran halaman jauh seperti tatasusunan tempatan.

Soalan penjelasan

• Adakah susunan stabil? Andaikan susunan (createdAt, id) yang tidak berubah; tanpanya, pemulihan yang tepat tidak dapat dijanjikan.
• Adakah pemulihan sekurang-kurangnya sekali (at-least-once) atau tepat sekali (exactly-once)? Pilih bacaan sekurang-kurangnya sekali dan biarkan pemanggil menyahduplikasi mengikut ID yang stabil; perkhidmatan jauh tidak mempunyai transaksi rentas permintaan.
• Bolehkah baris disisipkan atau dipadamkan? Andaikan snapshot atau token konsistensi menetapkan set hasil; jika tidak, janjikan hanya traversal yang lemah.
• Adakah panggilan serentak dibenarkan? Tetapkan lalai kepada penggunaan benang tunggal; panggilan serentak memerlukan kunci atau ralat keadaan yang jelas.
• Bolehkah lelaran diteruskan selepas kegagalan? Cuba semula ralat rangkaian sementara dalam had tertentu; sebarkan ralat pengesahan, parameter dan snapshot tamat tempoh serta-merta.

Jawapan 30 saat

“Saya membahagikan kursor kepada versi snapshot, token halaman seterusnya, dan indeks dalam halaman. Iterator menyimpan cache satu halaman; hasNext() tidak memajukan keadaan penghantaran, manakala next() menggunakan satu item dan memajukan indeks. Kursor yang dikekalkan mewakili item terakhir dihantar yang diperakui oleh pemanggil, jadi pemulihan mungkin mengulangi sempadan dan bersifat at-least-once; kod hiliran menyahduplikasi mengikut ID stabil. API memerlukan susunan yang stabil dan snapshot, jika tidak saya menyatakan konsistensi yang lebih lemah. Kegagalan rangkaian mempunyai had percubaan semula dan ralat kekal disebarkan.”

Jawapan langkah demi langkah

Langkah 1: Tentukan keadaan dan kontrak antara muka

Antara muka boleh mendedahkan hasNext(), next(), checkpoint(), dan close(). hasNext() boleh memeriksa penimbal atau membuat pratarik (prefetch) satu halaman, tetapi ia tidak boleh menandakan item sebagai dihantar. next() mengembalikan satu item dan memajukan index. checkpoint() mencipta token yang boleh disiri; pemanggil memutuskan bila kemajuan itu diperakui.

Langkah 2: Wujudkan 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 seterusnya gagal, simpan penimbal lama dan kedudukan penghantaran. Jika halaman baharu berjaya tetapi proses terhenti sebelum menyimpan titik semak, pemulihan mengulangi akhiran, iaitu bersifat at-least-once. Menyimpan titik semak sebelum penghantaran boleh melangkau item, jadi susunan adalah penting.

Langkah 3: Laksanakan bacaan halaman dan percubaan semula terhad

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 seterusnya apabila halaman semasa telah habis digunakan, menggunakan pengunduran eksponen (exponential backoff) dan kiraan percubaan maksimum. Had masa tamat (timeout) mungkin berlaku selepas permintaan pihak pelayan yang berjaya, jadi percubaan semula mesti menggunakan snapshot/token yang sama dan pelayan mesti mengembalikan halaman yang stabil atau sempadan pendua yang boleh diperhatikan.

Langkah 4: Kendalikan pendua, sisipan, dan pemadaman

Token halaman sahaja mungkin tidak menghalang data pendua selepas percubaan semula. Jika API mengembalikan id yang stabil, buang awalan pada sempadan pemulihan di mana id <= lastId; untuk isihan majmuk, bandingkan kursor (createdAt, id) yang lengkap. Jangan kembangkan set penyahduplikasian tanpa had; snapshot pelayan dan token sempadan memastikan penyahduplikasian kekal setempat pada tetingkap pemulihan.

Tanpa snapshot, baris baharu boleh muncul sebelum halaman semasa dan pemadaman boleh menyebabkan halaman seterusnya melangkau item. Janjikan hanya traversal usaha terbaik (best-effort) bagi hasil yang kelihatan, bukan exactly-once atau konsistensi yang kukuh. Dalam temu duga, turunkan jaminan secara eksplisit atau perlukan versi snapshot.

Langkah 5: Tentukan semantik titik semak dan pemulihan

Titik semak harus mengandungi versi, snapshot, token, indeks dalam halaman, ID stabil terakhir, ringkasan penapis (filter digest), dan masa tamat tempoh. Ringkasan penapis menghalang pemulihan kursor untuk satu pertanyaan ke dalam pertanyaan yang lain; tamat tempoh menghalang pembacaan hasil yang berbeza secara senyap selepas pelayan menuntut semula snapshot.

Bina semula iterator daripada titik semak. Jika pemanggil menyimpan serta-merta selepas menggunakan item, pemulihan mungkin mengulangi item tersebut, jadi penulisan hiliran mestilah idempoten mengikut ID stabil. Jika perniagaan memerlukan tiada pendua langsung, kemajuan dan hasil perniagaan mesti berkongsi transaksi atau storan hiliran mesti menyediakan jadual penyahduplikasian; iterator tidak boleh mencipta exactly-once dengan sendirinya.

Langkah 6: Kerumitan, tekanan belakang (backpressure), dan penutupan

Ruang penimbal ialah O(page_size) dan kemajuan tempatan ialah O(1) setiap item. Bacaan jauh adalah sekitar ceil(N / page_size), tidak termasuk percubaan semula. hasNext() mungkin mengeluarkan permintaan rangkaian, jadi pemanggil tidak seharusnya menganggapnya percuma. Pratarik boleh menyembunyikan kependaman tetapi mesti mengehadkan dirinya kepada satu halaman atau bajet bait.

close() membatalkan kerja yang belum selesai dan melepaskan sambungan; snapshot pelayan memerlukan TTL. Jika pengguna lebih perlahan daripada pengeluar, API harus mengehadkan kadar atau mengembalikan ralat snapshot tamat tempoh daripada melanjutkan snapshot selama-lamanya. Panggilan serentak mesti ditolak atau disirikan, jika tidak dua panggilan next() boleh memerhatikan indeks yang sama.

Contoh jawapan berkualiti tinggi

“Saya akan memodelkan iterator jauh sebagai mesin keadaan kecil dengan snapshot, pageToken, buffer, index, dan lastId. hasNext() hanya memastikan bahawa item penimbal wujud; next() memajukan index; checkpoint() menyimpan awalan yang diperakui pemanggil. Gantikan penimbal hanya selepas keseluruhan halaman berjaya, cuba semula had masa tamat sementara dengan had tertentu, dan sebarkan ralat kekal.

“Untuk pemulihan, saya memerlukan susunan yang stabil dan token snapshot. Titik semak juga mengandungi ringkasan pertanyaan, indeks dalam halaman, ID stabil terakhir, dan tamat tempoh. Pemulihan mungkin mengulangi sempadan, jadi saya menjanjikan at-least-once dan menjadikan penulisan hiliran idempoten mengikut ID. Tanpa snapshot, sisipan dan pemadaman melemahkan jaminan.

“Penimbal adalah O(pagesize), setiap next adalah O(1), dan halaman jauh adalah sekitar ceil(N/pagesize). Ujian meliputi halaman kosong, halaman pendua, token tamat tempoh, had masa tamat selepas kejayaan pelayan, kerosakan titik semak, mutasi, pemulihan berulang, next serentak, tekanan belakang, dan penutupan. Exactly-once memerlukan transaksi dikongsi atau storan penyahduplikasian.”

Kesilapan biasa

• Gejala → Menganggap API jauh sebagai tatasusunan dan memulihkan satu indeks integer → Sebab ia gagal → Sempadan halaman dan mutasi menghalakan indeks tersebut kepada item yang berbeza → Penyelesaian → Kekalkan snapshot, token, indeks dalam halaman, dan ID yang stabil.
• Gejala → Memajukan token dalam hasNext() → Sebab ia gagal → Pemanggil boleh memeriksa tanpa menggunakan dan kemudian mengalami kerosakan, menyebabkan data dilangkau → Penyelesaian → Majukan keadaan penghantaran hanya selepas next() mengembalikan item.
• Gejala → Beralih ke halaman seterusnya selepas tamat masa → Sebab ia gagal → Keseluruhan halaman mungkin hilang atau permintaan yang berjaya mungkin diduplikasi → Penyelesaian → Cuba semula token yang sama dan lakukan penyahduplikasian mengikut ID stabil.
• Gejala → Mendakwa exactly-once daripada iterator → Sebab ia gagal → Pengekalan titik semak dan kesan sampingan perniagaan bukan satu transaksi atomik tunggal → Penyelesaian → Janjikan at-least-once dan jadikan sink idempoten atau bertransaksi.
• Gejala → Pratarik dan percubaan semula tanpa had → Sebab ia gagal → Pengguna yang perlahan menghabiskan memori dan gangguan perkhidmatan menyekat selama-lamanya → Penyelesaian → Hadkan penimbal, percubaan, had masa tamat, dan TTL snapshot.

Soalan susulan dan jawapan

Bagaimana jika pelayan hanya menyediakan nombor halaman, bukan token snapshot?

Wajibkan kursor kunci majmuk yang stabil atau nyatakan bahawa hanya traversal konsisten lemah yang boleh dilakukan. Nombor halaman berubah selepas sisipan dan pemadaman, jadi ia tidak dapat membuktikan tiada data yang dilangkau atau diduplikasi.

Bagaimana jika sink menerima setiap item sekali sahaja dan tidak boleh menyahduplikasi?

Iterator tidak boleh menjamin exactly-once secara bersendirian. Letakkan kemajuan, penulisan perniagaan, dan titik semak dalam satu transaksi, atau wajibkan sink yang idempoten; jika tidak, nyatakan kemungkinan pendua ke dalam kontrak.

Bagaimana jika satu halaman terus mengalami had masa tamat?

Simpan penimbal lama dan jangan majukan token. Selepas had percubaan semula dicapai, bangkitkan ralat terperingkat supaya pemanggil boleh memilih untuk menjeda, melangkau, atau memulakan semula. Langkah melangkau mesti merekodkan jurang (gap) dan tidak boleh beralih ke halaman seterusnya secara senyap.