Оптимальное хранение структуры данных для быстрого поиска и сохранения

Question

Сценарий

У меня есть следующие методы:

public void AddItemSecurity(int itemId, int[] userIds)
public int[] GetValidItemIds(int userId)

Изначально я думаю о хранении в форме:

itemId -> userId, userId, userId

и

userId -> itemId, itemId, itemId

AddItemSecurity основано на том, как я получаю данные из стороннего API, GetValidItemIds вот как я хочу использовать его во время выполнения.

Потенциально существует 2000 пользователей и 10 миллионов элементов.Идентификаторы предметов указаны в форме:2007123456, 2010001234 (10 цифр, где первые четыре обозначают год).

AddItemSecurity не обязательно действовать очень быстро, но GetValidIds должно быть субсекундным.Кроме того, если есть обновление существующего itemId Мне нужно удалить этот идентификатор элемента для пользователей, которых больше нет в списке.

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

Если идентификатор элемента начинался с 0, я подумал о создании массива байтов длиной MaxItemId / 8 для каждого пользователя и установите бит true/false, если элемент присутствовал или нет.Это ограничит длину массива чуть более 1 МБ на пользователя и обеспечит быстрый поиск, а также простой способ обновления списка для каждого пользователя.Сохраняя это как Файлы, отображаемые в памяти Я думаю, что с платформой .Net 4 я также получу приличное кэширование (если на машине достаточно оперативной памяти), не реализуя логику кэширования самостоятельно.Решением может быть анализ идентификатора, удаление года и сохранение массива по годам.

Список ItemId -> UserId[] можно сериализовать непосредственно на диск и читать/записывать обычным способом. FileStream чтобы сохранить список и различать его при наличии изменений.

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

Вопрос

Стоит ли мне продолжать пробовать этот подход или есть другие пути, которые также следует изучить?Я думаю, что SQL-сервер не будет работать достаточно быстро и потребует дополнительных затрат (по крайней мере, если он размещен на другом сервере), но мои предположения могут быть ошибочными.Любая мысль или понимание этого вопроса приветствуются.И я хочу попытаться решить эту проблему, не добавляя слишком много оборудования :)

[Обновление 31 марта 2010 г.]

Сейчас я протестировал SQL Server 2008 при следующих условиях.

• Таблица с двумя столбцами (userid,itemid), оба Int
• Кластеризованный индекс по двум столбцам
• Добавлено около 800 000 элементов для 180 пользователей — всего 144 миллиона строк.
• Выделено 4 ГБ оперативной памяти для SQL-сервера.
• Двухъядерный ноутбук с тактовой частотой 2,66 ГГц
• SSD-диск
• Используйте SqlDataReader для чтения всех идентификаторов элементов в список.
• Перебрать всех пользователей

Если я запускаю один поток, он составляет в среднем 0,2 секунды.Когда я добавляю второй поток, оно увеличивается до 0,4 секунды, что все равно нормально.Дальше результаты падают.Добавление третьего потока увеличивает количество запросов до 2 секунд.Четвертый поток — до 4 секунд, пятый — увеличивает продолжительность некоторых запросов до 50 секунд.

Пока это происходит, процессор работает на крышу, даже в одном потоке.Мое тестовое приложение требует некоторого времени из-за быстрого цикла, а остальное — sql.

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

[Обновление 31 марта 2010 г. № 2]

Я провел быстрый тест с теми же данными, поместив их в виде битов в файлы, отображаемые в памяти.Он работает намного лучше.Шесть потоков обеспечивают время доступа от 0,02 до 0,06 с.Чисто по памяти.Сопоставленные файлы были сопоставлены одним процессом, и к ним одновременно обращались шесть других.И так как база sql занимала 4гб, то файлы на диске занимали 23мб.

Answer 1

После долгих испытаний я в итоге стал использовать файлы с отображением в памяти, помечая их разреженным битом (NTFS), используя код из Разреженные файлы NTFS с помощью C#.

В Википедии есть объяснение, что такое разреженный файл является.

Преимущество использования разреженного файла заключается в том, что мне не нужно заботиться о том, в каком диапазоне находятся мои идентификаторы.Если я напишу идентификаторы только между 2006000000 и 2010999999, файл выделит только 625 000 байт со смещением 250 750 000 в файле.Все пространство до этого смещения нераспределено в файловой системе.Каждый идентификатор хранится в виде установленного бита в файле.Вроде как битовый массив.А если последовательность id вдруг изменится, то его выделят в другой части файла.

Чтобы узнать, какие идентификаторы установлены, я могу выполнить вызов ОС, чтобы получить выделенные части разреженного файла, а затем проверить каждый бит в этих последовательностях.Также проверка того, установлен ли конкретный идентификатор, происходит очень быстро.Если он выходит за пределы выделенных блоков, то его там нет, если он попадает внутрь, это просто чтение одного байта и проверка битовой маски, чтобы увидеть, установлен ли правильный бит.

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

И хорошо то, что файлы, отображенные в памяти, также могут использоваться совместно с Java (что оказалось необходимым).Java также поддерживает файлы, отображенные в памяти в Windows, и реализация логики чтения/записи довольно тривиальна.

Answer 2

Я действительно думаю, что вам следует попробовать хорошую базу данных, прежде чем принять решение.Что-то подобное будет непросто поддерживать в долгосрочной перспективе.Ваша база пользователей на самом деле довольно мала.SQL Server должен без проблем обрабатывать то, что вам нужно.

Answer 3

2000 пользователей — это не так уж и плохо, но с 10 миллионами связанных элементов вам действительно стоит подумать о том, чтобы поместить это в базу данных.БД выполняют все функции хранения, персистентности, индексации, кэширования и т. д.что вам нужно, и они работают очень хорошо.

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