github.com/c1rno/distributed-priority-queue

Distributed priority queue

Точка отсчета Skeap & Seap: Scalable Distributed Priority Queues for Constantand Arbitrary Priorities Тут еще немного инфы про роутинг A Self-Stabilizing General De Bruijn Graph

Базовые сущности, которые необходимы для mvp

Aggregation Tree

Распределенная структура данных (описана в аппендиксе А статьи), ориентированный граф. Граф строится из нод (это отдельный процесс/сервер/т.д.), нода в свою очередь состоит из трех виртуальных нод - левая, средняя, правая, данные хранятся в них

Ноды имеют свой уникальный идентификатор - id - какой он будет нужно придумать; виртуальные ноды идентифицируются по лейблу, лейбл средней виртуальной ноды вычисляется как хеш от id ноды, лейбл левой виртуальной ноды = лейбл средней виртуальной ноды / 2, лейбл правой виртуальной ноды = ( лейбл средней виртуальной ноды + 1 ) / 2.

Более того, id нод дожны быть "сравнимы"/"comparable", т.е. для них должны быть определены операции больше/меньше/равно. Это нужно для роутинга - ноды должны знать свих "чилдов" и "парентов", которые определяются при сравнении id нод; id одной больше другой - первая парент и наоборот. И еще, про id нод, их зацикливают pred(v_min) =v_max and succ(v_max) =v_min, итого, физические ноды просто последовательно выстраиваются в кольцо.

Помимо id "чилда" и "парента" каждая нода должна знать лейблы своих виртуальных нод, а так же лейблы виртуальных нод своих "чилда" и "парента".