В статье «Делаем современное веб-приложение с нуля» я рассказал в общих чертах, как выглядит архитектура современных высоконагруженных веб-приложений, и собрал для демонстрации простейшую реализацию такой архитектуры на стеке из нескольких предельно популярных и простых технологий и фреймворков. Мы построили single page application с server side rendering, поддерживающее просмотр неких «карточек», набранных в Markdown, и навигацию между ними.

В этой статье я затрону чуть более сложную и интересную (как минимум мне, разработчику команды поиска) тему: полнотекстовый поиск. Мы добавим в наш контейнерный рай ноду Elasticsearch, научимся строить индекс и делать поиск по контенту, взяв в качестве тестовых данных описания пяти тысяч фильмов из TMDB 5000 Movie Dataset. Также мы научимся делать поисковые фильтры и копнём совсем немножко в сторону ранжирования.

Вы вероятно слышали о Дэвиде Хаффмане и его популярном алгоритме сжатия. Если нет, то поищите информацию в интернете — в этой статье я не буду вас грузить историей или математикой. Сегодня я хочу просто попытаться показать вам практический пример применения алгоритма к символьной строке.

От переводчика: данный текст даётся с незначительными сокращениями по причине местами излишней «разжёванности» материала. Автор абсолютно справедливо предупреждает, что отдельные темы покажутся чересчур простыми или общеизвестными. Тем не менее, лично мне этот текст помог упорядочить имеющиеся знания по анализу сложности алгоритмов. Надеюсь, что он будет полезен и кому-то ещё.
Из-за большого объёма оригинальной статьи я разбила её на части, которых в общей сложности будет четыре.
Я (как всегда) буду крайне признательна за любые замечания в личку по улучшению качества перевода.

Введение

Многие современные программисты, пишущие классные и широко распространённые программы, имеют крайне смутное представление о теоретической информатике. Это не мешает им оставаться прекрасными творческими специалистами, и мы благодарны за то, что они создают.

Тем не менее, знание теории тоже имеет свои преимущества и может оказаться весьма полезным. В этой статье, предназначенной для программистов, которые являются хорошими практиками, но имеют слабое представление о теории, я представлю один из наиболее прагматичных программистских инструментов: нотацию «большое О» и анализ сложности алгоритмов. Как человек, который работал как в области академической науки, так и над созданием коммерческого ПО, я считаю эти инструменты по-настоящему полезными на практике. Надеюсь, что после прочтения этой статьи вы сможете применить их к собственному коду, чтобы сделать его ещё лучше. Также этот пост принесёт с собой понимание таких общих терминов, используемых теоретиками информатики, как «большое О», «асимптотическое поведение», «анализ наиболее неблагоприятного случая» и т.п.

Эта статья рассказывает о времени выполнения и о расходе памяти большинства алгоритмов используемых в информатике. В прошлом, когда я готовился к прохождению собеседования я потратил много времени исследуя интернет для поиска информации о лучшем, среднем и худшем случае работы алгоритмов поиска и сортировки, чтобы заданный вопрос на собеседовании не поставил меня в тупик. За последние несколько лет я проходил интервью в нескольких стартапах из Силиконовой долины, а также в некоторых крупных компаниях таких как Yahoo, eBay, LinkedIn и Google и каждый раз, когда я готовился к интервью, я подумал: «Почему никто не создал хорошую шпаргалку по асимптотической сложности алгоритмов? ». Чтобы сохранить ваше время я создал такую шпаргалку. Наслаждайтесь!

В июле и августе 2020 года я, с подачи Григория Петрова, проводил для компании Evrone технические интервью на позицию Senior Golang Backend developer. И, видимо, буду вынужден продолжать проводить, о чём ниже.

Задача формулировалась как «найти человека, который сможет задать и поддерживать высокий уровень профессионализма в применении языка Go». То есть, сформулирована она была по-человечески, перевод на канцелярит — мой. Под эту задачу я сформировал новый опросник вместо того, которым пользовался несколько лет — старый был с жестким закосом под DevOps. Методику, которой я пользуюсь для создания опросников и количественной оценки соответствия кандидатов, я излагал в своем докладе «Техническое интервью как инженерная задача» на конференции Saint TeamLead 2019.

И вот что я хочу сказать вам, коллеги: вы меня огорчаете.

Присоединяйтесь к нам онлайн 6 февраля: поделимся опытом использования DDD в реальных условиях и поговорим, с какими проблемами сталкиваемся, как их решаем и какие преимущества можно получить.

Мы будем на связи в 19:00!

Всем привет! Я руковожу командой антиспама в Mail.ru Group, а также несколькими группами по машинному обучению. Тема этой статьи — саморазвитие для тимлидов/руководителей, но на самом деле многие техники и рецепты совершенно не зависят от роли. Для меня этот вопрос очень актуален, так как машинное обучение развивается крайне стремительно, и чтобы хотя бы быть в теме, надо потратить уйму времени. Поэтому вопрос, как и на что тратить время для развития, стоит достаточно остро.

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

Задавались ли вы когда-нибудь вопросом о том, почему размер Docker-контейнера, содержащего всего одно приложение, может находиться в районе 400 Мб? Или, может быть, вас беспокоили немаленькие размеры образа Docker, содержащего единственный бинарник размером в несколько десятков Мб?



Автор статьи, перевод которой мы сегодня публикуем, хочет разобрать основные факторы, влияющие на размеры контейнеров Docker. Он, кроме того, собирается поделиться рекомендациями по уменьшению размеров контейнеров.

Дорогие товарищи инженеры, сообщество Метархия представляет вашему вниманию современный курс по Node.js, который включает глубокий разбор всех возможностей и аспектов платформы. Основной упор делается на то, как создавать надежные высоконагруженные сервера приложений и API без привязки к конкретному фреймворку и даже протоколу, т.е. абстрагировать бизнес-логику в отдельный слой. К лекциям прикреплено множество примеров кода, демонстрирующих гибкую структуру приложений и архитектурные приемы, в том числе работу с СУБД через слой доступа к данным, создание интерактивных приложений на вебсокетах, обеспечение безопасности, Graceful shutdown, межпроцессовое взаимодействие, предотвращение утечек памяти, масштабирование и кластеризацию при помощи процессов и потоков. На текущий момент в курсе 38 лекций (около 35 и ½ часов видео), 37 репозиториев с примерами кода, 4 PDF со слайдами. Перед основной частью курса по Node.js нужно сначала освоить хоть частично курс по асинхронному программированию.

Пол Грэм — один из самых уважаемых людей среди ИТишников, основателей и инвесторов. Он первоклассный программист (написал два языка программирования), хакер, создатель дерзкого акселератора Y Combinator, философ. Своими помыслами и разумом Пол Грэм врывается в широкий спектр областей: от прогнозирования развития языков программирования на сто лет вперед до человеческих качеств и способов починить/хакнуть экономику. А ещё он осознает важность того, чтобы формулировать свои мысли в текст и делиться ими с окружающими.

Когда в 2015 году я начал читать Пола Грэма мой взгляд на жизнь поменялся. Я считаю его эссе одними из самых важных текстов, которые стоит прочитать все как можно раньше, чтобы сформировать у себя мышление, способ рассуждения и изложения мыслей.

Первую подборку переводов эссе Пола Грэма меня вдохновили сделать коллеги из tceh.com (60 переводов из 176). Вторую — Edison Software (125 переводов). Третью — PhilTech-акселератор (134 перевода и еще несколько в процессе). Потом был период (2017, 2018 и 2019), когда Пол Грэм не писал эссе (а занимался с детьми), а только немного в Твиттер и дал одно видео-интервью для стартап-школы. Но в конце 2019 и начале 2020 года он вновь стал публиковать глубокие тексты об которые интересно подумать. Предлагаю вашему вниманию ссылки на новые переводы (upd с прошлой подборки) и полный список всех эссе.

Novelty and Heresy (Да здравствует ересь!)
The Lesson to Unlearn (Вредные уроки)
The Bus Ticket Theory of Genius (Теория навязчивых идей)

Five Questions about Language Design (Пять вопросов о проектировании языков программирования)
What Made Lisp Different (Что сделало Lisp особенным)
After the Ladder (На смену корпоративной лестнице)
What I’ve Learned from Hacker News (Чему я научился у Hacker News)
Snapshot: Viaweb, June 1998 (разбор полетов: Viaweb июня 1998 года)
Some Heroes (Мои кумиры)
The Equity Equation (Как делить доли в стартапе)

Bash-скрипты: начало
Bash-скрипты, часть 2: циклы
Bash-скрипты, часть 3: параметры и ключи командной строки
Bash-скрипты, часть 4: ввод и вывод
Bash-скрипты, часть 5: сигналы, фоновые задачи, управление сценариями
Bash-скрипты, часть 6: функции и разработка библиотек
Bash-скрипты, часть 7: sed и обработка текстов
Bash-скрипты, часть 8: язык обработки данных awk
Bash-скрипты, часть 9: регулярные выражения
Bash-скрипты, часть 10: практические примеры
Bash-скрипты, часть 11: expect и автоматизация интерактивных утилит

Сегодня поговорим о bash-скриптах. Это — сценарии командной строки, написанные для оболочки bash. Существуют и другие оболочки, например — zsh, tcsh, ksh, но мы сосредоточимся на bash. Этот материал предназначен для всех желающих, единственное условие — умение работать в командной строке Linux.

Два предыдущих цикла статей были посвящены изоляции и многоверсионности и журналированию.

В этом цикле мы поговорим о блокировках (locks). Я буду придерживаться этого термина, но в литературе может встретиться и другой: замóк.

Цикл будет состоять из четырех частей:

1. Блокировки отношений (эта статья);
2. Блокировки строк;
3. Блокировки других объектов и предикатные блокировки;
4. Блокировки в оперативной памяти.

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

Читайте и другие серии.

Индексы:

1. Механизм индексирования;
2. Интерфейс метода доступа, классы и семейства операторов;
3. Hash;
4. B-tree;
5. GiST;
6. SP-GiST;
7. GIN;
8. RUM;
9. BRIN;
10. Bloom.

Изоляция и многоверсионность:

1. Изоляция, как ее понимают стандарт и PostgreSQL;
2. Слои, файлы, страницы — что творится на физическом уровне;
3. Версии строк, виртуальные и вложенные транзакции;
4. Снимки данных и видимость версий строк, горизонт событий;
5. Внутристраничная очистка и HOT-обновления;
6. Обычная очистка (vacuum);
7. Автоматическая очистка (autovacuum);
8. Переполнение счетчика транзакций и заморозка.

Журналирование:

1. Буферный кеш;
2. Журнал предзаписи — как устроен и как используется при восстановлении;
3. Контрольная точка и фоновая запись — зачем нужны и как настраиваются;
4. Настройка журнала — уровни и решаемые задачи, надежность и производительность.

В прошлый раз мы говорили о блокировках на уровне объектов, в частности — о блокировках отношений. Сегодня посмотрим, как в PostgreSQL устроены блокировки строк и как они используются вместе с блокировками объектов, поговорим про очереди ожидания и про тех, кто лезет без очереди.

Блокировки строк

Устройство

Напомню несколько важных выводов из прошлой статьи.

• Блокировка должна существовать где-то в разделяемой памяти сервера.
• Чем выше гранулярность блокировок, тем меньше конкуренция (contention) среди одновременно работающих процессов.
• С другой стороны, чем выше гранулярность, тем больше места в памяти занимают блокировки.

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

Есть разные пути решения этой проблемы. В некоторых СУБД происходит повышение уровня блокировки: если блокировок уровня строк становится слишком много, они заменяются одной более общей блокировкой (например, уровня страницы или всей таблицы).

Как мы увидим позже, в PostgreSQL такой механизм тоже применяется, но только для предикатных блокировок. С блокировками строк дело обстоит иначе.

Эта статья продолжает первую часть, содержащую подробное описание нашего пайплайна:



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

Итак, я остановился на том, что созданный .gitlab-ci.yml не позволяет реализовать пайплайн в полной мере, поскольку GitLab CI не предоставляет директив для разделения задач по пользователям и для описания зависимостей выполнения задач от статуса выполнения других задач, а также не позволяет разрешить модификацию .gitlab-ci.yml только для отдельных пользователей.

Вот некое простое значение:


И мы знаем, как к нему можно применить функцию:


Элементарно. Так что теперь усложним задание — пусть наше значение имеет контекст. Пока что вы можете думать о контексте просто как о ящике, куда можно положить значение:


Теперь, когда вы примените функцию к этому значению, результаты вы будете получать разные — в зависимости от контекста. Это основная идея, на которой базируются функторы, аппликативные функторы, монады, стрелки и т.п. Тип данных Maybe определяет два связанных контекста:

data Maybe a = Nothing | Just a

Позже мы увидим разницу в поведении функции для Just a против Nothing. Но сначала поговорим о функторах!

Внимание: перед тем как читать текст ниже, вы уже должны иметь представление о том, что такое монады. Если это не так, то прежде прочитайте вот этот пост!

Перед нами функция half:


И мы можем применить её несколько раз:

half . half $ 8
=> 2

Всё работает как и ожидалось. Но вот вы решили, что хорошо бы иметь лог того, что происходит с этой функцией:

half x = (x `div` 2, "Я только что располовинил  " ++ (show x) ++ "!")

Что ж, отлично. Но что будет если вы теперь захотите применить half несколько раз?

half . half $ 8

Вот то, что мы хотели бы, чтобы происходило:


Спойлер: автоматически так не сделается. Придётся всё расписывать ручками:

finalValue = (val2, log1 ++ log2)
    where (val1, log1) = half 8
          (val2, log2) = half val1

Фу! Это ни капли не похоже на лаконичное

half . half $ 8

А что, если у вас есть ещё функции, имеющие лог? Напрашивается такая схема: для каждой функции, возвращающей вместе со значением лог, мы бы хотели объединять эти логи. Это побочный эффект, а никто не силён в побочных эффектах так, как монады!

У функционального программирования много преимуществ, и его популярность постоянно растет. Но, как и у любой парадигмы программирования, у ФП есть свой жаргон. Мы решили сделать небольшой словарь для всех, кто знакомится с ФП.

В примерах используется JavaScript ES2015). (Почему JavaScript?)

Работа над материалом продолжается; присылайте свои пулл-реквесты в оригинальный репозиторий на английском языке.

В документе используются термины из спецификации Fantasy Land spec по мере необходимости.

Arity (арность)

Количество аргументов функции. От слов унарный, бинарный, тернарный (unary, binary, ternary) и так далее. Это необычное слово, потому что состоит из двух суффиксов: "-ary" и "-ity.". Сложение, к примеру, принимает два аргумента, поэтому это бинарная функция, или функция, у которой арность равна двум. Иногда используют термин "диадный" (dyadic), если предпочитают греческие корни вместо латинских. Функция, которая принимает произвольное количество аргументов называется, соответственно, вариативной (variadic). Но бинарная функция может принимать два и только два аргумента, без учета каррирования или частичного применения.

Привет, Хабр! Этой статьей я начинаю серию циклов (или цикл серий? в общем, задумка грандиозная) о внутреннем устройстве PostgreSQL.

Материал будет основан на учебных курсах по администрированию, которые делаем мы с Павлом pluzanov. Смотреть видео не все любят (я точно не люблю), а читать слайды, пусть даже с комментариями, — совсем «не то».

Конечно, статьи не будут повторять содержание курсов один в один. Я буду говорить только о том, как все устроено, опуская собственно администрирование, зато постараюсь делать это более подробно и обстоятельно. И я верю в то, что такие знания полезны прикладному разработчику не меньше, чем администратору.

Ориентироваться я буду на тех, кто уже имеет определенный опыт использования PostgreSQL и хотя бы в общих чертах представляет себе, что к чему. Для совсем новичков текст будет тяжеловат. Например, я ни слова не скажу о том, как установить PostgreSQL и запустить psql.

Вещи, о которых пойдет речь, не сильно меняются от версии к версии, но использовать я буду текущий, 11-й «ванильный» PostgreSQL.

Первый цикл посвящен вопросам, связанным с изоляцией и многоверсионностью, и план его таков:

1. Изоляция, как ее понимают стандарт и PostgreSQL (эта статья);
2. Слои, файлы, страницы — что творится на физическом уровне;
3. Версии строк, виртуальные и вложенные транзакции;
4. Снимки данных и видимость версий строк, горизонт событий;
5. Внутристраничная очистка и HOT-обновления;
6. Обычная очистка (vacuum);
7. Автоматическая очистка (autovacuum);
8. Переполнение счетчика транзакций и заморозка.

Ну, поехали.

Некоторые компании проводят собеседования с online написанием кода. Требуется решить олимпиадную задачку на скорость. В таких условиях нет времени посмотреть подробности реализации структур данных — нужно сразу реализовать идею. Но курсы по алгоритмам и структурам данных дают примеры или на псевдокоде, или на С++. Ещё эталонные решения задач написаны зачастую на С++. Готовясь к собеседованию, составил шпаргалку библиотек — аналогов контейнеров STL, что бы не тратить драгоценное время на поиск.

В первой части мы превратили наш сайт в Progressive Web App. Там же было сказано, что совсем недавно, 6 февраля 2019 года, Google предоставили простую возможность выкладывать PWA в Google Play при помощи Trusted Web Activity. Всё, что нужно сделать, это написать небольшую обёртку под Android, которую можно будет выложить в Google Play. Когда пользователь скачает такое приложение-обёртку, оно просто будет открывать наше PWA внутри Chrome. Конечно же, интерфейс Chrome будет спрятан и всё будет выглядеть красиво.

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