Программа курса Урок 27 из 148 · Используйте ИИ, чтобы понимать
Используйте ИИ, чтобы понимать

Двойник без ИИ: хэш-кольцо

Почему это важно В основе свёрнутого журнала из "Фиксации на себе" была одна идея. Вот она снова, в системе, которую вы могли бы действительно построить, с выключенным тьютором.

Для этой задачи тьютор выключен. Решите её сами.

Кластер кэша распределяет ключи по серверам через консистентное хэширование. Каждый сервер владеет некоторыми позициями на кольце целых чисел от 0 примерно до двух миллиардов. Ключ хэшируется в число и принадлежит первой позиции узла, не меньшей этого числа, по ходу кольца: после наибольшей позиции он переходит к наименьшей.

Позиции узлов хранятся отсортированными в общей таблице, но таблица - кольцевой буфер: она начинается там, где остановился последний записавший. Каждое чтение таблицы - сетевой запрос туда и обратно, поэтому чтения считаются.

Данные

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 - Tape различных позиций узлов, которые отсортированы, но могут быть повёрнуты (хранятся с любой начальной точки, возможно с 0). В нём хотя бы один узел. Для каждого хэша h верните наименьшую позицию >= h; если такой нет, верните наименьшую позицию из всех. Бюджет: при 100 000 узлов и 200 хэшах можно прочитать не больше 20 000 значений. len(ring) бесплатен.

ИИ выключен: нет тьютора, подсказок или готового решения для этой задачи. Только ваши собственные мысли.

Заметили проблему в этом уроке? Сообщите о ней · Спросить об этом уроке

Это упражнение откроется скоро

Закончи предыдущий урок, чтобы открылся этот. Весь курс бесплатный, аккаунт не нужен, и ты можешь прочитать этот урок прямо сейчас.