Компактное кодирование числа с суффиксом или префиксом

Question

Допустим, у меня есть 6-значные идентификаторы порядка:

000000
000001
000003
...
000020
...
999999

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

010000 - second node
020001 - third node
010003 - second node again
150004 - 16th node
...

Это работает нормально, но так как я точно знаю, что ожидаю только небольшуюколичество узлов (скажем, 16) Я теряю множество возможных идентификаторов, ограничивая себя до 10 ^ 4 вместо 10 ^ 6.Есть ли умный способ кодировать 15 уникальных узлов без ограничения возможных чисел?В идеале у меня было бы 10^6 - 15 возможностей.

РЕДАКТИРОВАТЬ: Я ищу решение, которое не будет равномерно распределять диапазон для каждого идентификатора узла.Я ищу способ кодировать идентификатор узла в уже существующем уникальном идентификаторе, не теряя (в идеале) больше, чем количество узлов возможностей.

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

Answer 1

Я теряю множество возможных идентификаторов, ограничивая себя 10 ^ 4 вместо 10 ^ 6.

У нас все еще есть 10^4 * 16 идентификаторы всего .

Существует ли умный способ кодировать 15 уникальных узлов без ограничения возможных чисел?

Эта проблема аналогична распределенной хэш-таблице разбиению пространства ключей.Наиболее известное решение этой проблемы - создать множество виртуальных узлов, разделить пространство ключей между этими виртуальными узлами, а затем назначить эти виртуальные узлы физическим особым образом (циклический, случайный, по запросу и т. Д.).

Самый простой способ реализовать разделение пространства ключей - убедиться, что каждый узел генерирует такой идентификатор:

vnode_id = order_id % total_number_of_vnodes

Например, если у нас всего 3 vnodes [0, 1, 2], тогда:

vnode 0 must generate ids: 0, 3, 6, 9...
vnode 1 must generate ids: 1, 4, 7, 10...
vnode 2 must generate ids: 2, 5, 7, 11...

Если у нас есть 7 vnode [0, 1, 2, 3, 4, 5, 6], то:

vnode 0 must generate ids: 0, 7, 14, 21... 
vnode 1 must generate ids: 1, 8, 15, 22... 
vnode 2 must generate ids: 2, 9, 16, 23... 
...
vnode 6 must generate ids: 6, 13, 20, 27... 

Тогда все физические узлы должны отображаться на виртуальный визвестный и распространенный способ, например, отображение 1: 1:

physical node 0 takes vnode 0
physical node 1 takes vnode 1
physical node 2 takes vnode 2

отображение по требованию:

physical node 0 takes vnode 0, 3, 7 (many orders)
physical node 1 takes vnode 1, 4 (less orders)
physical node 2 takes vnode 2 (no orders) 

Надеюсь, вы поняли идею.

В идеале у меня было бы 10 ^ 6 - 15 возможностей.

К сожалению, это невозможно.Учтите это: у нас есть 10 ^ 6 возможных идентификаторов и 15 различных узлов, каждый из которых генерирует уникальный идентификатор.

По сути, это означает, что так или иначе мы разделяем наши идентификаторы между узламикаждый узел получает в среднем 10^6 / 15, что намного меньше, чем желательно 10^6 - 15.

Используя описанный выше метод, мы все равно имеем в общей сложности 10^6 идентификаторов, но они будут распределены между vnode, которыев свою очередь будет сопоставлен с физическими узлами.Это лучшее практическое решение для вашей проблемы AFAIK.

Я ищу решение, которое не будет одинаково распределять диапазон для каждого идентификатора узла.Я ищу способ кодирования идентификатора узла в уже существующем уникальном идентификаторе, не теряя (в идеале) больше, чем количество узлов возможностей.

Не ожидайте чуда.Может быть много других хитростей, которые стоит попробовать.

Например, если Сервер и все Клиенты знают, что идентификатор следующего заказа должен быть 235, но скажем, Клиент 5 генерирует идентификатор заказа 240 (235 + 5) и отправляетэто к серверу.

Сервер ожидает идентификатор заказа 235, но получает идентификатор заказа 240. Итак, теперь сервер знает, что этот заказ поступает от клиента 5 (240 - 235).

Или мы можем попытатьсяиспользуйте другое поле для хранения идентификатора клиента.Например, если у вас есть время (ЧЧ: MM.SS), мы можем использовать секунды для хранения идентификатора клиента.

Просто несколько примеров, я думаю, вы поняли ...

Answer 2

Вы можете разделить 10 ^ 6 возможных идентификаторов на куски, близкие к равным, где начальный индекс каждого чанка равен 10 ^ 6, деленному на количество кусков, округление вниз, умножение на индекс чанка иРазмер фрагмента равен 10 ^ 6, разделенному на количество фрагментов, округленных вниз.В вашем примере шестнадцать блоков:

10^6 / 16 = 62,500
chunk1:  [     0,   62500)
chunk2:  [ 62500,  125000)
chunk3:  [125000,  187500)
chunk4:  [187500,  250000)
chunk5:  [250000,  312500)
chunk6:  [312500,  375000)
chunk7:  [375000,  437500)
chunk8:  [437500,  500000)
chunk9:  [500000,  562500)
chunk10: [562500,  625000)
chunk11: [625000,  687500)
chunk12: [687500,  750000)
chunk13: [750000,  812500)
chunk14: [812500,  875000)
chunk15: [875000,  937500)
chunk16: [937500, 1000000)

Чтобы вычислить глобальный идентификатор из локального идентификатора на узле X, рассчитайте 62500 * X + локальный идентификатор.Чтобы определить узел и локальный идентификатор из узла, вычислите узел = глобальный идентификатор / 62500 с округлением вниз и локальный идентификатор = глобальный идентификатор мода 62500.

При этом вы получаете возможность использовать практически все доступные индексы вплоть до округленияошибка.Деление и модуль на целые числа должны быть относительно быстрыми по сравнению с вводом / выводом между узлами.

Answer 3

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

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

0 -> A
1 -> B
2 -> C
...
9 -> J

Например:

{759243, 5} -> 759C4D

Теперь вы можете кодировать все 10 ^ 6 идентификаторов заказа вместе с6-битный идентификатор узла.

Answer 4

Позвольте n быть числом, представленным первыми 2 цифрами 6-значного ввода.Предполагая, что у вас есть 16 узлов, мы можем сделать:

nodeId = n % 16 

Также:

highDigit = n / 16

Где / представляет целочисленное деление.Для 16 узлов highDigit = [0..6]

Если m - это число, представленное последними 4 цифрами ввода, то мы можем восстановить исходный идентификатор заказа следующим образом:

orderId = highDigit*10^5 + m

С помощью этой схемы и 16 узлов вы можете представить 6 * 10 ^ 5 + 10 ^ 4 идентификатора заказа.