Индустриальные базы знаний
Темой семинара не будут самые большие или самые быстрые или самые «умные» базы знаний. Их вы без труда найдёте в списках «top ten» того и «top ten» этого, вот только вряд ли будете использовать в реальной жизни. Дело даже не в цене этих «самых-самых», дело в принципах принятия решения о внедрении. Во-первых, критериев выбора очень много, как бы не больше, чем систем на рынке, и достижение рекордного значения одной характеристики чисто статистически сузит выбор по всем остальным. Во-вторых, параметры возможных решений взаимосвязаны, часто зависимость обратная и рекорд по одному параметру оборачивается неизбежным провалом по другому. Поэтому речь пойдёт не о лучших из лучших, а о лучших из средних. О самых востребованных индустрией.
Для прогулявших предыдущий семинар по этой теме — два слова о самом понятии «база знаний».
Системы хранения знаний становятся всё более обыденной частью инфраструктуры. Причин две. Число разнообразных узкоспециальных систем выросло до той степени, при которой цена традиционных методов интеграции этих систем стала неприлично большой. В то же время потребность в объединении данных из разных систем продолжает расти. В науке объём междисциплинарных исследований растёт, и будет расти впредь. В бизнесе растут требования к системам управления и к скорости принятия решений. В индустрии развлечений требуется всё тщательней учитывать вкусы клиента, чтобы угодить им наилучшим образом. Как результат, если по старинке на каждую задачку по интеграции данных писать свою программулину, то не хватит ни специалистов, ни денег.
В традиционных СУБД для каждого приложения создаётся своя схема хранения данных, например свой набор таблиц, и в этой схеме строго определённым образом хранятся данные об объектах нескольких строго описанных видов. Так можно получить хорошую производительность ценой заметных дополнительных затрат на программирование — каждое приложение требует своей схемы. В «чистой» базе знаний схема хранения одна на все случаи жизни, а данные в неё можно запихать любые. В том числе можно запихать и описание самих данных, взаимосвязей между ними. А взаимосвязанные данные называются уже по другому — знания. И проку от них больше, и программные средства для их обработки отличаются универсальностью, а следовательно и дешевизной.
Это была бочка мёда.
Теперь бочка дёгтя: на обычной нагрузке база знаний медленнее базы данных.
В таблицах http://www4.wiwiss.fu-berlin.de/bizer/BerlinSPARQLBenchmark/results/index.html#multiResults хорошо видно, как OpenLink Virtuoso в роли базы знаний проигрывает по скорости в тридцать раз самой себе в роли классической реляционной СУБД.
Выходом являются гибридные системы, которые за фасадом базы знаний прячут как универсальное хранилище фактов, так и специализированные базы данных. В таком виде разрыв в скорости удаётся сократить до трёх-шести раз, а при правильной формулировке запросов — часто и до десятков процентов. Более того, если база знаний ставится рядом с уже имеющимися базами данных, то эти базы могут продолжать работать без изменений, это резко снижает издержки и риски.
Обратите внимание, что база знаний оказывается центром, предоставляющим очень разнообразные сервисы, и работает в среде, в которой каждый агент тянет одеяло на себя. Наивно надеяться, что всё это окружение подстроится под базу знаний, в лучшем случае админ исправит грубые ошибки конфигурации. И более того, «за время пути собака могла подрасти».
В часовой лекции при всём желании не описать все кубики и стрелочки диаграммы, хотя бы в общих чертах описывающей внутренности современной индустриальной СУБД. Вместо этого я постараюсь рассказать, как правильно выбрать базу знаний для своего проекта и сценарии её использования, на что смотреть, какие есть проблемы и какими методами они решаются.
Перед тем, как рассказывать именно о базах знаний, кратко изложу учебник по многокритериальной оптимизации в условиях неопределённости. «Многокритериальной оптимизации» — потому что мы хотим всего хорошего сразу, и как можно побольше. А «в условиях неопределённости»... Знаете, для архитектора большой корпоративной системы выбор базы для проекта уступает по важности только решению на ком жениться. При этом сравнимы не только срок действия решения и цена его изменения, но и неопределённость будущего. Жизнь — она длинная, и обстоятельства будут меняться.
Сначала термины.
Каждая система описывается многомерным пространством состояний. Скажем, состояние подъёмного крана можно описать массой груза на крюке, вылетом по горизонтали, высотой и т.п. При работе кран более-менее произвольно и многократно и обратимо переходит из одного допустимого состояния в другое, либо однократно и необратимо переходит в какое-то недопустимое состояние, скажем, «упал» или «сгорел». Допустимые состояния обычно образуют замкнутую и ограниченную область, и мы будет так подбирать и «оцифровывать» параметры, чтобы начало координат описывало некоторое «начальное» допустимое состояние и все параметры всегда были неотрицательными. Для проблем выбора достаточно исследовать границу этой области. Если я могу поднять груз в центнер, то излишне проверять, могу ли я поднять полцентнера — непременно подниму. Если на меня положить тонну, то я перейду в недопустимое состояние, добавочная тонна ситуацию не улучшит. Значит, при данных условиях искомая граница лежит где-то между центнером и тонной.
Для некоторой данной системы, исследуемая граница области будет непрерывной N-1 мерной поверхностью в N-мерном пространстве и будет ограничивать некоторый огрызок N-мерного параллепипеда с углом в нуле. Несколько систем на рынке — несколько огрызков более-менее похожей формы. В рекламе обычно приводят габариты этого параллепипеда, без подробностей.
Вот серийно выпускающееся чудо света — кран К-10000. Он может поднять до 200 тонн. Его стрела имеет вылет 100 метров. Он может поднимать груз со скоростью два метра в секунду. Им может управлять даже неопытный крановщик. Вот только полезный для клиента объём огрызка куда меньше объёма рекламируемого параллепипеда. Со скоростью два метра в секунду можно поднимать только лёгкий груз. 200 тонн можно поднять только строго на середине стрелы, в остальных её точках — не больше 100 тонн. Поднимать эти 200 тонн прилетит эксперт из Дании.
Занудное отступление.
Крайние значения параметров обычно связаны несложными уравнениями, поэтому сечения огрызка плоскостями обычно имеют относительно простую и предсказуемую форму, особенно сечения координатными плоскостями и параллельными им.
Случай первый, хороший: граница выпуклая вверх. Так бывает, когда параметры связаны системой линейных неравенств. Скажем, каждый паром имеет площадь палуб столько-то квадратных метров и может нести груз в столько-то тонн. Покупатель выбирает паром исходя из ожидаемой пропорции грузовиков и легковых машин и возможных цен на перевозку. Небольшая неопределённость в этой пропорции не приводит к совсем уж неверным решениям, а продавец старается для каждой цены предложить большое число вариантов. Для оптимизации достаточно симплекс-метода.
Случай второй, плохой: граница выпуклая вниз. Так бывает, когда произведение параметров ограничено. Скажем, произведение поднимаемой краном массы на скорость подъёма ограничено мощностью привода. Целевая функция покупателя при этом часто тоже нелинейна, поэтому он может крупно ошибиться. В случае крана — поднимать бетон часто и понемногу или медленно и большой бадьёй? В случае базы данных — делать много маленьких контрольных точек или мало но продолжительных? Максимум, чем может помочь продавец — избежать внезапных необъяснимых провалов в производительности, сделать границу как можно более гладкой, чтобы облегчить покупателю муки выбора. В отсутствие у большинства пользователей достаточно грамотных администраторов правильным решением является автоматическое конфигурирование базы данных, с минимальным числом задаваемых вручную параметров. Даже если оно слегка промахивается с настройкой, оно снижает риск того, что пользователь промахнётся по-крупному.
Случаё третий, самый плохой: граница произвольной формы. Большая цена ошибки и при этом нет возможности просчитать характеристики заранее. Могу «обрадовать»: для характеристик баз знаний характерен как раз третий случай.
Для оценки применимости базы знаний для конкретной нагрузки надо учесть очень много связанных параметров. Максимум, на что способен покупатель — экспериментально проверить, пролазят ли в ограничения данной системы на данном оборудовании несколько его простеньких случаев. Ещё он может почитать мнения окружающих.
Но чаще всего покупатель просто ищет подходящие бенчмарки. Благодаря таким лентяям бенчмарки становятся настоящим двигателем индустрии. Если я выбираю базу знаний, и нагрузка моей системы похожа на нагрузку, создаваемую прогоном бенчмарки, и прогон показывает хорошую скорость, то вдруг и моя система будет работать хорошо? Ведь есть же какая-никакая корреляция? И даже если её нет, то у меня будет замечательное оправдание перед начальником. Решение принято, и вот ещё один стартап начинает путь через тернии к банкротству.
Какова же правильная стратегия умного покупателя? Она очень проста. Спросить производителя! Это один из немногих случаев, когда лучше верить совершенно предвзятому производителю и продавцу, чем спрашивать других покупателей. Покупателей надо спрашивать о другом — о качестве поддержки, удобстве и полноте документации, багах... обо всём, кроме основной функциональности. Программиста спрашивайте о программе, покупателей спрашивайте о программном продукте, и смотрите не перепутайте!
Итак, умные покупатели задают разработчику вопрос за вопросом. Разработчик в отличие от них хорошо представляет себе форму «огрызка от параллепипеда», и знает, какие проблемы приводят к какой выемке в огрызке, и в первую очередь занимается теми проблемами, которые проще всего решить и которые при этом заметнее всего пользователям. Прямо идиллическая картинка, если только пользователь знает, что именно спрашивать. Давайте этому учиться на примере Linking Open Data Project, хотя бы по той причине, что те или иные данные из него понадобятся в любой крупной работе. А перед этим ограничим полёт нашей фантазии условиями, характерными для нашей академии.
Условие первое. Абсолютно необходимо, чтобы система стоила мало, обрабатывала много, обслуживалась раз в неделю ленивым студентом и при этом жужжала одна на весь институт, потому как на вторую денег уж точно не будет. Поэтому отсутствие квалифицированого администрирования считаем неизбежным, и это не должно приводить к фатальным потерям данных. Поэтому система должна работать на «комодах», т.е. на серверах, собранных в домашних условиях из недорогих железяк. Диски — SATA, планки памяти — относительно дешёвые, процессоры — не самые быстрые, межмашинные соединения — порты Gigabit Ethernet на материнской плате.
Условие второе. Абсолютно необходимо, чтобы система могла быть использована в учебных целях. Поэтому требуется более-менее полная и корректная поддержка стандартов W3C, а не только неких жаргонов.
Возможная активность базы.
Хоть для базы данных, хоть для базы знаний есть четыре основных вида нагрузки: пакетная загрузка, OLTP, интерактивные выборки, сложная аналитика. Для каждого из этих видов есть трюки, уменьшающие эффективность на других видах.
Пакетная загрузка хорошо идёт в монопольном режиме, но на время этого режима вся остальная нагрузка вообще отбрасывается.
OLTP может выиграть от буферизации свежих транзакций в отдельном маленьком хранилище, но все остальные нагрузки страдают от того, что каждый факт приходится искать в двух местах — в «новостях» и в стабильной части данных. Разработчики BigOWLIM рискнули сделать это и не прогадали, они действительно получили производительное масштабируемое хранилище с бессмертностью версий. Одна беда — они могут хранить только чистый RDF, и этим большим красивым микроскопом не очень удобно будет забивать наши маленькие гвоздики.
Интерактивные выборки выигрывают от материализованных видов, но ровно до тех пор, пока данные не начинают регулярно обновляться. Этот трюк не для колхозных исследовательских работ, должен предупредить. Во время тестирования всё с большой вероятностью работает, в реальной обстановке оно продолжает работать только у очень квалифицированной бригады и то только в тщательно спроектированных случаях. Oracle обоснованно любит эту технику (MJV, SPMJV), так как обоснованно предполагает наличие у покупателей денег на хороших админов. На диаграммах базы данных стандартно изображают в виде эдаких консервных банок. Это дезинформация. Правильный символ — сливной бачок, в который что-то понемножку всё время капает, что-то сочится из него, а ещё иногда юзер нажимает на большую кнопку. Материализованные виды отлично работают с замороженными данными, но вы вряд ли хотите заморозить весь бачок целиком или же тщательно его администрировать.
Сложная аналитика отличается особыми аппетитами: ей бы и монопольный режим не помешал, и материализованные виды и распараллеливание больших произведений на множество нитей. Придётся немного жертвовать производительностью и обойтись без монопольного режима. Материализованные виды достаточно успешно заменяются обычными временными таблицами, за которые целиком отвечает SQL-оптимизатор и которые поэтому не требуют ручного управления.
Вместо безуспешного поиска универсального решения, для исследовательского проекта можно пойти на компромисс с удобством и разные нагрузки просто разнести по времени. Пакетные загрузки будем планировать на ночь. Аналитику по возможности будем делать в те моменты, когда нет клиентов с OLTP. OLTP, в свою очередь, и планировать особо не надо, мы же делаем не банк и не магазин, это будет ежесекундной нагрузкой только в задачах симуляции.
Тут надо сделать важное предупреждение. Я работаю в компании OpenLink, в бригаде, которая выпускает OpenLink Virtuoso. И вот как раз OpenLink Virtuoso я и предлагаю на роль самого подходящего решения для описываемой нагрузки в заданных условиях. Основание для этого кажется простым и правдоподобным — раз большая часть инфраструктуры Linking Open Data успешно держится на Virtuoso, то и ещё один проект заработает. Однако я не просто «могу быть предвзят», я просто гарантированно предвзят, поэтому если вы начнёте свой проект — выбирайте платформу сами.
OpenLink Virtuoso поставляется в нескольких версиях. Бесплатная версия делает почти всё то же, что и стандартная платная, единственное исключение — в ней нет виртуальной схемы. Для большинства приложений это и не требуется, так как готовых традиционных баз данных просто нет. Ещё есть версия с поддержкой кластеров, но это выходит за рамки вводного семинара.
Теперь посмотрим повнимательней на функциональность Virtuoso и постараемся подобрать правильные варианты её использования.
Самые видные интерфейсы Virtuoso как базы знаний, конечно же, ODBC и SPARQL web service протокол. ODBC изначально предназначен для SQL, но Virtuoso поддерживает и выполнение SPARQL запросов через ODBC. В ODBC меньше накладные расходы в случае локальной сети, но чуть больше суммарная латентность в случае сети глобальной. В общем случае используйте то, что удобнее для клиента, да и всё.
Часто клиент отправляет на сервер однотипные вопросы, отличающиеся только некоторыми параметрами. Например, географическое приложение может последовательно запрашивать сведения о промышленности разных городов. ODBC позволяет передать каждый такой запрос двумя способами, существенно разными с точки зрения компилятора. Можно передать строку запроса с впечатанным в неё названием или иным идентификатором города. Запрос будет откомпилирован и только затем исполнен. Можно передать строку запроса с впечатанным в неё именем параметра, и отдельно передать фактическое значение этого параметра. Тогда запрос будет откомпилирован только однажды, перед первым исполнением, а потом результат компиляции будет мгновенно браться из кэша. Казалось бы, зачем при такой очевидной разнице в скорости вообще нужен вариант со впечатыванием параметров в строку запроса? Когда компилятор видит точную константу (скажем, имя города), он может быстро посмотреть статистику по числу фактов, связанных с этой константой. Если двум разным значениям параметра соответствуют существенно разные количества фактов, а база достаточно велика, то оптимальные планы выполнения этих двух запросом могут отличаться порядком действий, и выигрыш от более точного выбора этого порядка может перевесить добавочные затраты на компиляцию. Ещё важнее случай, когда компилятор по конкретному значению URI может узнать в какой именно таблице содержатся данные, относящиеся к этому URI, а в случае параметра вынужден генерировать избыточный код. Вам придётся ставить свои эксперименты, чтобы выбрать подходящий стиль запросов, тем более что могут быть и промежуточные варианты. Скажем, приложение ищет все болты, подходящие к данной гайке, либо все гайки, подходящие к данному болту, и запрос имеет два параметра — тип данной детали и её обозначение. Самым эффективным вполне может оказаться компромиссный вариант — тип впечатать, а обозначение — передать как параметр.
Но это был простой вопрос для разминки. Интереснее решить, что делать с логическим выводом. Virtuoso обеспечивает весьма скромную поддержку sameAs, subType, subProperty, обратных и транзитивных свойств, и их использование существенно замедляет работу. Не стоит ли вдобавок к оригинальным фактам сохранять однажды выведенные добавочные факты? Универсального ответа разумеется, дать невозможно. Тем не менее, почти универсальный ответ — не стоит, по тем же причинам, по которым не стоит пробовать классические материализованные виды. Разумеется, у разработчика может не быть выбора, если ему нужен логический вывод более мощный, чем встроенная поддержка. К счастью, такое пока случается достаточно редко, потому что разработчики боятся лезть в дебри. Отпугивает как недостаточно высокий средний уровень разработчиков, так и неготовность инструментальных средств. Этой зимой мы на семинаре по Fact++ попробовали решить задачу Эйнштейна, и быстро убедились, что даже лучшие имеющиеся средства вывода всё ещё остаются экспериментальными и нуждаются в существенном улучшении. Выходит, и здесь лучшим вариантом стал компромисс.
Есть ещё проблема обеспечения конфиденциальности, в виде достаточно непривычном для разработчиков, имеющих опыт работы с реляционными базами данных. В реляционных базах каждое приложение работает со своими таблицами, и пользователь, имеющий право пользоваться приложением обычно просто получает доступ к нескольким таблицам этого приложения. Изредка пользователь имеет право доступа только к некоторым строкам какой-то таблицы, но это ограничение обычно поддерживается на уровне приложения, а на уровне ядра оно задействуется только в исключительных случаях. Раз так — производительность row-level security никого особо не волновала. В случае базы знаний все факты лежат в одной таблице. Проверка права доступа к каждому отдельному факту убила бы производительность. Разумным компромиссом стал контроль доступа на уровне графов graph-level security, хотя и с ним хватило проблем. В случае реляционной базы данных каждое приложение хотя бы знает список своих таблиц, в то время как в базе знаний новые графы появляются регулярно и непредсказуемо. Следовательно для графов, не существовавших на момент настройки системы безопасности, должны быть заранее предусмотрены некоторые правила доступа по умолчанию. И эти правила должны быть описаны как для существующих, так и для создаваемых в будущем пользователей. Проблему облегчило введение понятия публичных и приватных графов. Прежде чем проверять права доступа к конкретному графу, проверяется принадлежность графа к одной из этих двух групп и право доступа пользователя к целой группе по умолчанию. Если прав достаточно, дальнейшая проверка не требуется. Мало того, что конфигурирование доступа перестало быть проблемой, так ещё и проверка стала зачастую выполняться статически во время компиляции запроса.
Таких проблем десятки, большая их часть слишком сложна для втискивания в короткую лекцию, но очень часто повторяется один и тот же сценарий: когда разработчик делает некоторую новую функциональность, он умышленно делает её «несовершенной» ради улучшений характеристик в некотором среднем случае. Он выгибает границу применимости вверх.
—-
(Это материалы к моему докладу на семинаре ИСИ СО РАН 25 марта 2010. Фактически часть его не была озвучена в аудитории из-за большого количества вопросов, обсуждение темы растянулось на день. Семинар начался в полдесятого и закончился в одиннадцать, а кофе мы потом пили до трёх.)
| Иван Николаевич Михайлов | |
| Ivan Mikhailov | |
| Род деятельности: |
программирование |
|---|---|
| Роль участника: | |
| Основной раздел: | |
| Гражданство: | |
| Сайт: | |
| Nickname | |
