Раздел 46 · Effect: Тихая Академия

Кольцо башен: шарды и сущности

middle-senior~20 мин

без входаВойди, чтобы отмечать прогресс, вести заметки и решать задачи в редакторе. войти

В прошлом уроке журнал башни стал актором: одно письмо за раз, без замков. Теперь акторов сорок, и у каждого письма должен быть один хозяин. Если письмо номер семь попадёт к двум башням, будет две записи; если ни к одной, письмо потеряется.

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

Деление по модулю

Самое короткое правило: превратить ключ письма в число и взять остаток от деления на число башен.

export const moduloOwner = (towers: ReadonlyArray<string>, key: string): string =>
  towers[hash(key) % towers.length] ?? '';

hash превращает строку в число, всегда одно и то же для одной строки. Каждая башня знает список башен, считает остаток и получает того же хозяина. Стола нет. Письма делятся поровну, насколько ровен хеш.

Беда приходит ночью, когда встаёт сорок первая башня. Остаток от деления на сорок и остаток от деления на сорок один для одного числа почти всегда разные. В нашем прогоне на две тысячи писем и переходе с четырёх башен на пять сменили хозяина 81% писем. Каждое такое письмо надо перенести: журнал, состояние, недописанную работу. Одна новая башня, и город переезжает целиком.

Кольцо

Другое правило. Свернём все числа хеша в кольцо, как циферблат. Каждую башню поставим на кольцо в точку, равную хешу её имени. Письмо идёт по кольцу от своей точки по часовой стрелке и достаётся первой башне, которую встретит. Это хеш-кольцо (consistent hashing).

Что будет с новой башней? Она встанет в свою точку и заберёт письма только на дуге перед собой, у одной соседки. Все остальные письма как шли, так и идут.

Одна точка на башню даёт кривые дуги: одной башне достанется полкольца, другой щель. Поэтому каждую башню ставят на кольцо много раз, под именами T-1#0, T-1#1 и так далее. Это виртуальные узлы. Дуги мельчают, и новая башня берёт понемногу у всех.

export const makeRing = (towers: ReadonlyArray<string>, virtualNodes: number): Ring => {
  const points = towers
    .flatMap((tower) =>
      Array.from({ length: virtualNodes }, (_, index) => ({ at: hash(`${tower}#${index}`), tower })),
    )
    .toSorted((left, right) => left.at - right.at);
  return {
    towers,
    ownerOf: (key) => {
      const at = hash(key);
      return (points.find((point) => point.at >= at) ?? points[0])?.tower ?? '';
    },
  };
};

Разберём.

  • flatMap ставит каждую башню на кольцо virtualNodes раз и складывает все точки в один список.
  • toSorted выстраивает точки по ходу кольца.
  • ownerOf ищет первую точку не меньше хеша ключа. Не нашлась, значит ключ после последней точки, и он достаётся первой: кольцо замкнулось.

На том же прогоне кольцо со ста точками на башню при переходе с четырёх башен на пять сменило хозяина у 22% писем, против 81% у модуля. Идеал для пятой башни это пятая часть, 20%: ровно столько ей и положено забрать. И сменили только письма, которые достались новой башне: у всех остальных хозяин прежний.

Ровно ли делятся письма? С одной точкой на башню в нашем прогоне у самой загруженной из четырёх башен 784 письма, у самой свободной 126: дуги кольца выходят какие придётся. Со ста точками 564 и 420. Виртуальные узлы сглаживают перекос, но не до нуля. И хеш тут не любой: FNV-1a без финального перемешивания битов кладёт похожие ключи вроде T-1#1 и T-1#2 рядом, кучей, поэтому в ring.ts после него стоит перемешивание fmix32 из murmur3.

Покрути кольцо сам:

Ползунок меняет число виртуальных узлов, кнопки добавляют и убирают башню. Под кольцом счётчик: сколько писем переехало на кольце и сколько переехало бы при делении по модулю.

Сущности кластера

Свернуть кольцо мы умеем, но кольцо не всё. Нужно ещё доставить письмо к хозяину, дождаться ответа, пережить смерть машины, на которой хозяин живёт. Это делает кластер Effect, effect/cluster. В нём акторы называются сущностями.

Сущность описывают теми же RPC, что служебную линию в уроке 93:

import { Effect, Ref, Schema } from 'effect';
import { ClusterSchema, Entity } from 'effect/cluster';
import { Rpc } from 'effect/rpc';

export const Deliver = Rpc.make('Deliver', {
  payload: { letter: Schema.Int, from: Schema.String },
  success: Schema.Int,
}).annotate(ClusterSchema.Persisted, true);

export const Received = Rpc.make('Received', { success: Schema.Array(Schema.Int) });

export const Tower = Entity.make('Tower', [Deliver, Received]);

export const TowerLayer = Tower.toLayer(
  Effect.gen(function* () {
    const letters = yield* Ref.make<ReadonlyArray<number>>([]);
    return Tower.of({
      Deliver: ({ payload }) =>
        Ref.modify(letters, (seen) => {
          const next = seen.includes(payload.letter) ? seen : [...seen, payload.letter];
          return [next.length, next];
        }),
      Received: () => Ref.get(letters),
    });
  }),
);

Entity.make('Tower', ...) даёт тип сущности. toLayer описывает, как построить одну башню: при первом письме на адрес кластер создаёт сущность, и у неё свой Ref. Обработчики одной сущности идут по одному, как у нашего актора. ClusterSchema.Persisted у Received просит кластер сохранять такие письма в хранилище сообщений; о том, зачем, следующий урок.

Позвать башню:

const program = Effect.gen(function* () {
  const clientFor = yield* Tower.client;
  yield* clientFor('T-2').Deliver({ letter: 1, from: 'T-1' });
  return yield* clientFor('T-2').Received();
});

clientFor('T-2') это адрес, а не машина. Вызывающий не знает, где живёт T-2, и не должен знать. Сегодня она на одном раннере, завтра на другом, адрес тот же.

Для тестов есть TestRunner.layer: кластер в одном процессе, хранилище в памяти, без сети. Одна особенность: кластер раздаёт шарды по настоящим часам, поэтому тесты кластера идут на it.live, а не на it.effect с TestClock. Под тестовыми часами кластер так и не дождётся своих шардов.

Под капотом

Где тут дыра

const owner = (towers: ReadonlyArray<string>, letter: number) => towers[letter % towers.length];

На его примере всё ровно: четыре башни, письма с первого по сотое, каждой по двадцать пять. Соседний пример: ночью встала пятая. Письмо 7 жило у T-4 (7 по модулю 4 это 3), теперь его хозяин T-3 (7 по модулю 5 это 2). Четыре письма из пяти сменили хозяина разом, у каждой башни журнал наполовину чужой, и до утра башни перекидывают письма друг другу вместо того, чтобы их доставлять. Модуль годится, когда делитель не меняется, как 300 шардов кластера. Для башен, которые приходят и уходят, нужно кольцо.

Нестабильно. Модули effect/cluster (Entity, Sharding, TestRunner, ClusterSchema) и effect/rpc, а с ними HashRing из ядра, в 4.1 помечены @stability unstable: имена, настройки и устройство шардов могут поменяться в минорной версии. Урок написан на 4.1.0.

Линия, этап 3

Линия узнаёт хозяина письма без конторы. Два новых модуля: src/ring.ts со своим хеш-кольцом и делением по модулю для сравнения и src/tower.ts с башней-сущностью кластера. Тесты кладут на кольцо две тысячи писем, ставят пятую башню и считают переезды, а башню-сущность зовут через TestRunner.layer.

Практика

Глубже в архиве

Как сервисы находят друг друга и делят нагрузку в распределённой системе, разобрано в уроке про топологию микросервисов раздела про бэкенд.

Дальше

Кольцо разложено, башни знают своих. Ринцвальд стоит у окна с журналом кадров и не уходит.

Гарантии доставки ждут в следующем уроке.