Зачем знать алгоритмы Основная секция
Доклад принят в Программу конференции
Авито, Sphinx
Пишет код на всём подряд, показывает другим как. В удачные дни код удается сносить, это обязательно показывает другим и заставляет "точно так же" втройне сильнее. Всю сознательную жизнь из этого выходят разные движки, прямо проклятие какое-то.
Тезисы
Why02
View more presentations from HighLoad2009.
Синопсис
Исходник можешь ты не знать, но алгоритмы знать обязан. Это потому, что даже минимальные познания о том, как что устроено внутри разных серверных программных систем позволяют ловко оптимизировать всякое, проводить правильные бенчмарки, принимать осознанные решения о разработке или неразработке своего велосипеда, и т.д. и т.п.
Тезисы:
1. О чем вообще доклад: как довольно-таки базовые знания всякого помогают понять происходящее в чужих (!) системах, с которыми приходится работать, типа СУБД.
2. Пронзаем мозгом базу данных.
2.1. Теория. Потроха любой SQL базы на пальцах за 10 минут: хранение rows (тупое и кластерное); индексы (вечный Btree и как он устроен); covering индексы; вычисление запросов с точки зрения банальной эрудиции (row lookup, WHERE, ORDER, GROUP); зачем и как бывают буфера.
2.2. Практика. Как внутри работает выборка по PK, по индексу, по covering индексу, как примерно может работать JOIN. Как идеал, бывает, расходится с реальностью на примере MySQL (LIMIT, выбор индекса, subselect). Отчего иногда случается fullscan и отчего иногда это хорошо. Полубоевые примеры "как по книжке" про разгон запросов при помощи covering index, форсирования fullscan, итд.
3. Пронзаем мозгом полнотекстовый поиск.
3.1. Теория. Потроха любого поиска на пальцах за 10 минут: что такое инвертированный индекс; как, в принципе, могут храниться атрибуты; вычисление запросов с точки зрения банальной эрудиции (пересечение списков, прыжки по чекпойнтам, row lookup).
3.2. Практика. Отчего и почему FT индекс нельзя хранить в базе, как и почему для него НЕ работает Btree. Отчего, почему, и как в Sphinx работают ловкие трюки про замену ключевых слов фильтрами и наоборот. Отчего не обязаны хорошо работать где-то еще. Почему нужны стоп-слова. Откуда взялся max_matches и почему оно влияет на скорость поиска.
4. Бонус-трек: пронзаем мозгом компилятор. "Зачем ассемблеру второй проход", чего нельзя ожидать от скриптовой среды типа PHP, почему в идеальном мире победит Java, а в реальном C++.
5. Выводы. Зачем же таки знать алгоритмы. Какие конкретно, те, что остались за бортом доклада. На какой позиции или в какой стране можно не знать.
Другие доклады секции Основная секция
Яндекс — технологическая компания, которая создаёт инновационные продукты на основе машинного обучения и нейронных сетей. Команда талантливых математиков и программистов развивает самую популярную в России поисковую систему и более 85 пользовательских сервисов, которые помогают людям в повседневных заботах.
СберМаркет (ООО «Инстамарт Технолоджис») — технологический онлайн-сервис, который помогает делать покупки не выходя из дома. Tech-команда СберМаркета создает один из самых сложных высоконагруженных e-commerce-проектов в России и делает это с любовью.
Группа «Иннотех» — это современная высокотехнологичная быстроразвивающаяся ИТ-компания, входит в Холдинг Т1. С 2020 года мы разрабатываем инновационные решения для цифровизации бизнеса. Группа «Иннотех» выстраивает партнерские отношения с ведущими компаниями финансового сектора, предлагая им комплексные решения для фронт- и бэк-офисов, современные финтех-продукты, системы работы с большими данными. Кроме того, группа «Иннотех» выполняет на заказ технологические проекты любой сложности, помогая своим клиентам на пути цифровой трансформации.
Data Egret
Строят публичную облачную платформу Yandex Cloud, чтобы дать компаниям доступ к технологиям и сервисам, которые проверены нагрузками Яндекса. Продукты Yandex Cloud — это масштабируемая инфраструктура, сервисы хранения данных, инструменты машинного обучения и средства разработки.
Garage Eight — международная продуктовая IT-компания. Создаем экосистему финансовых продуктов и сервисов на зарубежных рынках. К 2024 году у наших продуктов сотни тысяч активных пользователей в 183 странах.
Яндекс — технологическая компания, которая создаёт инновационные продукты на основе машинного обучения и нейронных сетей. Команда талантливых математиков и программистов развивает самую популярную в России поисковую систему и более 85 пользовательских сервисов, которые помогают людям в повседневных заботах.
Разрабатываем GigaChat и крутые устройства
СберМаркет (ООО «Инстамарт Технолоджис») — технологический онлайн-сервис, который помогает делать покупки не выходя из дома. Tech-команда СберМаркета создает один из самых сложных высоконагруженных e-commerce-проектов в России и делает это с любовью.
Строят публичную облачную платформу Yandex Cloud, чтобы дать компаниям доступ к технологиям и сервисам, которые проверены нагрузками Яндекса. Продукты Yandex Cloud — это масштабируемая инфраструктура, сервисы хранения данных, инструменты машинного обучения и средства разработки.
VK — это более 200 технологичных проектов, свыше 11 000 сотрудников и более 20 лет опыта создания высоконагруженных интернет-сервисов. ВКонтакте, Одноклассники, VK Cloud, Дзен, Маруся, VK Play — это лишь часть продуктов VK, которыми ежедневно пользуются миллионы людей по всей стране.
Tarantool — middleware для эффективного создания высоконагруженных сервисов. Сочетает в себе сервер приложений, гибридное хранилище данных, а также инструменты и средства масштабирования. Производительность систем на Tarantool может достигать 1 млн транзакций в секунду.
Altenar — международная IT-b2b-компания с офисами в России, на Мальте и в Греции, которая занимается разработкой высоконагруженного программного обеспечения для сбора, обработки, анализа спортивных данных в реальном времени и их последующего преобразования в информацию для b2b-клиентов.
ВКонтакте — крупнейшая социальная сеть в России и странах СНГ. Миссия — соединять людей, сервисы и компании, создавая простые и удобные инструменты коммуникации. VK — это больше 200 технопроектов. Свыше 10 000 человек создают и развивают одни из самых популярных и высоконагруженных интернет-сервисов в стране. Делают комфортнее, легче и интереснее жизнь сотне миллионов людей.
«Газпромбанк» (Акционерное общество) — один из крупнейших универсальных финансовых институтов России, предоставляющий широкий спектр продуктов и услуг корпоративным и частным клиентам, финансовым институтам, институциональным и частным инвесторам.
Яндекс 360 — это виртуальное пространство, в котором собраны сервисы для работы и повседневных задач: Почта, Диск для хранения файлов, Телемост с видеозвонками, Документы, Мессенджер, Рассылки, Заметки и Календарь. Яндекс 360 помогает организовать работу как одному человеку, так и целой команде организации в рамках продуктов Яндекс 360 для бизнеса.
Аспро — разработчик программного обеспечения. С 2010 года разрабатываем облачные системы, платформы и готовые решения для бизнеса.
Яндекс — технологическая компания, которая создаёт инновационные продукты на основе машинного обучения и нейронных сетей. Команда талантливых математиков и программистов развивает самую популярную в России поисковую систему и более 85 пользовательских сервисов, которые помогают людям в повседневных заботах.
IT-компания и основной цифровой партнер торговых сетей и бизнесов X5 Group. Команда из более 3500 специалистов разрабатывает решения, которые помогают 325 тысячам сотрудников группы работать с максимальным технологическим комфортом, а миллионам покупателей быстро и удобно покупать свежие продукты.
Команда Т-Банка — это разработчики, тестировщики, SRE-инженеры, архитекторы, аналитики, продакт-менеджеры, дизайнеры и другие специалисты. Вместе они создают финтех-продукты, которыми пользуются около 40 миллионов клиентов. Т-Банк развивает ИТ-индустрию, поддерживает комьюнити и делится экспертизой.
Samokat.tech — продуктово-технологическая команда, которая делает ИТ для ритейла реального времени. От доставки продуктов и товаров для дома за 15 минут до развития нового слоя городской инфраструктуры для мгновенной доставки любых товаров – с помощью технологий.
Строят публичную облачную платформу Yandex Cloud, чтобы дать компаниям доступ к технологиям и сервисам, которые проверены нагрузками Яндекса. Продукты Yandex Cloud — это масштабируемая инфраструктура, сервисы хранения данных, инструменты машинного обучения и средства разработки.
Samokat.tech — продуктово-технологическая команда, которая делает IТ для ретейла реального времени. От доставки продуктов и товаров для дома за 15 минут до развития нового слоя городской инфраструктуры для мгновенной доставки любых товаров — с помощью технологий.
Яндекс — технологическая компания, которая создает инновационные продукты на основе машинного обучения и нейронных сетей. Команда талантливых математиков и программистов развивает самую популярную в России поисковую систему и более 85 пользовательских сервисов, которые помогают людям в повседневных заботах.
Ozon — лидирующая платформа e-commerce в России. В команде Ozon Tech 3 800 инженеров — и она продолжает расти. Десятки миллионов людей пользуются сервисами Ozon, их IT-инфраструктура управляет миллионами процессов каждый час. Микросервисы на Go и C#, в стеке технологий есть Vue.js, Swift и Kotlin, Kubernetes, Kafka, Hadoop и ClickHouse.
Cloud.ru облачный провайдер, предоставляющий облачные решения и экспертную поддержку для бизнес-задач. Атмосфера стартапа, создание инноваций, клиентоцентричный подход –– это все мы, люди Cloud.
Команда Тинькофф — это разработчики, тестировщики, SRE-инженеры, архитекторы, аналитики, продакт-менеджеры, дизайнеры и другие специалисты. Вместе они создают финтех-продукты, которыми пользуются более 38 миллионов клиентов. Тинькофф развивает IT-индустрию, поддерживает комьюнити и делится экспертизой.
Компромиссная производительность (или какой логикой руководствуются владельцы коммерческих ресурсов)
Positive Technologies — ведущий разработчик продуктов, решений и сервисов для результативной кибербезопасности, позволяющих выявлять и предотвращать атаки до того, как они причинят неприемлемый ущерб бизнесу и целым отраслям экономики. Технологический портфель компании охватывает большинство категорий средств защиты информации и продолжает расширяться. Мы создаем метапродукты — новое поколение инструментов для достижения результативной кибербезопасности с минимальным участием человека. Кроме того, Positive Technologies — первая и единственная компания из сферы кибербеза на Московской бирже.
Tarantool — middleware для эффективного создания высоконагруженных сервисов. Сочетает в себе сервер приложений, гибридное хранилище данных, а также инструменты и средства масштабирования. Производительность систем на Tarantool может достигать 1 млн транзакций в секунду.
Строят публичную облачную платформу Yandex Cloud, чтобы дать компаниям доступ к технологиям и сервисам, которые проверены нагрузками Яндекса. Продукты Yandex Cloud — это масштабируемая инфраструктура, сервисы хранения данных, инструменты машинного обучения и средства разработки.
Ozon — лидирующая платформа e-commerce в России. В команде Ozon Tech 3 800 инженеров — и она продолжает расти. Десятки миллионов людей пользуются сервисами Ozon, их IT-инфраструктура управляет миллионами процессов каждый час. Микросервисы на Go и C#, в стеке технологий есть Vue.js, Swift и Kotlin, Kubernetes, Kafka, Hadoop и ClickHouse.
Команда Яндекс 360 создает продукты, которые решают повседневные задачи миллионов пользователей: от хранения воспоминаний до деловой переписки. В Яндекс 360 входят Почта, Диск, Документы, Телемост, Календарь, Заметки и Мессенджер
Сберба́нк - российский финансовый конгломерат, крупнейший универсальный банк России и Восточной Европы.
Предоставляют полный цикл DevOps-услуг и сопутствующие программные продукты.
«Флант» — лидер российского рынка DevOps и Kubernetes. №1 контрибьютор Kubernetes из России и единственный в России сертифицированный CNCF-поставщик услуг по Kubernetes (KCSP). С 2008 года занимается созданием и обслуживанием ИТ-инфраструктуры для критичных бизнес-приложений, с 2021 года предлагает продукты собственной разработки — экосистему решений Deckhouse для надежной enterprise-инфраструктуры. В 2023 году объединились с «Экспресс 42», и сегодня компания является вендором ПО и сервисной компанией по построению DevOps-решений под ключ.
NGENIX
Postgres Professional — разработчик российской системы управления базами данных Postgres Pro. СУБД входит в Единый реестр российского программного обеспечения и выпускается в редакциях: Postgres Pro Enterprise, Postgres Pro Standard, Postgres Pro Shardman, их сертифицированные ФСТЭК версии. Специалисты компании оказывают поддержку полного цикла: аудит, помощь в миграции, техподдержку 24х7 и SLA, обучение, заказные разработки, сертификацию специалистов. По данным исследования ЦСР за 2022 год, компания возглавляет рейтинг российских разработчиков СУБД. Команда Postgres Professional также активно развивает свободно распространяемую СУБД PostgreSQL. Занимает 1 место в России и 2 — в мире по вкладу в открытый код PostgreSQL.
Маркет позволяет покупателям заказывать товары прямо из дома и получать заказы по всей стране, а партнёрам — развивать свой бизнес, повышая продажи и привлекая новых клиентов. Для этого команда Маркета строит архитектуру так, чтобы можно было быстро делать новые фичи и не ломать важные сценарии, учится выдерживать многократный рост нагрузки и не перерасходовать ресурсы, следит, чтобы сайт Маркета работал как надо. У них есть целый арсенал технологий: микросервисы и микрофронты, тыквы и gracefull degradation, отложенная обработка запросов и автоматические системы нагрузочного тестирования. Изменяют архитектуру всех сервисов Маркета и помогают продуктовым командам быстро и безопасно развиваться.
Команда Тинькофф — это разработчики, продакт-менеджеры, дизайнеры, маркетологи, аналитики, тестировщики, SRE-инженеры и другие специалисты. Вместе они создают новые и развивают существующие финтех-продукты, которыми пользуются 25 миллионов клиентов и каждый из нас.
Компания Last.Backend занимается созданием DevOps технологий и продуктов. Имеет собственную систему оркестровки контейнеров аналога kubernetes. Так же занимается DevOps акселерацией компаний, помогая в кратчайшие сроки получить качественную автоматизированную инфраструктуру под проект с дальнейшим 24/7 мониторингом.
Raft — разработчик приложений, ИИ-систем и ИТ-инфраструктуры для бизнеса. Компания проектирует решения с использованием генеративного ИИ, включая YandexGPT, ChatGTP и LLaMA, помогает с миграцией в облако, организацией CI/CD и внедрением Kubernetes. Raft работает с клиентами из сфер ИТ, медицины, финансов, логистики, ритейла, образования и фудтеха. Среди них — Microsoft, X5 Group, DNS, Amwell, «БКС Мир инвестиций» и ВТБ. Разработчик специализируется на чат-ботах, инструментах анализа речи для оценки качества обслуживания и решениях по безопасности. Raft разрабатывает инструменты на базе облачных сервисов Yandex Cloud, включая YandexGPT API, Yandex SpeechKit и Yandex SpeechSense.
МТС — одна из ведущих экосистемных компаний России. Предоставляет услуги мобильной и фиксированной связи, решения в области объединенных коммуникаций, интернета вещей, обработки данных, облачных вычислений и кибербезопасности. Штат IT-специалистов компании превышает 8 000 человек.
ГК Юзтех входит в топ-15 лидеров разработки программного обеспечения на российском рынке согласно рейтингу CNews Analytics и в топ-7 лучших IT-работодателей России в 2022 г. по версии HH и Хабр. С 2006 года ГК Юзтех осуществляет полный спектр работ в области заказной разработки ПО для своих Заказчиков в отраслях: ретейл, финансы, телеком, IТ и в государственном секторе. Несколько фактов о ГК Юзтех: • 2000+ успешных проектов; • 50+ постоянных заказчиков; • 8 офисов по всей России; • больше половины топ-20 банков России — клиенты компании; • больше половины топ-10 российских FMCG-сетей — клиенты компании; • многие корпорации из Fortune 1000 — клиенты компании; • 20+ млн. пользователей ежедневно используют программные решения ГК Юзтех; • 60% сотрудников уровня Senior.
Делают мир удобным для бизнеса.
Noones - это криптовалютный P2P Marketplace
Яндекс — технологическая компания, которая создаёт инновационные продукты на основе машинного обучения и нейронных сетей. Команда талантливых математиков и программистов развивает самую популярную в России поисковую систему и более 85 пользовательских сервисов, которые помогают людям в повседневных заботах.
Гринатом – ИТ-компания в структуре Росатом с фокусом на разработке инновационных решений для современных бизнес-процессов в атомной отрасли и за ее пределами. Мы развиваем цифровую экосистему Росатома, создаем свое ПО и обеспечиваем атомную отрасль современными ИТ-решениями, услугами и сервисами.
Яндекс Go — это суперапп, предоставляющий сервисы, связанные с передвижением по городу. Он объединяет водителей и курьеров в сервисах для заказа такси, доставки и транспортировки грузов.
Tempesta Technologies
СберМаркет (ООО «Инстамарт Технолоджис») — технологический онлайн-сервис, который помогает делать покупки не выходя из дома. Tech-команда СберМаркета создает один из самых сложных высоконагруженных e-commerce-проектов в России и делает это с любовью.
Команда Т-Банка — это разработчики, тестировщики, SRE-инженеры, архитекторы, аналитики, продакт-менеджеры, дизайнеры и другие специалисты. Вместе они создают финтех-продукты, которыми пользуются около 40 миллионов клиентов. Т-Банк развивает ИТ-индустрию, поддерживает комьюнити и делится экспертизой.
Postgres Professional — разработчик российской системы управления базами данных Postgres Pro. СУБД входит в Единый реестр российского программного обеспечения и выпускается в редакциях: Postgres Pro Enterprise, Postgres Pro Standard, Postgres Pro Shardman, их сертифицированные ФСТЭК версии. Специалисты компании оказывают поддержку полного цикла: аудит, помощь в миграции, техподдержку 24х7 и SLA, обучение, заказные разработки, сертификацию специалистов. По данным исследования ЦСР за 2022 год, компания возглавляет рейтинг российских разработчиков СУБД. Команда Postgres Professional также активно развивает свободно распространяемую СУБД PostgreSQL. Занимает 1 место в России и 2 — в мире по вкладу в открытый код PostgreSQL.
Vi.Tech — это дочерняя компания ВсеИнструменты.ру, в которой делают IT-продукты для одного из крупнейших игроков на рынке e-commerce.
МТС — одна из ведущих экосистемных компаний России. Предоставляет услуги мобильной и фиксированной связи, решения в области объединенных коммуникаций, интернета вещей, обработки данных, облачных вычислений и кибербезопасности. Штат IT-специалистов компании превышает 8 000 человек.
Гринатом – ИТ-компания в структуре Росатом с фокусом на разработке инновационных решений для современных бизнес-процессов в атомной отрасли и за ее пределами. Мы развиваем цифровую экосистему Росатома, создаем свое ПО и обеспечиваем атомную отрасль современными ИТ-решениями, услугами и сервисами.
Команда Т-Банка — это разработчики, тестировщики, SRE-инженеры, архитекторы, аналитики, продакт-менеджеры, дизайнеры и другие специалисты. Вместе они создают финтех-продукты, которыми пользуются около 40 миллионов клиентов. Т-Банк развивает ИТ-индустрию, поддерживает комьюнити и делится экспертизой.
Грамант
«Яндекс.Метрика» — бесплатный интернет-сервис компании Яндекс, предназначенный для оценки посещаемости веб-сайтов и анализа поведения пользователей. По данным w3techs.com, в 2019 году Яндекс. Метрика являлась третьей по размеру системой веб-аналитики в Европе. По данным «Лаборатории Касперского», в 2021-2022 годах она была самым распространенным трекинговым сервисом в России и странах СНГ.
Postgres Professional — разработчик российской системы управления базами данных Postgres Pro. СУБД входит в Единый реестр российского программного обеспечения и выпускается в редакциях: Postgres Pro Enterprise, Postgres Pro Standard, Postgres Pro Shardman, их сертифицированные ФСТЭК версии. Специалисты компании оказывают поддержку полного цикла: аудит, помощь в миграции, техподдержку 24х7 и SLA, обучение, заказные разработки, сертификацию специалистов. По данным исследования ЦСР за 2022 год, компания возглавляет рейтинг российских разработчиков СУБД. Команда Postgres Professional также активно развивает свободно распространяемую СУБД PostgreSQL. Занимает 1 место в России и 2 — в мире по вкладу в открытый код PostgreSQL.
