Как выбрать равновероятную выборку из потока неизвестной длины
Интерактивный разбор объясняет reservoir sampling, или резервуарную выборку. Алгоритм держит
Механизм показан на картах, а затем на сервисе сбора логов. При
Разбор с интерактивными схемами стоит прочитать разработчикам потоковых систем. Он выводит математику без сложных обозначений и даёт простую реализацию. Для логов разной ценности есть взвешенный вариант алгоритма.
Интерактивный разбор объясняет reservoir sampling, или резервуарную выборку. Алгоритм держит
k элементов. Для элемента с номером n шанс попасть в массив равен k/n; при выборе он заменяет один из сохранённых случайным образом. Поэтому каждый элемент потока имеет равный шанс остаться в результате.Механизм показан на картах, а затем на сервисе сбора логов. При
k=5 сервис хранит не больше пяти сообщений и раз в секунду отправляет выборку: при потоке до пяти сообщений сохраняет все, а во время всплеска выбирает пять без преимущества у первых событий. Цена предсказуемой памяти: логи поступают пачками, а не непрерывно.Разбор с интерактивными схемами стоит прочитать разработчикам потоковых систем. Он выводит математику без сложных обозначений и даёт простую реализацию. Для логов разной ценности есть взвешенный вариант алгоритма.
Как SQLite обеспечивает атомарный коммит
Транзакция выглядит так, будто записалась целиком или не записалась вовсе, хотя питание может пропасть посреди записи. Разбор SQLite объясняет, как база создаёт эту гарантию с журналом отката. WAL работает иначе.
Материал пригодится при создании VFS для SQLite и разборе повреждений после сбоя: проверьте гарантии накопителя, драйвера и ОС для записи и синхронизации.
Транзакция выглядит так, будто записалась целиком или не записалась вовсе, хотя питание может пропасть посреди записи. Разбор SQLite объясняет, как база создаёт эту гарантию с журналом отката. WAL работает иначе.
Материал пригодится при создании VFS для SQLite и разборе повреждений после сбоя: проверьте гарантии накопителя, драйвера и ОС для записи и синхронизации.
Как одну проверку Clippy ускорили в 3133 раза
Казалось бы, проверить скобки в вызовах макросов Rust просто. Но Clippy делал это после раскрытия макросов, когда [], () или {} уже нельзя получить напрямую. Знак восстанавливали по фрагменту исходного кода.
В обстоятельном разборе показана цена решения: для каждого выражения, инструкции и элемента программы проверка поднималась по цепочке раскрытий, дважды запрашивала данные компилятора и блокировала таблицу преобразования идентификаторов в строки. Одна функция забирала 25% времени Clippy.
Исправление заняло менее 200 строк: проверку перенесли на этап до раскрытия макросов, где скобки видны сразу. Материал пригодится авторам статических анализаторов и компиляторных плагинов: профилируйте обход каждого узла дерева и проверяйте ускорение замерами.
Казалось бы, проверить скобки в вызовах макросов Rust просто. Но Clippy делал это после раскрытия макросов, когда [], () или {} уже нельзя получить напрямую. Знак восстанавливали по фрагменту исходного кода.
В обстоятельном разборе показана цена решения: для каждого выражения, инструкции и элемента программы проверка поднималась по цепочке раскрытий, дважды запрашивала данные компилятора и блокировала таблицу преобразования идентификаторов в строки. Одна функция забирала 25% времени Clippy.
Исправление заняло менее 200 строк: проверку перенесли на этап до раскрытия макросов, где скобки видны сразу. Материал пригодится авторам статических анализаторов и компиляторных плагинов: профилируйте обход каждого узла дерева и проверяйте ускорение замерами.
Как устроен исполняемый файл Linux и как разобрать его вручную
Обстоятельная первая часть серии об ELF, формате исполняемых и компонуемых файлов, начинается с программы на ассемблере x86-64, которая печатает
Вместо готовых анализаторов автор читает шестнадцатеричный дамп, учитывает порядок байтов от младшего к старшему и находит таблицу заголовков секций по смещению
Материал fasterthanli.me полезен системным разработчикам и тем, кто хочет связать сырые байты ELF с кодом, данными и именами секций. Страница не обновлялась около семи лет, поэтому это учебный разбор, а не справочник по текущим инструментам.
Обстоятельная первая часть серии об ELF, формате исполняемых и компонуемых файлов, начинается с программы на ассемблере x86-64, которая печатает
hi there. После сборки NASM и компоновки файл занимает 8,68 КиБ, а gzip -9 сжимает его до 372 байт.Вместо готовых анализаторов автор читает шестнадцатеричный дамп, учитывает порядок байтов от младшего к старшему и находит таблицу заголовков секций по смещению
0x2140. Записи в ней указывают, где начинаются части файла и сколько байтов занимают. Затем автор пишет собственный разбор с библиотекой nom.Материал fasterthanli.me полезен системным разработчикам и тем, кто хочет связать сырые байты ELF с кодом, данными и именами секций. Страница не обновлялась около семи лет, поэтому это учебный разбор, а не справочник по текущим инструментам.
Как реализовать get or create в PostgreSQL без гонок и раздувания таблицы
Обстоятельный разбор операции: вернуть существующую строку или создать новую, не обновляя совпавшие данные, как при upsert. На таблице тегов видно, почему SELECT перед INSERT даёт идемпотентность, но ломается при двух одновременных запросах.
Карта решений:
1. Перехват нарушения уникальности закрывает гонку, но неудачная вставка оставляет мёртвую строку до очистки;
2. 50 000 попыток вставить существующий тег заняли около 12 секунд и увеличили таблицу с 8192 байт до 1776 КБ;
3. VACUUM убрал мёртвые строки и вернул размер к 8192 байтам. Обычно очистку по заданным порогам запускает autovacuum.
Читайте статью, если синхронизируете справочники под нагрузкой. Проверьте долю конфликтов: при частых дублях перехват исключений создаёт мёртвые строки и добавляет работы autovacuum.
Обстоятельный разбор операции: вернуть существующую строку или создать новую, не обновляя совпавшие данные, как при upsert. На таблице тегов видно, почему SELECT перед INSERT даёт идемпотентность, но ломается при двух одновременных запросах.
Карта решений:
1. Перехват нарушения уникальности закрывает гонку, но неудачная вставка оставляет мёртвую строку до очистки;
2. 50 000 попыток вставить существующий тег заняли около 12 секунд и увеличили таблицу с 8192 байт до 1776 КБ;
3. VACUUM убрал мёртвые строки и вернул размер к 8192 байтам. Обычно очистку по заданным порогам запускает autovacuum.
Читайте статью, если синхронизируете справочники под нагрузкой. Проверьте долю конфликтов: при частых дублях перехват исключений создаёт мёртвые строки и добавляет работы autovacuum.
Как читать Big O и находить лишнюю сложность в коде
Обстоятельная интерактивная статья объясняет Big O без секундомера: нотация показывает, как растёт время работы вместе с объёмом входа. O(1), O(log n), O(n) и O(n²) разобраны на графиках и примерах JavaScript.
Карта материала:
1. сумма циклом растёт линейно, а формула
2. пузырьковая сортировка в худшем случае проходит n элементов n раз;
3. бинарный поиск отбрасывает половину вариантов за шаг и находит число среди миллиарда не более чем за 31 попытку.
Практический блок переносит теорию в код. Поиск в массиве имеет O(n), в
Обстоятельная интерактивная статья объясняет Big O без секундомера: нотация показывает, как растёт время работы вместе с объёмом входа. O(1), O(log n), O(n) и O(n²) разобраны на графиках и примерах JavaScript.
Карта материала:
1. сумма циклом растёт линейно, а формула
(n × (n + 1)) / 2 требует постоянного числа операций;2. пузырьковая сортировка в худшем случае проходит n элементов n раз;
3. бинарный поиск отбрасывает половину вариантов за шаг и находит число среди миллиарда не более чем за 31 попытку.
Практический блок переносит теорию в код. Поиск в массиве имеет O(n), в
Set: O(1), но создание new Set(items) требует O(n). Материал пригодится, чтобы оценивать алгоритмы по росту затрат и учитывать цену подготовки вместо единичных замеров.Как устроена машина Тьюринга и где проходит граница вычислимого
Интерактивная статья ведёт от устройства машины к пределам вычислений. У неё четыре части: лента, головка, программа и состояние. Пять команд позволяют печатать символ, двигать головку, менять состояние и останавливать выполнение.
Примеры запускаются в тексте и прокручиваются пошагово вперёд или назад. Сначала машина бесконечно печатает нули, затем чередует 0 и 1 и складывает 2 и 6 в двоичной записи.
Дальше разбор «Turing Machines» переходит к задаче остановки: нельзя написать программу, которая по любой программе и входным данным наверняка определит, завершится вычисление или будет идти вечно. Через этот предел объясняется полнота по Тьюрингу: система полна, если может смоделировать машину Тьюринга.
Читать стоит тем, кто хочет связать определение с исполняемыми примерами и понять границы алгоритмов.
Интерактивная статья ведёт от устройства машины к пределам вычислений. У неё четыре части: лента, головка, программа и состояние. Пять команд позволяют печатать символ, двигать головку, менять состояние и останавливать выполнение.
Примеры запускаются в тексте и прокручиваются пошагово вперёд или назад. Сначала машина бесконечно печатает нули, затем чередует 0 и 1 и складывает 2 и 6 в двоичной записи.
Дальше разбор «Turing Machines» переходит к задаче остановки: нельзя написать программу, которая по любой программе и входным данным наверняка определит, завершится вычисление или будет идти вечно. Через этот предел объясняется полнота по Тьюрингу: система полна, если может смоделировать машину Тьюринга.
Читать стоит тем, кто хочет связать определение с исполняемыми примерами и понять границы алгоритмов.
30 паттернов распределённых систем
Это карта готовых решений для систем, где узлы отказывают, сеть задерживает сообщения, а копии данных нужно синхронизировать.
Материал можно читать от своей задачи:
• упорядочить изменения: логические часы Лэмпорта, гибридные часы и векторы версий;
• синхронизировать копии: ведущий с последователями, реплицируемый журнал и консенсус Paxos;
• ускорить запросы: чтение с ведомых узлов, пакеты и конвейер запросов;
• обслуживать журналы: отмечать последнюю репликацию и часть, которую уже можно удалить.
Catalog of Patterns of Distributed Systems даёт краткое описание каждого решения и ссылки на главы онлайн-книги. Архитекторам и бэкенд-разработчикам стоит сопоставить сбой или узкое место своей системы с готовым механизмом, прежде чем проектировать свой протокол.
Это карта готовых решений для систем, где узлы отказывают, сеть задерживает сообщения, а копии данных нужно синхронизировать.
Материал можно читать от своей задачи:
• упорядочить изменения: логические часы Лэмпорта, гибридные часы и векторы версий;
• синхронизировать копии: ведущий с последователями, реплицируемый журнал и консенсус Paxos;
• ускорить запросы: чтение с ведомых узлов, пакеты и конвейер запросов;
• обслуживать журналы: отмечать последнюю репликацию и часть, которую уже можно удалить.
Catalog of Patterns of Distributed Systems даёт краткое описание каждого решения и ссылки на главы онлайн-книги. Архитекторам и бэкенд-разработчикам стоит сопоставить сбой или узкое место своей системы с готовым механизмом, прежде чем проектировать свой протокол.
❤1
Forwarded from Точка входа в программирование
Как устроена база данных: собираем клон SQLite на C
Это обстоятельная серия для тех, кому знаком SQL, но путь данных от запроса до файла скрыт за интерфейсом СУБД. Автор строит клон SQLite с нуля на C и документирует каждый слой. Всего 15 частей: маршрут идёт от цикла чтения команд и компилятора SQL к многоуровневому B-дереву.
Сначала появляются цикл чтения команд, простейший компилятор SQL и виртуальная машина. Затем одна таблица в памяти получает тесты, сохранение на диск и курсор для обхода записей. Дальше автор разбирает формат узлов B-дерева, двоичный и рекурсивный поиск, разделение узлов и обновление их родителей.
В серии How Does a Database Work? удобно идти по порядку и смотреть, как знакомые операции превращаются в структуры данных. Читать стоит разработчикам, которые работают с SQL и хотят разобраться в индексах, полном сканировании таблицы и границе между памятью и диском.
Это обстоятельная серия для тех, кому знаком SQL, но путь данных от запроса до файла скрыт за интерфейсом СУБД. Автор строит клон SQLite с нуля на C и документирует каждый слой. Всего 15 частей: маршрут идёт от цикла чтения команд и компилятора SQL к многоуровневому B-дереву.
Сначала появляются цикл чтения команд, простейший компилятор SQL и виртуальная машина. Затем одна таблица в памяти получает тесты, сохранение на диск и курсор для обхода записей. Дальше автор разбирает формат узлов B-дерева, двоичный и рекурсивный поиск, разделение узлов и обновление их родителей.
В серии How Does a Database Work? удобно идти по порядку и смотреть, как знакомые операции превращаются в структуры данных. Читать стоит разработчикам, которые работают с SQL и хотят разобраться в индексах, полном сканировании таблицы и границе между памятью и диском.
Let’s Build a Simple Database
How Does a Database Work?
Writing a sqlite clone from scratch in C
Как агенты тестируют код и почему одного промпта мало
В исследовании агенты реализовывали Zstd на Rust и по указанию применяли TDD (разработку через тесты), фаззинг, тестирование свойств или формальные методы. Автор сравнил 26 вариантов промпта и 4 навыка, по 80 запусков на условие и уровень рассуждений.
Режим без дополнительных инструкций оказался выше среднего. На максимальном уровне фаззинг и тестирование свойств были чуть лучше формальных методов, а рекомендованные навыки и TDD показали слабые результаты.
Агенты доказывали малозначимые свойства или перебирали случайные данные, часто попадая в отбраковку. Тест с 4 одинаковыми входными потоками не замечал их перестановку. Исследование How well do agents use test/verification techniques? стоит прочитать тем, кто принимает агентный код: проверяйте, какую ошибку способен обнаружить тест, а не только зелёный результат.
В исследовании агенты реализовывали Zstd на Rust и по указанию применяли TDD (разработку через тесты), фаззинг, тестирование свойств или формальные методы. Автор сравнил 26 вариантов промпта и 4 навыка, по 80 запусков на условие и уровень рассуждений.
Режим без дополнительных инструкций оказался выше среднего. На максимальном уровне фаззинг и тестирование свойств были чуть лучше формальных методов, а рекомендованные навыки и TDD показали слабые результаты.
Агенты доказывали малозначимые свойства или перебирали случайные данные, часто попадая в отбраковку. Тест с 4 одинаковыми входными потоками не замечал их перестановку. Исследование How well do agents use test/verification techniques? стоит прочитать тем, кто принимает агентный код: проверяйте, какую ошибку способен обнаружить тест, а не только зелёный результат.
Как Uber переписала шардирование Schemaless на Go без простоя
Подробный технический разбор миграции хранилища. Материал ценен схемой перехода между реализациями: новая сначала пропускала запросы к старой, затем команда переносила по одной операции.
Карта материала:
1. чтение выполняли обе реализации, после чего ответы сравнивали;
2. долю проверки меняли настройкой, поскольку она удваивала запросы к узлам хранения;
3. запись проверяли интеграционными тестами и тестовым трафиком: один запрос мог успешно выполниться лишь раз.
После миграции медианная задержка всех запросов уменьшилась на 85%, 99-й перцентиль на 70%, загрузка процессора более чем на 85%.
В разборе Uber Engineering стоит изучить совместимость и переключение долей трафика. Для критичного сервиса заранее разделите проверки чтения и записи.
Подробный технический разбор миграции хранилища. Материал ценен схемой перехода между реализациями: новая сначала пропускала запросы к старой, затем команда переносила по одной операции.
Карта материала:
1. чтение выполняли обе реализации, после чего ответы сравнивали;
2. долю проверки меняли настройкой, поскольку она удваивала запросы к узлам хранения;
3. запись проверяли интеграционными тестами и тестовым трафиком: один запрос мог успешно выполниться лишь раз.
После миграции медианная задержка всех запросов уменьшилась на 85%, 99-й перцентиль на 70%, загрузка процессора более чем на 85%.
В разборе Uber Engineering стоит изучить совместимость и переключение долей трафика. Для критичного сервиса заранее разделите проверки чтения и записи.
Go 1.27: что проверить перед обновлением сервисов
Практический обзор Go 1.27 отделяет ускорение после пересборки от изменений, которые требуют проверки кода. Для типичных серверных нагрузок автор приводит прирост 3–5%, для отдельных микротестов до 10%. Причины: более точное встраивание функций компилятором и меньше расходов на выделение памяти.
Отдельно разобраны сборщик мусора для сервисов с сотнями гигабайт живых данных и встроенная функция
В практическом гайде на DEV Community можно сверить детали перед обновлением. Сохраните его, если поддерживаете Go-сервисы: пересоберите стенд и сравните скорость, паузы сборщика мусора и отладку на своей нагрузке.
Практический обзор Go 1.27 отделяет ускорение после пересборки от изменений, которые требуют проверки кода. Для типичных серверных нагрузок автор приводит прирост 3–5%, для отдельных микротестов до 10%. Причины: более точное встраивание функций компилятором и меньше расходов на выделение памяти.
Отдельно разобраны сборщик мусора для сервисов с сотнями гигабайт живых данных и встроенная функция
clear. Она очищает срезы и карты без нового выделения памяти, что пригодится при повторном использовании буферов. Данные DWARF помогают отладчику лучше показывать переменные, а go mod tidy оставляет меньше шума в изменениях go.mod.В практическом гайде на DEV Community можно сверить детали перед обновлением. Сохраните его, если поддерживаете Go-сервисы: пересоберите стенд и сравните скорость, паузы сборщика мусора и отладку на своей нагрузке.