Скільки бітів у пам'яті потрібно виділити для зберігання IP-адреси

Скільки бітів у пам'яті потрібно виділити для зберігання IP-адреси



Урок 4
§4. Глобальна мережа Інтернет



1. Згадайте, навіщо дані, що передаються Інтернетом, розбиваються на пакети.
2. Яка роль маршрутизаторів?
3. Яким чином можна підключити ноутбук до Інтернету? Якщо всі варіанти доступні, який ви оберете? Чому?
4. Наведіть приклад, коли комп'ютер може мати кілька 1Р-адрес.
5. Скільки бітів у пам'яті потрібно виділити для зберігання 1Р-адреси?
6. Навіщо потрібні доменні адреси?
7. Виконайте за вказівкою вчителя завдання у робочому зошиті.



Підготуйте повідомлення



а) «Історія розвитку Інтернету»
б) «Протоколи Інтернету»
в) "Служба DNS"
г) «Домени верхнього рівня»



Завантажити матеріали уроку



Оптимізуємо використання пам'яті для пошуку IP-адрес



Близько трьох років у мене виникали проблеми з моїм навчальним сайтом Mess With DNS: періодично у нього закінчувалася пам'ять і він перезавантажувався OOM.



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



Шлях був складним, і в процесі я багато чого навчилася.



Доступно всього приблизно 100 МБ пам'яті



Mess With DNS працює в VM з приблизно 465 МБ ОЗУ, які, згідно ps aux (стовпець RSS), розділені якось так:



Залишається приблизно 110 МБ вільної пам'яті.



Коли я встановила GOMEMLIMIT на 250 МБ, щоб якщо Mess With DNS використовував більше 250 МБ пам'яті, запускався збирач сміття; гадаю, це допомагало, але цілком проблему не вирішило.



Проблема: OOM вбиває скрипт бекапу



Кілька тижнів тому я вперше почала виконувати бекап бази даних Mess With DNS за допомогою restic.



Він працював нормально, але оскільки Mess With DNS працює без особливо великого обсягу вільної пам'яті, напевно, restic іноді потрібно більше пам'яті, ніж було доступно в системі, тому іноді скрипт бекапу вбивався по OOM.



Це було проблемою, бо





  1. бекапи іноді могли пошкоджуватися


  2. що важливіше, при своїй роботі restic відключає блокування, тому мені доводилося вручну виконувати розблокування, щоб бекапи продовжували працювати. Виконання подібної ручної праці — перше, чого я намагаюся позбутися у всіх своїх веб-сервісах (ні в кого на це немає часу!), тому мені дуже хотілося щось із цим зробити.




Ймовірно, ця проблема має кілька рішень, але я вирішила зробити так, щоб Mess With DNS використовував менше пам'яті, і в системі залишалося більше вільної пам'яті (в основному тому, що це мені здалося цікавим завданням).



Чим зайнята пам'ять: IP-адреси



У минулому я кілька разів виконувала профіль пам'яті Mess With DNS, тому знала, що займає основну частину пам'яті Mess With DNS: IP-адреси.



При запуску Mess With DNS завантажує в пам'ять базу даних, в якій можна пошукати ASN кожної IP-адреси, щоб при отриманні DNS-запиту вона могла б взяти вихідну IP-адресу виду 74.125.16.248 і повідомити, що ця IP-адреса належить GOOGLE .



Сама ця база даних займає приблизно 117 МБ пам'яті, і проста перевірка du дала мені зрозуміти, що це занадто - вихідні текстові файли мали розмір всього 37 МБ!



$ du -sh *.tsv 26M ip2asn-v4.tsv 11M ip2asn-v6.tsv


Спочатку це працювало так: у мене був масив виду



і я виконувала двійковий пошук по ньому, щоб знайти діапазони, що містили IP.По суті, це найпростіша річ, до того ж, дуже швидка: моя машина може виконувати приблизно 9 мільйонів операцій пошуку за секунду.



Спроба 1: використовуємо SQLite



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





  • написала короткий скрипт на Python з використанням sqlite-utils для імпорту файлів TSV до бази даних SQLite


  • змінила свій код, щоб виконувався вибір із бази даних




Це дозволило досягти моєї початкової мети за рівнем використання пам'яті (після збирання сміття пам'ять тепер взагалі практично не використовувалася, тому що вся таблиця була на диску!), хоч я і не знаю точно, наскільки активне застосування збирача сміття викликало б це рішення у разі множини Одночасних запитів. Я виконала короткий профіль пам'яті, на одну операцію пошуку розподілявся приблизно 1 КБ пам'яті.



Але поговоримо про проблеми, з якими я зіткнулася при роботі з SQLite.



Проблема: як зберігати IPv6 адреси



SQLite не має підтримки big integer, а адреси IPv6 мають розмір 128 бітів, тому я вирішила зберігати їх як текст.



Зрештою я обрала таку схему:



CREATE TABLE ipv4_ranges ( start_ip INTEGER NOT NULL, end_ip INTEGER NOT NULL, asn INTEGER NOT NULL, country TEXT NOT NULL, name TEXT NOT NULL ); CREATE TABLE ipv6_ranges ( start_ip TEXT NOT NULL, end_ip TEXT NOT NULL, asn INTEGER, country TEXT, name TEXT ); CREATE INDEX idx_ipv4_ranges_start_ip ON ipv4_ranges (start_ip); CREATE INDEX idx_ipv6_ranges_start_ip ON ipv6_ranges (start_ip); CREATE INDEX idx_ipv4_ranges_end_ip ON ipv4_ranges (end_ip); CREATE INDEX idx_ipv6_ranges_end_ip ON ipv6_ranges (end_ip);


Крім того, я дізналася, що Python має модуль ipaddress , тому можна використовувати ipaddress.ip_address(s).exploded , щоб адреси IPv6 розгорталися і порівняння рядків виконувалося правильно.



Проблема: це в п'ятсот разів повільніше



Я провела невеликий бенчмаркінг, показаний нижче. З'ясувалося, що за секунду може виконуватися 17 тисяч операцій пошуку адрес IPv6, схожі показники були і для IPv4.



Це мене дуже розчарувало: можливість виконувати пошук 17 тисяч адрес на розділ цілком би мене влаштувала (у Mess With DNS не дуже багато трафіку), але початковий код міг виконувати пошук 9 мільйонів разів на секунду.



 ips := []net.IP<> count := 20000 for i := 0; i < count; i++ < // створюємо випадкову адресу IPv6 bytes := randomBytes() ip := net.IP(bytes[:]) ips = append(ips, ip) >now := time.Now() success := 0 for _, ip := range ips < _, err := ranges.FindASN(ip) if err == nil < success++ >> fmt.Println(success) elapsed := time.Since(now) fmt.Println("number per second" , float64(count)/elapsed.Seconds())


Настав час EXPLAIN QUERY PLAN



Я ніколи не робила EXPLAIN у SQLite, тому вирішила, що це буде цікава можливість перевірити, що робить план запитів.



sqlite> explain query plan select * from ipv6_ranges where '2607:f8b0:4006:0824:0000:0000:0000:200e' BETWEEN start_ip and end_ip; QUERY PLAN `--SEARCH ipv6_ranges USING INDEX idx_ipv6_ranges_end_ip (end_ip>?)


Схоже, він використовує індекс end_ip, але не індекс start_ip; отже, мабуть, логічно, що він повільніший, ніж двійковий пошук.



Я спробувала розібратися, чи можна якось зробити, щоб SQLite використовувала обидва індекси, але не змогла нічого знайти; мабуть вона все одно сама знає, як краще.



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



Намагаючись змусити SQLite використовувати обидва індекси, я спробувала наступне:



Спроба 2: використовуємо trie



Наступною моєю ідеєю було використання trie (префіксного дерева), тому що в мене було невиразне враження, що trie вимагатиме менше пам'яті, і я знайшла бібліотеку ipaddress-go, що дозволяє шукати IP-адреси за допомогою trie.



Я спробувала використати її (код), але думаю, що робила щось зовсім не так, тому що в порівнянні з моїм наївним масивом + двійковим пошуком:





  • воно використовувало НАБАГАТО більше пам'яті (800 МБ для зберігання одних лише адрес IPv4)


  • операції пошуку виконувались набагато повільніше (я могла виконувати лише 100 тисяч за секунду проти 9 мільйонів за секунду)




Не зовсім розумію, що тут пішло не так, але я здалася і вирішила натомість спробувати зробити так, щоб мій масив використав менше пам'яті, а двійковий пошук залишити.



Примітки щодо профілю пам'яті



Я дізналася, що за допомогою пакету runtime можна дізнатися скільки пам'яті розподілено в програмі на даний момент. Саме так я отримала всі представлені у пості показники. Ось код:



func memusage() < runtime.GC() var m runtime.MemStats runtime.ReadMemStats(&m) fmt.Printf("Alloc = %v MiB\n", m.Alloc/1024/1024) // записуємо mem.prof f , err := os.Create("mem.prof") if err != nil < log.Fatal(err) >pprof.WriteHeapProfile(f) f.Close() >


Ще я дізналася, що якщо використовувати pprof для аналізу профілю купи, проаналізувати його можна двома способами: передавати go tool pprof або --alloc-space , або --inuse-space . Не знаю, чому цього раніше не зрозуміла, але alloc-space повідомляє про все, що було розподілено, а inuse-space включає тільки пам'ять, яка використовується на даний момент.



Тим не менш, я часто виконувала go tool pprof -pdf --inuse_space mem.prof > mem.pdf . Крім того, щоразу при використанні pprof я зверталася до свого введення в pprof - напевно, цей пост я використовую найчастіше з написаних мною. Варто додати до нього --alloc-space та --inuse-space .



Спроба 3: робимо так, щоб масив займав менше пам'яті



Я зберігала свої записи ip2asn так:



У мене було три ідеї щодо того, як це покращити:





  1. У Name і Country є безліч повторень, тому що багато діапазонів IP-адрес належать одному ASN


  2. net.IP всередині влаштований як [] byte, тому здається, що тут використовується необов'язковий покажчик. Може, є спосіб вбудувати його у struct?


  3. Можливо, мені навіть не потрібні були одночасно і початковий IP, і кінцевий IP: часто діапазони розташовані послідовно, тому, ймовірно, я зможу переналаштувати так, щоб був потрібний тільки початковий IP




Ідея 3.1: звільнення від дублювання Name та Country



Я вирішила, що можу зберегти інформацію ASN в масив, а потім просто зберігати індекс масиву в моїй структурі IPRange . Ось struct, щоб ви зрозуміли, що я маю на увазі:



type IPRange struct < StartIP netip.Addr EndIP netip.Addr ASN uint32 Idx uint32 >type ASNInfo struct < Country string Name string >type ASNPool struct


І це спрацювало! Споживання пам'яті знизилося з 117 МБ до 65 МБ - економія 50 МБ. Я була дуже рада цьому.



Наскільки великі ASN?



Невелика примітка: я зберігаю ASN в uint32 , але чи це правильно? Я подивилася у файлі ip2asn, найбільше значення було 401307, хоча в деяких рядках було вказано 4294901931, що набагато більше, але все одно знаходиться в межах uint32. Тому безперечно варто використовувати uint32 .



59.101.179.0 59.101.179.255 4294901931 Unknown AS4294901931


Ідея 3.2: використовувати netip.Addr замість net.IP



Виявилося, я не єдина вважала, що net.IP використовує невиправдано велику кількість пам'яті - ще в 2021 році розробники з Tailscale випустили нову бібліотеку роботи з IP-адресами для Go, яка вирішує цю та багато інших проблем. Вони написали про це чудову посаду.



Я (на втіху) виявила, що ця нова бібліотека для IP-адрес не тільки існує і робить рівно те, що мені потрібно, але і стала стандартною бібліотекою Go під назвою netip.Addr. Перехід на netip.Addr був дуже простим і дозволив заощадити ще 20 МБ пам'яті, тобто тепер ми споживаємо лише 46 МБ.



Я не спробувала третю ідею (видалення кінцевого IP з struct), тому що я і так програмувала надто багато для суботнього ранку, і мене цілком влаштовували мої досягнення.



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



У реальному житті все це було заплутаніше



Хоч я й намагалася пояснити процес простим лінійним чином: «я спробувала X, потім Y, потім Z», насправді це не зовсім правда — я завжди намагаюся викладати свій реальний процес налагодження (повний хаос) так, щоб він здавався лінійним і зрозумілим, тому що реальність фіксувати надто стомлюючим. Насправді процес був швидше таким:





  • спробуємо SQLite


  • спробуємо trie


  • переосмислюємо знову всі висновки, які я зробила про SQLite, повертаємося назад і переглядаємо результати


  • так, стоп, а що там щодо індексів?


  • Дуже запізно усвідомлюємо, що можна було використовувати runtime для перевірки того, скільки пам'яті використовується для всього, і починаємо це робити


  • знову повертаємось до trie, можливо, я все не так зрозуміла


  • здаємось і повертаємося до двійкового пошуку


  • знову вивчаємо всі показники trie/SQLite, щоб переконатися, що я не помилилась




Примітка про використання 512 МБ пам'яті



Хтось запитав мене, чому мені просто не додати VM ще пам'яті. Я з легкістю могла б дозволити собі оплачувати VM з 1 ГБ пам'яті, але я вважала, що 512 МБ має бути достатньо (та насправді і 256 МБ має бути достатньо!), тому я вважала за краще залишитися в рамках цього обмеження. Це свого роду цікава головоломка.



Деякі ідеї з відповідей



Мені запропонували багато хороших ідей, про які я не подумала. Я записала їх на згадку, і, напевно, колись знову влаштую «Веселий день підвищення продуктивності».





  • Спробувати пакет Go unique для ASNPool. Хтось спробував його, але він використовує більше пам'яті, ймовірно, тому що вказівники в Go мають розмір 64 біти


  • Спробувати компілювати з опцією GOARCH=386 , щоб використовувати 32-бітові покажчики для економії простору (можливо, у поєднанні з unique!)


  • Повинно бути можливим зберігати всі IPv6 адреси всього в 64 бітах, тому що тільки перші 64 біти адреси публічні


  • Інтерполяційний пошук може бути швидше двійкового, тому що IP-адреси числові


  • Спробувати формат бази даних MaxMind з mmdbwriter або mmdbctl


  • Пакет таблиць маршрутизації Tailscale art




Результат: заощаджено 70 МБ пам'яті!



Я розгорнула нову версію і тепер Mess With DNS використовує менше пам'яті! Ура!





  • операції пошуку стали трохи повільнішими — у моєму мікробенчмарку кількість знизилася з 9 мільйонів до 6 мільйонів на секунду, можливо тому, що я додала невеликий ступінь непрямого управління. Втім, обмін зниження пам'яті невелике збільшення необхідних ресурсів видається прийнятним компромісом.


  • система все одно використовує більше пам'яті. чим сирі текстові файли (46 МБ проти 37 МБ); гадаю, простір займають покажчики, і це нормально.




Не знаю точно, чи все це вирішить мої проблеми з пам'яттю, ймовірно, ні! Але мені було цікаво, я дізналася щось нове про SQLite, все ще не знаю, що думати про trie, і ще більше полюбила двійковий пошук.



IP-адреси



IPv4 використовує 32-бітові адреси, що обмежують адресний простір 4294967296 (2 32) можливими унікальними адресами. Кожен хост і маршрутизатор в Інтернеті мають IP-адресу. IP-адреса не має відношення до хоста. Він має відношення до мережного інтерфейсу, тому іноді хост або маршрутизатор можуть мати кілька IP-адрес.



ІР-адреси мають ієрархічну організацію. Перша частина має змінну довжину та задає мережу, а остання вказує на хост.



Зазвичай IP-адреси записуються у вигляді 4 десяткових чисел, кожне в діапазоні від 0 до 255 розділеними точками (dot-decimal notation). Кожна частина представляє один байт адреси. Наприклад, шістнадцяткова адреса 80D00297 записується як 128.208.2.151.



Визначення:
Префікс - безперервний блок простору IP-адрес, що відповідає мережі, в якій мережева частина збігається для всіх хостів.



Префікс визначається найменшою IP-адресою в блоці та розміром блоку. Розмір визначається числом бітів в мережній частині, біти, що залишилися, в частині хоста можуть змінюватись. Таким чином, розмір є мірою двійки. Він записується після префікса IP-адреси у вигляді слеша та довжини мережевої частини в бітах. У попередньому прикладі префікс містить 28 адрес і тому для мережевої частини відводиться 24 біта. Записується так: 128.208.2.0/24.



Класи IP-мереж



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



Всього 3 класи IP-адрес:





  • Клас A. IP мережевих адрес використовує ліві 8 біт (найлівіший байт) для вказівки мережі, що залишилися 24 біти (що залишилися три байти) для ідентифікації інтерфейсу хоста в цій мережі. Адреси класу A завжди мають найлівіший біт найлівішого байта нульовим, тобто значення від 0 до 127 для першого байта в десятковій нотації. Таким чином, доступно максимум 128 адрес мереж класу A, кожна з яких може містити до 33,554,430 інтерфейсів.Однак мережі 0.0.0.0 (відома як маршрут за замовчуванням) та 127.0.0.0 (loop back мережа) мають спеціальне призначення і не доступні для використання як ідентифікатори мережі. Тому доступно лише 126 адрес мереж класу A.


  • Клас B. IP мережевих адрес використовує ліві 16 біт (два лівих байти) для ідентифікації мережі, що залишилися 16 біт (останні два байти) вказують хостові інтерфейси. Адреса класу B завжди має найлівіші два біти встановленими в 1 0. Таким чином, для номера мережі залишається 14 біт, що дає 32767 доступних мереж класу B. Перший байт адреси мережі класу B може приймати значення від 128 до 191, і кожна з таких мереж може мати до 32766 доступних інтерфейсів.


  • Клас C. IP мережевих адрес використовує ліві 24 біт (три лівих байта) для ідентифікації мережі, що залишилися 8 біт (останній байт) вказує хостовий інтерфейс. Адреса класу З завжди має найлівіші три біти встановленими в 1 1 0. Таким чином, для номера мережі залишається 14 біт, що дає 4,194,303 доступних мереж класу B. Перший байт адреси мережі класу B може приймати значення від 192 до 255, і кожна з таких мереж може мати до 254 доступних інтерфейсів. Однак мережі класу C з першим байтом більше, ніж 223, зарезервовані та не використовуються.




Існує також спеціальні адреси, які зарезервовані для 'непов'язаних' мереж - це мережі, які використовують IP, але не підключені до Інтернету. Ось ці адреси:





  • Одна мережа класу A: 10.0.0.0


  • 16 мереж класу B: 172.16.0.0 – 172.31.0.0


  • 256 мереж класу С: 192.168.0.0 – 192.168.255.0




Мережеві адреси, адреси інтерфейсів та широкомовні адреси



IP адреса може означати одну з трьох:





  • Адреса IP мережі (група IP пристроїв, які мають доступ до загального середовища передачі - наприклад, всі пристрої в сегменті Ethernet). Мережева адреса завжди має біти інтерфейсу (хоста) адресного простору встановленими в 0 (якщо мережа не розбита на підмережі - як ми ще побачимо);


  • Широкомовна адреса IP мережі (адреса для 'розмови' з усіма пристроями в IP мережі). Широкомовні адреси для мережі завжди мають інтерфейсні (хостові) біти адресного простору встановленими в 1 (якщо мережа не розбита на підмережі – знову ж таки, як ми невдовзі побачимо).


  • Адреса інтерфейсу (наприклад, Ethernet-адаптер або PPP інтерфейс хоста, маршрутизатора, сервера друку ітд). Ці адреси можуть мати будь-які значення хостових бітів, виключаючи всі нулі або всі одиниці – щоб не плутати з адресами мереж та широкомовними адресами.






  • Для мережі класу A: (один байт під адресу мережі, три байти під номер хоста)


    • 10.0.0.0 мережа класу А, тому що всі хостові біти дорівнюють 0.


    • 10.0.1.0 адреса хоста у цій мережі


    • 10.255.255.255 широкомовна адреса цієї мережі, оскільки всі мережеві біти встановлені в 1




    • 172.17.0.0 мережа класу B


    • 172.17.0.1 адреса хоста у цій мережі


    • 172.17.255.255 мережна широкомовна адреса




    • 192.168.3.0 адреса мережі класу C


    • 192.168.3.42 хостова адреса в цій мережі


    • 192.168.3.255 мережна широкомовна адреса




    Майже всі доступні мережеві IP-адреси належать класу C.



    Маска підмережі



    Довжина префікса не виводиться з IP-адреси, тому протокол маршрутизації змушені передавати префікси на маршрутизатори. Іноді префікси задаються за допомогою довжини.



    Визначення:
    Маска підмережі - двійкова маска, що відповідає довжині префікса, в якій одиниці вказують на мережну частину.



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



    Стандартна маска підмережі - всі мережеві біти в адресі встановлені в '1' і всі хостові біти встановлені в '0'. Це означає, що стандартні маски підмережі для трьох класів мереж:





    • A клас - маска підмережі: 255.0.0.0


    • B клас - маска підмережі: 255.255.0.0


    • C клас - маска підмережі: 255.255.255.0




    Виконання операції І між маскою та IP-адресою дозволяє виділити мережну частину.



    Про маску підмережі потрібно пам'ятати три речі:





    • Маска підмережі призначена тільки для локальної інтерпретації локальних IP-адрес (де локальний означає - в тому ж мережному сегменті);


    • Маска підмережі – не IP адреса – вона використовується для локальної модифікації інтерпретації IP адреси.




    Безкласова міждоменна маршрутизація



    Спочатку використовувалася класова адресація (INET), але з другої половини 90-х років XX століття вона була витіснена безкласовою адресацією (CIDR), коли кількість адрес в мережі визначається маскою підмережі.



    Ніхто не знає точно, скільки мереж підключено до Інтернету, але очевидно, що їх багато — можливо, близько мільйона. Різні алгоритми маршрутизації вимагають, щоб кожен маршрутизатор обмінювався інформацією про доступні адреси з іншими маршрутизаторами. Чим більший розмір таблиці, тим більше даних необхідно передавати та обробляти. Зі зростанням розміру таблиці час обробки зростає щонайменше лінійно. Що більше даних доводиться передавати, то вище ймовірність втрати (у разі тимчасової) частини інформації дорогою, що може призвести до нестабільності роботи алгоритмів вибору маршрутів.



    На щастя, спосіб зменшити розмір таблиць маршрутизації все ж таки існує. Застосуємо той же принцип, що і при розбитті на підмережі: маршрутизатор може дізнаватися про розташування IP-адрес по префіксам різної довжини. Але замість того, щоб розділяти мережу на підмережі, ми об'єднаємо кілька коротких префіксів у один довгий. Цей процес називається агрегацією маршруту (route aggregation). Довгий префікс, отриманий в результаті, іноді називають супермережею (supernet), на противагу підмережам з поділом блоків адрес.



    При агрегації IP-адреси містяться у префіксах різної довжини. Одна і та сама IP-адреса може розглядатися одним маршрутизатором як частина блоку /22 (що містить 2 10 адрес), а іншим - як частина більшого блоку /20 (що містить 2 12 адрес). Це залежить від того, якою інформацією володіє маршрутизатор. Такий метод працює і для розбиття на підмережі і називається CIDR (Classless InterDomain Routing - безкласова міждоменна маршрутизація).

Related

Категорії