Pull to refresh
0
0
Андрей Асеев @bsdw

User

Send message

Немного внутренностей словарей в CPython (и PyPy)

Reading time9 min
Views52K
Внутреннее устройство словарей в Python не ограничивается одними лишь бакетами и закрытым хешированием. Это удивительный мир разделяемых ключей, кеширования хешей, DKIX_DUMMY и быстрого сравнения, которое можно сделать ещё быстрее (ценой бага с примерной вероятностью в 2^-64).

Если вы не знаете количество элементов в только что созданном словаре, сколько памяти расходуется на каждый элемент, почему теперь (CPython 3.6 и далее) словарь реализован двумя массивами и как это связано с сохранением порядка вставки, или просто не смотрели презентацию Raymond Hettinger «Modern Python Dictionaries A confluence of a dozen great ideas». Тогда добро пожаловать.


Впрочем, люди знакомые с лекцией, тоже могут найти немного подробностей и свежей информации, и для совсем новичков, не знакомых с бакетами и закрытым хешированием, статья тоже будет интересна.
Total votes 24: ↑24 and ↓0+24
Comments7

Вышел uvloop — продвинутая реализация цикла событий для asyncio в Python

Reading time1 min
Views43K
В стандартной библиотеке Python 3.4 в своё время появился модуль asyncio, позволивший удобно и быстро писать асинхронный код. А уже к Python 3.5 в синтаксис были добавлены конструкции async/await, окончательно оформившие асинхронность «из коробки» как красивую и гармоничную часть языка.



Хотя asyncio сам по себе и позволяет писать высоконагруженные веб-приложения, оптимизация производительности не была приоритетом при создании модуля.

Один из авторов упомянутого PEP-492 (async/await) Юрий Селиванов (на Хабре — 1st1, его твиттер) взялся за разработку альтернативной реализации цикла событий для asyncio — uvloop. Вчера вышла первая альфа-версия модуля, о чём автор написал развёрнутый пост.

Если вкратце, то uvloop работает примерно в 2 раза быстрее Node.js и практически не уступает программам на Go.
Под катом небольшая выжимка из записи в блоге
Total votes 34: ↑32 and ↓2+30
Comments60

Система непересекающихся множеств и её применения

Reading time10 min
Views70K
Добрый день, Хабрахабр. Это еще один пост в рамках моей программы по обогащению базы данных крупнейшего IT-ресурса информацией по алгоритмам и структурам данных. Как показывает практика, этой информации многим не хватает, а необходимость встречается в самых разнообразных сферах программистской жизни.
Я продолжаю преимущественно выбирать те алгоритмы/структуры, которые легко понимаются и для которых не требуется много кода — а вот практическое значение сложно недооценить. В прошлый раз это было декартово дерево. В этот раз — система непересекающихся множеств. Она же известна под названиями disjoint set union (DSU) или Union-Find.

Условие


Поставим перед собой следующую задачу. Пускай мы оперируем элементами N видов (для простоты, здесь и далее — числами от 0 до N-1). Некоторые группы чисел объединены в множества. Также мы можем добавить в структуру новый элемент, он тем самым образует множество размера 1 из самого себя. И наконец, периодически некоторые два множества нам потребуется сливать в одно.

Формализируем задачу: создать быструю структуру, которая поддерживает следующие операции:

MakeSet(X) — внести в структуру новый элемент X, создать для него множество размера 1 из самого себя.
Find(X) — возвратить идентификатор множества, которому принадлежит элемент X. В качестве идентификатора мы будем выбирать один элемент из этого множества — представителя множества. Гарантируется, что для одного и того же множества представитель будет возвращаться один и тот же, иначе невозможно будет работать со структурой: не будет корректной даже проверка принадлежности двух элементов одному множеству if (Find(X) == Find(Y)).
Unite(X, Y) — объединить два множества, в которых лежат элементы X и Y, в одно новое.

На рисунке я продемонстрирую работу такой гипотетической структуры.


Как такое сделать и зачем оно нужно
Total votes 114: ↑109 and ↓5+104
Comments29

Свой асинхронный tcp-сервер за 15 минут с подробным разбором

Reading time7 min
Views79K

Ранее я представил пару небольших постов о потенциальной роли Spring Boot 2 в реактивном программировании. После этого я получил ряд вопросов о том, как работают асинхронные операции в программировании в целом. Сегодня я хочу разобрать, что такое Non-blocking I/O и как применить это знание для создания небольшого tcp–сервера на python, который сможет обрабатывать множество открытых и тяжелых (долгих) соединений в один поток. Знание python не требуется: все будет предельно просто со множеством комментариев. Приглашаю всех желающих!
Читать дальше →
Total votes 22: ↑19 and ↓3+16
Comments17

Пулы потоков: ускоряем NGINX в 9 и более раз

Reading time15 min
Views87K
Как известно, для обработки соединений NGINX использует асинхронный событийный подход. Вместо того, чтобы выделять на каждый запрос отдельный поток или процесс (как это делают серверы с традиционной архитектурой), NGINX мультиплексирует обработку множества соединений и запросов в одном рабочем процессе. Для этого применяются сокеты в неблокирующем режиме и такие эффективные методы работы с событиями, как epoll и kqueue.

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

Каждый процесс расходует память и каждое переключение между ними требует дополнительных циклов процессора, а также приводит к вымыванию L-кэшей

У медали есть и обратная сторона. Главной проблемой асинхронного подхода, а лучше даже сказать «врагом» — являются блокирующие операции. И, к сожалению, многие авторы сторонних модулей, не понимая принципов функционирования NGINX, пытаются выполнять блокирующие операции в своих модулях. Такие операции способны полностью убить производительность NGINX и их следует избегать любой ценой.

Но даже в текущей реализации NGINX не всегда возможно избежать блокировок. И для решения данной проблемы в NGINX версии 1.7.11 был представлен новый механизм «пулов потоков». Что это такое и как его применять разберем далее, а для начала познакомимся с нашим врагом в лицо.
Читать дальше →
Total votes 72: ↑71 and ↓1+70
Comments58

Разница между nginx и apache с примерами

Reading time26 min
Views108K

Во время собеседований на роль linux/unix администратора во многих IT-компаниях спрашивают, что такое load average, чем nginx отличается от apache httpd и что такое fork. В этой статье я постараюсь объяснить, что рассчитывают услышать в ответ на эти вопросы, и почему.


Здесь важно очень хорошо понимать основы администрирования. В идеальной ситуации при постановке задачи системному администратору выставляют ряд требований. Если же ситуация не идеальная, то, по сути, требование к администратору одно: «Хочу, чтобы всё работало». Иными словами, сервис должен быть доступен 24/7 и, если какое-то решение не удовлетворяет этим требованиям (масштабирование и отказоустойчивость относятся к доступности), то можно сказать, что администратор плохо сделал свою работу. Но если разные решения двух администраторов работают 24/7, как понять, какое из них лучше?


Хороший системный администратор при выборе решения при заданных требованиях ориентируется на два условия: минимальное потребление ресурсов и их сбалансированное распределение.


Вариант, когда одному специалисту нужно 10 серверов для выполнения задания, а второму всего 2, мы рассматривать не будем, что тут лучше – очевидно. Далее под ресурсами я буду понимать ЦПУ (cpu), ОЗУ (ram) и диск (hdd).


Давайте рассмотрим ситуацию: один администратор создал решение, которое требует 10% cpu, 5% ram и 10% hdd от всего вашего оборудования, а второй использовал для этого 1% cpu, 40% ram и 20% hdd. Какое из этих решений лучше? Тут все становится уже не так очевидно. Поэтому хороший администратор всегда должен уметь грамотно подобрать решение, исходя из имеющихся ресурсов.


Читать дальше →
Total votes 72: ↑69 and ↓3+66
Comments73

Неразбериха с Boeing 737 MAX: анализ возможных причин аварий

Reading time40 min
Views71K
image

«Столкновение с землёй в управляемом полёте» (Controlled Flight into Terrain) — это авиационный термин, обозначающий аварию нормально функционирующего самолёта из-за того, что пилоты были чем-то отвлечены или дезориентированы. Настоящий кошмар. По моим оценкам, ещё хуже столкновение с землёй в автоматизированном полёте, когда система управления самолётом заставляет его совершать пикирование в землю, несмотря на отчаянные попытки экипажа спасти ситуацию. Такова предполагаемая причина двух недавних аварий новых самолётов Boeing 737 MAX 8. Я попытался разобраться, как могли произойти эти инциденты.

Примечание: изучение катастроф MAX 8 находится на раннем этапе, поэтому многое из статьи основано на данных из непрямых источников, другими словами, на утечках и слухах, а также на рассуждениях тех людей, которые знают или не знают, о чём говорят. Так что учитывайте это, если решите продолжить чтение.

Аварии


Ранним утром 29 октября 2018 года рейс 610 авиакомпании Lion Air вылетел из Джакарты (Индонезия) с 189 людьми на борту. Это был новый, эксплуатировавшийся всего четыре месяца 737 MAX 8 — последняя модель линейки самолётов Boeing, созданной ещё в 1960-х. Взлёт и подъём до высоты примерно 1 600 футов (480 метров) был нормальным, после чего пилоты убрали закрылки (элементы крыла, повышающие подъёмную силу при малых скоростях). В этот момент воздушное судно неожиданно снизилось до 900 футов (270 метров). В радиопереговорах с авиадиспетчерами пилоты сообщали о «проблеме с системой управления» и спрашивали данные о своей высоте и скорости, отображаемых на экранах радаров диспетчеров.
Читать дальше →
Total votes 126: ↑118 and ↓8+110
Comments429

Асинхронность в программировании

Reading time26 min
Views91K

В области разработки высоконагруженных многопоточных или распределенных приложений часто возникают дискуссии об асинхронном программировании. Сегодня мы подробно погрузимся в асинхронность и изучим, что это такое, когда она возникает, как влияет на код и язык программирования, которым мы пользуемся. Разберемся, зачем нужны Futures и Promises и затронем корутины и операционные системы. Это сделает компромиссы, возникающие во время разработки ПО, более явными.


В основе материала — расшифровка доклада Ивана Пузыревского, преподавателя школы анализа данных Яндекса.


Читать дальше →
Total votes 71: ↑67 and ↓4+63
Comments70

Знай сложности алгоритмов

Reading time2 min
Views988K
Эта статья рассказывает о времени выполнения и о расходе памяти большинства алгоритмов используемых в информатике. В прошлом, когда я готовился к прохождению собеседования я потратил много времени исследуя интернет для поиска информации о лучшем, среднем и худшем случае работы алгоритмов поиска и сортировки, чтобы заданный вопрос на собеседовании не поставил меня в тупик. За последние несколько лет я проходил интервью в нескольких стартапах из Силиконовой долины, а также в некоторых крупных компаниях таких как Yahoo, eBay, LinkedIn и Google и каждый раз, когда я готовился к интервью, я подумал: «Почему никто не создал хорошую шпаргалку по асимптотической сложности алгоритмов? ». Чтобы сохранить ваше время я создал такую шпаргалку. Наслаждайтесь!
Читать дальше →
Total votes 312: ↑296 and ↓16+280
Comments99

Поиск с помощью регулярных выражений может быть простым и быстрым

Reading time21 min
Views48K
В этой статье мы рассмотрим два способа поиска с помощью регулярных выражений. Один широко распространён и используется в стандартных интерпретаторах многих языков. Второй мало где применяется, в основном в реализациях awk и grep. Оба подхода сильно различаются по своей производительности:



В первом случае поиск занимает A?nAn времени, во втором — An.

Степени обозначают повторяемость строк, то есть A?3A3 — это то же самое, что и A?A?A?AAA. Графики отражают время, требуемое для поиска через регулярные выражения.

Обратите внимание, что в Perl для поиска строки из 29 символов требуется более 60 секунд. А при втором методе — 20 микросекунд. Это не ошибка. При поиске 29-символьной строки Thompson NFA работает примерно в миллион раз быстрее. Если нужно найти 100-символьную строку, то Thompson NFA справится менее чем за 200 микросекунд, а Perl понадобится более 1015 лет. Причём он взят лишь для примера, во многих других языках наблюдается та же картина — в Python, PHP, Ruby и т. д. Ниже мы рассмотрим этот вопрос более детально.

Наверняка вам трудно поверить приведённым данным. Если вы работали с Perl, то вряд ли подмечали за ним низкую производительность при работе с регулярными выражениями. Дело в том, что в большинстве случаев Perl обращается с ними достаточно быстро. Однако, как следует из графика, можно столкнуться с так называемыми патологическими регулярными выражениями, на которых Perl начинает буксовать. В то же время у Thompson NFA такой проблемы нет.

Возникает логичный вопрос: а почему бы в Perl не использовать метод Thompson NFA? Это возможно и следует делать, и об этом пойдёт далее речь.
Читать дальше →
Total votes 85: ↑79 and ↓6+73
Comments14

Майкл Стоунбрейкер — Hadoop на распутье

Reading time11 min
Views18K
[@tsafin — Обладателя премии Тьюринга Майкла Стоунбрейкера представлять не надо, он и его студенты из Беркли и MIT создали, по ощущениям, большую часть реляционных и нереляционных баз данных за последние пару десятилетий. Ingres и Postgres, C-Store и Vertica, H-Store и VoltDB – вот лишь малая часть проектов и фирм, на который Майкл и его студенты повлияли напрямую, а ведь еще есть множество форков и деривативов…

Т.о. когда он критикует что-то, будь то NoSQL или Hadoop, то индустрии стоит, как минимум, прислушаться, а лучше попытаться измениться.

Мне показалось интересной его точка зрения на Hadoop, высказанная в статьях 2012 и 2014 года, и было интересно проследить развитие точки зрения «классика» за такой короткий промежуток времени.

Первую статью «Possible Hadoop Trajectories», опубликованную в «Comunications of ACM» http://cacm.acm.org/blogs/blog-cacm/149074-possible-hadoop-trajectories/fulltext, Стоунбрейкер написал в мае 2012 года в соавторстве с Джереми Кепнером (Jeremy Kepner), который в тот момент работал как старший технический персонал в MIT, и как исследователь в MIT Mathematics Department и MIT Computer Science and AI Lab. Эта статья, написанная в соавторстве, кажется более дерзкой и задорной, по сравнению со второй, написанной уже им самим двумя годами позже (да и, чего уж там, первая статья написана IMHO в лучшем стиле), но я публикую их в связке, т.к. контекст за прошедшие пару лет сильно изменился, и было бы нечестно по отношению к экосистеме Hadoop/HDFS оставлять это незамеченным.
Читать дальше →
Total votes 16: ↑16 and ↓0+16
Comments10

Эра NoSQL позади

Reading time5 min
Views55K

Новый тренд на HighLoad++ — множество докладов об использовании оперативной памяти. Слово Константину Осипову, разработчику платформы Tarantool, автору доклада «Что особенного в СУБД для данных в оперативной памяти».

Ты отвечал в MySQL за производительность, как так получилось, что ты решил разрабатывать свою СУБД?
В MySQL я руководил одной из команд разработки сервера, за производительность там отвечали все.

MySQL по многим параметрам был работой мечты, но, к сожалению после того, как мы стали частью Oracle, многое изменилось.

Несколько моих коллег ушли в MariaDB, кто-то основал свою компанию (SeveralNines, FromDual). Я никогда не чувствовал себя «недогруженным», а с уходом многих ключевых разработчиков работа вообще превратилась в марафон по передаче знаний. Сопротивление поглощению, желание начать всё с чистого листа, бунт против медленного принятия решений большой компанией, нежелание по разным причинам уезжать в США, в конце концов, хорошее предложение от Mail.Ru, которому к этому моменту уже было около года — и я ушёл.

Если бы знал, куда ухожу, ещё десять раз подумал бы. Иногда вообще не было веры, что удастся сделать что-то полезное, чем будут пользоваться за пределами Mail.Ru, да и сейчас Tarantool очень далёк пока от «идеальной СУБД».
Читать дальше →
Total votes 48: ↑35 and ↓13+22
Comments30

Дюк, вынеси мусор! — 1. Введение

Reading time13 min
Views210K


Наверняка вы уже читали не один обзор механизмов сборки мусора в Java и настройка таких опций, как Xmx и Xms, превратилась для вас в обычную рутину. Но действительно ли вы в деталях понимаете, что происходит под капотом вашей виртуальной машины в тот момент, когда приходит время избавиться от ненужных объектов в памяти и ваш идеально оптимизированный метод начинает выполняться в несколько раз дольше положенного? И знаете ли вы, какие возможности предоставляют вам последние версии Java для оптимизации ответственной работы по сборке мусора, зачастую сильно влияющей на производительность вашего приложения?

Попробуем в нескольких статьях пройти путь от описания базовых идей, лежащих в основе всех сборщиков мусора, до разбора алгоритмов работы и возможностей тонкой настройки различных сборщиков Java HotSpot VM (вы ведь знаете, что таких сборщиков четыре?). И самое главное, рассмотрим, каким образом эти знания можно использовать на практике.
Узнать
Total votes 36: ↑36 and ↓0+36
Comments7

19 советов по повседневной работе с Git

Reading time14 min
Views285K


Если вы регулярно используете Git, то вам могут быть полезны практические советы из этой статьи. Если вы в этом пока новичок, то для начала вам лучше ознакомиться с Git Cheat Sheet. Скажем так, данная статья предназначена для тех, у кого есть опыт использования Git от трёх месяцев. Осторожно: траффик, большие картинки!

Содержание:
  1. Параметры для удобного просмотра лога
  2. Вывод актуальных изменений в файл
  3. Просмотр изменений в определённых строках файла
  4. Просмотр ещё не влитых в родительскую ветку изменений
  5. Извлечение файла из другой ветки
  6. Пара слов о ребейзе
  7. Сохранение структуры ветки после локального мержа
  8. Исправление последнего коммита вместо создания нового
  9. Три состояния в Git и переключение между ними
  10. Мягкая отмена коммитов
  11. Просмотр диффов для всего проекта (а не по одному файлу за раз) с помощью сторонних инструментов
  12. Игнорирование пробелов
  13. Добавление определённых изменений из файла
  14. Поиск и удаление старых веток
  15. Откладывание изменений определённых файлов
  16. Хорошие примечания к коммиту
  17. Автодополнения команд Git
  18. Создание алиасов для часто используемых команд
  19. Быстрый поиск плохого коммита

Читать дальше →
Total votes 152: ↑149 and ↓3+146
Comments62

Как работает реляционная БД

Reading time51 min
Views534K
Реляционные базы данных (РБД) используются повсюду. Они бывают самых разных видов, от маленьких и полезных SQLite до мощных Teradata. Но в то же время существует очень немного статей, объясняющих принцип действия и устройство реляционных баз данных. Да и те, что есть — довольно поверхностные, без особых подробностей. Зато по более «модным» направлениям (большие данные, NoSQL или JS) написано гораздо больше статей, причём куда более глубоких. Вероятно, такая ситуация сложилась из-за того, что реляционные БД — вещь «старая» и слишком скучная, чтобы разбирать её вне университетских программ, исследовательских работ и книг.

На самом деле, мало кто действительно понимает, как работают реляционные БД. А многие разработчики очень не любят, когда они чего-то не понимают. Если реляционные БД используют порядка 40 лет, значит тому есть причина. РБД — штука очень интересная, поскольку в ее основе лежат полезные и широко используемые понятия. Если вы хотели бы разобраться в том, как работают РБД, то эта статья для вас.
Читать дальше →
Total votes 232: ↑229 and ↓3+226
Comments134

MapReduce 2.0. Какой он современный цифровой слон?

Reading time10 min
Views28K


Если ты ИТшник, то нельзя просто так взять и выйти на работу 2-го января: пересмотреть 3-ий сезон битвы экстрасенсов или запись программы «Гордон» на НТВ (дело умственных способностей вкуса).
Нельзя потому, что у других сотрудников обязательно будут для тебя подарки: у секретарши закончился кофе, у МП — закончились дедлайны, а у администратора баз данных — амнезия память.
Оказалось, что инженеры из команды Hadoop тоже любят побаловать друг друга новогодними сюрпризами.

2008


2 января. Упуская подробное описание эмоционально-психологического состояния лиц, участвующих в описанных ниже событиях, сразу перейду к факту: поставлен таск MAPREDUCE-279 «Map-Reduce 2.0». Оставив шутки про число, обращу внимание, что до 1-ой стабильной версии Hadoop остается чуть менее 4 лет.

За это время проект Hadoop пройдет эволюцию из маленького инновационного снежка, запущенного в 2005, в большой снежный com ком, надвигающийся на ИТ, в 2012.
Ниже мы предпримем попытку разобраться, какое же значение январский таск MAPREDUCE-279 играл (и, уверен, еще сыграет в 2013) в эволюции платформы Hadoop.
...
Total votes 39: ↑33 and ↓6+27
Comments11

Как за месяц сильно прокачаться в Data Science

Reading time12 min
Views43K
Привет, хабр!



Меня зовут Глеб, я долгое время работаю в ритейловой аналитике и сейчас занимаюсь применением машинного обучения в данной области. Не так давно я познакомился с ребятами из MLClass.ru, которые за очень короткий срок довольно сильно прокачали меня в области Data Science. Благодаря им, буквально за месяц я стал активно сабмитить на kaggle. Поэтому данная серия публикаций будет описывать мой опыт изучения Data Science: все ошибки, которые были допущены, а также ценные советы, которые мне передали ребята. Сегодня я расскажу об опыте участия в соревновании The Analytics Edge (Spring 2015). Это моя первая статья — не судите строго.
Читать дальше →
Total votes 29: ↑26 and ↓3+23
Comments16

Краткая история масштабирования LinkedIn

Reading time9 min
Views26K
Примечание переводчика: Мы в «Латере» занимаемся созданием биллинга для операторов связи. Мы будем писать об особенностях системы и деталях ее разработки в нашем блоге на Хабре (например, об обеспечении отказоустойчивости), но почерпнуть что-то интересное можно и из опыта других компаний. Сегодня мы представляем вашему вниманию адаптированный перевод заметки главного инженера LinkedIn Джоша Клемма о процессе масштабирования инфраструктуры социальной сети.



Сервис LinkedIn был запущен в 2003 году с целью создания и поддержания сети деловых контактов и расширения возможностей поиска работы. За первую неделю в сети зарегистрировалось 2 700 человек. Спустя несколько лет число продуктов, клиентская база и нагрузка на серверы заметно выросли.

Сегодня в LinkedIn насчитывается более 350 миллионов пользователей по всему миру. Мы проверяем десятки тысяч веб-страниц каждую секунду, каждый день. На мобильные устройства сейчас приходится более 50% нашего трафика по всему миру. Пользователи запрашивают данные из наших бэкенд-систем, которые, в свою очередь, обрабатывают по несколько миллионов запросов в секунду. Как же мы этого добились?
Читать дальше →
Total votes 31: ↑29 and ↓2+27
Comments5

Тюним память и сетевой стек в Linux: история перевода высоконагруженных серверов на свежий дистрибутив

Reading time10 min
Views94K
image

До недавнего времени в Одноклассниках в качестве основного Linux-дистрибутива использовался частично обновлённый OpenSuSE 10.2. Однако, поддерживать его становилось всё труднее, поэтому с прошлого года мы перешли к активной миграции на CentOS 7. На подготовительном этапе перехода для CentOS были отработаны все внутренние процедуры, подготовлены конфиги и политики настройки (мы используем CFEngine). Поэтому сейчас во многих случаях миграция с одного дистрибутива на другой заключается в установке ОС через kickstart и развёртывании приложения с помощью системы деплоя нашей разработки — всё остальное осуществляется без участия человека. Так происходит во многих случаях, хотя и не во всех.

Но с самыми большими проблемами мы столкнулись при миграции серверов раздачи видео. На их решение у нас ушло полгода.
Читать дальше →
Total votes 110: ↑104 and ↓6+98
Comments73

Почему вы никогда не должны говорить «никогда»

Reading time7 min
Views56K
Эта моя публикация чуть более чем полностью является ответом на перевод статьи «Почему вы никогда не должны использовать MongoDB». Статья, которая, по сути, рекомендует держаться подальше от MongoDB, является самой заплюсованной в хабе. И это звучит как приговор. Поэтому логично либо хаб закрыть и больше никогда не читать, либо написать ещё более рейтинговое опровержение. Конечно же, я выбрал второй вариант, рискуя своим рейтингом и кармой (ввиду крайней холиварности в комментах).

image
Картинка самоиронии

Читать дальше →
Total votes 136: ↑106 and ↓30+76
Comments211

Information

Rating
Does not participate
Location
Москва, Москва и Московская обл., Россия
Registered
Activity