[Перевод] Оптимизируем использование памяти для поиска IP-адресов11.11.2024 13:30

477ceff09b32701a02cb3fc9b177c5ac.png

Около трёх лет у меня возникали проблемы с моим обучающим сайтом 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

Изначально это работало так: у меня был массив вида

type IPRange struct {
	StartIP net.IP
	EndIP   net.IP
	Num     int
	Name    string
	Country string
}

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

Попытка 1: используем SQLite

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

Поэтому я:

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

  • изменила свой код, чтобы выполнялся выбор из базы данных

Это позволило достичь моей изначальной цели по уровню использования памяти (после сборки мусора память теперь вообще практически не использовалась, потому что вся таблица была на диске!), хоть я и не знаю точно, насколько активное применение сборщика мусора вызвало бы это решение в случае множества одновременных запросов. Я выполнила краткое профилирование памяти, на одну операцию поиска распределялся примерно 1 КБ памяти.

Но давайте поговорим о проблемах, с которыми я столкнулась при работе с SQLite.

Проблема: как хранить адреса IPv6

SQLite не имеет поддержки big integer, а адреса IPv6 имеют размер 128 битов, поэтому я решила хранить их как текст. Наверно, BLOB мог бы подойти лучше, но изначально я думала, что BLOB нельзя сравнивать, однако в документации SQLite написано, что можно.

В конечном итоге я выбрала такую схему: 

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 использовать оба индекса, я попробовала следующее:

  • использовать составной индекс вместо двух отдельных

  • выполнять ANALYZE

  • использовать INTERSECT для поиска пересечения результатов start_ip < ? и ? < end_ip. Два индекса всё равно не использовались, но запрос стал медленнее буквально в тысячу раз, потому что ему нужно было создать результаты обоих подзапросов в памяти и найти их пересечение.

Попытка 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 так: 

type IPRange struct {
	StartIP net.IP
	EndIP   net.IP
	Num     int
	Name    string
	Country string
}

У меня было три идеи по поводу того, как это улучшить:

  1. В Name и Country есть множество повторений, потому что многие диапазоны IP-адресов принадлежат одному ASN

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

  3. Возможно, мне даже не нужны были одновременно и начальный IP, и конечный IP: часто диапазоны расположены последовательно, поэтому, вероятно, я смогу перенастроить всё так, чтобы требовался только начальный IP

Идея 3.1: избавление от дублирования Name и Country

Я решила, что могу сохранить информацию ASN в массив, а затем просто сохранять индекс массива в мою struct 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 {
	asns   []ASNInfo
	lookup map[ASNInfo]uint32
}

И это сработало! Потребление памяти снизилось с 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, и ещё сильнее полюбила двоичный поиск.

© Habrahabr.ru