Подходы и инструменты работы с BigData — все только начинается, начи-на-ет-ся

    Вы еще не сохраняете десятки миллионов событий в день? К вам еще не забегают менеджеры с кричащим вопросом — когда твой дорогущий кластер на «надцати» машинах посчитает агрегированную статистику по продажам за неделю (а в глазах читается: «чувак, ребята на php/python/ruby/go решают задачу за час, а ты со своей Бигдатой тянешь время днями, доколе?»)? Вы еще не вскидываетесь ночью в холодном поту от кошмара: «разверзлось небо и на вас, ваших коллег и весь нафиг город вывалилось огромная куча… Бигдаты и никто не знает, что с этим всем теперь делать»? :-)

    Есть еще интересный симптом — в компании скапливается много-много логов и кто-то, по фамилии, отдаленно звучащей как «Сусанин», говорит: «коллеги, а в логах на самом деле сокрыто золото, там есть информация о путях пользователей, о транзакциях, о группах, о поисковых запросах — а давайте это золото начать извлекать»? И вы превращаетесь в «извлекателя» добра из терабайт (и их десятков) информационного водопада под мотивирующие советы: «а разве нельзя в потоке получать ценную для бизнеса информацию, зачем гонять часами кластера?».

    Если это не о вас, тогда и не заходите под кат, ибо там — треш и жесткий технологический трепет…

    Зря вы зашли под кат. Но мужчины — не отступают и бьются до конца. На самом деле, цель поста: сориентировать читателя и сформировать ему минимальный и эффективный «армейский паек» знаний и умений, которые пригодятся на самом сложном начальном этапе внедрения Бигдаты в компании.

    Итак, разминка.

    Что знает и чего еще не знает разработчик



    Говоря «по чесноку» мы, разработчики, бываем двух видов (я вижу, что пунктов ниже три):
    • с математическим образованием
    • с техническим образованием
    • гуманитарии


    В ВУЗе обычно (не все, конечно, говорю за себя) мы боремся с гормональным взрывом, знакомимся с красивыми девушками, спим на парах, кодим ночью что хотим, учимся перед сессией и в конце концов запоминаем список книг, куда нужно если что — глянуть. И еще в ВУЗе мы можем встретить преподавателей или коллег, которые своей энергией, отношением к делу, стремлением к компетенции и жизненной позицией могут стать нашими ориентирами на всю жизнь и подогревать нас и мотивировать в различных обстоятельствах (ну вот, снова довел себя до слез).

    Если после ВУЗа системно тратить по паре часов в день на теорию в метро (автобусе, маршрутке) и по 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 месяцев придется вступить в бой. Надеюсь, информация и советы окажутся полезными и сэкономят вам, уважаемы коллеги, здоровье и манну.

    А напоследок, ну чтобы понимать, как это может быть устроено изнутри, вид с птичьего полета нашего нового облачного сервиса:


    Ну это так, упрощенно, если что :-) Поэтому — спрашивайте в комментах.
    1С-Битрикс
    Company

    Comments 13

      +1
      Если есть доступ к IEEE Xplore — можно дополнительно поглядеть обзорную теоретическую статейку на тему анализа Big Data и её визуализации. :)

        +2
        трудолюбивые от природы разработчики лишь успевают поцеловать перед сном так и не открытый, но стоящий на самом видном месте дома многотомник Кнута :-)

        Как ни печально осозновать, но в большинстве случаев все именно так…

        Кнут для многих — это своего рода икона :)
          0
          А он нудный. Седвжик гораздо проще и читается как детектив :-)
          +4
          Дайте просто сслыку на вашу облачную биг дату, шоб почитать без прибауточек, ок?
          +2
          Александр, я ваш стиль изложения начинаю угадывать со второго абзаца :) Сильно давите терминами…
          И не даете вывода, или хотя бы совета. Что-то в стиле «Если хотите A — почитайте Б и вероятнее всего решите делать это на В».

          А еще более полезными были бы статьи про боевые архитектуры. В качестве примера возьму картинки из заключения статьи. На партнерской конференции Демидов рассказывал про ее первую часть (js -> nginx + lua -> Kinesis). Было бы интересно про вторую часть услышать — что там у рекомендательного сервиса в «мозгах», почему и с чем сравнивали.
            0
            Ага, спасибо, напишем про это подробно. А внутри там Mahout Taste сильно доработанный пока и обвешанный кучей датчиков, но на подходе еще несколько двигателей, расскажем про них подробно в мае.
            +1
            Зачем спарк в амазоне, когда есть Google Cloud Dataflow! Те же яйца, только в профиль.
              0
              Интересно, там MapReduce?
                0
                Насколько я понял — вроде как нет, но глубоко не копал еще.
              +1
              Объясните мне: оно в режиме реального времени работает? Если нет (это же не RTB), то почему нельзя последовательно техники MapReduce применять (которые по сути просто свертка данных для дальнейшего анализа, грамм радия на тонну руды) + кластеризовывать понемногу, зачем все эти танцы с бубнами?
                0
                оно в режиме реального времени работает?

                Рекомендации — почти да, т.к. ответы на какое-то время кэшируются.

                А сбор статистики и анализ — это через MapReduce.

              Only users with full accounts can post comments. Log in, please.