Gesaan dan skop
Anda menyelenggara API fail, organisasi, atau graf pengetahuan yang sumbernya boleh menunjuk ke sumber lain melalui alias atau ikatan (bindings). Klien meminta pengembangan rekursif yang serupa dengan Depth: infinity WebDAV. Reka bentuk rentasan, pelaporan kitaran, belanjawan kedalaman dan nod, serta terangkan bila 508 tidak wajar digunakan. Ini sesuai untuk temu duga backend, storan, dan platform.
RFC 5842 mentakrifkan 508 untuk menamatkan operasi kedalaman tak terhingga selepas gelung ditemui; ia bukan kod generik untuk gelung pengalihan semula atau masa tamat CPU. Andaikan graf boleh merentasi penyewa (tenants) dan setiap pinggir (edge) serta nod memerlukan kebenaran.
Perkara yang diuji oleh penemu duga
- Sama ada anda memodelkan rentasan rekursif sebagai graf dan bukannya menunggu limpahan tindanan (stack overflow).
- Sama ada anda membezakan nod berulang daripada nod pada laluan semasa, menggunakan keadaan dikunjungi global dan laluan untuk tugas yang berbeza.
- Sama ada anda menetapkan belanjawan untuk kedalaman, nod, pinggir, bait, dan masa, kemudian mengembalikan kegagalan yang boleh diambil tindakan oleh klien.
Jawapan yang lemah hanya menambah kedalaman rekursi maksimum. Jawapan yang kukuh merangkumi identiti sumber yang stabil, kitaran laluan berbanding subgraf dikongsi, kehabisan belanjawan, sempadan 508, dan keselamatan cache berbilang penyewa.
Soalan penjelasan untuk ditanya terlebih dahulu
- Adakah hubungan itu sebuah pokok (tree), DAG, atau graf berarah sewenang-wenangnya? DAG masih memerlukan set dikunjungi untuk mengelakkan kerja pendua; graf sewenang-wenangnya juga memerlukan pengesanan kitaran laluan semasa.
- Adakah klien memerlukan pengembangan lengkap, hasil berhalaman, atau kebolehcapaian sahaja? Kontrak output menentukan sama ada hasil separa atau kerja tak segerak adalah sah.
- Adakah ID sumber unik secara global? Alias dan ikatan rentas penyewa memerlukan identiti kanonikal sebelum kunci dikunjungi dibina.
- Siapa yang mengawal belanjawan? Perkhidmatan mesti mengenakan had keras; kedalaman yang disediakan oleh klien tidak boleh menentukan penggunaan pangkalan data atau memori secara langsung.
Jawapan 30 saat
“Saya memodelkan hubungan sebagai graf berarah dan mengkanonisasikan setiap sumber kepada ID yang stabil. Semasa rentasan, saya mengekalkan set laluan semasa untuk mengesan kitaran sebenar dan set dikunjungi global untuk mengelakkan pengembangan semula subgraf yang dikongsi. Perkhidmatan ini menguatkuasakan had keras pada kedalaman, nod, pinggir, bait respons, dan masa jam sebenar (wall time). Kitaran yang dikesan boleh menghasilkan 508; belanjawan yang habis menghasilkan ralat had eksplisit atau keadaan kerja tak segerak. Hasil merangkumi pinggir kitaran yang disunting (redacted), sebab pemotongan, dan ID permintaan, tidak sekali-kali nod yang tidak dibenarkan. Ujian meliputi kitaran kendiri, kitaran alias, subgraf dikongsi, pinggir dinafikan, dan graf dalam yang berniat jahat.”
Penyelesaian langkah demi langkah
1. Tentukan sempadan 508
RFC 5842 menggunakan 508 apabila operasi sumber rekursif menemui gelung tak terhingga. Pengalihan semula URL biasa memerlukan perlindungan rantai pengalihan semula; masa tamat atau belanjawan yang habis memerlukan ralatnya sendiri. Status menerangkan kelas kegagalan, manakala badan respons menyediakan diagnostik.
2. Kanonisasikan identiti sumber
Selesaikan alias kepada tupel penyewa, jenis sumber, dan ID tidak boleh ubah. Jangan gunakan rentetan laluan, varian huruf besar/kecil, atau URL yang berbeza sebagai kunci dikunjungi. Resolusi alias juga memerlukan had lompatan (hop limit) supaya ia tidak boleh bergelung sebelum rentasan graf bermula.
3. Asingkan keadaan laluan dan keadaan dikunjungi
path mewakili cabang DFS semasa; pinggir ke nod dalam path ialah kitaran. visited mewakili nod yang telah selesai atau dimasukkan ke dalam baris gilir untuk permintaan ini dan menghapuskan kerja pendua dalam graf berbentuk berlian. Satu set gabungan sama ada melaporkan perkongsian sah sebagai kitaran atau terlepas kitaran pada cabang lain.
4. Tetapkan belanjawan dan peraturan pemotongan
Hadkan kedalaman maksimum, nod, pinggir, bait respons, dan masa jam dinding. Guna pakai belanjawan bagi setiap penyewa dan permintaan, serta lakukan halaman bagi bacaan pangkalan data. Apabila habis, kembalikan kiraan, sebab pemotongan, dan mekanisme penerusan. Jika protokol memerlukan hasil yang lengkap, cipta kerja rentasan tak segerak dan bukannya mengembalikan pokok separa yang mengelirukan.
5. Kendalikan kebenaran dan caching
Benarkan setiap sumber sebelum menambahkannya ke hasil yang boleh dilihat. Kunci cache mesti menyertakan penyewa, versi kebenaran, dan parameter rentasan; jika tidak, satu penyewa mungkin membuat inferens nod tersembunyi penyewa lain daripada diagnostik kitaran. Untuk graf yang mahal, cache pinggir kanonikal tetapi semak semula kebenaran untuk setiap permintaan.
6. Pilih bentuk respons
Apabila kitaran ditemui dan klien memahami diagnostik, kembalikan 508 dengan ID kitaran yang disunting, lokasi pemotongan, dan ID permintaan. Jika klien mahukan usaha terbaik, kembalikan koleksi berhalaman yang berjaya ditandakan truncated; itu berbeza daripada kegagalan keseluruhan operasi 508. Jangan labelkan limpahan tindanan pangkalan data atau gelung kendiri proksi sebagai 508 tanpa memadankan puncanya.
7. Uji serangan dan laluan kegagalan
Uji kitaran kendiri, A-ke-B-ke-A, berbilang alias untuk satu nod, subgraf dikongsi, kedalaman tepat pada had, fan-out besar, pinggir rentas penyewa yang dinafikan, dan masa tamat. Pastikan setiap nod dikembangkan paling banyak sekali, penafian tidak mengubah kiraan yang kelihatan, dan ralat tidak mendedahkan ID sumber tersembunyi.
Contoh jawapan berkualiti tinggi
“Saya menganggap pengembangan rekursif sebagai masalah graf berarah. Saya menyelesaikan alias kepada penyewa dan ID sumber yang stabil, menggunakan keadaan laluan semasa untuk kitaran sebenar, dan menggunakan keadaan dikunjungi global untuk penyahduplikasian subgraf yang dikongsi. Belanjawan kedalaman, nod, pinggir, saiz respons, dan masa ialah had keras yang dihantar ke dalam pertanyaan berhalaman. Saya mengembalikan 508 hanya apabila operasi rekursif benar-benar menemui kitaran dan klien menyokong kontrak tersebut; pengalihan biasa dan masa tamat menggunakan ralat mereka sendiri. Respons hanya mengandungi data kitaran yang dibenarkan dan disunting serta ID permintaan. Kunci cache merangkumi penyewa, versi kebenaran, dan parameter. Ujian meliputi kitaran kendiri, kitaran alias, graf berlian, pinggir dinafikan, dan kedalaman berniat jahat.”
Kesilapan biasa
- Menyamakan kedalaman maksimum dengan pengesanan kitaran → Pokok dalam yang sah gagal manakala kitaran cetek boleh kekal → Gunakan keadaan laluan untuk kitaran dan kedalaman hanya sebagai belanjawan.
- Hanya mengekalkan dikunjungi global → Subgraf yang dikongsi dilaporkan sebagai kitaran → Asingkan laluan semasa daripada keadaan rentasan global.
- Mengembalikan 508 untuk setiap masa tamat → Klien tidak dapat membezakan kitaran graf daripada beban lampau → Jadikan status sepadan dengan punca sebenar.
- Mengembangkan sebelum kebenaran → Butiran ralat boleh membocorkan nod tersembunyi → Berikan kebenaran sebelum rentasan yang kelihatan dan pengiraan.
- Meninggalkan versi kebenaran daripada kunci cache → Hasil daripada akses lama kekal kelihatan → Ikat entri cache kepada penyewa, versi kebenaran, dan parameter.
Soalan susulan dan respons
Jika graf ialah DAG, mengapa perlu mengekalkan keadaan laluan semasa?
Model data mungkin menjanjikan DAG, tetapi migrasi, alias, atau penulisan serentak boleh melanggarnya buat sementara waktu. Keadaan laluan ialah perlindungan masa jalan yang murah; kitaran yang dikesan juga harus mengenal pasti sumber penulisannya dan menyekat ikatan baharu.
Bolehkah anda mengembalikan 508 apabila pelanggan mahukan apa sahaja nod yang ditemui?
Jangan samarkan data separa sebagai kegagalan 508 yang lengkap. Tentukan kontrak berhalaman atau tak segerak yang mengembalikan halaman yang lengkap, sebab pemotongan, dan kursor penerusan. Gunakan 508 hanya apabila klien memerlukan pengembangan lengkap atomik.
Bagaimanakah anda menghalang penyewa dengan fan-out tinggi daripada menghabiskan pangkalan data?
Tetapkan kuota keserempakan, nod, pinggir, masa pertanyaan, dan bait respons bagi setiap penyewa; hadkan pra-ambil kelompok dan gunakan tekanan balik (backpressure). Bariskan atau tolak permintaan yang melebihi belanjawan, pantau penggunaan dan punca kegagalan bagi setiap penyewa, dan jangan biarkan klien memintas had dengan meningkatkan kedalaman.