|
|
Пишет kouzdra (![[info]](http://lj.rossia.org/img/userinfo.gif){kind=small} kouzdra)@ 2014-02-18 14:39:00 |
 |
|
 |
|
|
|
|
|
|
 |
|
 |
Обещаное по представлению данных
Откровений особенных тут нет, правда относятся imho эти приемчики к разряду "хорошо известных в узких кругах", а мысль что "10 гигабайтную базу данных" нередко можно ужать до структурки в 200-400 метров, помещающейся без напряга в оперативной памяти целиком - и получить совсем другой перформанс и куда более другую алгоритмику, вызывает бывает "разрыв шаблона"*. Я чтобы не разводить теорий просто расскажу что и как тогда было сделано - а творческое осмысление - на откуп читателям.
1. Сразу было решено отказаться от фиксированного размера записей полей etc. Отмечу, что тут была допущена ошибка - на уровне дизайна было встроено ограничение - запись не превышает размер кластера в БД (0.5-8 КB, обычно 2-4, в зависимости от параметров при создании таблицы). Этого почти всегда хватало, но время от времени возникали "записи-исключения".
2. Поля записей устроены были так, что их можно было легко "скипнуть" или "декодировать" узнав размер. Размер записи определялся суммой размеров полей.
3. Блок в таблице был организован как последовательность записей, в начале блока сидело их количество и в зависимости от параметров создания - в начале каждой записи могла сидеть ее длина - для некоторого ускорения доступа. При подгрузке блока в кэш расположение записей в нем индексировалось. При удалении записи "дырка" помечалась маркером.
Идентификатор записи - два числа - номер блока, номер записи в блоке. 3 байта. Больше 256 записей в блоке не допускалось (что как ни смешно тоже оказалось не самым удачным решением - бывали случаи сильно недозаполненных из-за этого блоков.
Представление данных:
1. Числа: разрядность в принципе неограничена, хотя реально с более чем 32 битным библиотека не работала (просто не возникало потребности). Делятся на знаковые и беззнаковые (в основном затем, что поля с отрицательными значениями встречаются не очень часто). Беззнаковые кодировались так: если < 192 - просто одним байтом, если больше - младшие 6 бит в первом байте (в диапазоне 192-255), остальные - по 7 бит в кадом байте, старший бит - маркер конца. Знаковые - аналогично, только один бит в первом байте расходовался под знак.
На практике большая часть чисел вписывалась в 1-2 байта (чаще в 1 причем - почему и было сдвинуто до 192, а не 128 - просто опытный факт - так оно было заметно компактнее).
[Обдумывался еще вариант сделать часть полей "инкрементальными" (по отношению к предыдущему числовому полю - часто они идут с небольшой дельтой), но руки не дошли]
2.Даты - сворачивались в целое знаковое число с нулем емнимп в 1980 году - подбиралось так, чтобы уменьшить вероятность выхода за 2 байта, младший байт всегда содержал все 8 бит, переменная длина начиналась со второго.
3. Единичные символы и булевские - в первом приближении понятно - по байтику (про булевские будет отдельная песня)
4. строки - длина строки (в формате беззнакового целого переменной длины - причем не строки, а блока данных) и данные. Тут начинается легкое извращение: строковые поля могли снабжаться типом упаковки и табличкой упаковки. Варианты следующие:
- упаковки нет
- частотная упаковка - статический Хаффман (сжатие на "обычном" тексте примерно до 60% исходного)
- словарная упаковка 1К или 4К словарем - соответственно 10 или 12 битов на гнездо (cтепень сжатия 30-40% от исходного, для однотипных данных может быть больше). В этом случае имелся способ соспоставления с образцом без декодирования строки, который точно давал негативы, и примерно 1% ложных позитивов (то есть в случае позитива надо было проверять распаковкой)
Соответственно утилита для реорганизации умела в числе прочего пересобрать статистику и перепаковать. На практике где-то в районе 3-5 тыс записей статистика стабилизировалась и дальнейшие перепаковки давали скорее символический эффект. В первом приближении получалось прилично уже на 200-300 записях.
Были "начальные" таблички для русского, английского языков и их смеси - в принципе уже они давали очень хорошее приближение. Так же строка могла представляться индексом в таблице "наиболее частых значений"
Теперь - запись в целом: в начале как уже говорилось, могла идти длина. Поля могли иметь атрибут "имеет значение по умолчанию", соответствующие обычно нулю или пустой строке (хотя в описании таблицы могли быть заданы отличные от умолчательные значения).
После длины записи (если она есть), шла битовая шкала с чистом битов, равным количеству полей, могущих иметь "умолчательные значения". С понятым смыслом - 1 - имеет значение по умолчанию и физически в записи не представлено. Булевские поля с "значением по умолчанию" всегда представлялись только этим битом (0/1).
Основной смысл - в большинстве всяких форм обычно есть куча незаполненных полей и терять на каждое из них даже по байту как-то жаль.
Кроме того, строковые поля еще могли быть снабжены табличкой "наиболее частых значений" - тогда с ними ассоциировался еще один бит в шкале - "есть/нет" и если значение поля попадало в табличку - они кодировались просто индексом в табличке. Опять же - потому что это частый весьма случай, когда 90% полей содержат минимум вариантов значений (например имена/фамилии/отчества). Генерились таблички опять же полуавтоматически - запуском утилиты реорганизации.
Доступ к полям и их модификации был полностью прозрачен - снаружи в С++ запись выглядела как структура с полями, которые можно читать или присваивать (и ее всю аналогично), в блок она коммитилась вызовом метода, название я уже забыл.
При изменении размера записи следующие за ней в блоке передвигались, если запись при этом не влезала в блок - она перекидывалась в конец таблицы, а на ее месте оставлялась пометка об удалении. Идентификатор при этом менялся. То есть идентификатор вообще говоря был внутренним делом и использовать его для ссылок нельзя.
Собственно все. Эффект в среднем получался как я уже говорил - раз в 10 в среднем по всей базе, иногда (например при малозаполненных больших структурах - в 30-40 раз на таблицу).
Про индексы речь отдельным постом.
*) После примерно аналогичного прогруза Юли Л., она попробовала применить на практике в своей америке, когда тамошнее творение для анализа кобольских программ, хранящее данные в SQL проработало 3 дня и так и не досчитало.
После этого была налабана прога на Визуальном Васике по этим заветам только в упрощенном виде нужные части базы были засосаны в ОЗУ (кажется хватило 64 метров) и оно вместе со всем включая импорт в память из базы стало отрабатывать примерно за полчаса.
Откровений особенных тут нет, правда относятся imho эти приемчики к разряду "хорошо известных в узких кругах", а мысль что "10 гигабайтную базу данных" нередко можно ужать до структурки в 200-400 метров, помещающейся без напряга в оперативной памяти целиком - и получить совсем другой перформанс и куда более другую алгоритмику, вызывает бывает "разрыв шаблона"*. Я чтобы не разводить теорий просто расскажу что и как тогда было сделано - а творческое осмысление - на откуп читателям.
1. Сразу было решено отказаться от фиксированного размера записей полей etc. Отмечу, что тут была допущена ошибка - на уровне дизайна было встроено ограничение - запись не превышает размер кластера в БД (0.5-8 КB, обычно 2-4, в зависимости от параметров при создании таблицы). Этого почти всегда хватало, но время от времени возникали "записи-исключения".
2. Поля записей устроены были так, что их можно было легко "скипнуть" или "декодировать" узнав размер. Размер записи определялся суммой размеров полей.
3. Блок в таблице был организован как последовательность записей, в начале блока сидело их количество и в зависимости от параметров создания - в начале каждой записи могла сидеть ее длина - для некоторого ускорения доступа. При подгрузке блока в кэш расположение записей в нем индексировалось. При удалении записи "дырка" помечалась маркером.
Идентификатор записи - два числа - номер блока, номер записи в блоке. 3 байта. Больше 256 записей в блоке не допускалось (что как ни смешно тоже оказалось не самым удачным решением - бывали случаи сильно недозаполненных из-за этого блоков.
Представление данных:
1. Числа: разрядность в принципе неограничена, хотя реально с более чем 32 битным библиотека не работала (просто не возникало потребности). Делятся на знаковые и беззнаковые (в основном затем, что поля с отрицательными значениями встречаются не очень часто). Беззнаковые кодировались так: если < 192 - просто одним байтом, если больше - младшие 6 бит в первом байте (в диапазоне 192-255), остальные - по 7 бит в кадом байте, старший бит - маркер конца. Знаковые - аналогично, только один бит в первом байте расходовался под знак.
На практике большая часть чисел вписывалась в 1-2 байта (чаще в 1 причем - почему и было сдвинуто до 192, а не 128 - просто опытный факт - так оно было заметно компактнее).
[Обдумывался еще вариант сделать часть полей "инкрементальными" (по отношению к предыдущему числовому полю - часто они идут с небольшой дельтой), но руки не дошли]
2.Даты - сворачивались в целое знаковое число с нулем емнимп в 1980 году - подбиралось так, чтобы уменьшить вероятность выхода за 2 байта, младший байт всегда содержал все 8 бит, переменная длина начиналась со второго.
3. Единичные символы и булевские - в первом приближении понятно - по байтику (про булевские будет отдельная песня)
4. строки - длина строки (в формате беззнакового целого переменной длины - причем не строки, а блока данных) и данные. Тут начинается легкое извращение: строковые поля могли снабжаться типом упаковки и табличкой упаковки. Варианты следующие:
- упаковки нет
- частотная упаковка - статический Хаффман (сжатие на "обычном" тексте примерно до 60% исходного)
- словарная упаковка 1К или 4К словарем - соответственно 10 или 12 битов на гнездо (cтепень сжатия 30-40% от исходного, для однотипных данных может быть больше). В этом случае имелся способ соспоставления с образцом без декодирования строки, который точно давал негативы, и примерно 1% ложных позитивов (то есть в случае позитива надо было проверять распаковкой)
Соответственно утилита для реорганизации умела в числе прочего пересобрать статистику и перепаковать. На практике где-то в районе 3-5 тыс записей статистика стабилизировалась и дальнейшие перепаковки давали скорее символический эффект. В первом приближении получалось прилично уже на 200-300 записях.
Были "начальные" таблички для русского, английского языков и их смеси - в принципе уже они давали очень хорошее приближение. Так же строка могла представляться индексом в таблице "наиболее частых значений"
Теперь - запись в целом: в начале как уже говорилось, могла идти длина. Поля могли иметь атрибут "имеет значение по умолчанию", соответствующие обычно нулю или пустой строке (хотя в описании таблицы могли быть заданы отличные от умолчательные значения).
После длины записи (если она есть), шла битовая шкала с чистом битов, равным количеству полей, могущих иметь "умолчательные значения". С понятым смыслом - 1 - имеет значение по умолчанию и физически в записи не представлено. Булевские поля с "значением по умолчанию" всегда представлялись только этим битом (0/1).
Основной смысл - в большинстве всяких форм обычно есть куча незаполненных полей и терять на каждое из них даже по байту как-то жаль.
Кроме того, строковые поля еще могли быть снабжены табличкой "наиболее частых значений" - тогда с ними ассоциировался еще один бит в шкале - "есть/нет" и если значение поля попадало в табличку - они кодировались просто индексом в табличке. Опять же - потому что это частый весьма случай, когда 90% полей содержат минимум вариантов значений (например имена/фамилии/отчества). Генерились таблички опять же полуавтоматически - запуском утилиты реорганизации.
Доступ к полям и их модификации был полностью прозрачен - снаружи в С++ запись выглядела как структура с полями, которые можно читать или присваивать (и ее всю аналогично), в блок она коммитилась вызовом метода, название я уже забыл.
При изменении размера записи следующие за ней в блоке передвигались, если запись при этом не влезала в блок - она перекидывалась в конец таблицы, а на ее месте оставлялась пометка об удалении. Идентификатор при этом менялся. То есть идентификатор вообще говоря был внутренним делом и использовать его для ссылок нельзя.
Собственно все. Эффект в среднем получался как я уже говорил - раз в 10 в среднем по всей базе, иногда (например при малозаполненных больших структурах - в 30-40 раз на таблицу).
Про индексы речь отдельным постом.
*) После примерно аналогичного прогруза Юли Л., она попробовала применить на практике в своей америке, когда тамошнее творение для анализа кобольских программ, хранящее данные в SQL проработало 3 дня и так и не досчитало.
После этого была налабана прога на Визуальном Васике по этим заветам только в упрощенном виде нужные части базы были засосаны в ОЗУ (кажется хватило 64 метров) и оно вместе со всем включая импорт в память из базы стало отрабатывать примерно за полчаса.
