Conteúdo do curso Lição 27 de 148 · Use IA para entender
Use IA para entender

IA desligada gêmea: o hash ring

Por que isso importa O log encapsulado em Fixation on yourself tinha uma ideia em seu cerne. Aqui está ele novamente, em um sistema que você pode realmente construir, com a IA desligada.

O tutor está com a IA desligada para este problema. Resolva por conta própria.

A cluster de cache distribui chaves por servidores com hashing consistente. Cada servidor é dono de algumas posições em um anel de números inteiros de 0 até cerca de dois bilhões. Uma chave é transformada em um número por hash, e ela pertence à primeira posição de nó na ou após esse número, dando a volta no anel: passando pela maior posição, ela volta para a menor.

As posições dos nós são armazenadas ordenadas em uma tabela compartilhada, mas a tabela é um buffer circular: ela começa onde o último escritor parou. Cada leitura da tabela é uma viagem de ida e volta na rede, então as leituras são contadas.

Os dados

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]
Sua vez

Escreva owners(ring, hashes). ring é uma Tape de posições de nós distintos que estão ordenadas mas podem estar rotacionadas (armazenadas a partir de qualquer ponto inicial, possivelmente 0). Ela contém pelo menos um nó. Para cada hash h, retorne a menor posição >= h; se não houver nenhuma, retorne a menor posição de todas. Budget: com 100.000 nós e 200 hashes você pode ler no máximo 20.000 valores. len(ring) é grátis.

IA desligada: sem tutor, dicas ou solução resolvida nesta. Apenas seu próprio pensamento.

Viu um problema nesta lição? Reporte-o · Pergunte sobre esta lição

Este exercício abre em breve

Termine a lição anterior para que esta seja desbloqueada. O curso inteiro é gratuito, não precisa de conta, e você pode ler esta lição agora mesmo.