Мне кажется эта задача красиво средствами базы данных не решается.
Любое решение будет либо медленным, либо вероятностное распределение итоговое не будет желаемым.
100 запросов в секунду - зачем такой нетипичной задачей грузить базу данных?
Задайся вопросом, сколько у тебя записей? миллионы? миллиарды? может эффективнее будет держать список id на бакэнде массивом и выбирать от туда?
* Запили миниатюрный сервис с сокетами, в который бакэнд при удалении или добавлении записи будет присылать id, а при перезапуске будет загружать весь список id... памяти это занимать будет порядка 16х от количества записей умножить на логарифм (зависит от того какие списки поддерживает бакэнд, нужно хранить упорядочный num -> id, причем это просто массива, при добавлении id добавляется в конец, а при удалении - на место удаленного ставится элемент с конца, к сожалению тогда для быстрого удаления нужен map: id->num).
* Списков таких должно быть несколько - свой по каждому значению веса (считается что вес - целочисленный и вариантов значений значительно меньше общего количества записей), соответственно каждый id попадает в свой список.
* Каждый раз, как идет запрос на случайный id, считаешь два случайных числа:
- первое на интервале [0..максимальное значение веса) - выбираешь какой вес сейчас сработает
это нужно делать с учетом вероятности, которое соответствует каждому весу, т.е. для каждого веса свой интервал значений случайного числа, для 1 это будет попадание между [0..1), для 2 - [1..3), для 3 - [3..6), для 4 - [6..10),.. макс значение интервала равно сумма арифметической прогрессии 1....N где N максимальное значение веса. Левое значение интервала для n считать по формуле
суммы арифметической прогрессии а правое + значение веса для него.
- второе, [0..максимальное значение num в соответствующем списке)
второе число даст искомый номер в массиве, а значит и id.
* Для значений весов которые не используются (пустые списки id) нужно будет исключать такое число из списка доступных значений весов, делать новый список с меньшим количеством и давать соответствие значений их этого нового списка с меньшим количеством весов и общим, чтобы такие неиспользуемые веса не попадались.
К примеру из весов 1..10 используются только 1,4 и 10, тогда делаем получаем новый список из 3 элементов, но в формуле расчета интервала для вычисления правой границы использовать значение веса, т.е.:
[0..1), [1,5),[5..15) - общий интервал [0..15)
Решение масштабируется до количества нод по максимальному значению веса (своя машина на свой номер веса) - как бы это смешно не звучало.
Решение может использовать детерминированный алгоритм случайного числа (
актуально для гемблинг игр, например в ммрпг принятие решение по выпадению дропа с мобов).
Трудоемкость алгоритма О(1) с очень маленькой константой, но требует память O(n)= n*log(n) с процессором O(n) log(n) на любые модификации.
p.s. Данный алгоритм можно реализовать и в базе данных, на тригерах, так как держать в оперативной памяти списки не требуется, причем базы могут быть отдельные от реальной (очень неудобно и повышенная нагрузка на процессор, лучше использовать key->value базы данных только как хранилище списков id)