Проксі працює, але здає мою IP 🕵️

Після успішного handshake я майже записав кандидата в робочий пул. Але ж проксі може додати мою реальну адресу в X-Forwarded-For і формально все одно повернути HTTP 200 😬

Тому validator спочатку йде до echo напряму й запам’ятовує адресу клієнта. Потім повторює запит через проксі.

Якщо direct IP знову видно як peer або вона з’явилась у Forwarded, X-Forwarded-For, X-Real-IP чи Client-IP — кандидат відхиляється.

Для разової зовнішньої перевірки використовую:

ANONYMITY_CHECK_URL=https://httpbingo.org/get

Саме /get, а не /ip. Поточному parser потрібні і origin, і об’єкт headers. Тому ipify та ifconfig.me сюди без доробки не підходять.

У лабораторії в мене інший endpoint:

ANONYMITY_CHECK_URL=http://10.10.10.2:8000/

Він перевіряє HAProxy та контейнери 301–308, але нічого не доводить про публічний Internet. Для production потрібен ще власний HTTPS echo. Чужий безкоштовний сервіс сьогодні працює, а завтра вводить rate limit — і знову весело 🙃

Адресу отримали. Тепер можна ранжувати. І тут найшвидші кандидати підготували ще один сюрприз.

Десять IP в одному плащі 🧥

Відсортував кандидатів за latency, подивився на красиву верхівку списку й уже хотів радіти 🚀

Потім перевірив ASN. Виявилось, кілька найшвидших адрес сидять в одного провайдера й навіть в одній підмережі. На папері проксі різні, а впадуть дружною компанією 😅

Для цього зробив окремий demo:

./scripts/run-diversity-ranking-demo.sh

Результат скорочено:

INPUT
proxy-1: ASN=AS1, latency=10ms
proxy-2: ASN=AS1, latency=11ms
proxy-3: ASN=AS2, latency=20ms

OUTPUT
1. proxy-1: ASN=AS1, score=92.909091
2. proxy-3: ASN=AS2, score=49.619048
3. proxy-2: ASN=AS1, score=28.444444

Повільніший AS2 піднявся між двома AS1 через ASN/subnet penalty. Це синтетичний тест: production snapshot він не чіпає, зате добре показує логіку ranker 🔍

Ще додав MIN_SCORE_THRESHOLD. Якщо нормальних кандидатів лише 40, POOL_SIZE=150 не змушує добирати 110 трупів для красивої цифри. Порожнє місце в пулі краще за проксі, який не пройшов поріг.

З ранжуванням розібрався. Залишилось безпечно передати результат між worker. Один ключ у Redis? Ну звісно, ні 😬

Один ключ у Redis? Ага, зараз 😅

Спочатку хотів тримати весь стан в одному Redis key. Fetcher записав список, validator його оновив, ranker відсортував. Просто ж 🤔

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

Тому розділив конвеєр на повні snapshots:

proxy_pool:raw:v1
proxy_pool:validated:v1
proxy_pool:reserve:v1
proxy_pool:active:v1

Перевірити поточний стан можна так:

./scripts/run-redis-rows.sh

На лабораторному стенді зараз:

proxy_pool:raw:v1: 1
proxy_pool:validated:v1: 1
proxy_pool:reserve:v1: 1
proxy_pool:active:v1: 1
transparent-gateway:validated:v1: 1

Ці числа показують, що ключі містять повні списки. Чи належать вони одному циклу — окремо звіряю через generated_at, source_generated_at і logs.

Запис теж зробив без проміжного стану: спочатку тимчасовий key, потім атомарний Redis RENAME. Читач бачить старий або новий повний JSON, а не половину нового пулу 🛡

Active готовий. Тепер просто віддам його HAProxy й піду пити каву. Принаймні такий був план ☕️

Віддав mixed pool у HAProxy. Майже 🚧

План здавався нормальним: ranker формує active pool, HAProxy підхоплює backend через config або Runtime API, я задоволений і йду далі 😎

Але пул змішаний: HTTP, HTTPS, SOCKS4, SOCKS5, ще й credentials подекуди є. HAProxy як TCP backend не виконає SOCKS handshake і не дістане пароль за credential_ref.

От і приїхали 😬

Між redsocks та upstream довелось додати protocol-aware relay:

VM → iptables → redsocks :12345
   → egress_relay :12000
   → HTTP / HTTPS / SOCKS4 / SOCKS5 upstream
   → destination

Перед новим з’єднанням relay перевіряє active snapshot, але не частіше ніж раз на три секунди. Потім вибирає кандидата, виконує правильний handshake і тільки тоді підставляє credentials. Restart або reload не потрібен ⚙️

Є чесне обмеження: у живому active pool поки один агрегований HAProxy endpoint. Тому показати реальний cooldown між двома direct candidates на цьому стенді я не можу. Логіка покрита unit-тестами, а HAProxy failover окремо перевірений на восьми LXC.

Отака вийшла проста задача «автоматично оновлювати список проксі» 😅

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

Автоматичний пул проксі — код, тести й граблі 🚀

Зібрав увесь шлях в одну статтю: від першого JSON до active pool, який gateway підхоплює без рестарту. Інформації вийшло нормально так 😅

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

python3 -m venv .venv
. .venv/bin/activate
python -m pip install -r requirements-dev.txt
python -m pytest -q

Результат:

............................ [100%]
28 passed

Усередині статті:

• connector adapters;
• HTTP, HTTPS, SOCKS4 і SOCKS5 validation;
• authenticated proxy без secrets у Redis;
• перевірка витоку IP;
• ASN diversity та quality threshold;
• атомарні snapshots;
• глухий кут із HAProxy;
• protocol-aware egress relay;
• шість практичних перевірок.

Обмеження теж не ховав: стенд поки має один агрегований HAProxy endpoint, для реальної різноманітності потрібні direct candidates, а для постійної зовнішньої перевірки — власний HTTPS echo.

Стаття, до якої вела ця серія:
https://devdays.net.ua/articles/avtomatychnyi-pul-proksi-zbir-validatsiia-ranzhuvannia/

Код:
https://github.com/Va1b0rt/TransparentGateway

Далі буду відучувати gateway від ручного налаштування однієї VM: Proxmox, cloud-init і deployment. Там теж без граблів не обійдеться ⚙️😬

Gateway працює. А повторити його я зможу? 🤔

Transparent Gateway уже маршрутизує DNS і TCP, оновлює active pool та переживає перезапуск контейнерів. На схемі — майже production. На диску — кілька днів моїх ручних пригод 😅

Поки VM жива, різниці не видно. Але якщо диск завтра вирішить піти у відпустку, чи вдасться відтворити той самий gateway на чистій машині без історії shell і магічного "десь я це вже правив"?

Почав із простого аудиту на gateway: перевірив середовище, стан cloud-init, версію Debian і запущені сервіси.

systemd-detect-virt
cloud-init status
. /etc/os-release; echo "$PRETTY_NAME"
docker compose ps

Ключові рядки виглядали так:

kvm
status: done
Debian GNU/Linux 13 (trixie)

Docker також показав усі шість сервісів запущеними. Здавалося б, де проблема?

Проблема в одному слові: done стосується cloud-init, а не всього gateway. VM створена автоматично, застосунок — ще ні. Далі пішов шукати, де саме закінчується автоматизація 🔍

Щоб зрозуміти, яку частину gateway справді можна відтворити, порівняв вміст робочої VM з тим, що зберігає Git. Перевірку запускав на gateway з кореня проєкту:

cd /opt/transparent-gateway
git ls-files | grep -E \
  '(^|/)(deploy|cloud-init|systemd|.*\.service$|docker-compose\.yml$|\.env\.example$)'

Результат короткий:

.env.example
docker-compose.yml

Скрипту розгортання немає. Конфігурації cloud-init немає. Окремого systemd-сервісу для gateway теж немає. Робочі .env, списки проксі та паролі живуть лише на конкретній VM.

До того ж відтворити треба не лише контейнери. У хоста три мережеві ролі: керування, клієнтський gateway і лабораторна мережа з проксі та echo-сервісом. Переплутати два інтерфейси — і Docker буде зелений, а клієнтський трафік піде гуляти не туди 🚶‍♂️

Отже, копії каталогу недостатньо. Потрібна процедура, яка відтворює весь стан — від мережі до повної перевірки готовності.

Запхнути все розгортання в runcmd. YAML починає мститися 📜

План номер два: cloud-init встановить Docker, забере код із Git, створить конфігурацію, передасть секрети й виконає docker compose up. Один YAML — одна VM — усі задоволені. Перші хвилин п’ять 😅

Далі runcmd росте, повторний запуск стає окремою пригодою, а перевірити розгортання можна лише створенням нової VM. Якщо команда впала посередині, треба вгадати, що вже виконалося, а що тільки збиралося.

Із секретами ще веселіше. Cloud-init зберігає отриманий user-data всередині /var/lib/cloud/instances/ і може згадати його в журналах. Передати там пароль проксі або токен API — це залишити секрет на диску під табличкою "я тут" 🔐

На gateway сам факт збереження можна перевірити без відкриття вмісту:

find /var/lib/cloud/instances -maxdepth 2 \
  -type f -name 'user-data*' -printf '%m %p\n'

Висновок вийшов простий: cloud-init потрібен, але він не повинен знати всю біографію застосунку. Його робота — зробити VM керованим хостом і передати естафету окремому коду розгортання.

Де закінчується cloud-init і починається gateway ⚙️

Після двох крайнощів межа нарешті стала нормальною:

шаблон Proxmox
  → cloud-init: ім’я, SSH, мережа
  → код розгортання: версія, конфігурація, systemd
  → Docker Compose
  → перевірка: знімки стану, проксі, весь маршрут

Секрети надходять окремим захищеним каналом. Шаблон їх не бачить, у Git їх немає, а user-data не перетворюється на музей паролів.

Ще одна важлива різниця: запущений контейнер — не обов’язково готовий сервіс. Зелений статус не доводить, що активний список проксі свіжий, relay приймає з’єднання, а клієнт справді виходить через gateway.

Тому остаточний критерій буде жорстким: нова VM з чистого шаблону, повторюване розгортання, перезавантаження і жодної додаткової SSH-команди. Якщо треба "тільки один маршрут руками поправити" — автоматизація ще не завершена 😅

У статті зібрав аудит поточної VM, дві відкинуті крайнощі й архітектуру наступного етапу:
https://devdays.net.ua/articles/chomu-transparent-gateway-ne-hotovyi-do-production/

Наступний матеріал буде практичним: створю чистий шаблон, підготую cloud-init і systemd, а потім перевірю перезавантаження та повне відтворення gateway.

Видалити VM і не пошкодувати 😅

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

Зараз gateway прив’язаний до конкретної VM. Якщо з нею щось станеться, швидко розгорнути таку саму не вийде. Тому хочу перетворити налаштовану вручну машину на відтворюване розгортання: створив нову VM, запустив автоматизацію — отримав готовий gateway.

Мій домашній стенд працює на Proxmox, тому почну з чистого шаблону Debian. Це базова VM без коду gateway, паролів, даних Redis і слідів попередніх експериментів. Proxmox використовуватиме її як основу для створення нових машин.

Початкове налаштування виконає cloud-init. Це стандартний механізм, який готує VM під час першого запуску: задає ім’я машини, створює користувача, додає SSH-ключі, налаштовує мережу та встановлює Docker.

На цьому робота cloud-init закінчується. Він готує операційну систему, але не розгортає сам Transparent Gateway. Код застосунку, його конфігурацію, секрети, запуск контейнерів і перевірку готовності передам окремому сценарію. Так початкове налаштування VM не залежить від конкретної версії gateway, а застосунок можна оновити без створення нової машини.

Після розгортання systemd керуватиме запуском gateway і підніматиме його після перезавантаження.

Хто тут за що відповідає 🧩

Щоб автоматизація не перетворилася на один великий скрипт із правами root, розділив розгортання на кілька частин:

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

Шаблон містить лише чистий Debian і підтримку cloud-init. У ньому немає коду Transparent Gateway, секретів, Docker-образів або даних Redis. Це основа, яку можна використовувати для різних машин.

Proxmox створює з шаблону нову VM, підключає мережеві інтерфейси й передає початкові налаштування через cloud-init.

Cloud-init готує операційну систему: створює користувача, додає SSH-ключі, налаштовує мережу та встановлює Docker. Після цього машина готова прийняти застосунок, але самого gateway на ній ще немає.

Далі окремий сценарій доставляє потрібну версію коду, перевіряє конфігурацію та запускає контейнери. Секрети передаються окремо: вони не потрапляють ані в шаблон, ані в Git, ані в дані cloud-init.

Після розгортання керування переходить до systemd. Він запускає Transparent Gateway після Docker і мережі, а також піднімає його знову після перезавантаження VM.

Останній етап — перевірка готовності. Вона дивиться не лише на запущені контейнери, а й на свіжість пулу проксі та проходження клієнтського запиту через gateway.

Тепер кожна частина має одну роботу. А якщо щось зламається, принаймні не доведеться шукати одну потрібну команду посеред YAML на три екрани 😅

Шаблон, який нічого не знає про gateway 🧼

Розгортання починається не з Docker і навіть не з коду застосунку. Спочатку потрібна чиста основа для майбутніх VM.

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

За основу взяв офіційний Debian 13 genericcloud. Цей образ уже підготовлений для роботи з cloud-init, тому не потрібно щоразу проходити встановлення Debian вручну.

Створення шаблону автоматизував скриптом create-clean-template.sh із репозиторію Transparent Gateway. Він завантажує образ і файл із контрольними сумами, перевіряє завантажений qcow2, створює VM у Proxmox, додає диск cloud-init і перетворює результат на шаблон.

Запускається скрипт від root на хості Proxmox:

sudo ./deploy/proxmox/create-clean-template.sh

На цьому місці дуже хочеться запустити підготовлену VM й перевірити, чи Debian узагалі завантажується. Але після першого запуску система вже створить власні SSH-ключі, ідентифікатор машини та стан cloud-init. Якщо потім перетворити її на шаблон, цей багаж можуть отримати всі наступні VM.

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

Коду Transparent Gateway, паролів, Docker-образів і даних Redis у шаблоні немає. Він знає лише про Debian, віртуальне обладнання та cloud-init.

Першу VM із цього шаблону створив без проблем. Debian завантажився, мережа й SSH запрацювали, а cloud-init завершився з попередженням.

Ну а як інакше. Це ж був перший запуск 😅

Debian готовий. Gateway ще ні 🧱

Чистий шаблон є. Тепер Proxmox може створити з нього нову VM, але сам Debian ще не знає, яке ім’я отримати, хто матиме доступ через SSH і як налаштувати мережу.

Ці параметри Proxmox передає через cloud-init. Під час першого запуску він створює адміністративного користувача, додає дозволені SSH-ключі, налаштовує мережеві інтерфейси та встановлює Docker.

Після завантаження перевірив результат:

cloud-init status --wait
ip -br address
docker --version
docker compose version

Cloud-init завершився зі статусом done, мережеві інтерфейси отримали потрібні адреси, а Docker і Compose були готові до роботи.

Але контейнерів на машині ще немає. Як і коду Transparent Gateway, його конфігурації та секретів. Cloud-init підготував звичайний Docker-хост і на цьому закінчив свою роботу.

Тепер цю VM можна використовувати не лише для gateway. А нову версію застосунку можна розгорнути без повторного створення машини та нового запуску cloud-init.

Наступний крок — доставити на підготовлений хост конкретну версію Transparent Gateway. Одного docker compose up -d недостатньо: ця команда не перевірить, який код лежить на диску, чи на місці конфігурація та секрети й чи готовий gateway приймати трафік. Потрібен окремий сценарій, який перевірить середовище, розгорне потрібну версію, запустить контейнери та дочекається готовності сервісів. Саме ним і займуся далі.

docker compose up — і готово. Так? 😏

VM підготовлена, Docker встановлений. Найкоротший шлях далі виглядає очевидно: забрати код і виконати docker compose up -d.

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

Тому додав до репозиторію Transparent Gateway окремий сценарій deploy/deploy.py. Він запускається на новій VM після доставки коду.

Для лабораторного стенда команда виглядає так:

sudo python3 deploy/deploy.py \
  --source "$PWD" \
  --commit "$(git rev-parse HEAD)" \
  --lab-fixture \
  --timeout 300

Перед запуском контейнерів сценарій перевіряє Debian, Docker, каталоги, мережеві інтерфейси та отриману версію коду. Потім виконує docker compose config --quiet, щоб зупинитися ще до запуску, якщо конфігурація пошкоджена або в ній бракує обов’язкових значень.

Прапорець --lab-fixture додає локальний проксі з авторизацією та echo-сервіс. Вони потрібні лише для стенда: через них можна перевірити маршрут клієнтського запиту, не залежачи від зовнішнього проксі або доступності інтернету.

Лише після всіх перевірок сценарій збирає образи, запускає контейнери та чекає, поки validator додасть придатний проксі до активного пулу.

Успішне завершення виглядає приблизно так:

POOL_COUNTS {"active": 1, "raw": 1, "reserve": 1, "validated": 1}
LOCAL_READY

Тепер є одна команда, яка приводить чистий Docker-хост до готового локального стенда. Залишилося виконати її ще раз і переконатися, що повторне розгортання нічого не ламає. Бо перший успішний запуск — це ще не автоматизація. Це поки що везіння 😅

Другий запуск має бути нудним 🔁

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

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

Для такої перевірки додав до репозиторію deploy/verify-repeat.py. Перед повторним розгортанням він зберігає ідентифікатори контейнерів, стан Redis, контрольні суми й права конфігураційних файлів, правила iptables та політику маршрутизації.

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

sudo python3 deploy/verify-repeat.py \
  --source "$PWD" \
  --commit "$(git rev-parse HEAD)"

Результат вийшов саме таким, яким і мав бути:

PASS same 6 application and 2 fixture containers
PASS Redis process and data preserved
PASS config bytes/inodes/mtime/permissions unchanged
PASS iptables and policy routing unchanged
IDEMPOTENT_REPEAT PASS

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

З кодом порядок. Тепер залишилося передати на нову VM секрети й не розкласти їх дорогою по Git, cloud-init і журналах 😅

Код у Git. А паролі куди? 🔐

Розгортання вже можна повторити на новій VM. Але gateway потрібні паролі проксі й токен провайдера. Додати їх до репозиторію — означає залишити в історії Git. Передати через cloud-init теж не варіант: отримані дані залишаються на диску VM і можуть потрапити в журнали 🫠

Тому секрети підготував окремо на довіреній машині. Каталог належить root, має права 0700 і не потрапляє в Git.

Для передачі додав до репозиторію deploy/secret-transfer.py 🚚

sudo python3 deploy/secret-transfer.py send \
  --host tgadmin@<gateway> \
  --directory /root/tg-runtime

Сценарій передає файли через стандартний ввід SSH. Значення не з’являються в аргументах процесів і не друкуються в термінал.

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

/etc/transparent-gateway/runtime

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

Успішний результат не показує жодного секретного значення:

SECRET_DELIVERY PASS files=5 changed=5; validated, root-owned; values hidden

У результаті нову VM вдалося розгорнути без паролів у шаблоні, Git або cloud-init, що не може не радувати 😌

Тепер можна перезавантажити машину й подивитися, чи повернеться gateway до роботи без ручного запуску контейнерів 🔄

Перезавантажив VM. Gateway повернувся сам 🔄

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

Можна було залишити цю роботу Docker через restart: unless-stopped. Але тоді запуском одночасно керували б Docker і systemd. Один уже перезапускає контейнери, а другий ще тільки намагається зрозуміти, чому вони впали. Весела компанія, але для нормальної діагностики не підходить 😅

Тому для всіх контейнерів залишив:

restart: "no"

А керування всім gateway передав одному systemd-сервісу. Для його встановлення додав deploy/install-service.py:

sudo python3 deploy/install-service.py \
  --commit "$(git rev-parse HEAD)" \
  --lab-fixture

Сценарій перевіряє, що потрібна версія вже розгорнута, конфігурація придатна для запуску, а мережа й Docker готові. Потім установлює transparent-gateway.service і вмикає його автоматичний запуск.

Systemd спочатку чекає мережу та Docker. Лише після цього запускає контейнери й повідомляє про готовність, коли gateway отримав свіжий пул проксі та пройшов локальну перевірку.

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

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

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

sudo python3 deploy/verify-boot.py

Результат:

PASS ordering: network-online + Docker ready before application
PASS same 6 application + 2 lab containers; Docker auto-restart disabled
PASS Redis marker and protected config/secrets/proxy CA preserved
PASS fresh pools and authenticated local relay echo after reboot
REBOOT_CHECK PASS

VM справді перезавантажилася, systemd сам підняв gateway, а конфігурація, секрети й дані Redis залишилися на місці ✅

Тепер можна перевіряти не лише сам gateway, а й повний шлях трафіку з окремої клієнтської машини.

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

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

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-коди, супутниковий зв’язок і носії даних. Надлишкові біти здаються зайвими лише доти, доки щось не зламається 😄