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



В деревьях поиска, таких как двоичное дерево поиска, AVL дерево, красно-чёрное дерево и т.п. каждый узел содержит только одно значение (ключ) и максимум двое потомков. Однако есть особый тип дерева поиска, который называется B-дерево (произносится как Би-дерево). В нем узел содержит более одного значения (ключа) и более двух потомков. B-дерево было разработано в 1972 году Байером и МакКрейтом и называлось Сбалансированное по высоте дерево поиска порядка m (Height Balanced m-way Search Tree). Свое современное название B-дерево получило позже.

Введение

Деревья представляют собой структуры данных, в которых реализованы операции над динамическими множествами. Из таких операций хотелось бы выделить — поиск элемента, поиск минимального (максимального) элемента, вставка, удаление, переход к родителю, переход к ребенку. Таким образом, дерево может использоваться и как обыкновенный словарь, и как очередь с приоритетами.

Основные операции в деревьях выполняются за время пропорциональное его высоте. Сбалансированные деревья минимизируют свою высоту (к примеру, высота бинарного сбалансированного дерева с n узлами равна log n). Большинство знакомо с такими сбалансированными деревьями, как «красно-черное дерево», «AVL-дерево», «Декартово дерево», поэтому не будем углубляться.

В чем же проблема этих стандартных деревьев поиска? Рассмотрим огромную базу данных, представленную в виде одного из упомянутых деревьев. Очевидно, что мы не можем хранить всё это дерево в оперативной памяти => в ней храним лишь часть информации, остальное же хранится на стороннем носителе (допустим, на жестком диске, скорость доступа к которому гораздо медленнее). Такие деревья как красно-черное или Декартово будут требовать от нас log n обращений к стороннему носителю. При больших n это очень много. Как раз эту проблему и призваны решить B-деревья!

B-деревья также представляют собой сбалансированные деревья, поэтому время выполнения стандартных операций в них пропорционально высоте. Но, в отличие от остальных деревьев, они созданы специально для эффективной работы с дисковой памятью (в предыдущем примере – сторонним носителем), а точнее — они минимизируют обращения типа ввода-вывода.

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

В этом цикле мы поговорим о блокировках (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. Настройка журнала — уровни и решаемые задачи, надежность и производительность.

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

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

Уровни журнала

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

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

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

Контрольная точка

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

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

Журнал

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

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

Чтобы это работало, журнальная запись в обязательном порядке должна попасть на диск до того, как туда попадет измененная страница. Отсюда и название: журнал предзаписи (write-ahead log).

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

Я с удивлением обнаружил, что многие разработчики, даже давно использующие postgresql, не понимают оконные функции, считая их какой-то особой магией для избранных. Ну или в лучшем случае «копипастят» со StackOverflow выражения типа «row_number() OVER ()», не вдаваясь в детали. А ведь оконные функции — полезнейший функционал PostgreSQL.
Попробую по-простому объяснить, как можно их использовать.

Когда я начал изучать стандартный ввод/вывод в Java, то первое время был немного шокирован обилием интерфейсов и классов пакета java.io.*, дополненных еще и целым перечнем специфических исключений.

Потратив изрядное количество часов на изучение и реализацию кучи разнообразных туториалов из Интернета, начал чувствовать себя уверенно и вздохнул с облегчением. Но в один прекрасный момент понял, что для меня все только начинается, так как существует еще и пакет java.nio.*, известный ещё под названием Java NIO или Java New IO. Вначале казалось, что это тоже самое, ну типа вид сбоку. Однако, как оказалось, есть существенные отличия, как в принципе работы, так и в решаемых с их помощью задачах.

Разобраться во всем этом мне здорово помогла статья Джакоба Дженкова (Jakob Jenkov) – “Java NIO vs. IO”. Ниже она приводиться в адаптированном виде.

Поспешу заметить, что статья не является руководством по использованию Java IO и Java NIO. Её цель – дать людям, начинающим изучать Java, возможность понять концептуальные отличия между двумя указанными инструментами организации ввода/вывода.

Предыдущий цикл был посвящен изоляции и многоверсионности PostgreSQL, а сегодня мы начинаем новый — о механизме журналирования (write-ahead logging). Напомню, что материал основан на учебных курсах по администрированию, которые делаем мы с Павлом 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. Блокировки в оперативной памяти.

Существует множество книг и статей по данной теме. В этой статье я попробую понятно рассказать самое основное.

Бинарное дерево — это иерархическая структура данных, в которой каждый узел имеет значение (оно же является в данном случае и ключом) и ссылки на левого и правого потомка. Узел, находящийся на самом верхнем уровне (не являющийся чьим либо потомком) называется корнем. Узлы, не имеющие потомков (оба потомка которых равны NULL) называются листьями.


Рис. 1 Бинарное дерево

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

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



В общем, если вам интересен рассказ о том, как C++ программист из Подмосковья искал работу в Европе, желательно в Великобритании, а нашел-таки в Нидерландах, переехал туда сам и привез жену, все это с непогашенной ипотекой в России и с небольшими приключениями — добро пожаловать под кат.

На протяжение многих лет в США была распроcтранена практика требовать претендентов на различные вакансии не только резюме, но еще и сопроводительное письмо (cover letter). В последние годы важность этого аспекта начала снижаться – уже в 2016 году сопроводительные письма требовали только около 30% работодателей. Это нетрудно объяснить – у HR-специалистов, проводящий первоначальный скрининг, обычно слишком мало времени, чтобы читать письма, на анализ самих резюме по статистике уходит всего несколько секунд.

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

Я нашла интересный пост о том, как сегодня следует подходить к написанию cover letter при поиске работы в США, и подготовила его адаптированный перевод.

Ищете работу за границей? Будучи в сфере IT-рекрутинга уже более 10 лет, я часто даю айтишникам советы о том, как быстро найти работу за рубежом. В этой статье приведены самые распространенные из них.

Для удаленной работы есть миллион причин. Торчать по 8-9 часов в офисе вовсе не так здорово, как это показано в сериалах. В один прекрасный день, летом 2018-го, я просто решила, что мне нужно больше личного пространства и собралась увольняться, тем более на моей должности в то время я доросла до максимума и дальнейших перспектив не предвиделось.



Моя работа была чем-то средним между саппортом, тестировщиком, оператором SQL и Excel-ниндзя, а хотелось углубиться в тестирование.

Так как я уверенно говорила и писала по-английски, я решила сразу искать на зарубежном рынке. Просмотрела несколько бирж фриланса, почитала отзывы об Upwork и ее аналогах и решила не связываться. Сложно конкурировать в мелких проектах с гражданами Индии, которые готовы работать за 3 доллара в час. Также мне показалось непродуктивным подавать заявки в онлайн-сервисы, работающие по принципу глобального посредника между удаленными сотрудниками и компаниями, судя по отзывам, отбор у них очень жесткий, а темп работы невероятно напряженный.

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

Пришло время составлять резюме для переезда в другую страну?

Тогда заходи, присаживайся, наливай кофеек. Я расскажу, как это сделать.

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

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

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

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

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

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

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

Ну, поехали.

Я только что завершил шестинедельный процесс трудоустройства на должность middle-senior разработчика на рынке, где сейчас ведется активная охота за талантами (Амстердам). Иными словами, я побывал на куче собеседований. Чтобы аккуратно разведать, какие компании мне больше всего подходят, я старался задавать побольше вопросов. Тут нужно найти правильный баланс, исходя из своих потребностей и того, кто с вами общается.

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

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

Графики, отчеты и аналитика – все это так или иначе присутствует в back-office любого, даже совсем маленького, предприятия. Когда в обычных таблицах в Excel/Numbers/Libre становится уже тесно, но data все еще не очень big, традиционные решения для внутренних потребностей компании часто строятся с помощью реляционных баз данных, таких как PostgreSQL, MySQL или MariaDB.

Эти базы данных бесплатны, благодаря SQL удобно интегрируются с остальными компонентами в системе, они популярны и с ними умеют работать большинство разработчиков и аналитиков. Нагрузку (трафик и объемы) они могут переварить достаточно объемную, чтобы спокойно продержаться до того момента, когда компания сможет позволить себе более сложные (и дорогие) решения для аналитики и отчетов.