Konteks dan cakupan
Anda mengelola API file, organisasi, atau knowledge-graph yang sumber dayanya dapat mengarah ke sumber daya lain melalui alias atau binding. Klien meminta ekspansi rekursif yang mirip dengan Depth: infinity WebDAV. Rancang traversal, pelaporan siklus, anggaran kedalaman dan node, serta jelaskan kapan 508 tidak tepat digunakan. Topik ini cocok untuk wawancara backend, penyimpanan, dan platform.
RFC 5842 mendefinisikan 508 untuk menghentikan operasi kedalaman tak terbatas setelah loop ditemukan; ini bukan kode umum untuk loop pengalihan (redirect) atau batas waktu CPU. Asumsikan graf dapat melintasi banyak tenant dan setiap edge serta node memerlukan otorisasi.
Apa yang diuji oleh pewawancara
- Apakah Anda memodelkan traversal rekursif sebagai graf daripada menunggu terjadinya stack overflow.
- Apakah Anda membedakan node yang berulang dari node pada jalur saat ini, menggunakan state visited global dan state path untuk tugas yang berbeda.
- Apakah Anda menetapkan anggaran untuk kedalaman, node, edge, byte, dan waktu, lalu mengembalikan kegagalan yang dapat ditindaklanjuti oleh klien.
Jawaban yang lemah hanya menambahkan kedalaman rekursi maksimum. Jawaban yang kuat mencakup identitas sumber daya yang stabil, siklus jalur vs subgraf bersama, habisnya anggaran, batasan 508, dan keamanan cache multi-tenant.
Pertanyaan klarifikasi untuk diajukan terlebih dahulu
- Apakah relasinya berupa tree, DAG, atau graf berarah arbitrer? DAG masih memerlukan set visited untuk menghindari pekerjaan duplikat; graf arbitrer juga memerlukan deteksi siklus pada jalur saat ini.
- Apakah klien memerlukan ekspansi lengkap, hasil berhalaman (paged), atau hanya keterjangkauan (reachability)? Kontrak keluaran menentukan apakah hasil parsial atau pekerjaan asinkron valid.
- Apakah ID sumber daya unik secara global? Alias dan binding lintas-tenant memerlukan identitas kanonikal sebelum kunci visited dibuat.
- Siapa yang mengontrol anggaran? Layanan harus memberlakukan batas tegas (hard limits); kedalaman yang disediakan klien tidak dapat secara langsung menentukan konsumsi database atau memori.
Jawaban 30 detik
“Saya memodelkan relasi sebagai graf berarah dan mengkanonisasi setiap sumber daya ke ID yang stabil. Selama penelusuran, saya menyimpan set jalur saat ini untuk mendeteksi siklus nyata dan set visited global untuk menghindari ekspansi ulang subgraf bersama. Layanan menerapkan batas tegas pada kedalaman, node, edge, byte respons, dan waktu proses (wall time). Siklus yang terdeteksi dapat menghasilkan 508; anggaran yang habis menghasilkan error batas eksplisit atau status pekerjaan asinkron. Hasil mencakup edge siklus yang disunting (redacted), alasan pemotongan, dan ID permintaan, tidak pernah menyertakan node yang tidak terotorisasi. Pengujian mencakup siklus mandiri (self-cycles), siklus alias, subgraf bersama, edge yang ditolak, dan graf dalam yang berbahaya.”
Solusi langkah demi langkah
1. Tentukan batasan 508
RFC 5842 menggunakan 508 ketika operasi sumber daya rekursif menemui loop tak terbatas. Pengalihan URL biasa memerlukan perlindungan rantai pengalihan; batas waktu habis atau anggaran yang habis memerlukan error-nya sendiri. Status menjelaskan kelas kegagalan, sedangkan isi respons menyediakan diagnostik.
2. Kanonisasi identitas sumber daya
Selesaikan alias menjadi tupel tenant, jenis sumber daya, dan ID yang tidak dapat diubah (immutable). Jangan gunakan string jalur, varian huruf besar-kecil, atau URL yang berbeda sebagai kunci visited. Resolusi alias juga memerlukan batas lompatan (hop limit) agar tidak dapat berputar sebelum penelusuran graf dimulai.
3. Pisahkan state jalur dan state visited
path mewakili cabang DFS saat ini; sebuah edge ke node di path adalah sebuah siklus. visited mewakili node yang telah selesai atau diantrekan untuk permintaan ini dan menghapus pekerjaan duplikat dalam graf berbentuk berlian. Satu set gabungan akan melaporkan pembagian legal sebagai siklus atau melewatkan siklus di cabang lain.
4. Tetapkan anggaran dan aturan pemotongan
Batasi kedalaman maksimum, node, edge, byte respons, dan waktu proses (wall-clock time). Terapkan anggaran per tenant dan per permintaan, serta lakukan paging pada pembacaan database. Saat anggaran habis, kembalikan jumlah, alasan pemotongan, dan mekanisme kelanjutan. Jika protokol memerlukan hasil yang lengkap, buat pekerjaan penelusuran asinkron alih-alih mengembalikan tree parsial yang menyesatkan.
5. Tangani otorisasi dan caching
Otorisasi setiap sumber daya sebelum menambahkannya ke hasil yang terlihat. Kunci cache harus mencakup tenant, versi izin, dan parameter penelusuran; jika tidak, satu tenant dapat menyimpulkan node tersembunyi milik tenant lain dari diagnostik siklus. Untuk graf yang mahal, cache edge kanonikal tetapi periksa kembali otorisasi untuk setiap permintaan.
6. Pilih bentuk respons
Ketika siklus ditemukan dan klien memahami diagnostik, kembalikan 508 dengan ID siklus yang disunting, lokasi pemotongan, dan ID permintaan. Jika klien menginginkan upaya terbaik (best effort), kembalikan koleksi berhalaman yang berhasil dan ditandai truncated; itu berbeda dari kegagalan seluruh operasi pada 508. Jangan melabeli database stack overflow atau loop mandiri proxy sebagai 508 tanpa mencocokkan penyebabnya.
7. Uji serangan dan jalur kegagalan
Uji siklus mandiri, A-ke-B-ke-A, beberapa alias untuk satu node, subgraf bersama, kedalaman tepat pada batas, fan-out besar, edge lintas-tenant yang ditolak, dan batas waktu habis. Pastikan bahwa setiap node diekspansi paling banyak satu kali, penolakan tidak mengubah jumlah yang terlihat, dan error tidak mengungkapkan ID sumber daya tersembunyi.
Contoh jawaban berkualitas tinggi
“Saya memperlakukan ekspansi rekursif sebagai masalah graf berarah. Saya menyelesaikan alias ke tenant dan ID sumber daya yang stabil, menggunakan state jalur saat ini untuk siklus nyata, dan menggunakan state visited global untuk deduplikasi subgraf bersama. Anggaran kedalaman, node, edge, ukuran respons, dan waktu adalah batas tegas yang diteruskan ke dalam kueri berhalaman. Saya mengembalikan 508 hanya ketika operasi rekursif benar-benar menemui siklus dan klien mendukung kontrak tersebut; pengalihan biasa dan batas waktu habis menggunakan error-nya masing-masing. Respons hanya berisi data siklus yang terotorisasi dan disunting serta ID permintaan. Kunci cache mencakup tenant, versi izin, dan parameter. Pengujian mencakup siklus mandiri, siklus alias, graf berlian, edge yang ditolak, dan kedalaman berbahaya.”
Kesalahan umum
- Menyamakan kedalaman maksimum dengan deteksi siklus → Tree dalam yang valid gagal sementara siklus dangkal dapat tetap ada → Gunakan state jalur untuk siklus dan kedalaman hanya sebagai anggaran.
- Hanya menyimpan visited global → Subgraf bersama dilaporkan sebagai siklus → Pisahkan jalur saat ini dari state penelusuran global.
- Mengembalikan 508 untuk setiap batas waktu habis → Klien tidak dapat membedakan siklus graf dari kelebihan beban (overload) → Buat status cocok dengan penyebab sebenarnya.
- Melakukan ekspansi sebelum otorisasi → Detail error dapat membocorkan node tersembunyi → Berikan otorisasi sebelum penelusuran yang terlihat dan penghitungan.
- Menghilangkan versi izin dari kunci cache → Hasil dari akses lama tetap terlihat → Ikat entri cache ke tenant, versi izin, dan parameter.
Pertanyaan lanjutan dan tanggapan
Jika graf adalah DAG, mengapa harus mempertahankan state jalur saat ini?
Model data mungkin menjanjikan DAG, tetapi migrasi, alias, atau penulisan konkuren dapat melanggarnya untuk sementara waktu. State jalur adalah pengaman runtime yang murah; siklus yang terdeteksi juga harus mengidentifikasi sumber penulisannya dan memblokir binding baru.
Bisakah Anda mengembalikan 508 ketika pelanggan menginginkan node apa pun yang ditemukan?
Jangan menyamarkan data parsial sebagai kegagalan 508 lengkap. Tentukan kontrak berhalaman atau asinkron yang mengembalikan halaman yang selesai, alasan pemotongan, dan kursor kelanjutan. Gunakan 508 hanya ketika klien memerlukan ekspansi lengkap yang atomik.
Bagaimana Anda mencegah tenant dengan fan-out tinggi menghabiskan kapasitas database?
Tetapkan kuota konkurensi, node, edge, waktu kueri, dan byte respons per tenant; batasi prefetch batch dan terapkan backpressure. Antrekan atau tolak permintaan yang melebihi anggaran, pantau konsumsi per tenant dan penyebab kegagalan, dan jangan biarkan klien melewati batas dengan meningkatkan kedalaman.