Silabus Pelajaran 27 dari 148 · Gunakan AI untuk memahami
Gunakan AI untuk memahami

Kembaran AI-off: ring hash

Kenapa ini penting Log yang dibungkus di Fixation on yourself punya satu ide utama. Ini dia lagi, di sistem yang mungkin benar-benar kamu bangun, dengan tutor dimatikan.

Tutor dimatikan untuk soal ini. Kerjakan sendiri.

A cluster cache menyebarkan kunci ke server dengan consistent hashing. Setiap server memiliki beberapa posisi pada lingkaran bilangan bulat dari 0 sampai sekitar dua miliar. Sebuah kunci di-hash ke sebuah angka, dan ia milik posisi node pertama pada atau setelah angka tersebut, berputar di lingkaran: melewati posisi terbesar, ia kembali ke posisi terkecil.

Posisi node disimpan secara terurut dalam tabel bersama, tapi tabelnya adalah circular buffer: tabel dimulai di mana penulis terakhir berhenti. Setiap pembacaan tabel adalah satu round trip jaringan, jadi pembacaan dihitung.

Data

from creative.budget import Tape
ring = Tape([700, 900, 100, 300])   # sorted positions 100, 300, 700, 900, stored from 700
hashes = [250, 950]
# owners(ring, hashes) -> [300, 100]
Giliranku

Tulis owners(ring, hashes). ring adalah Tape dari posisi node yang berbeda yang sudah terurut tapi mungkin diputar (disimpan dari titik awal mana saja, mungkin 0). Ini berisi setidaknya satu node. Untuk setiap hash h, kembalikan posisi terkecil >= h; jika tidak ada, kembalikan posisi terkecil dari semuanya. Budget: dengan 100,000 node dan 200 hash kamu boleh membaca maksimal 20,000 nilai. len(ring) gratis.

AI mati: tidak ada tutor, petunjuk atau solusi lengkap untuk yang ini. Hanya pemikiranmu sendiri.

Ada masalah di pelajaran ini? Laporkan · Tanya tentang pelajaran ini

Latihan ini akan segera dibuka

Selesaikan pelajaran sebelumnya agar pelajaran ini terbuka. Seluruh kursus ini gratis, tidak butuh akun, dan kamu bisa baca pelajaran ini sekarang.