Kurrikulum Leson 27 van 148 · Gebruik AI om te verstaan
Gebruik AI om te verstaan

AI-af skep: die hash ring

Waarom dit saak maak Die omsluitende log in Fixation on yourself het een idee in die kern gehad. Hier is dit weer, in 'n stelsel wat jy dalk werklik kan bou, met die tutor af

Die tutor is afgeskakel vir hierdie probleem. Werk dit self uit.

A cache cluster versprei sleutels oor bedieners met consistent hashing. Elke bediener besit sekere posisies op 'n ring van heelgetalle van 0 tot by ongeveer twee miljard. 'n Sleutel word na 'n nommer gehash, en dit behoort aan die eerste knoopposisie by of na daardie nommer, deur die ring te gaan: verby die grootste posisie, draai dit terug na die kleinste.

Die node-posisies word gesorteer in 'n gedeelde tabel gestoor, maar die tabel is 'n sirkelvlakbuffer: dit begin waar die laaste skrywer opgehou het. Elke lees van die tabel is 'n netwerk-rondrit, so word leesaksies getel.

Die 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]
Jou beurt

Skryf owners(ring, hashes). ring is 'n Tape van unieke knoopposisies wat gesorteer is maar mag geroteer wees (gestoor vanaf enige beginpunt, moontlik 0). Dit hou ten minste een knoop. Vir elke hash h, gee die kleinste posisie >= h terug; as daar geen is nie, gee die kleinste posisie van almal terug. Budget: met 100,000 knope en 200 hashes mag jy hoogstens 20,000 waardes lees. len(ring) is gratis.

AI af: geen tutor, wenke of uitgewerkte oplossing op hierdie een nie. Net jou eie denke.

Sien jy 'n probleem in hierdie les? Rapporteer dit · Vra oor hierdie les

Hierdie oefening open binnekort

Voltooi die lesie voor dit en hierdie een sal ontvanklik wees. Die hele kursus is gratis, geen rekening nodig nie, en jy kan hierdie les nou lees.