Получите быстрый произвольный доступ к двоичным файлам, но также последовательный при необходимости. Как сделать макет?

Question

У меня есть около 1 миллиарда наборов данных, имеющих DatasetKey, и каждый из них содержит от 1 до 50 000 000 дочерних записей (некоторые объекты), в среднем это около 100, но есть много жирных хвостов.

Как только данныезаписано, обновление данных не производится, только чтение.

Мне нужно прочитать данные по DatasetKey и одно из следующего:
Получить количество дочерних записей
Получить первые 1000 дочерних записей(не более 1000)
Получить первые 5000 дочерних записей (не более 5000)
Получить первые 100000 дочерних записей (не более 100000)
Получить все дочерние записи

Каждая дочерняя запись имеет размер около 20 байт до 2 КБ (в среднем 450 байт).

Мой макет, который я хочу использовать, будет следующим:

Я создаю файл размером вне менее 5 МБ.
Каждый файл содержит как минимум один ключ DatasetKey, но если размер файла все еще меньше 5 МБ, я добавляю новые ключи DatasetKeys (с дочерними записями) до тех пор, пока не превышаю 5 МБ.какой файл-смещениеs Я найду, какие данные.
Далее я планирую хранить сериализованные пакеты с использованием буферов протокола.
Один пакет для первых 1000 записей,
один для следующих 4000 записей,
один дляследующие 95000 записей,
один для следующих оставшихся записей.

Я храню размеры файлов в ОЗУ (при сохранении всех заголовков требуется много ОЗУ, необходимого на машине, которую я использую).Когда мне нужно получить доступ к определенному ключу Dataset, я смотрю в оперативной памяти, какой файл мне нужен.Затем я получаю размер файла из оперативной памяти.Когда размер файла составляет около 5 МБ или меньше, я буду читать весь файл в память и обрабатывать его.Если это больше, чем 5 МБ, я буду читать только первый xKB, чтобы получить заголовок.Затем я загружаю нужную позицию с диска.

Как это звучит?Это полная чушь?Или хороший путь?

Используя этот дизайн, я имел в виду следующее:

Я хочу хранить свои данные в собственном двоичном файле, а не в базе данных, чтобы упростить резервное копирование иобрабатывать файлы в будущем.
Я бы использовал postgresql, но я решил, что хранение двоичных данных заставит postgresqls-toast выполнить более одного обращения к данным.
Хранение одного файла для каждого DatasetKey требует слишком много временидля записи всех значений на диск.
Данные рассчитываются в ОЗУ (поскольку не все данные помещаются одновременно в ОЗУ, они рассчитываются по блокам).
Размер файла 5 МБ - только приблизительная оценка.

Что ты скажешь?Заранее благодарю за помощь!

edit

Дополнительная справочная информация:

DatasetKey имеет тип ulong.

Дочерняя запись (есть разные типы) в большинстве случаев выглядит следующим образом:

public struct ChildDataSet
{
    public string Val1;
    public string Val2;
    public byte Val3;
    public long Val4;
}

Я не могу сказать, к каким именно данным обращаются.Планируется, что пользователи получат доступ к первым 1000, 5000, 100000 или всем данным определенных DatasetKeys.Исходя из их настроек.

Я хочу сохранить как можно меньшее время отклика и использовать как можно меньше дискового пространства.

@ Что касается произвольного доступа (вопрос Марка Гравелса):

Мне не нужен доступ к элементу №.123456 для конкретного ключа данных.

При хранении более одного DatasetKey (с дочерними записями) в одном файле (так, как я его разработал, чтобы не создавать много файлов), мне необходим произвольный доступ к первым 1000 записям определенного DatasetKey.в этом файле или в первых 5000 (так что я прочитал бы пакет 1000 и 4000).

Мне нужен только доступ к следующему, касающемуся одного конкретного DatasetKey (uint):
1000 дочерних записей (иливсе дочерние записи, если меньше 1000)
5000 дочерних записей (или все дочерние записи, если меньше 5000)
100000 дочерних записей (или все дочерние записи, если меньше 100000)
все дочерние записи

Все остальные вещи, о которых я упоминал, когда у меня пробовал только дизайн: -)

РЕДАКТИРОВАТЬ, потоковая передача для одного списка в классе?

public class ChildDataSet
{
    [ProtoMember(1)]
    public List<Class1> Val1;
    [ProtoMember(2)]
    public List<Class2> Val2;
    [ProtoMember(3)]
    public List<Class3> Val3;
}

Можно ли выполнить потоковую передачу для Val1, например, получить первые 5000 записей Val1

Answer 1

Перейти с одним файлом. В начале файла сохраните сопоставление идентификатора со смещением. Предполагая, что ваше пространство идентификаторов невелико, сохраните массив пар ID + смещение, отсортированных по идентификатору. Используйте бинарный поиск, чтобы найти правильную запись. Примерно log (n / K) ищет, где «K» - это количество пар ID + смещение, которые вы можете сохранить на одном блоке диска (хотя ОС может потребоваться дополнительный дополнительный поиск или два для поиска каждого блок).

Если вы хотите потратить немного памяти для уменьшения количества обращений к диску, сохраняйте отсортированный в памяти массив каждого 10-тысячного идентификатора. При поиске идентификатора найдите ближайший идентификатор, не переходя. Это даст вам диапазон в 10000 ID в заголовке, по которому вы сможете выполнить бинарный поиск. Вы можете очень точно увеличить / уменьшить объем используемой памяти, увеличив / уменьшив количество ключей в таблице в памяти.

Плотное пространство идентификаторов : Но все это совершенно не нужно, если ваше пространство идентификаторов относительно плотное, что может показаться, поскольку у вас есть 1 миллиард идентификаторов из общего возможного ~ 4 миллиардов (при условии uint - это 32 бита).

Метод сортированного массива, описанный выше, требует сохранения идентификатора + смещение для 1 миллиарда идентификаторов. Предполагая, что смещения составляют 8 байтов, это требует 12 ГБ в заголовке файла. Если бы вы использовали прямой массив смещений, для этого потребовалось бы 32 ГБ в заголовке файла, но теперь только один поиск диска (плюс поиск ОС) и никакой таблицы поиска в памяти.

Если 32 ГБ - это слишком много, вы можете использовать гибридную схему, где вы используете массив на первых 16 или 24 битах и ​​используете отсортированный массив для последних 16 или 8. Если у вас есть несколько уровней массивов, то вы в основном есть три (как кто-то еще предложил).

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

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

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

Answer 2

Фокус, кажется, на первых n элементах; в этом случае protobuf-net идеален. Позвольте мне продемонстрировать:

using System;
using System.IO;
using System.Linq;
using ProtoBuf;


class Program
{
    static void Main()
    {
        // invent some data
        using (var file = File.Create("data.bin"))
        {
            var rand = new Random(12346);
            for (int i = 0; i < 100000; i++)
            {
                // nothing special about these numbers other than convenience
                var next = new MyData { Foo = i, Bar = rand.NextDouble() };

                Serializer.SerializeWithLengthPrefix(file, next, PrefixStyle.Base128, Serializer.ListItemTag);
            }
        }
        // read it back
        using (var file = File.OpenRead("data.bin"))
        {
            MyData last = null;
            double sum = 0;
            foreach (var item in Serializer.DeserializeItems<MyData>(file, PrefixStyle.Base128, Serializer.ListItemTag)
                .Take(4000))
            {
                last = item;
                sum += item.Foo; // why not?
            }
            Console.WriteLine(last.Foo);
            Console.WriteLine(sum);
        }
    }
}
 [ProtoContract]
class MyData
{
     [ProtoMember(1)]
     public int Foo { get; set; }
     [ProtoMember(2)]
     public double Bar { get; set; }
}

В частности, поскольку DeserializeItems<T> является потоковым API, легко получить ограниченное количество данных с помощью LINQ Take (или просто foreach с break).

Обратите внимание, что существующая публичная библиотека не будет любить вас за использование struct; v2 там лучше, но лично я бы сделал это class.

Answer 3

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

Создайте некоторые настройки для:

• Оригинальный размер файла
• Отдельные заголовки файлов
• Стратегия кеширования (сколько и что в памяти)

Answer 4

Почему бы не попробовать Отображенные в память файлы или SQL с FileStream ?