Навіщо мені формула Шеннона? 🤨

На «Теорії інформації та кодуванні» дійшли до формули Шеннона:

H(X) = -Σ p(x) log₂ p(x)

Дивився на неї й не міг зрозуміти, навіщо вона мені взагалі потрібна. Ймовірності, логарифми, якась абстрактна ентропія — чудовий набір, щоб закрити конспект і піти писати код 😅

Зрозуміліше стало після простого пояснення: формула показує, скільки інформації в середньому несе одне повідомлення. Чим рідше трапляється символ або подія, тим більше інформації дає її поява.

Уявімо чотири символи. Якщо вони трапляються однаково часто, кожен можна записувати двома бітами. Але якщо символ A займає 70% тексту, витрачати на нього стільки ж місця, як на рідкісний символ, — марнотратство.

Частому A можна дати короткий код, а рідкісним символам — довші. Завдяки цьому більша частина тексту записуватиметься меншою кількістю бітів. Вихідний текст не зміниться, але середній розмір одного символу зменшиться.

Ось навіщо потрібна статистика: вона показує, де дані передбачувані й де можна не витрачати зайві біти. На цьому принципі працює стиснення без втрат. Ентропія не стискає файл сама, але показує нижню межу його середнього розміру. Хаффман і арифметичне кодування вже намагаються підібратися до цієї межі 📦

З контрольними сумами логіка трохи інша. Великий файл перетворюється на коротке значення фіксованої довжини. Наприклад, контрольна сума довжиною 8 біт має лише 256 можливих значень.

Файлів може бути значно більше ніж 256. Отже, рано чи пізно два різні файли отримають однакову контрольну суму. Це і називається колізією: дані різні, а результат перевірки однаковий 🎭

Контрольна сума довжиною b біт має 2ᵇ можливих значень. Для однієї випадково пошкодженої копії шанс збігу з початковою сумою становить приблизно:

1 / 2ᵇ

Що більше бітів, то менша ймовірність пропустити випадкову помилку. Але якщо файлів багато, порівнюється вже величезна кількість пар, тому шанс хоча б однієї колізії зростає.

Формула Шеннона не створює алгоритм стиснення або готову контрольну суму. Вона дає основу для розрахунків: скільки інформації містять дані, скільки бітів потрібно для їх кодування та наскільки надійно коротке значення може їх розрізняти.

Коли це пояснили людською мовою, логарифм нарешті влаштувався на роботу 😄

Як 160 біт перетворилися на 28 📦

Візьмемо повідомлення з двадцяти символів:

AAAAAAAAAAAAAABBBBCD

У звичайному текстовому файлі кожна латинська літера займає один байт — 8 біт. Отже, все повідомлення потребує 160 біт.

Але в нашому словнику є лише чотири символи: A, B, C і D. Нам не потрібна вся таблиця ASCII. Чотири символи можна позначити чотирма комбінаціями з двох бітів:

A = 00
B = 01
C = 10
D = 11

20 × 2 = 40 біт

Символи трапляються з різною частотою:

A — 14 разів, 70%
B —  4 рази, 20%
C —  1 раз,   5%
D —  1 раз,   5%

Тут і з’являється алгоритм Хаффмана. Він не вигадує короткі коди навмання, а щоразу об’єднує два найрідкісніші символи:

C 5% + D 5% = 10%
10% + B 20% = 30%
30% + A 70% = 100%

Так утворюється дерево. На кожному розгалуженні одному напрямку даємо 0, іншому — 1. Шлях від вершини дерева до символу стає його кодом:

A = 0
B = 10
C = 110
D = 111

Частий A опинився найближче до вершини й отримав один біт. До рідкісних C і D потрібно пройти три розгалуження, тому їхні коди довші.

Тут працює важливе правило: жоден код не повинен бути початком іншого. Інакше дані не вдасться однозначно прочитати.

Наприклад, такий словник був би поганим:

A = 0
B = 01
C = 1

Послідовність 01 можна прочитати як один символ B або як два символи A і C.

У правильному словнику все однозначно:

0 | 10 | 110 | 111
A | B  | C   | D

Рахуємо новий розмір:

A: 14 × 1 = 14 біт
B:  4 × 2 =  8 біт
C:  1 × 3 =  3 біти
D:  1 × 3 =  3 біти

Разом: 28 біт

Отримав 28 біт замість 40 — на 30% менше. Порівняно зі звичайним текстовим файлом на 160 біт економія становить 82,5%.

Формула Шеннона для такого розподілу дає приблизно 1,26 біта на символ, або близько 25 біт для всього повідомлення. Хаффман витратив 28, бо довжина кожного коду має бути цілою.

Для короткого повідомлення ще потрібно зберігати словник, і він може з’їсти всю економію. Але на мільярді символів різниця між двома й 1,4 біта на символ становить близько 75 мегабайтів. На трильйоні — вже 75 гігабайтів.

Подібні принципи просто зараз стискають архіви, зображення, резервні копії та мережевий трафік по всьому світу. Так абстрактна формула починає економити цілком реальні терабайти 📉

Чотири біти пережили помилку 🧩

Потрібно передати чотири біти:

1011

Якщо під час передачі один із них зміниться, приймач побачить іншу нормальну комбінацію й не знатиме, де сталася помилка. Початкової інформації вже недостатньо для відновлення.

Тому до чотирьох корисних бітів додамо три перевірочні. Отримаємо код Геммінга 7,4: сім бітів передають чотири біти даних і дозволяють виправити одну помилку.

Розкладаємо біти по позиціях:

Позиція:  1  2  3  4  5  6  7
Вміст:   p1 p2 d1 p4 d2 d3 d4
Значення: p1 p2  1 p4  0  1  1

Перевірочні біти відповідають за різні групи:

p1 перевіряє позиції 1, 3, 5, 7
p2 перевіряє позиції 2, 3, 6, 7
p4 перевіряє позиції 4, 5, 6, 7

Їх підбираємо так, щоб XOR усіх бітів у кожній групі дорівнював нулю. Для 1011 отримуємо:

p1 = 0
p2 = 1
p4 = 0

Передаємо: 0110011

Припустимо, шостий біт пошкодився:

Було:     0110011
Прийшло:  0110001

Приймач повторює три перевірки:

s1 = 0
s2 = 1
s4 = 1

s4 s2 s1 = 110₂ = 6

Число 6 прямо вказує на пошкоджену позицію. Змінюємо шостий біт назад, а з позицій 3, 5, 6 і 7 забираємо початкові дані:

0110001 → 0110011 → 1011

На рівні процесора саме виправлення займає кілька команд. Три перевірки вже записали номер пошкодженої позиції в BL, а отримані сім бітів лежать у AL:

test bl, bl
jz   .done

mov  cl, 7
sub  cl, bl
mov  dl, 1
shl  dl, cl
xor  al, dl

.done:

test bl, bl перевіряє, чи дорівнює номер помилки нулю. jz .done завершує виправлення, якщо всі перевірки пройшли.

Позиції в нашому записі рахуються зліва направо від 1 до 7, а зсув у регістрі — справа наліво від 0. Команди mov cl, 7 і sub cl, bl переводять номер позиції у потрібну кількість зсувів. Для позиції 6 отримаємо один зсув.

mov dl, 1 створює одиницю, а shl dl, cl пересуває її до пошкодженого біта. Для шостої позиції маска виглядає так:

00000010

xor al, dl перемикає лише цей біт: 0 стає 1, а 1 — 0. Інші біти не змінюються.

За можливість відновлення заплатили трьома додатковими бітами. Код Геммінга 7,4 виправляє одну помилку, але не врятує від довільної кількості пошкоджень. Складніші коди додають більше надлишкової інформації.

Саме завдяки їй працюють ECC-пам’ять, QR-коди, супутниковий зв’язок і носії даних. Надлишкові біти здаються зайвими лише доти, доки щось не зламається 😄

Gateway працює. А клієнт про це знає? 🧪

Останні три пости були важливим ліричним відступом. Розібрався, навіщо потрібна формула Шеннона, як із неї виростає стиснення та чому надлишкові біти іноді рятують дані. Тепер повертаюся до Transparent Gateway 🌐

Gateway уже пережив повторне розгортання й перезавантаження. Контейнери запущені, пул проксі свіжий, локальний echo-сервіс відповідає.

Але досі gateway перевіряв переважно сам себе. Такий тест доводить, що його компоненти працюють, але нічого не говорить про трафік іншої машини.

Тому створив окрему клієнтську VM. На ній немає коду Transparent Gateway, паролів проксі або налаштувань proxy в застосунках. Єдиний маршрут IPv4 за замовчуванням веде через gateway, тому непомітно піти напряму клієнт не може.

Перевірку запускаю з довіреної машини:

python3 deploy/verify-readiness.py \
  --gateway tgadmin@<gateway> \
  --client tgadmin@<client>

Сценарій спочатку перевіряє gateway: стан systemd, свіжість пулів і наявність придатного проксі. Потім через SSH передає клієнту невеликий тест. Встановлювати на клієнт код проєкту або копіювати туди SSH-ключі не потрібно.

Клієнт відкриває звичайне TCP-з’єднання — без адреси проксі та його пароля. Запит проходить таким маршрутом:

клієнт
  → Transparent Gateway
  → локальний проксі
  → локальний echo-сервіс
  → відповідь клієнту

Echo-сервіс повертає ідентифікатор запиту та адресу, з якої побачив з’єднання. Перевірка звіряє їх зі свіжим активним пулом, тому випадкова відповідь від іншого сервісу за успіх не зарахується.

Результат:

PASS client default via gateway; no alternative default
PASS usable active upstream and local relay CONNECT/echo
PASS transparent client TCP/echo
LAB_READINESS PASS

Окрема VM без налаштувань проксі надіслала звичайний TCP-запит. Transparent Gateway перехопив його, передав через локальний проксі та повернув відповідь клієнту ✅

Отже, локальний маршрут працює повністю — від клієнта до echo-сервісу й назад. Але вихід в інтернет, публічний HTTPS і DNS цей тест ще не перевіряє. Для цього знадобляться зовнішній проксі та публічний echo-сервіс.

Підняв публічний echo для перевірки виходу через проксі 🌍

Коротко для тих, хто щойно приєднався. Transparent Gateway — це окрема VM між клієнтською машиною та рештою мережі. Клієнт користується мережею як звичайно: не потрібно вказувати проксі окремо в браузері чи кожній програмі.

Gateway перехоплює DNS-запити, за допомогою яких програми знаходять IP-адреси сайтів, і TCP-з’єднання, якими передається основний трафік. Потім спрямовує їх через проксі — проміжний сервер, який підключається до потрібного ресурсу від імені клієнта. У результаті сайт бачить адресу проксі, а не клієнтської машини.

Щоб не передавати трафік через першу-ліпшу адресу зі списку, окремі компоненти збирають проксі, перевіряють їхню доступність і залишають справні в активному пулі. Gateway бере маршрути саме з цього пулу. Зараз автоматизую розгортання всієї системи з чистої VM у Proxmox і поетапно перевіряю, чи справді трафік проходить потрібним шляхом.

Попередня перевірка довела, що клієнтський запит проходить через Transparent Gateway і локальний проксі. Але весь маршрут залишився всередині лабораторної мережі.

Щоб перевірити реальний вихід назовні, потрібна публічна точка, яка прийме HTTPS-запит і покаже адресу, з якої він прийшов. Якщо ця адреса збігається з виходом активного проксі, значить запит справді залишив лабораторію потрібним маршрутом.

Готові публічні сервіси для визначення IP існують, але сьогодні вони працюють, завтра змінюють формат відповіді, а післязавтра блокують автоматичні запити. Для повторюваної перевірки хотілося контролювати обидві сторони.

Тому виніс echo-сервіс в окремий проєкт — TransparentGatewayEcho 🔊

На зовнішній машині вже працював Nginx Proxy Manager, тому через нього й опублікував сервіс. NPM приймає HTTPS на порту 443 і передає запит контейнеру echo у внутрішній мережі Docker. Сам порт контейнера назовні не відкритий.

Echo-сервіс повертає JSON із випадковим ідентифікатором запиту, адресою клієнта та обмеженим набором діагностичних заголовків. Паролі, cookies й заголовки авторизації у відповідь не потрапляють.

Для перевірки додав до репозиторію verify.py:

python3 verify.py https://echo.devdays.net.ua/

Перший запуск завершився JSONDecodeError. Спочатку здавалося, що echo-сервіс повернув неправильну відповідь. Насправді запит до нього взагалі не дістався.

Cloudflare відхилив стандартний User-Agent бібліотеки Python і повернув власну HTML-сторінку з HTTP 403 та кодом 1010. Скрипт очікував JSON і закономірно подавився HTML 😅

Додав власний User-Agent:

TG-Echo-Verify/1.0

Також навчив перевірку показувати HTTP-статус і тип відповіді, якщо замість JSON приходить помилка від зовнішнього сервісу.

Після цього запит дістався echo-сервісу:

PASS HTTPS certificate and hostname verification; HTTP 200
PASS source IP=[hidden]; spoofed peer rejected
PASS diagnostic headers and fresh request ID
PASS Authorization/Cookie/Proxy-Authorization excluded
PUBLIC_ECHO_CHECK PASS

Тепер є контрольована публічна точка, яка приймає HTTPS, повертає унікальний ідентифікатор запиту та показує адресу, передану Cloudflare ✅

Сам Transparent Gateway до неї ще не ходив. Локальний тестовий проксі бачить лише лабораторний echo-сервіс і не має виходу в інтернет. Наступний крок — додати зовнішній TLS-проксі й провести запит через нього.

Підняв зовнішній TLS-проксі для контрольованого виходу 🔐

Публічний echo-сервіс готовий. Тепер Transparent Gateway потрібен проксі, який справді може дістатися до нього з інтернету.

Випадковий відкритий проксі для такого тесту не підходить. Сьогодні він працює, через годину зникає, а його вихідна адреса й правила доступу залишаються загадкою. Якщо перевірка впаде, незрозуміло, зламався gateway чи просто помер черговий безкоштовний проксі.

Тому підняв власний тестовий TLS-проксі й виніс його в окремий проєкт — TransparentGatewayProxy 🌐

До нього gateway підключається напряму через TLS на порту 3129. Nginx Proxy Manager і Cloudflare в цьому маршруті не беруть участі.

Під час налаштування задаю адресу сервера та єдину зовнішню адресу, з якої дозволено підключення:

sudo python3 setup.py \
  --server-ip "$PROXY_IP" \
  --allow-source "$GATEWAY_IP/32"

Сценарій створює власний CA, сертифікат сервера та випадкові дані авторизації. Пароль передається всередині TLS-з’єднання, тому Basic authentication тут не їде інтернетом відкритим текстом.

Проксі також перевіряє TCP-адресу клієнта. Підроблений X-Forwarded-For не допоможе, бо рішення приймається за реальною адресою з’єднання.

Після підготовки запускаю контейнер і локальну перевірку:

docker compose up -d --build --wait
docker compose exec -T proxy python /app/verify.py

Проксі не дозволяє відкривати довільні адреси. Для стенда йому доступні лише публічний echo-сервіс і визначені DNS-цілі. Спроба підключитися до 127.0.0.1:22, службової адреси хмарного сервера або стороннього порту завершується відмовою.

Результат локальної перевірки:

PASS TLS certificate/identity
PASS missing and wrong credentials 407
PASS forbidden targets 403
PASS nested HTTPS certificate/hostname
PASS fresh echoed request ID; proxy credentials absent
PROXY_LOCAL_CHECK PASS

Приватний ключ CA та ключ сервера залишаються на машині з проксі. На gateway передаю лише публічний CA-сертифікат, адресу підключення та дані авторизації.

Після передачі запускаю перевірку вже з gateway:

sudo python3 verify.py \
  --directory /etc/transparent-gateway/external-upstream \
  --remote \
  --dns

Вона перевіряє TLS-сертифікат проксі, правильну й неправильну авторизацію, заборонені адреси, HTTPS-запит до публічного echo та DNS-over-HTTPS.

PASS TLS certificate/identity
PASS nested HTTPS certificate/hostname
PASS DNS-over-HTTPS through authenticated proxy
UPSTREAM_REMOTE_CHECK PASS

Отже, gateway може встановити захищене з’єднання із зовнішнім проксі, пройти авторизацію та дістатися через нього до публічного echo-сервісу й DNS ✅

Окрема перевірка довела, що з хоста gateway зовнішній проксі доступний і справно працює. Але клієнтський трафік через нього ще не піде: Transparent Gateway використовує лише ті проксі, які пройшли validator і потрапили до активного пулу.

Додав новий проксі до конфігурації та запустив звичайний цикл перевірки. Локальний проксі залишився активним, а зовнішній validator відхилив — хоча хвилину тому той успішно пройшов TLS, авторизацію, HTTPS і DNS.

Отже, наступним кроком довелося з’ясовувати, чому ручна перевірка бачить справний проксі, а validator — ні 😅

Для CONNECT порт не опція 🧩

Зовнішній проксі працював. Окрема перевірка успішно проходила TLS, авторизацію, публічний HTTPS і DNS.

Але Transparent Gateway не додавав його до активного пулу.

Перед додаванням кожного проксі validator перевіряє, чи може той передавати реальні запити. Для HTTPS він просить проксі відкрити тунель до потрібного сервера за допомогою команди CONNECT.

Validator надсилав такий запит:

CONNECT echo.devdays.net.ua HTTP/1.1

Тут указаний домен, але немає порту.

Домен echo.devdays.net.ua визначає сервер, а порт 443 — HTTPS-сервіс на ньому. Без порту проксі отримує неповну адресу й не знає, куди саме відкривати тунель.

Правильний запит:

CONNECT echo.devdays.net.ua:443 HTTP/1.1

Окрема перевірка проксі додавала :443, тому працювала. Validator цього не робив, тому проксі правильно відхиляв його запит.

Виправлення звелося до простого правила: під час створення CONNECT завжди додавати порт, навіть якщо він стандартний для HTTPS.

Після виправлення validator надіслав правильну адресу:

echo.devdays.net.ua:443

Зовнішній проксі пройшов перевірку й потрапив до активного пулу:

active: 2
validated: 2

Тепер у gateway є два перевірені маршрути: локальний проксі для лабораторного echo-сервісу та зовнішній — для публічного HTTPS і DNS ✅

Наступним кроком перевірю обидва маршрути з окремої клієнтської VM.

На кілька постів зверну в алгоритми 🧠

На кілька постів знову відійду від Transparent Gateway. Цього разу — в алгоритми та структури даних.

Зараз готуюся до олімпіади з програмування. І ця підготовка потроху змінює моє ставлення до речей, які раніше здавалися необов’язковими.

Програмую вже близько десяти років. Глибокого знання алгоритмів у мене немає, і для задач, із якими стикався в роботі, воно досі не було необхідним.

Це не історія про те, що колись усе вивчив, а потім просто не користувався. Багатьох алгоритмів я не знав і досі не знаю. Нічого страшного в цьому не бачу: до своєї мрії стати кращим програмістом іду поступово й кидати цей шлях не збираюся.

Алгоритми є майже в кожному плані навчання програмуванню, тому свого часу взявся за Кормена. Спроба була чесною, але недовгою: від книги хотілося спати значно сильніше, ніж розбирати чергове доведення 😴

Після цього прочитав «Грокаємо алгоритми». Вона виявилася набагато доступнішою і дала загальне уявлення про пошук, сортування, графи та складність обчислень.

Але тоді враження залишилося приблизно таким: алгоритми — цікава штука для людей з особливими інтересами, яким від усієї цієї теорії чомусь не хочеться спати.

Водночас саме програмування мене драйвило й продовжує драйвити. Тому особливої суперечності тут не бачив: код пишеться, проєкти працюють, а Кормен спокійно стоїть на полиці.

Підготовка до олімпіади показала інший бік програмування. Тут недостатньо знайти будь-яке правильне рішення. Потрібно побачити структуру задачі й вибрати спосіб, який не з’їсть увесь час або пам’ять.

Тому наступні кілька постів будуть про алгоритми. Трохи відпочинемо від серверів, проксі та розгортання — і подивимося, навіщо всі ці дерева взагалі вигадали 🌲

Правильного результату для олімпіади недостатньо ⏱️

Першим бажанням в олімпіадній задачі часто стає звичайний перебір.

Потрібно знайти пару елементів — переберу всі пари. Потрібно перевірити відрізки масиву — перевірю кожен відрізок. На прикладах з умови все працює, відповідь правильна, можна відправляти.

А потім тести повідомляють, що чекати до завтра вони не збираються 😅

Наприклад, у масиві 200 000 елементів подвійний цикл може виконати близько 40 мільярдів операцій:

200 000 × 200 000 = 40 000 000 000

Логічно код може бути бездоганним. Але за відведену секунду він просто не встигне отримати результат.

Рішення зі складністю O(n log n) для того самого обсягу даних потребуватиме приблизно 3,6 мільйона кроків:

200 000 × log₂(200 000) ≈ 3 600 000

Відповідь та сама, але різниця у швидкості — у тисячі разів.

Те саме стосується пам’яті. Можна створити таблицю для всіх можливих пар і навіть правильно її заповнити. Але якщо вона не поміститься в доступну пам’ять, правильність уже нікого не врятує.

Тому обмеження в умові — це частина задачі. Вони підказують, чи можна використовувати перебір, чи доведеться шукати інший підхід.

Поступово звикаю перед написанням коду ставити додаткові запитання:

• скільки буде даних;
• які операції повторюються;
• що доводиться рахувати знову;
• чи можна один раз зберегти частину результату;
• чи існує структура даних саме для таких операцій.

Одне з таких запитань і привело мене до дерева Фенвіка.

Нуль задач і значно більше мотивації 🔥

Вчора взяв участь в олімпіаді з програмування у складі команди PDAU_RootAccess.

Очікування були скромними, але завдання все одно виявилися значно складнішими, ніж очікував. У підсумку команда не розв’язала жодної задачі.

У таблиці команди з таким результатом опинилися в діапазоні 426–605. Окремого місця нам навіть не виділили — настільки впевнено розташувалися у хвості 😅

Для порівняння: минулого року розв’язували по три-чотири задачі в кожному турі й дійшли щонайменше до другого. Можливо, навіть до третього — точно вже не пам’ятаю, тому вигадувати не буду.

Вітаю команду cViVCNUFT_ComputerWorms — Haidei, Hrom і CHEREMUKHIN — із перемогою та чудовим результатом 🏆

Окремий респект команді sPolit_vozduhbenders — Yabchenko, Sadovnikov і Khalin. Команда політеху посіла восьме місце. Дуже крутий результат 👏

Минулорічна олімпіада залишила змішані почуття й багато роздратування. Цього разу результат у таблиці значно гірший, але реакція зовсім інша. Замість бажання посперечатися із задачами з’явився інтерес: як вони насправді розв’язуються і яких знань мені не вистачило.

Олімпіада добре показала слабкі місця. Недостатньо знати, що графи, дерева й динамічне програмування десь існують. Потрібно за обмежений час упізнати потрібну ідею, оцінити її складність і перетворити на робочий код.

Саме над цим і будемо працювати. Розберемо задачі, підтягнемо алгоритми й наступного разу прийдемо підготовленішими.

Сьогоднішню таблицю вже не змінимо. А от те, з чим прийдемо на наступну олімпіаду, — цілком 💪

Як дерево Фенвіка зберігає суми 🌲

Дерево Фенвіка корисне в задачах, де числа в масиві змінюються, а суми потрібно рахувати багато разів.

Візьмемо вісім чисел:

3 1 4 1 5 9 2 6

Нехай потрібно виконувати дві операції:

• додати число до одного елемента;
• знайти суму від початку масиву до вибраної позиції.

Звичайний цикл легко знайде суму. Але для сьомої позиції він прочитає сім елементів. Якщо масив містить сотні тисяч чисел і таких запитів багато, постійний перебір стає дорогим.

Можна заздалегідь порахувати всі накопичені суми:

3 4 8 9 14 23 25 31

Тоді сума перших семи чисел одразу дорівнює 25.

Але після зміни третього числа доведеться виправити суми для третьої, четвертої, п’ятої та всіх наступних позицій. Швидке читання отримали, зате оновлення стало повільним.

Дерево Фенвіка зберігає не всі накопичені суми, а суми окремих блоків. Для восьми позицій вони виглядають так:

позиція 1 зберігає суму [1]
позиція 2 зберігає суму [1–2]
позиція 3 зберігає суму [3]
позиція 4 зберігає суму [1–4]
позиція 5 зберігає суму [5]
позиція 6 зберігає суму [5–6]
позиція 7 зберігає суму [7]
позиція 8 зберігає суму [1–8]

Щоб знайти суму перших семи чисел, не потрібно читати всі сім:

[1–4] + [5–6] + [7]

У дереві це три комірки:

tree[4] + tree[6] + tree[7]

Вони не перетинаються й разом точно покривають позиції від першої до сьомої.

Якщо змінюється третє число, потрібно оновити лише блоки, до яких воно належить:

[3]
[1–4]
[1–8]

Тобто комірки:

tree[3]
tree[4]
tree[8]

Ось і вся основна ідея: дерево Фенвіка зберігає масив як набір блоків різного розміру. Великий потрібний відрізок складається з кількох готових блоків, а одна зміна торкається лише тих блоків, які містять змінений елемент.

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

Для цього й використовується дивний вираз i & -i.

Навіщо дереву Фенвіка i & -i 🧩

У дереві Фенвіка кожна позиція зберігає суму блоку. Розмір цього блоку можна отримати так:

i & -i

Першого разу цей вираз виглядає як чаклунство. Насправді він просто залишає наймолодший установлений біт числа — крайню праву одиницю в його двійковому записі.

Розберемо число 6:

6 = 00000110

Щоб отримати -6, комп’ютер інвертує біти й додає одиницю:

  00000110
↓ інвертуємо
  11111001
↓ додаємо 1
  11111010

Тепер виконуємо побітове AND:

  00000110
& 11111010
----------
  00000010

Отримали 2.

Отже:

6 & -6 = 2

Саме два елементи входять до блоку, який закінчується на шостій позиції:

[5–6]

Інший приклад — позиція 4:

4 = 00000100
4 & -4 = 4

Тому четверта комірка зберігає блок із чотирьох чисел:

[1–4]

Для позиції 7 результат дорівнює одиниці:

7 = 00000111
7 & -7 = 1

Отже, сьома комірка відповідає лише за себе:

[7]

Тепер можна знайти суму перших семи чисел.

Починаємо з позиції 7. Її блок має розмір 1, тому додаємо tree[7] і переходимо до позиції 6:

7 - 1 = 6

Шоста позиція зберігає блок із двох чисел. Додаємо tree[6] і переходимо до четвертої:

6 - 2 = 4

Четверта зберігає чотири числа:

4 - 4 = 0

Дійшли до нуля — сума готова:

tree[7] + tree[6] + tree[4]

У коді це виглядає так:

def prefix_sum(i):
    result = 0

    while i > 0:
        result += tree[i]
        i -= i & -i

    return result

Під час оновлення рухаємося в інший бік. Якщо змінилася третя позиція, потрібно оновити всі більші блоки, які її містять:

3 → 4 → 8

Для цього розмір блоку не віднімаємо, а додаємо:

def add(i, value):
    while i <= n:
        tree[i] += value
        i += i & -i

Замість проходу по всьому масиву кожна операція відвідує лише кілька комірок. Для мільйона елементів це приблизно двадцять переходів.

Концепція справді проста: зберігаємо суми правильно підібраних блоків і пересуваємося між ними. Але щоб побачити цю простоту за двійковими числами та i & -i, довелося добряче посидіти.

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

У наступному пості повернуся до Transparent Gateway. Зовнішній проксі вже потрапив до активного пулу — залишилося провести через нього запит із клієнтської VM і перевірити весь маршрут, а не лише окремі його частини.

Клієнтський трафік пройшов через обидва проксі 🧪

Алгоритмічний відступ завершено, повертаюся до Transparent Gateway.

Перед паузою зовнішній TLS-проксі нарешті пройшов validator і потрапив до активного пулу. Тепер у gateway є два маршрути:

локальний проксі
  → локальний echo-сервіс

зовнішній TLS-проксі
  → публічний echo-сервіс

Але перевірка проксі з самого gateway доводить лише те, що gateway може до них підключитися. Клієнтський трафік усе ще міг не перехоплюватися, піти неправильним маршрутом або взагалі обійти gateway.

Тому фінальну перевірку запускаю з окремої клієнтської VM. На ній немає адрес проксі, паролів або коду проєкту. Програми відкривають звичайні з’єднання, а єдиний маршрут за замовчуванням веде через Transparent Gateway.

Команда запускається з довіреної машини:

python3 deploy/verify-readiness.py \
  --public \
  --gateway tgadmin@<gateway> \
  --client tgadmin@<client>

Параметр --public додає до локальної перевірки справжній вихід в інтернет.

Спочатку клієнт звертається до локального echo-сервісу:

клієнт
  → Transparent Gateway
  → локальний проксі
  → локальний echo

Цей маршрут перевіряє перехоплення TCP-з’єднання, relay, авторизацію на проксі та повернення відповіді всередині стенда.

Потім клієнт виконує DNS-запит і встановлює HTTPS-з’єднання з публічним echo-сервісом:

клієнт
  → Transparent Gateway
  → зовнішній TLS-проксі
  → Cloudflare
  → публічний echo

Публічний сервіс повертає свіжий ідентифікатор запиту та адресу, з якої побачив з’єднання. Перевірка звіряє її з вихідною адресою зовнішнього проксі в активному пулі.

Для локального маршруту виконується така сама перевірка. Тому випадкова відповідь від іншого сервісу або пряме з’єднання клієнта за успіх не зарахуються.

Окремо клієнт надсилає три UDP-пакети не на DNS-порт. Transparent Gateway підтримує DNS через UDP, але довільний UDP-трафік через TCP-проксі передати не може. Такий трафік повинен блокуватися, а не тихо виходити в обхід проксі.

Після тесту лічильник правила DROP збільшився на три. Отже, усі контрольні пакети gateway справді зупинив.

Скорочений результат:

PASS validator cycle and lineage; two usable active upstreams
PASS fresh client UDP DNS via gateway
PASS TCP and verified public HTTPS
PASS public echo matches active exit [IP hidden]
PASS local transparent echo
PASS direct non-DNS UDP blocked
FULL_CLIENT_READINESS PASS

Тепер перевірені не лише окремі контейнери та проксі. Звичайний клієнт без власних налаштувань проксі пройшов через gateway до локального й публічного echo-сервісів, а непідтримуваний трафік не зміг обійти маршрут ✅

Наступна перевірка — перезавантажити gateway і переконатися, що обидва маршрути повернуться без ручного запуску.

Після перезавантаження повернувся весь маршрут 🔄

Раніше вже перевіряв автоматичний запуск Transparent Gateway після перезавантаження. Тоді у стенді був лише локальний проксі, тому перевірка закінчувалася на внутрішньому echo-сервісі.

Відтоді з’явився зовнішній TLS-проксі, його сертифікат, дані авторизації та публічний echo-сервіс. Старої перевірки вже недостатньо: systemd може успішно запустити контейнери, але це ще не означає, що клієнт знову вийде через них в інтернет.

Перед перезавантаженням зберігаю контрольний стан:

sudo python3 deploy/verify-boot.py --prepare
sudo systemctl reboot

Сценарій запам’ятовує ідентифікатор поточного завантаження, контейнери, стан захищених файлів і тестове значення в Redis.

Після повернення машини запускаю з довіреного комп’ютера повну перевірку:

python3 deploy/verify-full-boot.py \
  --gateway tgadmin@<gateway> \
  --client tgadmin@<client>

Спочатку вона перевіряє сам gateway:

- машина справді перезавантажилася;
- systemd сам запустив Transparent Gateway;
- конфігурація, секрети й сертифікат проксі не змінилися;
- дані Redis пережили перезавантаження;
- validator провів новий цикл і зібрав свіжий активний пул.

Потім окрема клієнтська VM повторює обидва маршрути:

клієнт
  → gateway
  → локальний проксі
  → локальний echo

клієнт
  → gateway
  → зовнішній TLS-проксі
  → публічний echo

Також перевіряються DNS, HTTPS-сертифікат, вихідна адреса проксі та блокування UDP-трафіку, який gateway не підтримує.

Скорочений результат:

PASS reboot: boot ID changed
PASS systemd automatic startup
PASS Redis and protected files preserved
PASS fresh proxy pools after reboot
FULL_CLIENT_READINESS PASS
FULL_REBOOT_CHECK PASS

Після перезавантаження нічого не запускав руками. Gateway сам підняв сервіси, дочекався нового пулу проксі й знову провів клієнтський трафік через локальний та публічний маршрути ✅

Але машина все ще існувала до початку перевірки. Наступний тест цікавіший: видалити gateway повністю й відтворити його з чистого шаблону.

Чиста VM стала готовим gateway за шість хвилин ♻️

Перезавантаження пройшло успішно. Але воно перевірило машину, на якій уже були код, конфігурація, секрети й дані Redis.

Якщо втратити її диск, systemd уже нічим не допоможе. Тому для фінальної перевірки зупинив робочий gateway і створив нову VM із чистого шаблону Debian.

Старий диск не копіював. Нова машина на початку не мала коду Transparent Gateway, конфігурації, контейнерів, образів Docker або томів із даними.

Щоб не виконувати весь процес руками, додав до репозиторію сценарій deploy/proxmox/recreate-lab.py. Він запускає повне відтворення стенда:

sudo python3 deploy/proxmox/recreate-lab.py \
  --evidence /root/tg-recreate-evidence

Каталог --evidence потрібен для результатів перевірки. Сценарій створює його сам і відмовляється перезаписувати попередній запуск.

Далі він послідовно:

зупиняє старий gateway
  ↓
створює нову VM із чистого шаблону
  ↓
чекає завершення cloud-init
  ↓
перевіряє порожній стан машини
  ↓
доставляє код і секрети
  ↓
розгортає Transparent Gateway
  ↓
перевіряє клієнтський трафік
  ↓
перезавантажує VM
  ↓
повторює повну перевірку

Перед розгортанням окремо переконався, що на новій VM немає каталогу застосунку, контейнерів, образів і томів Docker. Так тест не міг випадково використати залишки попереднього gateway.

Потім машина отримала код і шість захищених файлів конфігурації. Cloud-init підготував Debian і Docker, сценарій розгорнув застосунок, а systemd узяв на себе подальший запуск.

Перша повна готовність настала приблизно через три хвилини після початку створення VM:

clone:        20.81s
cloud-init:   97.63s
deployment:   78.27s
first ready: 189.44s

Після цього новий gateway перезавантажився й повторно провів клієнтський трафік через локальний та зовнішній проксі.

Фінальний результат:

PASS fresh machine identity
PASS clean application state before deployment
PASS cloud-init, secrets, deployment and systemd
FULL_CLIENT_READINESS PASS
FULL_REBOOT_CHECK PASS
RECREATE_CHECK PASS

Уся перевірка разом із перезавантаженням тривала трохи більше шести хвилин. Ручних виправлень — нуль.

Тепер Transparent Gateway існує не лише у вигляді вдало налаштованої VM. Його вдалося відтворити з чистого шаблону, провести через повну перевірку й перезавантажити без жодного «зараз швиденько зайду через SSH» 😌

У наступному пості зберу результат цілком, залишу посилання на статтю та репозиторій і чесно відмічу, чого цей стенд усе ще не перевіряє.

Transparent Gateway нарешті відтворюється з чистої VM ⚙️

Починав із gateway, який добре працював, але жив на одній вручну підготовленій VM. Поки її диск цілий — усе чудово. Якщо ні, залишається археологія в історії команд і спроби згадати, чому цей маршрут колись запрацював 😅

Тепер увесь шлях виглядає так:

чистий шаблон Debian
  → нова VM у Proxmox
  → cloud-init готує систему
  → окремо надходять код і секрети
  → сценарій розгортає gateway
  → systemd керує запуском
  → клієнт перевіряє локальний та публічний маршрути

Фінальний тест почався з чистої VM без коду, контейнерів, образів Docker, Redis і старих SSH-ключів.

Приблизно через три хвилини клієнт уже проходив через Transparent Gateway до локального та публічного echo-сервісів. Потім VM перезавантажилася й повторила весь маршрут без ручного втручання.

Повний цикл разом із перезавантаженням зайняв трохи більше шести хвилин:

FULL_CLIENT_READINESS PASS
FULL_REBOOT_CHECK PASS
RECREATE_CHECK PASS
manual repairs: 0

Але називати це повним відновленням після втрати хоста ще рано.

Шість файлів із конфігурацією та секретами для тесту забрав зі старої VM. Окрему резервну копію цього набору та процедуру її відновлення ще потрібно підготувати.

Також за межами перевірки залишилися:

- IPv6;
- оновлення токенів і сертифікатів проксі;
- робота з API справжнього провайдера;
- повне закріплення версій пакетів і базових Docker-образів;
- моніторинг і повний аудит безпеки.

Тобто gateway уже можна відтворити з чистого шаблону, але один зелений PASS усе ще не перетворює лабораторний стенд на безсмертний production 😌

У статті зібрав увесь шлях: шаблон Proxmox, cloud-init, доставку секретів, systemd, локальний і публічний echo, помилку з CONNECT, перезавантаження та повне відтворення VM:

https://devdays.net.ua/articles/rozghortannia-transparent-gateway-proxmox-cloud-init-systemd/

Код, сценарії розгортання та перевірки:

https://github.com/Va1b0rt/TransparentGateway

24 години на AI-агента — і захист перед AI-суддею 🎃

Зареєструвався на HackerRank Orchestrate October 2026. Бейдж учасника вже прилетів, тепер чекаю умову задачі.

Формат такий: на старті отримую практичну проблему, для якої потрібно спроєктувати й реалізувати AI-агента. На роботу — 24 години ⏱

Яку саме проблему доведеться вирішувати цього разу, поки не розкривають. Завдання надішлють 24 жовтня.

Користуватися AI-інструментами дозволено: Claude Code, Cursor, Codex або інші на власний вибір. Разом із кодом потрібно здати результати роботи агента та історію спілкування з AI під час розробки.

А після здачі — 30-хвилинна голосова співбесіда з AI-суддею. Потрібно пояснити архітектуру, свої рішення та компроміси.

Оцей момент мене й зацікавив. Згенерований код ще доведеться розібрати настільки, щоб відповісти, чому система влаштована саме так. «Воно якось запрацювало» — слабенький план для захисту 😅

Після участі розберу конкретну задачу, своє рішення і те, що вдалося перевірити за відведений час.

HackerRank Orchestrate — October 2026
https://www.hackerrank.com/hackerrank-orchestrate-october26

Встановив власний проєкт за власною інструкцією 😅

Transparent Gateway уже працював на домашньому стенді. Після попередніх пригод навіть навчився розгортатися на новій машині.

Але захотілося перевірити простішу й значно кориснішу ситуацію: людина відкрила GitHub, завантажила код і вирішила ним скористатися. Без моїх готових віртуалок і підказок через плече 🤔

Для тих, хто не застав початок: Transparent Gateway — це шлюз між клієнтськими машинами та інтернетом. Програми звертаються до сайтів звичайним способом, а шлюз спрямовує їхні з’єднання через налаштований проксі. Вписувати проксі окремо в браузер чи кожну програму не потрібно.

Маршрут виходить такий:

клієнт → gateway → проксі → сайт

Тому підготував чистий Debian і почав із цілком буденної команди:

git clone https://github.com/Va1b0rt/TransparentGateway.git

Далі потрібно було ввести параметри мережі, додати проксі й запустити сервіси.

Саме цей шлях і захотів зробити нормальним: щоб для першого запуску не доводилося спочатку вивчати внутрішню будову всього проєкту ⚙️

Почав із налаштувань. Бо адреса проксі одна, а файлів, яким щось від неї потрібно, уже декілька.

Налаштування без екскурсії по конфігах ⚙️

Для першого запуску gateway потрібні досить прості речі: клієнтська мережа, адреса проксі, його порт і, за потреби, логін із паролем.

Але всередині проєкту вони розкладаються по різних файлах. Частина належить мережевим налаштуванням, частина — списку проксі, ще частина — даним доступу.

Вручну це зробити можна. Але змушувати людину розбирати всі ці файли ще до першого запуску якось негостинно 😅

Тому додав до репозиторію scripts/tgctl.py — скрипт для налаштування й керування gateway.

На підготовленій машині, з каталогу проєкту, запускаю:

sudo python3 scripts/tgctl.py configure

Він послідовно запитує потрібні значення. Наприклад:

Protocol ... [http]: socks5
Authorised upstream proxy host or IP: proxy.example.com
Proxy port [3128]: 1080

Тут proxy.example.com — вигаданий приклад. Для роботи вводжу дані свого реального проксі.

Якщо потрібна авторизація, скрипт запитає логін і пароль. Пароль під час введення не відображається 🔑

Відповіді потрапляють у робочі файли з потрібними правами. Після цього окремою командою перевіряю конфігурацію:

sudo python3 scripts/tgctl.py check

У результаті перше знайомство з проєктом уже не починається з ручного редагування JSON-файлів ✅

А от чому пароль узагалі лежить окремо від адреси проксі — там є своя причина.

Мільйон доларів і трохи математики 💸

Прочитав у пості розбір про шанси стати доларовим мільйонером. Для України автор отримав приблизно 0,05%.

Спочатку взяв частку мільйонерів у населенні, потім додав власні припущення про стартові умови та вплив війни. Вийшла цифра, після якої хочеться закрити калькулятор і застрелитись піти зробити чай 😅

У коментарях зачепилися за питання: а чи можна цей відсоток вважати моїм особистим шансом?
Автор пояснив свою думку через можливості. Там, де більший платоспроможний ринок, легше знайти справу, на якій можна заробити великий капітал. Самого бажання багато працювати недостатньо, якщо покупцям нічим платити.

Із цим погоджуюся. Але між «скільки людей уже мають мільйон» і «чи зможу заробити його за життя» є різниця.

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

Щоб порахувати саме шанс, потрібно знати, скільки людей починали зі схожих умов, що робили й до чого прийшли за певний час. Самого ділення кількості мільйонерів на населення для цього замало. Звіт Credit Suisse, на який послався автор, описує розподіл статків, а не ймовірність конкретної людини розбагатіти.

Моя перша думка була простішою: «Але ж за ці гроші змагаються не всі».

Не кожен хоче будувати бізнес, продавати свій продукт чи ризикувати заради більшого доходу. Комусь достатньо стабільної роботи — і це нормальний вибір.

Тільки тут теж легко намалювати собі красиву математику. Прибрати зі знаменника всіх, хто «не грає», поділити ще раз — і порадіти новому відсотку. Але скільки насправді людей пробували, скільки не вийшло й за який період це рахувати? Цих даних у мене немає. Тому власні «тепер уже точно 5%» вигадувати не буду 🙂

Натомість є інша важлива деталь: жити в Україні й продавати лише в Україні — не одне й те саме.

Наприклад, можу робити гру або сервіс тут, а продавати людям з інших країн. Тоді можливості мого продукту залежать уже не тільки від того, скільки готові витратити покупці вдома.

Легкою задачу це не робить. За кордоном на мій продукт теж ніхто спеціально не чекає: доведеться знайти покупця й переконати його заплатити.

Тому думку автора про нерівні можливості приймаю. Місце, де живеш і працюєш, справді має значення. Але свої особисті шанси з цього відсотка все одно не вирахую.

Не знаю, наскільки вони вищі за 0,05%. І підміняти неприємну цифру приємнішою тільки заради настрою теж не хочу.

Але між «у цій країні мало мільйонерів» і «у мене майже немає шансів» — висновок, якого ця математика не доводить.

Мільйона поки немає. Але й статистично довести, що варто кидати спроби за нього конкурувати, теж не вдалося. Продовжую працювати 😅