Вы еще не сохраняете десятки миллионов событий в день? К вам еще не забегают менеджеры с кричащим вопросом — когда твой дорогущий кластер на «надцати» машинах посчитает агрегированную статистику по продажам за неделю (а в глазах читается: «чувак, ребята на php/python/ruby/go решают задачу за час, а ты со своей Бигдатой тянешь время днями, доколе?»)? Вы еще не вскидываетесь ночью в холодном поту от кошмара: «разверзлось небо и на вас, ваших коллег и весь нафиг город вывалилось огромная куча… Бигдаты и никто не знает, что с этим всем теперь делать»? :-)
Есть еще интересный симптом — в компании скапливается много-много логов и кто-то, по фамилии, отдаленно звучащей как «Сусанин», говорит: «коллеги, а в логах на самом деле сокрыто золото, там есть информация о путях пользователей, о транзакциях, о группах, о поисковых запросах — а давайте это золото начать извлекать»? И вы превращаетесь в «извлекателя» добра из терабайт (и их десятков) информационного водопада под мотивирующие советы: «а разве нельзя в потоке получать ценную для бизнеса информацию, зачем гонять часами кластера?».
Если это не о вас, тогда и не заходите под кат, ибо там — треш и жесткий технологический трепет…
Зря вы зашли под кат. Но мужчины — не отступают и бьются до конца. На самом деле, цель поста: сориентировать читателя и сформировать ему минимальный и эффективный «армейский паек» знаний и умений, которые пригодятся на самом сложном начальном этапе внедрения Бигдаты в компании.
Итак, разминка.
Говоря «по чесноку» мы, разработчики, бываем двух видов (я вижу, что пунктов ниже три):
В ВУЗе обычно (не все, конечно, говорю за себя) мы боремся с гормональным взрывом, знакомимся с красивыми девушками, спим на парах, кодим ночью что хотим, учимся перед сессией и в конце концов запоминаем список книг, куда нужно если что — глянуть. И еще в ВУЗе мы можем встретить преподавателей или коллег, которые своей энергией, отношением к делу, стремлением к компетенции и жизненной позицией могут стать нашими ориентирами на всю жизнь и подогревать нас и мотивировать в различных обстоятельствах (ну вот, снова довел себя до слез).
Если после ВУЗа системно тратить по паре часов в день на теорию в метро (автобусе, маршрутке) и по 8 часов на практику «проектирования и создания программного обеспечения» и прочитать минимально необходимые для общей грамотности книжечки, то вы выдохните с чувством выполненного долга лет в 40, а если еще и спать ночами — то лет в 50. Вот что я имею в виду:
Коллеги, это только то, что касается «проектировать ПО и писать хороший код».
А математика для разработчика — это отдельный мир. Дело в том, что, чтобы хорошенько понять рассматриваемые ниже алгоритмы и подстраивать их под нужды компании — нужно, как бы помягче сказать, неплохо разбираться в следующих областях математики:
А если вам повезет столкнуться с кластеризацией данных (сгруппируй похожих Покупателей, Товары и т.п.), то:
Ну да, конечно можно и не разбираться и скопипастить. Но если вам придется адаптировать и смешивать алгоритмы под свои нужды — фундаментальные знания, безусловно, нужны и тут лучше всего наверно работать совместной командой, у участников которой достаточно знаний чтобы понимать, куда идти.
И вы спросите — а нужен проекту математик, который живет математикой, спит с математикой и наизусть помнит доказательство теоремы Пифагора 20 способами и с постером «Бином Ньютона» над ложем — для понимания и организации процесса работы с Бигдатой? А он хороший код писать умеет — быстро, в релиз? А он не будет зависать перед монитором на 15 минут с гримасой ужасного страдания, созерцая быстро сделанный объектно-дизориентированный алогичный, но сексуальный хак? Ответ на этот вопрос мы знаем — ибо невозможно (кроме гениев и джедаев) одинаково хорошо преуспеть в служении светлой и темной сторонам.
Видимо поэтому умные от природы дяденьки и тетеньки усердно занимаются Computer Science и пишут только им понятные, написанные языком формул статьи, а трудолюбивые от природы разработчики лишь успевают поцеловать перед сном так и не открытый, но стоящий на самом видном месте дома многотомник Кнута :-)
Ну конечно бывают и исключения! А еще говорят, что люди иногда самовозгараются и он них остается кучка пепла.
Итак, коллеги, перечислим, с чем вам придется столкнуться в первых боях с Бигдатой.
Алгоритмы это области сначала кажутся очень очень простыми и хорошо «идут под водочку с огурчиками».
Ну что сложного? Никакой математики, только физика и химия. Матрица Пользователи*Товары и ищи похожие строчки, используя изучаемые в старшей группе детского сада формулы похожести векторов:
Но на самом деле все гораздо хуже. Если у вас миллионы Пользователей и Товаров (как у нас), научно-популярные книжечки по построению рекомендательных систем, а также 99% имеющейся в сети информации и научных статей — можно смело выкинуть. Не-под-хо-дит :-)
Тут выползает скрытый монстр под названием "проклятие размерности", начинаются серьезные вопросы по масштабируемости, скорости работы алгоритмов (все же знают, что Amazon придумал Item2Item алгоритм не от хорошей жизни, а потому — что User2Item алгоритм просто начал тормозить), превентивной оценки качества моделей и др.
А присовокупив настойчивую просьбу отдела маркетинга изменять коллаборативную фильтрацию в онлайне… — вы понимаете, что становится жарко.
Принцип построения ну тоже до боли простой. Мы формируем профили объектов, будь то Пользователи, Группы или Товары и затем ищем похожие объекты методом хоть всем известного косинуса угла между векторами.
Чувствуете запах? Именно, запахло миром поисковиков…
Последнее время даже сам Mahout стал рассказывать о большой роли поисковых движков в построении рекомендательных систем.
И тут от вас уже требуются знания алгоритмов IR — ну если проект не очень очень простой. Хотя бы отличать «precision» от «recall» и «F1» — нужно уметь.
И конечно все это можно сжечь, когда данных становится много, ибо многое перестает работать и нужно самим выполнять реализацию IR-алгоритмов с пониманием их сути, например в NoSQL и/или памяти.
Но будьте осторожны! Вас сама команда может объявить Еретиком и сжечь за инакомыслие прямо на кухне :-)
Про инструменты мы поговорим позже. А в качестве алгоритмов нам сейчас предлагается не очень много вариантов:
Со вторым поинтереснее. Если вы еще не поняли принцип MapReduce — это нужно сделать, он простой как «трусы за 1 руб 20 коп» и мощный.
Есть, например, даже глава в известном Стенфордском курсе по обработке больших данных о том, как перевести на язык MapReduce любую операцию реляционной алгебры (и гонять по данным SQL!!!).
Но тут подвох. Нужные вам известные простые алгоритмы из популярных книг нужно перевести в распределенный вид для использования MapReduce — а как сделать это, не сообщается :-) Распределенных алгоритмов, получается, гораздо меньше и они нередко… другие.
Можете столкнуться еще с потоковыми алгоритмами обработки больших данных, но это отдельная тема другого поста.
У вас несколько миллионов документов или пользователей и нужно найти группы. Либо склеить похожих. В лоб задача — не решается, слишком долго и дорого сравнивать каждого с каждым либо гонять итерации k-means.
Поэтому и придумали трюки с:
Если у вас много данных, то ни k-means, ни c-means, ни, тем более, классическая иерархическая кластеризация — вам не помогут. Нужно «хакать» технологии и математику, искать решения в научных статьях и экспериментировать.
Тема интересная, обширная, полезная — но требует иногда серьезного знания вышеуказанных разделов математики.
С одной стороны, стороны бизнесовой, тут довольно понятно — вы учите модель на заранее подготовленных данных угадывать новые данные. Например, у нас 10000 писем и для каждого известно, спам это или нет. А затем мы подаем в модель новое письмо и, о чудо, модель говорит нам, спам это или нет.
По «силе угадывания» модели делятся на:
А вот алгоритмов — очень много, вот полезный ресурс.
И конечно это только малая часть алгоритмов, с которыми вам, вероятно, придется иметь дело.
Вот мы и дошли до инструментов. Что есть готового, что поможет нам в борьбе с Бигдатой?
Многие начинают со старого и доброго Hadoop MapReduce. В принципе сам Hadoop — это сборная солянка разных подпроектов, которые так между собой переплелись, что их уже родная мать не отделит.
Из наиболее востребованных:
Немного в сторонке находится Spark. Этот фреймворк выглядит, как бы мягко сказать, более современным, и позволяет обрабатывать данные, размещая их по возможности в памяти, а также выстраивать цепочки запросов — что, конечно, удобно. Мы сами его активно используем.
Хотя впечатления от Spark очень противоречивые. Он покрыт машинным маслом и торчащими проводами под напряжением — видимо его еще долго будут шлифовать, чтобы можно было разумными способами контролировать использование Spark оперативной памяти, не вызывая для этого духов Вуду.
А если вы в облаке Амазон, то HDFS вам, скорее всего, не понадобиться и можно напрямую использовать облачное объектное хранилище s3.
К сожалению, развернуть Spark в Амазоне — достаточно непросто. Да, есть известный скрипт, но — не стоит. Мало того, что он загружает половину кода Университета Беркли в Калифорнии вам на сервер, так еще потом если его неаккуратно запустить (добавить хотите новую машину в кластер или обновить) — ваш кластер Spark будет нещадно изуродован и сломан и ближайшую ночь вы проведете не в объятиях подруги, а занимаясь любовью с bash/ruby/копипастами конфигурации в 100-500 местах :-)
А, чтобы сохранился позитивный осадок, посмотрите, как классно очень недавно Амазон стал продавать новый облачный сервисмашинного обучения, основанный на старом и добром «industry-standard logistic regression algorithm» (и никаких «лесов» и танцев с инопланетянами).
Вот наверно и все, что хотелось рассказать в вводном посте про алгоритмы и технологии обработки больших данных, с которыми разработчику вероятнее всего в ближайшие 3-6 месяцев придется вступить в бой. Надеюсь, информация и советы окажутся полезными и сэкономят вам, уважаемы коллеги, здоровье и манну.
А напоследок, ну чтобы понимать, как это может быть устроено изнутри, вид с птичьего полета нашего нового облачного сервиса:
Ну это так, упрощенно, если что :-) Поэтому — спрашивайте в комментах.
Есть еще интересный симптом — в компании скапливается много-много логов и кто-то, по фамилии, отдаленно звучащей как «Сусанин», говорит: «коллеги, а в логах на самом деле сокрыто золото, там есть информация о путях пользователей, о транзакциях, о группах, о поисковых запросах — а давайте это золото начать извлекать»? И вы превращаетесь в «извлекателя» добра из терабайт (и их десятков) информационного водопада под мотивирующие советы: «а разве нельзя в потоке получать ценную для бизнеса информацию, зачем гонять часами кластера?».
Если это не о вас, тогда и не заходите под кат, ибо там — треш и жесткий технологический трепет…
Зря вы зашли под кат. Но мужчины — не отступают и бьются до конца. На самом деле, цель поста: сориентировать читателя и сформировать ему минимальный и эффективный «армейский паек» знаний и умений, которые пригодятся на самом сложном начальном этапе внедрения Бигдаты в компании.
Итак, разминка.
Что знает и чего еще не знает разработчик
Говоря «по чесноку» мы, разработчики, бываем двух видов (я вижу, что пунктов ниже три):
- с математическим образованием
- с техническим образованием
- гуманитарии
В ВУЗе обычно (не все, конечно, говорю за себя) мы боремся с гормональным взрывом, знакомимся с красивыми девушками, спим на парах, кодим ночью что хотим, учимся перед сессией и в конце концов запоминаем список книг, куда нужно если что — глянуть. И еще в ВУЗе мы можем встретить преподавателей или коллег, которые своей энергией, отношением к делу, стремлением к компетенции и жизненной позицией могут стать нашими ориентирами на всю жизнь и подогревать нас и мотивировать в различных обстоятельствах (ну вот, снова довел себя до слез).
Если после ВУЗа системно тратить по паре часов в день на теорию в метро (автобусе, маршрутке) и по 8 часов на практику «проектирования и создания программного обеспечения» и прочитать минимально необходимые для общей грамотности книжечки, то вы выдохните с чувством выполненного долга лет в 40, а если еще и спать ночами — то лет в 50. Вот что я имею в виду:
- взрослые языки программирования на уровне спецификаций (C++, java, C#)
- пару популярных языков типа PHP, Python, Go
- понять и… простить все нормальные и «ненормальные» формы SQL
- книжечки по шаблонам проектирования (GoF, Fauler и др)
- книжечки в стиле «Эффективный ...»
- понять, как работает unix — изнутри
- понять сетевые протоколы на уровне RFC (чем отличается TCP от IP знают еще не все)
- как работает… компьютер! спускаясь до операционки и ее системных вызовов, проходя мультипроцессорные системы с их кэшами и мьютексами и спинлоками и до уровня микросхем
- провалить 10 программных проектов на ООП
- удалить код и единственный экземпляр бэкапа данных в пятницу вечером (говорят раза 3 нужно это сделать, чтобы наработать мозоль в мозгу)
Коллеги, это только то, что касается «проектировать ПО и писать хороший код».
А математика для разработчика — это отдельный мир. Дело в том, что, чтобы хорошенько понять рассматриваемые ниже алгоритмы и подстраивать их под нужды компании — нужно, как бы помягче сказать, неплохо разбираться в следующих областях математики:
- теория вероятностей с поддтанцовками в виде моделей Маркова (иначе PageRank не поймете как работает, не поймете байесовскую фильтрацию, не поймете кластеризацию LSH)
- комбинаторика, без которой сложно понять теорию вероятностей
- теория множеств (чтобы понять теорию вероятностей, и хотя бы чтобы понять Jaccard-расстояние в коллаборативке, но встречается повсеместно)
- линейная алгебра (коллаборативная фильтрация, сжатие размерностей, матрицы co-occurence, eigenvectors/values — это не векторы, придуманные Евгением!!)
- математическая статистика (даже не знаю где в Бигдате ее нет)
- машинное обучение (тут математический трэш и ад, начиная с примитивных перцептронов, продолжая «stochastic gradient descent» и не заканчивая нейронными сетями)
А если вам повезет столкнуться с кластеризацией данных (сгруппируй похожих Покупателей, Товары и т.п.), то:
- для понимания старого и доброго k-means в евклидовых пространствах ничего не потребуется, кроме того, что он не работает без лома и грубой силы на «больших данных» :-)
- для понимания c-means в неевклидовых пространствах, возможно потребуется дополнительная чашечка кофе (хотя он тоже не работает с большими данными)
- а вот для понимания популярной сейчас спектральной кластеризации (тут я сознательно упростил и даже чуть извратил «power iteration clustering»), при которой мы перемещаем данные из одного пространства в другое (т.е. нужно кластеризовать рога, а вы кластеризуете копыта и получается даже ничего), вы скорее всего выпрыгнете в окошко с бесполезным томиком «Алгоритмы на C++» Седжвика :-)
Ну да, конечно можно и не разбираться и скопипастить. Но если вам придется адаптировать и смешивать алгоритмы под свои нужды — фундаментальные знания, безусловно, нужны и тут лучше всего наверно работать совместной командой, у участников которой достаточно знаний чтобы понимать, куда идти.
Нужен аналитик?
И вы спросите — а нужен проекту математик, который живет математикой, спит с математикой и наизусть помнит доказательство теоремы Пифагора 20 способами и с постером «Бином Ньютона» над ложем — для понимания и организации процесса работы с Бигдатой? А он хороший код писать умеет — быстро, в релиз? А он не будет зависать перед монитором на 15 минут с гримасой ужасного страдания, созерцая быстро сделанный объектно-дизориентированный алогичный, но сексуальный хак? Ответ на этот вопрос мы знаем — ибо невозможно (кроме гениев и джедаев) одинаково хорошо преуспеть в служении светлой и темной сторонам.
Видимо поэтому умные от природы дяденьки и тетеньки усердно занимаются Computer Science и пишут только им понятные, написанные языком формул статьи, а трудолюбивые от природы разработчики лишь успевают поцеловать перед сном так и не открытый, но стоящий на самом видном месте дома многотомник Кнута :-)
Ну конечно бывают и исключения! А еще говорят, что люди иногда самовозгараются и он них остается кучка пепла.
Алгоритмы
Итак, коллеги, перечислим, с чем вам придется столкнуться в первых боях с Бигдатой.
Коллаборативная фильтрация
Алгоритмы это области сначала кажутся очень очень простыми и хорошо «идут под водочку с огурчиками».
Ну что сложного? Никакой математики, только физика и химия. Матрица Пользователи*Товары и ищи похожие строчки, используя изучаемые в старшей группе детского сада формулы похожести векторов:
- Евклидово расстояние
- Расстояние городских кварталов
- Косинус угла между векторами
- Коэффициент кореляции Пиросона
- Расстояние Jaccard (на множествах)
Но на самом деле все гораздо хуже. Если у вас миллионы Пользователей и Товаров (как у нас), научно-популярные книжечки по построению рекомендательных систем, а также 99% имеющейся в сети информации и научных статей — можно смело выкинуть. Не-под-хо-дит :-)
Тут выползает скрытый монстр под названием "проклятие размерности", начинаются серьезные вопросы по масштабируемости, скорости работы алгоритмов (все же знают, что Amazon придумал Item2Item алгоритм не от хорошей жизни, а потому — что User2Item алгоритм просто начал тормозить), превентивной оценки качества моделей и др.
А присовокупив настойчивую просьбу отдела маркетинга изменять коллаборативную фильтрацию в онлайне… — вы понимаете, что становится жарко.
Content-based рекомендательные системы
Принцип построения ну тоже до боли простой. Мы формируем профили объектов, будь то Пользователи, Группы или Товары и затем ищем похожие объекты методом хоть всем известного косинуса угла между векторами.
Чувствуете запах? Именно, запахло миром поисковиков…
Последнее время даже сам Mahout стал рассказывать о большой роли поисковых движков в построении рекомендательных систем.
И тут от вас уже требуются знания алгоритмов IR — ну если проект не очень очень простой. Хотя бы отличать «precision» от «recall» и «F1» — нужно уметь.
И конечно все это можно сжечь, когда данных становится много, ибо многое перестает работать и нужно самим выполнять реализацию IR-алгоритмов с пониманием их сути, например в NoSQL и/или памяти.
Но будьте осторожны! Вас сама команда может объявить Еретиком и сжечь за инакомыслие прямо на кухне :-)
Обработка, фильтрация, агрегирование
Про инструменты мы поговорим позже. А в качестве алгоритмов нам сейчас предлагается не очень много вариантов:
Со вторым поинтереснее. Если вы еще не поняли принцип MapReduce — это нужно сделать, он простой как «трусы за 1 руб 20 коп» и мощный.
Есть, например, даже глава в известном Стенфордском курсе по обработке больших данных о том, как перевести на язык MapReduce любую операцию реляционной алгебры (и гонять по данным SQL!!!).
Но тут подвох. Нужные вам известные простые алгоритмы из популярных книг нужно перевести в распределенный вид для использования MapReduce — а как сделать это, не сообщается :-) Распределенных алгоритмов, получается, гораздо меньше и они нередко… другие.
Можете столкнуться еще с потоковыми алгоритмами обработки больших данных, но это отдельная тема другого поста.
Кластеризация
У вас несколько миллионов документов или пользователей и нужно найти группы. Либо склеить похожих. В лоб задача — не решается, слишком долго и дорого сравнивать каждого с каждым либо гонять итерации k-means.
Поэтому и придумали трюки с:
- minhash
- simhash
- LSH
Если у вас много данных, то ни k-means, ни c-means, ни, тем более, классическая иерархическая кластеризация — вам не помогут. Нужно «хакать» технологии и математику, искать решения в научных статьях и экспериментировать.
Тема интересная, обширная, полезная — но требует иногда серьезного знания вышеуказанных разделов математики.
Машинное обучение
С одной стороны, стороны бизнесовой, тут довольно понятно — вы учите модель на заранее подготовленных данных угадывать новые данные. Например, у нас 10000 писем и для каждого известно, спам это или нет. А затем мы подаем в модель новое письмо и, о чудо, модель говорит нам, спам это или нет.
По «силе угадывания» модели делятся на:
- бинарные классифиаторы, например угадывающие «спам/не спам»
- мультиклассовые классификаторы, например относящие документы к нескольким группам
- использующие регрессию, например угадывающие возраст или температуру воздуха
А вот алгоритмов — очень много, вот полезный ресурс.
И конечно это только малая часть алгоритмов, с которыми вам, вероятно, придется иметь дело.
Инструменты
Вот мы и дошли до инструментов. Что есть готового, что поможет нам в борьбе с Бигдатой?
Многие начинают со старого и доброго Hadoop MapReduce. В принципе сам Hadoop — это сборная солянка разных подпроектов, которые так между собой переплелись, что их уже родная мать не отделит.
Из наиболее востребованных:
- HDFS — кластерная файловая система для хранения вашей Бигдаты
- MapReduce — чтобы делать выборки из этих данных
- Hive — чтобы не связываться с низкоуровневыми MapReduce-техниками, а использовать старый добрый SQL
- Mahout — чтобы не изучать математику, а взять готовое и увидеть, что оно с большими данными не работает :-)
- YARN — чтобы управлять всем этим «курятником»
Немного в сторонке находится Spark. Этот фреймворк выглядит, как бы мягко сказать, более современным, и позволяет обрабатывать данные, размещая их по возможности в памяти, а также выстраивать цепочки запросов — что, конечно, удобно. Мы сами его активно используем.
Хотя впечатления от Spark очень противоречивые. Он покрыт машинным маслом и торчащими проводами под напряжением — видимо его еще долго будут шлифовать, чтобы можно было разумными способами контролировать использование Spark оперативной памяти, не вызывая для этого духов Вуду.
А если вы в облаке Амазон, то HDFS вам, скорее всего, не понадобиться и можно напрямую использовать облачное объектное хранилище s3.
К сожалению, развернуть Spark в Амазоне — достаточно непросто. Да, есть известный скрипт, но — не стоит. Мало того, что он загружает половину кода Университета Беркли в Калифорнии вам на сервер, так еще потом если его неаккуратно запустить (добавить хотите новую машину в кластер или обновить) — ваш кластер Spark будет нещадно изуродован и сломан и ближайшую ночь вы проведете не в объятиях подруги, а занимаясь любовью с bash/ruby/копипастами конфигурации в 100-500 местах :-)
А, чтобы сохранился позитивный осадок, посмотрите, как классно очень недавно Амазон стал продавать новый облачный сервисмашинного обучения, основанный на старом и добром «industry-standard logistic regression algorithm» (и никаких «лесов» и танцев с инопланетянами).
В добрый путь!
Вот наверно и все, что хотелось рассказать в вводном посте про алгоритмы и технологии обработки больших данных, с которыми разработчику вероятнее всего в ближайшие 3-6 месяцев придется вступить в бой. Надеюсь, информация и советы окажутся полезными и сэкономят вам, уважаемы коллеги, здоровье и манну.
А напоследок, ну чтобы понимать, как это может быть устроено изнутри, вид с птичьего полета нашего нового облачного сервиса:
Ну это так, упрощенно, если что :-) Поэтому — спрашивайте в комментах.
