• Bitmap-индексы в Go: поиск на дикой скорости



      Вступительное слово


      Я выступил с этим докладом на английском языке на конференции GopherCon Russia 2019 в Москве и на русском — на митапе в Нижнем Новгороде. Речь в нём идёт о bitmap-индексе — менее распространённом, чем B-tree, но не менее интересном. Делюсь записью выступления на конференции на английском и текстовой расшифровкой на русском.

      Мы рассмотрим, как устроен bitmap-индекс, когда он лучше, когда — хуже других индексов и в каких случаях он значительно быстрее них; увидим, в каких популярных СУБД уже есть bitmap-индексы; попробуем написать свой на Go. А «на десерт» мы воспользуемся готовыми библиотеками, чтобы создать свою супербыструю специализированную базу данных.

      Очень надеюсь, что мои труды окажутся для вас полезными и интересными. Поехали!
      Читать дальше →
    • Рефакторинг программы на Go: ускорение в 23 раза

      • Translation


      Привет! Меня зовут Марко, я работаю в Badoo в отделе «Платформы». У нас довольно много всего написано на Go, и зачастую это критичные к производительности системы. Именно поэтому сегодня я предлагаю вашему вниманию перевод статьи, которая мне очень понравилась и, я уверен, будет вам очень полезна. Автор пошагово показывает, как он подходил к проблемам производительности и как их решал. В том числе вы познакомитесь с богатым инструментарием, доступным в Go для такой работы. Приятного чтения!

      Несколько недель назад я прочитал статью «Хороший код против плохого кода в Go», где автор шаг за шагом демонстрирует рефакторинг реального приложения, решающего реальные бизнес-задачи. Она сфокусирована на превращении «плохого кода» в «хороший код»: более идиоматичный, более понятный, полноценно использующий специфику языка Go. Но автор также заявлял о важности производительности рассматриваемого приложения. Во мне взыграло любопытство: давайте попробуем её ускорить!
      Читать дальше →
    • Как Pusher Channels доставил уже 10.000.000.000.000 сообщений

      • Translation

      Привет! Недавно я натолкнулся на довольно интересное описание архитектуры Pusher Channels и решил его перевести для вас. На мой взгляд, автор очень доступно описал подходы к построению высоконагруженной и масштабируемой архитектуры. Скорее всего, статья будет полезна новичкам, а также специалистам из смежных областей.


      В офисе компании Pusher у нас висит небольшой счетчик с постоянно увеличивающейся цифрой. Он показывает количество доставленных сообщений за всё время существования Pusher Channels. В пятницу в 22:20 по UTC число увеличилось на один разряд и достигло 10.000.000.000.000. В нём 13 нулей — 10 трлн.



      Вы можете подумать, что счётчик общего количества сообщений — бесполезная кичливая метрика. Но это число — ключевой индикатор успеха Pusher Channels, нашего продукта для коммуникации в режиме реального времени. Во-первых, данный счётчик отражает доверие, оказанное нам пользователями. Во-вторых, он измеряет масштабируемость нашей системы. Чтобы цифра увеличивалась, мы в Pusher должны сделать так, чтобы пользователи доверяли отправку сообщений нашему сервису, и мы должны быть уверены в том, что наша система способна обработать эти сообщения. Но что нам стоит доставить 10 трлн сообщений? Давайте посмотрим.

      Читать дальше →
    • Знакомство с гео-библиотекой S2 от Google и примеры использования

        Привет, Хабр!

        Меня зовут Марко, я работаю в Badoo в команде «Платформа». Не так давно на GopherCon Russia 2018 я рассказывал, как работать с координатами. Для тех, кто не любит смотреть видео (и всех интересующихся, конечно), публикую текстовый вариант своего доклада.



        Введение


        Сейчас у большинства людей в мире есть смартфон с постоянным доступом в Интернет. Если говорить в цифрах, то в 2018 году смартфон будет у почти 5 млрд людей, и 60% из них пользуются мобильным Интернетом.

        Это огромные числа. Компаниям получать координаты пользователей стало легко и просто. Эти лёгкость и доступность породили (и продолжают порождать) огромное количество сервисов, основанных на координатах.

        Всем нам известны компании типа Uber, игры, покорившие мир, такие как Ingress и Pokemon Go. Да что уж там, в любом банковском приложении есть возможность увидеть банкоматы или скидки поблизости.

        Мы в Badoo также очень активно используем координаты, чтобы предоставлять своим пользователям лучший, актуальный и интересный для них сервис. Но о каком именно использовании идёт речь? Давайте посмотрим на примеры сервисов, которые у нас есть.
        Читать дальше →
      • Как новичок в Go контрибьютил

        • Translation


        Rocky Runs Up The Stairs


        Привет, Хабр. Вы, наверно, меня помните: я – Марко Кевац, системный программист в Badoo. Недавно я наткнулся на небольшой рассказ о том, как новичок сделал изменение в рантайме языка Go. Несмотря на то, что этот пост, наверное, довольно неожиданно встретить в хабраблоге Badoo, и многие могут сказать, что он банален и переполнен наивной радостью, я считаю, что такие истории демонстрируют, насколько сообщество Go доброжелательно и внимательно по отношению ко всем его участникам. Поэтому и перевел его.


        А ещё в посте есть два интересных факта, связанных с внутренностями языка. Приятного чтения!

        Читать дальше →
      • Инструменты для разработчика Go: знакомимся с лейблами профайлера

        • Translation

        DrawingПривет. Меня зовут Марко. Я системный программист в Badoo. Представляю вашему вниманию перевод поста замечательной rakyll о новой фиче в Go 1.9. Мне кажется, что лейблы будут очень полезны для профилирования ваших Go-программ. Мы в Badoo, например, используем аналогичную штуку для того, чтобы тегировать куски кода в наших программах на С. И если срабатывает таймер и в лог выводится стек-трейс, то в дополнение к нему мы выводим такой вот тег. В нем, например, может быть сказано, что мы обрабатывали фотографии пользователя с определенным UID. Это невероятно полезно, и я очень рад, что похожая возможность появилась и в Go.

        Читать дальше →
      • Логирование, интерфейсы и аллокации в Go

        • Translation


        Привет Хабр. Последний свой пост я публиковал сравнительно недавно, так что вряд ли вы успели забыть, что меня зовут Марко. Сегодня публикую перевод небольшой заметки, которая касается нескольких очень вкусных оптимизаций из еще не вышедшего Go 1.9. Эти оптимизации позволяют генерировать меньше мусора в большинстве программ на Go. Меньше мусора – меньше задержки и затраты на сборку этого мусора.


        Эта статья о новых оптимизациях компилятора, которые готовятся к релизу Go 1.9, но я бы хотел начать разговор с логирования.

        Читать дальше →
      • Какой map быстрее, и есть ли альтернатива Judy


          Кадр из Top Gear: USA (серия 2)


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


          Практически с самого начала в качестве реализации ассоциативных массивов мы использовали Judy. У неё есть C-интерфейс и множество преимуществ. Мы даже используем обёртку для PHP, так как в версиях PHP до 7.0 Judy сильно выигрывает по количеству потребляемой памяти по сравнению со встроенными мапами.


          Однако время идёт, и с момента последнего релиза Judy прошло немало лет – самое время посмотреть на альтернативы.


          Меня зовут Марко, я – системный программист Badoo в команде «Платформа». Мы с коллегами провели небольшое исследование в поисках альтернатив Judy, сделали выводы и решили поделиться ими с вами.

          Читать дальше →
        • Position-independent code (PIC) в разделяемых библиотеках на x64

          • Translation

          enter image description here


          Привет, я все еще Марко и все еще системный программист в Badoo. На прошлой неделе я опубликовал перевод о PIC в шареных библиотеках, но есть вторая часть – про разделяемые библиотеки на х64, поэтому решил не оставлять дело незаконченным.

          Читать дальше →
        • Position-independent code (PIC) в разделяемых библиотеках

          • Translation

          enter image description here


          Привет. Меня зовут Марко, и я системный программист в Badoo. Я очень люблю досконально разбираться в том, как работают те или иные вещи, и тонкости работы разделяемых библиотек в Linux не исключение. Я представляю вам перевод именно такого разбора. Приятного чтения.

          Читать дальше →
          • +65
          • 11.8k
          • 9
        • История одного толстого бинарника

          • Translation

          enter image description here


          Привет. Меня зовут Марко (я системный программист в Badoo). И я представляю вашему вниманию перевод поста по Go, который мне показался интересным. Go действительно ругают за толстые бинарники, но при этом хвалят за статическую линковку и за удобство выкладки единственного файла. Если на современных серверах толстые бинарники – не проблема, то на встраиваемых системах – еще как. Автор описывает свою историю борьбы с ними в Go.

          Читать дальше →
        • Как работать с JIT

          • Translation

          enter image description here


          В некоторых внутренних системах для быстрого поиска по большому битовому массиву мы в Badoo используем JIT. Это очень интересная и не самая известная тема. И, чтобы исправить такую досадную ситуацию, я перевел полезную статью Элая Бендерски о том, что такое JIT и как его использовать.

          Читать дальше →
          • +49
          • 11.6k
          • 8
        • Новогодние обещания Go-разработчика

          • Translation

          image
          Фото Roman Pronskiy


          Это перевод поста одного из главных разработчиков языка Go, Расса Кокса, где он в традиционном для новогоднего времени формате дает себе обещания и планирует выполнить их.


          Наступило время принятия решений, и я подумал, что имеет смысл немного рассказать о том, над чем я хочу работать в наступившем году применительно к Go.


          Каждый год я ставлю перед собой цель — помочь Go-разработчикам. Я хочу быть уверен, что то, что делают создатели Go, оказывает положительное влияние на всех Go-разработчиков. Потому что у них есть масса способов совершить ошибку: например, можно потратить слишком много времени на очистку или оптимизацию кода, которому это не требуется; откликаться только на самые распространенные или недавние жалобы и запросы; излишне сосредотачиваться на краткосрочных улучшениях. Поэтому так важно взглянуть на все со стороны и заняться тем, что принесет больше всего пользы для Go-сообщества.


          В этой статье я опишу несколько основных задач, на которых я сосредоточусь в этом году. Это мой собственный список, а не всей команды создателей Go.

          Читать дальше →
        • Создание кастомных Go-профилей с помощью pprof. Запоминаем стеки

          • Translation

          Кадр из сериала «Коломбо»

          Go-шный пакет pprof часто используется для профилирования процессора или памяти, но не все знают о возможности создавать собственные кастомные профили. Они могут быть полезны для поиска утечек ресурсов или, например, для слежения за злоупотреблением какими-нибудь тяжелыми вызовами.
          Читать дальше →
        • Архитектура ассемблера Go

          • Translation
          image Привет, Хабр! Меня зовут Марко Кевац, я системный программист Badoo в команде «Платформа», и я очень люблю Go. Если сложить эти две вещи, то вы поймёте, насколько я люблю ассемблер в Go.

          Совсем недавно мы рассказывали на Хабре о том, на каких конференциях побывали. Одной из них была GopherCon 2016, где практически всем запомнился доклад Роба «Командира» Пайка про Go-шный ассемблер. Представляю вам перевод его доклада, оформленный в виде статьи. Я постарался дать в тексте как можно больше ссылок на релевантные статьи в «Википедии».
          Читать дальше →
        • Профилирование и оптимизация программ на Go

          • Tutorial

          Введение


          В этой статье я расскажу, как профилировать и оптимизировать приложения на языке Go с использованием встроенных и общих инструментов, доступных в ОС Linux.

          Что такое профайлинг и оптимизация? Если ваша программа работает недостаточно быстро, использует слишком много памяти, неоптимально использует процессор, вы хотите понять, в чем дело, и исправить — это и есть профайлинг и оптимизация.

          Я привел такое определение, чтобы сразу отсечь вопросы некорректной работы приложения. В этой статье мы не будем говорить о проблемах мультитредового программирования, о дата-рейсах (англ. data race), о поиске ошибок (англ. debugging). Для всего этого в Go есть свои утилиты и подходы, но оставим эту тему на будущее.



          Читать дальше →
        • Сбор и анализ логов демонов в Badoo

            Введение


            В Badoo несколько десятков «самописных» демонов. Большинство из них написаны на Си, остался один на С++ и пять или шесть на Go. Они работают примерно на сотне серверов в четырех дата-центрах.

            В Badoo проверка работоспособности и обнаружение проблем с демонами лежат на плечах отдела мониторинга. Коллеги с помощью Zabbix и скриптов проверяют, запущен ли сервис, отвечает ли он на запросы, а также следят за версиями. Кроме того, в отделе анализируется статистика демонов и скриптов, работающих с ними, на предмет аномалий, резких скачков и т.п.



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

            Мы построили такую систему и спешим поделиться подробностями. Наверняка у кого-то из вас будет стоять похожая задача, и прочтение данной статьи убережет от ошибок, которые мы успели совершить.
            Читать дальше →
          • Geo индекс для поиска новых знакомых или революционное открытие ученых из Австрии

              Как вы знаете, Badoo — сервис для поиска новых людей. Кроме всего прочего, мы позволяем искать людей вокруг и в «игре» тоже показываем людей, которые находятся недалеко от вас. Эта часть «вокруг» очень и очень важна. Ведь молодому человеку из Новосибирска гораздо интереснее познакомиться с девушкой, которая живет в пяти минутах ходьбы от него, а не во Владивостоке.
              Мы до сих пор не рассказывали публично о том, как мы это делаем. Но новое открытие австрийских ученых настолько нас обрадовало, что мы решились это сделать. Перейдем же к делу.
              Badoo работает по всему миру и наш поиск работает абсолютно одинаково, вне зависимости от того, в какой точке земного шара вы находитесь. Как же эффективно искать людей вокруг среди всех 200+ миллионов пользователей?
              Решение нетривиально, честно говоря. Нам нужен какой-то индекс, какой-то способ сразу же сузить область поиска. В случае с земным шаром, самым простым разбиением является сетка географических широт и долгот. Однако проблема с этой сеткой в ее неравномерности. Ячейка у северного полюса и ячейка у экватора имеют совсем разные формы. Такое несимметричное разбиение вносит большие проблемы, если мы хотим равномерно распределить нагрузку по поисковому кластеру.
              Читать дальше →
            • Slow Lori атака на веб-сервер Apache

                Slow Lori — это животное, живущее в юговосточной Азии и известное своей медлительностью и размеренными движениями. По нему была названа новая DoS и DDoS атака на веб-сервер Apache.

                image

                Данный тип атаки был обнародован специалистом по безопасности RSnake 17 июня и подробно описан на странице http://ha.ckers.org/blog/20090617/slowloris-http-dos

                Атака заключается в очень медленной посылке все новых и новых HTTP заголовков в рамках одного HTTP запроса, никогда его не завершая.

                Поскольку Apache выделяет ресурсы для запроса очень рано, то на один такой запрос тратится «полноценное» кол-во ресурсов. Такое же, как и для обычного запроса.

                Как известно, Apache использует для обработки запросов или процессы или смесь процессов с нитями. Использование нитей позволит отсрочить смерть, но так или иначе Apache упрется в ограничение по памяти или ограничение, заданное администратором.

                Что самое неприятное, Slowlori атака не оставляет никаких следов, кроме огромного количества открытых cоединений со статусом ESTABLISHED. Не будет никаких записей даже в access_log-е.

                Первоначально разработчики Apache не очень активно отреагировали на сообщение RSnake в список рассылки, ответив ему что данная атака давно известна и является минусом не самого веб-вервера, а скорее TCP-стека. Однако, в дальнейшем разработчики веб-сервера Apache зашевелились и начали активно обсуждать пути решения проблемы.

                Веб-серверы основанные на state machine не подвержены данной атаке. Таким образом простейшим способом обезопасить себя от Slowlori атаки является использование двухуровневой архитектуры, когда первым на пути является веб\прокси сервер, основанный на state machine, такой как nginx.

                Другими возможными решениями являются Access HTTP фильтры в FreeBSD, использование хитрых правил на файрволе, которые, в то же время, могут отсечь и легитимных медленных пользователей.

                Кроме собственно изменения архитектуры, разработчики Apache согласны в необходимости внедрения более мелких, локальных таймаутов. На данный момент в Apache 2.2 реализован один обший таймаут, влияющий на практически все IO действия.

                Более подробную информацию можно получить в списке рассылки httpd-dev и в пока не открытой для публичного доступа статье на LWN.