Какое лучшее решение для выделения числа из очень большого диапазона чисел?

Описание требования

Есть пул №1 - 160 000 000.

При создании объекта необходимо выделить объекту один номер. Есть некоторые правила

  1. номер в пуле
  2. номер, не занятый другим объектом

Также пользователь иногда указывает один номер для создания объекта.

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

Обратите внимание, что здесь мы используем mongo DB. Я не хочу менять базу данных, потому что это одна проблема.

Решение 1

Создайте большую таблицу (коллекцию) со 160 000 000 элементов. Структура коллекции такова.

number,allocated

При выделении номера используйте метод find_one_and_update для обновления одной записи, измените выделенное значение с false на true.

проблема

проблема для этого решения заключается в том, что создание коллекции из 160 000 000 слишком тяжело

Решение 2

Аналогично решению 1, за исключением того, что мы не генерируем 160 000 000 за один раз. Вместо этого мы генерируем 1000 каждый раз. Когда эти 1000 записей закончатся, мы создадим еще 1000

проблема

Проблема в том, что иногда пользователь может указать номер. Например, мы генерируем 1000 записей в коллекции, но вместо этого хотим использовать число 5000. Так что это проблема сейчас, потому что мы не генерировали ее

Решение 3

Каждый раз, когда мы создаем объект, мы генерируем случайное число в пределах 1-160 000 000 для этого объекта и сохраняем его в базе данных.

проблема

Трудно избежать того, что сгенерированное вами случайное число не использовалось ранее


python mongodb algorithm
person Kramer Li    schedule 17.01.2017    source источник
comment
Если вы хотите сгенерировать последовательность (псевдо) случайных чисел в диапазоне без повторений, вы можете использовать Linear Конгруэнтный генератор с полным периодом   -  person samgak    schedule 17.01.2017
comment
Если вы не можете повторно использовать номер, похоже, вам придется поддерживать коллекцию использованных вещей, которая в конечном итоге будет состоять как минимум из 159 999 999 вещей.   -  person wwii    schedule 17.01.2017
comment
@samgak можно ли учитывать указанный пользователем номер?   -  person wwii    schedule 17.01.2017
comment
... is too heavy - это относится ко времени или пространству?   -  person wwii    schedule 17.01.2017
comment
@wwii, если указанные пользователем числа составляют небольшую часть от общего числа, их можно сохранить в отдельной таблице, а если они уже использовались, то пропустить это случайное число и использовать следующее (или следующее и т. д.)   -  person samgak    schedule 17.01.2017
comment
@wwii в основном время. Создание коллекции из 160 000 000 записей заняло у меня около 10 минут.   -  person Kramer Li    schedule 17.01.2017

Ответы (1)


arrow_upward
1
arrow_downward

Обычный способ сделать это — иметь счетчик (Sharded) Atomic. Изначально счетчик имеет нулевое значение. Когда есть необходимость в индексе, следует вызвать API, который будет атомарно увеличивать этот счетчик и выдавать его старое значение.

Хотя это, вероятно, будет намного быстрее, чем подходы, которые вы упомянули, это все же может быть недостаточно быстрым в зависимости от ваших потребностей. Узким местом в приведенной выше ситуации является одиночная блокировка, обычно используемая при атомарном приращении. Это не идеально в некоторых распределенных ситуациях.

Использование общих счетчиков:

Обычный способ повысить производительность в таких распределенных сценариях — использовать сегментированные счетчики:

  1. Разделить счетчик (разбить диапазон значений 1..160,000,000 на N непересекающихся диапазонов).
  2. Запустите один и тот же сервис атомарного приращения в N потоках/процессах/сущностях/машинах с N разными блокировками.
  3. Основываясь на некотором свойстве (возможно, адресе объекта или хеше объекта), выберите один из диапазонов (в распределенной системе вы можете использовать распределенное хеширование)
  4. Запросите следующий индекс в соответствующей службе, упомянутой в (2).

Вышеупомянутое повысит производительность в N раз и, вероятно, будет соответствовать потребностям вашего приложения.

По этой ссылке можно прочитать интересную информацию о сегментированных счетчиках.

Обратите внимание: если вы хотите использовать генерацию случайных чисел (Решение 3), вы можете оптимизировать поиск существования ключа, используя Фильтры Блума. Этого может быть достаточно в зависимости от ваших потребностей в производительности.

person user1952500    schedule 17.01.2017