В докладе рассказывается об алгоритмах замещения блоков данных в кэше СУБД. Будет рассказано о том, как можно повысить эффективность работы менеджера буферов СУБД Sedna за счет внедрения более совершенных алгоритмов замещения, какими достоинствами или недостатками обладают одни алгоритмы по сравнению с другими. Также вкратце будут описаны существующие решения в данной области и приведены примеры СУБД, их использующие.
Докладчик: Дмитрий Сиващенко
презентация с семинара (pdf)
Доклад посвящен системе Cassandra — распределенной Key/value СУБД,
специально созданной Facebook для покрытия основных требований этой
наиболее популярной соц. сети: устойчивость к сбоям отдельных
серверов, надежность, быстрота, простота масштабируемости. Будет
рассказано об особенностях архитектуры всей системы в целом, а также о
специфике работы использующихся в системе алгоритмов, обеспечивающих
её быстроту и надежность. В докладе дополнительно будет рассмотрен
принцип работы приложений Facebook с системой Cassandra на примере
Facebook Inbox Search.
Докладчик: Сиващенко Дмитрий
Материалы:
Презентация с семинара (pdf)
В докладе будет рассмотрена распределенная Key/value СУБД на примере Bigtable (google). Основной целью было создание хранилища для использования в сервисах Google быстрого и максимально легко масштабируемого. В докладе описываются требования, которые были поставлены перед разработчиками системы, и рассказывается, как их удалось достичь: чем пожертвовали и на чём сконцентрировали внимание при создании BigTable. Доклад описывает особенности параллелизма системы, представление данных, подход к целостности и доступности (availability) данных. Также будет рассмотрены другие реализации подобного типа хранилищ, что в них было добавлено и как они используются.
Докладчик: Михов Олег
Материалы:
Презентация с семинара (pdf)
Префиксные деревья (tries) и их разновидности являются одними из самых эффективных структур данных для хренения ассоциативных массивов (обычно со строковыми ключами). Некоторые реализации префиксных деревьев (HAT-trie) сравнимы по производительности с хэш-таблицами.
При этом, в отличие от хэш-таблиц, они позволяют поддерживать отношение порядка между ключами, а также быстро получать все ключи по заданному префиксу.
Предлагается реализация разновидности префиксных деревьев для поддержки индексов баз данных в качестве альтернативы B-деревьям. Наиболее похожим типом деревьев является HAT-trie (cache-conscious trie). В данном типе деревьев учитываются особенности хренения данных в СУБД: изменения локальны относительно страниц; используется максимально компактное представление узлов (с целью занять наименьшее количество страниц). Кроме того, в отличие от B-деревьев, в продложенной структуре данных нет ограничений на длину ключа. Основная задача, которая была решена в ходе работы — это разработка эффективного алгоритма разделения страниц (splitting). Этот алгоритм позволяет обеспечивать оптимальное заполнение страниц.
В настоящее время выполняется сравнение прототипной реализации с существующими реализациями B-деревьев, в том числе, с B-деревьями, во внутренних страницах которых данные представлены в виде префиксного дерева.
Докдадчик: Борисенко Олег.
Материалы:
В докладе рассказывается о способах вытеснения блоков БД из буферов основной памяти. В первой части доклада рассказывается об основных подходах к управлению буферами в БД, о классификации алгоритмов вытеснения, о преимуществах и недостатках отдельных алгоритмов. Вторая часть посвящена рассмотрению алгоритмов ARC и CAR, предложенных авторами оригинальной статьи.
Докладчик: Сиващенко Дмитрий.
Материалы:
Презентация с семинара (pdf)