четверг, 30 октября 2008 г.

Хранилище записей фиксированной длины

Хранилище записей фиксированной длины (часть II) Случилось вдруг создать такой велосипед, который хранил бы в файле записи фиксированной длины и позволял бы ими оперировать.  Почему бы не воспользоваться базой данных? На самом деле этот велосипед должен предоставлять локальный кэш одной из таблиц центральной БД в системе, в разработке которой я принимаю участие. Требования к нему специфические:
  • производительность, настроенная на чтение-запись отдельных полей записей;
  • доступ только по индексу записи, либо по её ключу (никаких запросов и выборок);
  • отказоустойчивость может быть принесена в жертву (это лишь кэш);
  • размеры файла могут достигать нескольких гигобайт (записи маленькие, но их мно-о-о-ого);
  • доступ к записям производится в случайном порядке (т.е. любое кэширование мало что даст);
Впрочем, это все оправдания. Мне же хотелось показать идею и её реализацию, а точнее прототип кода, адаптированный к блогу.
Организацию хранилища записей я позаимствовал у классов ADO. Таблица - набор записей, у таблицы есть набор колонок, доступ к значению поля записи определен на пересечении таблицы, колонки и записи (точнее ее индекса в таблице).
Отличия от класса DataTable в способе хранения данных. Данные хранятся в физическом потоке (Stream) и доступ к ним осуществляется через классы BinaryReader/BinaryWriter.
Начну, пожалуй, с реализации базового класса нетипизированной колонки. Будут и типизированные, но нетипизированные нужны для складывания их в коллекцию колонок:
public class Column
   {
       private readonly int _offset;
       private readonly int _size;
       private readonly ColumnCollection _columns;

       protected Column(ColumnCollection columns, int offset, int size)
       {
           if (columns == null)
           {
               throw new ArgumentNullException("columns");
           }
           _columns = columns;
           _offset = offset;
           _size = size;
       }

       public int Offset { get { return _offset; } }

       public int Size { get { return _size; } }

       public ColumnCollection Columns { get { return _columns; } }
   }
Здесь все просто. Каждая колонка знает размер значения в байтах, свою коллекцию колонок и смещение относительно начала записи. Все это запоминается в констуркторе колонки. Далее класс типизированной колонки. Типизированная колонка абстрактная, т.к. читать и писать данные придется с помощью BinaryReader/BinaryWriter-а, а они не имеют generic методов для чтения/записи значений.
public abstract class Column<T> : Column
    {
        protected Column(ColumnCollection columns, int offset, int size)
            : base(columns, offset, size)
        {
        }

        public abstract T ReadValue(BinaryReader reader);
        public abstract void WriteValue(BinaryWriter writer, T value);
    }
Типичный класс колонки:
class Int32Column : Column<int>
    {
        public Int32Column(ColumnCollection columns, int offset)
            : base(columns, offset, 4)
        {
        }

        public override int ReadValue(BinaryReader reader)
        {
            return reader.ReadInt32();
        }

        public override void WriteValue(BinaryWriter writer, int value)
        {
            writer.Write(value);
        }
    }
Таких классов несколько, не буду приводить код каждого из них, все они подобны. Немного отличается только класс строковой колонки, но о ней возможно позже. Обратите внимание, что класс типизированной колонки скрытый! Это объясняется тем, что я не собираюсь предоставлять возможность создания колонок сложных типов. Ограничусь лишь некоторыми примитивными. Класс коллекции колонок содержит в себе список колонок и число байт, требуемое для записи данных во всех колонках.
public class ColumnCollection
    {
        private readonly List<Column> _columns = new List<Column>();
        private int _size;

        public Column<int> AddInt32Column()
        {
            return AddInt32Column(this.Size);
        }

        public Column<int> AddInt32Column(int offset)
        {
            return AddColumn(new Int32Column(this, offset));
        }

        private Column<T> AddColumn<T>(Column<T> column)
        {
            _size = Math.Max(_size, column.Offset + column.Size);
            _columns.Add(column);
            return column;
        }

        public int Size { get { return _size; } }
    }
Коллекция колонок является так же производящим классом для типизированных колонок. Для каждого типа колонки (а их у меня чуть больше, чем только Int32Column) определено два метода создания экземпляра колонки: первый метод добавляет колонку в конец записи (указывает Offset, равный текущему размеру коллекции колонок в байтах), а второй - позволяет указать Offset вручную. Это потребуется для так называемых union полей.

Вот что из себя представляет базовый тип хранилища:
public abstract class StreamStorage
    {
        public abstract T ReadValue<T>(Column<T> column, int rowIndex);
        public abstract void WriteValue<T>(Column<T> column, int rowIndex, T value);
    }
Всего лишь два абстрактных метода, позволяющий писать и читать значения, соответствующие указанным колонкам и индексу записи. Этот базовый тип нужен для объявления базового типа записи. Хотел я параметризовать тип записи типом хранилища и тип хранилища типом записи, и возможно смог бы это сделать, но меня посетила идея, что у файла должен быть заголовок. И что заголовок - это второй тип записи. Т.е. хранилище надо параметризовывать двумя типами записи, но тогда каждую запись надо будет параметризовывать типом хранилища, в котором 2 типа записи... Но это все лишнее. Записи от хранилища не нужно ничего, кроме возможности обратиться к вышеуказанным методам. Потому базовый тип хранилища не имеет generic параметров. А базовый тип записи имеет generic параметр - конкретный тип записи:
public class RowBase<TRow>
        where TRow : RowBase<TRow>
    {
        private static readonly ColumnCollection s_columns = new ColumnCollection();
        public static ColumnCollection ColumnCollection { get { return s_columns; } }

        private readonly int _index;
        private readonly StreamStorage _storage;

        protected RowBase(StreamStorage storage, int index)
        {
            _storage = storage;
            _index = index;
        }

        public virtual void Initialize()
        {
        }

        public int GetIndex()
        {
            return _index;
        }

        public StreamStorage GetStorage()
        {
            return _storage;
        }

        protected T ReadValue<T>(Column<T> column)
        {
            return _storage.ReadValue(column, GetIndex());
        }

        protected void WriteValue<T>(Column<T> column, T value)
        {
            _storage.WriteValue(column, GetIndex(), value);
        }
    }
Базовый класс записи со спецификацией типа (т.е. все записи одного типа) привязаны к одному экземпляру коллекции колонок. Сделано это лишь для проверок. Для работоспособности хранилища интересен лишь размер записи, который определен в коллекции колонок и смещения самих колонок относительно записи. Но хранилище так же будет знать экземпляр коллекции колонок для проверки экземпляров колонок, которые приходят на публичные методы чтения и записи значений. Базовый класс записи содержит в себе ссылку на экземпляр хранилища, свой индекс, и определяет защищенные методы для чтения и записи значений.

Надеюсь, что код конкретной записи прояснит все что не ясно:
public class TestRow : RowBase<TestRow>
    {
        private static readonly Column<Guid> s_GuidColumn = ColumnCollection.AddGuidColumn();
        private static readonly Column<int> s_Int32Column = ColumnCollection.AddInt32Column();

        public TestRow(StreamStorage storage, int index)
            : base(storage, index)
        {
        }

        public Guid GuidValue
        {
            get { return ReadValue(s_GuidColumn); }
            set { WriteValue(s_GuidColumn , value); }
        }

        public int Int32Value
        {
            get { return ReadValue(s_Int32Column); }
            set { WriteValue(s_Int32Column, value); }
        }

        public override void Initialize()
        {
            base.Initialize();
            GuidValue = Guid.NewGuid();
            Int32Value = 0;
        }
    }
Итак, тип конкретной записи определяет колонки (статические поля), которые создает обращаясь к статической коллекции колонок, определенной у базового типа записи. Тип конкретной записи определяет свойства экземпляра записи. Реализация каждого свойства обращается к базовым методам чтения/записи значения и передает соответствующий экземпляр колонки. При обращении к свойству записи происходит передача колонки и номера записи хранилищу и вызывается метод чтения либо записи значения из хранилища.

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

4 комментария:

  1. Хмммм, а как же SQLite? Именно для этих целей она и предназначена.

    Неплохая статейка:
    http://www.mikeduncan.com/sqlite-on-dotnet-in-3-mins/

    Только там небольшая ошибка: DataSource в коннекшин стринге пишется с пробелом “Data Source=C:CheckoutWorldDominator.s3db”

    СУВ, Aikin

    ОтветитьУдалить
  2. Спасибо за ссылку. Про SQLite наслышан, но дела не имел.

    SQLite - хорошо, но нам нужен был именно двоичный файл с прямым объектным доступом к полям записей.

    Будет время - устрою сравнительный стесс тест.

    ОтветитьУдалить
  3. База в SQLite -- имменно двоичный файл. Не знаю что ты имеешь ввиду под "объектным доступом", но для Лайта есть ADO провайдер. Накрутить над ней SomeObjectDao не составит труда.

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

    В общем, советую посмотреть ;-)

    ОтветитьУдалить
  4. aikin>База в SQLite -- имменно двоичный файл. Не знаю что ты имеешь ввиду под "объектным доступом", но для Лайта есть ADO провайдер. Накрутить над ней SomeObjectDao не составит труда.

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

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

    Обязательно напишу. Спасибо за проявленный интерес :)

    aikin>В общем, советую посмотреть ;-)

    Обязательно посмотрю. Для других задач - то что доктор прописал!

    ОтветитьУдалить