Добрый день, дорогие хабражители.

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

От переводчика: Это первая статья из цикла о Node.js от команды Mozilla Identity, которая занимается проектом Persona. Как клиентская, так и серверная часть Persona написаны на JavaScript. В ходе работы команда проекта создала несколько инструментов на все случаи жизни — от локализации до отладки, управления зависимостями и многого другого. В этой серии статей разработчики Mozilla делятся с сообществом своим опытом и этими инструментами, которые пригодятся любому, кто пишет высоконагруженный сервис на Node.js.

Первая статья цикла посвящена распространённой проблеме Node.js — утечкам памяти, особенностям утечек в высоконагруженных проектах и библиотеке node-memwatch, которая помогает найти и устранить такие утечки в Node.

Все статьи цикла:

1. "Охотимся за утечками памяти в Node.js"
2. "Нагружаем Node под завязку"
3. "Храним сессии на клиенте, чтобы упростить масштабирование приложения"
4. "Производительность фронтэнда. Часть 1 — конкатенация, компрессия, кэширование"
5. "Пишем сервер, который не падает под нагрузкой"
6. "Производительность фронтэнда. Часть 2 — кешируем динамический контент с помощью etagify"
7. "Приручаем конфигурации веб-приложений с помощью node-convict"
8. "Производительность фронтенда. Часть 3 — оптимизация шрифтов"
9. "Локализация приложений Node.js. Часть 1"
10. "Локализация приложений Node.js. Часть 2: инструментарий и процесс"
11. "Локализация приложений Node.js. Часть 3: локализация в действии"
12. "Awsbox — PaaS-инфраструктура для развёртывания приложений Node.js в облаке Amazon"

---

Зачем заморачиваться?

Вы можете спросить, зачем вообще отслеживать утечки памяти? Неужели нет более важных дел? Почему бы просто не перезапускать процесс время от времени, или просто добавить памяти на сервер? Есть три причины, по которым устранять утечки всё-таки важно:

1. Возможно, вы не сильно переживаете об утечках памяти, но этого нельзя сказать о V8 (движок JavaScript на котором работает Node). Чем больше памяти занято, тем активнее работает сборщик мусора, замедляя ваше приложение. Так что в Node утечки напрямую вредят производительности.
2. Утечки могут привести к другим проблемам. Протекающий код может блокировать ограниченные ресурсы. У вас могут закончиться файловые дескрипторы или вы вдруг не сможете открыть ещё одно соединение с БД. Такие проблемы могут возникнуть задолго до того, как кончится память, но обрушат ваше приложение ничуть не хуже.
3. Рано или поздно ваше приложение упадёт. И это наверняка случится во время наплыва посетителей. Вас все засмеют и будут писать про вас гадости на Hacker News.

По заявкам слушателей, так сказать. Правильно соединить кабель — половина дела, но если он будет свободно болтаться, то долго он не проживет — или заденут, или порвут, или откусят(необязательно со злыми намерениями). А может просто под своим весом выскользнуть из соединения. А может не выскользнуть, что еще хуже — поди-ка найди место пропадания контакта. Так что эта статья расскажет о том, какими способами можно закрепить кабель так, чтоб он никуда не делся.
Да и вот такие крепления некрасивы, неудобны, и выдают непрофессионала:

Эта статья — частичный перевод исчерпывающего руководства Дэвида Хоуэлса (David Howells) и Пола Маккени (Paul E. McKenney) распространяемого в составе документации Linux (Documentation/memory-barriers.txt онлайн версия).

Must read для разработчиков ядра/драйверов и очень познавательно для прикладных программистов.

Уважаемые коллеги, которые сталкивались с классификатором адресов Российской Федерации КЛАДР знают, насколько это странная база (в первую очередь своей структурой), а также большим количеством неточностей в самих данных.

В 2011 году за дело взялась ФНС, которая начала разрабатывать новую единую базу Федеральной информационной адресной системы (ФИАС) для того, что бы покончить с адресным бардаком, царящим среди различных ведомств.

Постановка задачи поиска в строке

Часто приходится сталкиваться со специфическим поиском, так называемым поиском строки (поиском в строке). Пусть есть некоторый текст Т и слово (или образ) W. Необходимо найти первое вхождение этого слова в указанном тексте. Это действие типично для любых систем обработки текстов. (Элементы массивов Т и W – символы некоторого конечного алфавита – например, {0, 1}, или {a, …, z}, или {а, …, я}.)

Наиболее типичным приложением такой задачи является документальный поиск: задан фонд документов, состоящих из последовательности библиографических ссылок, каждая ссылка сопровождается «дескриптором», указывающим тему соответствующей ссылки. Надо найти некоторые ключевые слова, встречающиеся среди дескрипторов. Мог бы иметь место, например, запрос «Программирование» и «Java». Такой запрос можно трактовать следующим образом: существуют ли статьи, обладающие дескрипторами «Программирование» и «Java».

Поиск строки формально определяется следующим образом. Пусть задан массив Т из N элементов и массив W из M элементов, причем 0<M≤N. Поиск строки обнаруживает первое вхождение W в Т, результатом будем считать индекс i, указывающий на первое с начала строки (с начала массива Т) совпадение с образом (словом).
Пример. Требуется найти все вхождения образца W = abaa в текст T=abcabaabcabca.

Образец входит в текст только один раз, со сдвигом S=3, индекс i=4.

Оглавление (на данный момент)

Часть 1. Описание, операции, применения.
Часть 2. Ценная информация в дереве и множественные операции с ней.
Часть 3. Декартово дерево по неявному ключу.
To be continued...

Декартово дерево (cartesian tree, treap) — красивая и легко реализующаяся структура данных, которая с минимальными усилиями позволит вам производить многие скоростные операции над массивами ваших данных. Что характерно, на Хабрахабре единственное его упоминание я нашел в обзорном посте многоуважаемого winger, но тогда продолжение тому циклу так и не последовало. Обидно, кстати.

Я постараюсь покрыть все, что мне известно по теме — несмотря на то, что известно мне сравнительно не так уж много, материала вполне хватит поста на два, а то и на три. Все алгоритмы иллюстрируются исходниками на C# (а так как я любитель функционального программирования, то где-нибудь в послесловии речь зайдет и о F# — но это читать не обязательно :). Итак, приступим.

Введение

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

Следующий пункт нашей обязательной программы — куча (heap). Думаю, также многим известная структура данных, однако краткий обзор я все же приведу.
Представьте себе двоичное дерево с какими-то данными (ключами) в вершинах. И для каждой вершины мы в обязательном порядке требуем следующее: ее ключ строго больше, чем ключи ее непосредственных сыновей. Вот небольшой пример корректной кучи:

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

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

Два года назад, работая над Awesome, я присоединился к разработке XCB, который является частью инициативы Freedesktop. Мне пришлось изучить тайны протокола X11 и весь древний и таинственный мир, окружающий его.

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