강의 계획 레슨 148개 중 27번째 · 이해하려고 AI 쓰기
이해하려고 AI 쓰기

AI 끈 쌍둥이: 해시 링

왜 중요한가 자기 자신에 대한 고집의 감긴 기록은 핵심에 생각 하나가 있었어요. 여기 다시, 실제로 만들 법한 시스템에서, 튜터를 끈 채로 있어요.

이 문제에서는 튜터가 꺼져 있어요. 직접 알아내세요.

캐시 클러스터가 일관된 해싱으로 키를 서버에 퍼뜨려요. 모든 서버는 0부터 약 20억까지의 정수로 된 링 위의 위치 몇 개를 가져요. 키는 숫자로 해시되고, 링을 돌며 그 숫자 이상인 첫 노드 위치에 속해요: 가장 큰 위치를 지나면 가장 작은 것으로 돌아가요.

노드 위치는 공유 표에 정렬되어 저장되지만, 표는 원형 버퍼예요: 마지막으로 쓴 쪽이 남긴 곳에서 시작해요. 표의 모든 읽기는 네트워크 왕복이라 읽기를 세요.

데이터

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]
내 차례

owners(ring, hashes)를 쓰세요. ring은 정렬됐지만 회전됐을 수 있는(어떤 시작점에서든, 0일 수도 있게 저장된) 서로 다른 노드 위치의 Tape예요. 노드는 적어도 하나 있어요. 각 해시 h에 대해 >= h인 가장 작은 위치를 반환하고, 없으면 전체에서 가장 작은 위치를 반환하세요. 예산: 노드 100,000개와 해시 200개에서 최대 20,000개의 값을 읽을 수 있어요. len(ring)은 공짜예요.

AI 끔: 이 문제에는 튜터도, 힌트도, 풀이도 없어요. 내 생각만으로.

이 레슨에서 문제를 발견했나요? 알려 주세요 · 이 레슨에 대해 묻기

이 연습은 곧 열려요

앞의 레슨을 마치면 이 레슨이 열려요. 강좌 전체가 무료이고 계정도 필요 없으며, 이 레슨은 지금 바로 읽을 수 있어요.