У меня есть элементы базы данных, которым, в дополнение к их первичному ключу, нужен индекс, уникальный для группы, к которой принадлежат элементы.Давайте назовем свойство nbr и свойство, которое группирует элементы и определяет область уникальных nbr: s, которые мы назовем group.Это nbr должно находиться в диапазоне [1-N], а может быть установлено , когда элементы импортируются из внешнего источника.Поскольку все элементы должны иметь nbr, задача состоит в том, как отследить, какие значения используются, чтобы включить возможность выбора бесплатного nbr для новых элементов, которые добавляются вручную.
Я использую DynamoDB и Redis.У меня не может быть индекса DynamoDB на nbr.Идея, которую я имею до сих пор, состоит в том, чтобы использовать Redis для отслеживания того, какие номера были использованы для определенной группы, чтобы для ключа Redis, такого как <MYGROUP>-item-nbrs, я мог хранить все используемые nbr: s и реализовывать логику, чтобы найтиследующий свободный nbr.Отверстия в диапазоне использованных nbr приемлемы, но отверстия должны быть заполнены, прежде чем считать номера исчерпанными.
По сути, я хочу найти неиспользуемые индексы разреженного массива максимального размера N.
Что было бы хорошей структурой для хранения этой информации в Redis для быстрого поиска свободного nbr?Мои идеи на данный момент включают в себя:
Одна строка с разделителями-запятыми всех используемых nbr в отсортированном порядке?Чтобы найти свободный nbr, выдается команда GET, и строка анализируется до тех пор, пока не будет найдено отверстие или конец списка, выбранный номер вставляется в строку, а затем заменяется вся строка.Когда N велико, это кажется очень неэффективным.
Хеш, где каждый используемый nbr хранится как его собственное поле, и используется, например, HSCAN для итерации по полямхеш, чтобы найти свободный nbr.Когда N большое, HSCAN должен сканировать множество полей.
Разделение my nbr: s на поля, называемые, скажем, p1-20, p21-40, p41-60,..., каждый из которых содержит отсортированный набор используемых nbr: s только внутри этого раздела, а когда раздел исчерпан (больше нет свободных nbr: s), удалите его полностью, чтобы ускорить дальнейшую итерацию.Используйте HSCAN для итерации и HSET для запуска нового раздела.
Сохранение всех свободных nbr вместо всех используемых и использование отсортированных наборов и ZPOPMIN или обычных списков и LPOP, возможно разделенныхв подмножества.Предварительно заполнить Redis всеми свободными nbr 1-N кажется некрасивым.
Скажем, N имеет величину 65536.
Есть ли какое-либо решениевыше лучше / хуже, по производительности или по другим причинам?Есть ли лучший / умный способ, возможно, использующий какой-то умный аспект Redis, о котором я не знаю?
Редактировать:
Ответ Кевина привел к следующему решению (псевдокод):
function getFreeNbr() {
while (true) {
send "WATCH numbers"
nbr = send "BITPOS numbers 0"
if nbr < N
send "MULTI"
send "SETBIT numbers $nbr 1"
if send "EXEC" != NULL
return nbr
end if
else
send "UNWATCH numbers"
return -1
end if
}
}