Артём Нургалиев, «‎Кэш на кэш: как ускоряли автобиддеры»‎

Transcript

1. Артём Нургалиев, руководитель подгруппы «Сервисы эффективности рекламы» Кэш на кэш: как ускоряли автобиддеры
2. 2 Привет! Я Артём Нургалиев Руководитель подгруппы разработки 11:25 3 года пишу на Go в Ozon Занимаюсь ранжированием рекламных товаров и автобиддерами Люблю, когда наши сервисы работают стабильно и быстро
3. 3 01 Выясним, зачем кэш в автобиддере План доклада
4. 4 01 Выясним, зачем кэш в автобиддере 02 Посмотрим на детали реализации популярных библиотек для кэширования План доклада
5. 5 01 Выясним, зачем кэш в автобиддере 02 Посмотрим на детали реализации популярных библиотек для кэширования 03 Разберём TinyLFU в Ristretto: как приблизительно считать частотности без блокировок План доклада
6. 6 01 Выясним, зачем кэш в автобиддере 02 Посмотрим на детали реализации популярных библиотек для кэширования 03 Разберём TinyLFU в Ristretto: как приблизительно считать частотности без блокировок План доклада 04 Выберем лучший вариант!
7. 7 Реклама В поиске, каталоге, рекомендациях и других плейсментах
8. 8 Реклама В поиске, каталоге, рекомендациях и других плейсментах На каждый запрос проводится рекламный аукцион
9. 9 Реклама В поиске, каталоге, рекомендациях и других плейсментах На каждый запрос проводится рекламный аукцион Аукцион учитывает рекламную ставку и релевантность товара
10. 10 Зачем автобиддеры? Продавцу сложно вручную выставлять эффективные рекламные ставки по всем товарам
11. 11 Зачем автобиддеры? Продавцу сложно вручную выставлять эффективные рекламные ставки по всем товарам Автобиддеры динамически управляют рекламными ставками по всем товарам в различных плейсментах
12. 12 Зачем автобиддеры? Продавцу сложно вручную выставлять эффективные рекламные ставки по всем товарам Автобиддеры динамически управляют рекламными ставками по всем товарам в различных плейсментах Автобиддер «Максимум кликов» позволяет получить максимальное количество кликов при условии ограничения на бюджет
13. 13 Архитектура автобиддера ETL-обновления Автобиддер Запрос: 1. Контекст запроса 2. Набор товаров [SKU1, SKU2, …] Шардированный Redis Get/Set
14. 14 Во все шарды ходить долго! ETL-обновления Автобиддер Запрос: 1. Контекст запроса 2. Набор товаров [SKU1, SKU2, …] Шардированный Redis Get/Set Батчовый запроc, нет ключа для шардирования по запросу
15. 15 Как ускорить? ETL-обновления Автобиддер Запрос: 1. Контекст запроса 2. Набор товаров [SKU1, SKU2, …] Шардированный Redis Get/Set Кэшируем значение из Redis’a Кэшируем отсутствие значений в Redis’e Используем TTL сильно меньше периода обновлений In-Memory Cache
16. 16 Победа! Расходимся
17. 17 Победа! Расходимся А какой кэш выбрать?
18. 18 Выясняем требования 01 Какая будет нагрузка? • Максимальная • В среднем • Квантили
19. 19 Выясняем требования 01 Какая будет нагрузка? • Максимальная • В среднем • Квантили 02 Что кэшируем? • Типы данных, количество уникальных объектов • Максимальный размер кэша • Влезут ли все данные в кэш?
20. 20 Выясняем требования 01 Какая будет нагрузка? • Максимальная • В среднем • Квантили 02 03 Что кэшируем? • Типы данных, количество уникальных объектов • Максимальный размер кэша • Влезут ли все данные в кэш? Паттерны доступа к данным: • Как часто изменяются данные? • Батчовая нагрузка? • Какие-то ключи читают/пишут чаще? • Какой ожидается Hit-Rate • Баланс между Read/Write
21. 21 Смотрим на детали реализации Выяснили требования. Как теперь выбрать библиотеку? Предоставляемый интерфейс 01 В зависимости от библиотеки может различаться:
22. 22 Смотрим на детали реализации Выяснили требования. Как теперь выбрать библиотеку? Масштабируемость с ростом числа ядер и горутин 02 В зависимости от библиотеки может различаться: Предоставляемый интерфейс 01
23. 23 Смотрим на детали реализации Выяснили требования. Как теперь выбрать библиотеку? Масштабируемость с ростом числа ядер и горутин 02 Удаление по TTL 03 В зависимости от библиотеки может различаться: Предоставляемый интерфейс 01
24. 24 Смотрим на детали реализации Выяснили требования. Как теперь выбрать библиотеку? Масштабируемость с ростом числа ядер и горутин 02 Удаление по TTL 03 Размещение данных в памяти (GC) 04 В зависимости от библиотеки может различаться: Предоставляемый интерфейс 01
25. 25 Смотрим на детали реализации Выяснили требования. Как теперь выбрать библиотеку? Масштабируемость с ростом числа ядер и горутин 02 Удаление по TTL 03 Размещение данных в памяти (GC) 04 Политика вытеснения ключей 05 В зависимости от библиотеки может различаться: Предоставляемый интерфейс 01
26. 26 Что будем сравнивать 01 Freecache Bigcache Fastcache Ristretto 02 Самописный кэш 03
27. 27 Предоставляемый интерфейс 01
28. 28 Выбираем интерфейс 01 Freecache GetWithBuf(key, buf []byte) (val []byte, err error) Set (key, value []byte)
29. 29 Выбираем интерфейс 01 Freecache GetWithBuf(key, buf []byte) (val []byte, err error) Set (key, value []byte) Требуется сериализация ключа и значения. Можно переиспользовать buf []byte
30. 30 Выбираем интерфейс 01 Freecache GetWithBuf(key, buf []byte) (val []byte, err error) Set (key, value []byte) Ristretto Get(key interface{}) (value interface{}, ok bool) Put(key interface{}, value interface{}) 02 Требуется сериализация ключа и значения. Можно переиспользовать buf []byte
31. 31 Выбираем интерфейс 01 Freecache Ristretto Get(key interface{}) (value interface{}, ok bool) Put(key interface{}, value interface{}) 02 Требуется сериализация ключа и значения. Можно переиспользовать buf []byte Требуется сериализация ключа Для хранения вычисляется keyHash, conflictHash := c.keyToHash(key) По умолчанию keyToHash только для []byte, string, uint64.., можно написать свой GetWithBuf(key, buf []byte) (val []byte, err error) Set (key, value []byte)
32. 32 Выбираем интерфейс 01 Freecache GetWithBuf(key, buf []byte) (val []byte, err error) Set (key, value []byte) Ristretto Get(key interface{}) (value interface{}, ok bool) Put(key interface{}, value interface{}) Самописный кэш Get(key Key) (value Value, ok bool) Put(key Key, value Value) 02 03 Требуется сериализация ключа и значения. Можно переиспользовать buf []byte Требуется сериализация ключа Для хранения вычисляется keyHash, conflictHash := c.keyToHash(key) По умолчанию keyToHash только для []byte, string, uint64.., можно написать свой
33. 33 Выбираем интерфейс 01 Freecache Ristretto Get(key interface{}) (value interface{}, ok bool) Put(key interface{}, value interface{}) 02 Требуется сериализация ключа и значения. Можно переиспользовать buf []byte Требуется сериализация ключа Для хранения вычисляется keyHash, conflictHash := c.keyToHash(key) По умолчанию keyToHash только для []byte, string, uint64.., можно написать свой Не требуется сериализация Самописный кэш Get(key Key) (value Value, ok bool) Put(key Key, value Value) 03 GetWithBuf(key, buf []byte) (val []byte, err error) Set (key, value []byte)
34. 34 02 Конкурентный доступ
35. 35 Пишем кэш с конкурентным доступом map 01
36. 36 Пишем кэш с конкурентным доступом map 01 sync.Map 02
37. 37 Пишем кэш с конкурентным доступом map 01 sync.Map 02 map + Mutex/RWMutex 03
38. 38 Пишем кэш с конкурентным доступом N шардов: map + Mutex/RWMutex 04 shard_id = hash(key) % N shard1 shard2 shard3 RWMutex 1 RWMutex 2 RWMutex 3
39. 39 03 Удаление по TTL
40. 40 Реализуем удаление по TTL expire — время, когда ключ устареет expire часто определяется по таймеру с секундными интервалами!
41. 41 Реализуем удаление по TTL expire — время, когда ключ устареет expire часто определяется по таймеру с секундными интервалами! Можно проверять expire при get-операции
42. 42 Реализуем удаление по TTL expire — время, когда ключ устареет expire часто определяется по таймеру с секундными интервалами! Можно проверять expire при get-операции Можно запустить сборщик устаревших объектов, сборщик проходится по ключам и удаляет их раз в интервал. Удаление происходит под блокировкой эффективнее брать блокировку на диапазон
43. 43 04 Размещение в памяти
44. 44 Сохраняем значения в память shard1 Шардировали. Типичное число шардов = 256 Смотрим, как хранит значения один шард 1. Самописный кэш может хранить типизированные данные: map[Key]storeItem 2. Ristretto хранит map[keyHash]storeItem keyHash, conflictHash := c.keyToHash(key) storeItem{ value Value expire Time } storeItem{ value interface{} expire Time conflictHash uint64 }
45. 45 Оптимизируем хранение для GC shard1 3. Bigcache хранит Map и RingBuffer map[uint64]uint32 Ключ -– hash(key), значение — offset в буфере var hash1 uint64 = hash(key1) Map hash(x) hash(y) 2 1 … store entry4 store entry2 store entry1 store entry5 RingBuffer … 0 1 2 6 7
46. 46 Оптимизируем хранение для GC shard1 3. Bigcache хранит Map и RingBuffer map[uint64]uint32 Ключ – hash(key), значение — offset в буфере var hash1 uint64 = hash(key1) Map hash(x) hash(y) hash(t) 2 1 7 … store entry4 store entry2 store entry1 store entry5 RingBuffer store entry9 … 0 1 2 6 7
47. 47 4. Freecache Каждый шард хранит 256 слотов и RingBuffer Каждый слот — отсортированный по hash16 массив, хранящий offset в RingBuffer. Внутри слота ищем бинарным поиском 256 slots h16(x) offset:2 … store entry4 store entry2 store entry3 store entry5 RingBuffer … … 0 1 2 6 7 h16(s) offset:1 h16(f) offset:6 h16(k) offset:4 h16(y) offset:0 …
48. 48 4. Freecache Каждый шард хранит 256 слотов и RingBuffer Каждый слот — отсортированный по hash16 массив, хранящий offset в RingBuffer. Внутри слота ищем бинарным поиском 256 slots h16(x) offset:2 … store entry4 store entry2 store entry3 store entry5 store entry1 RingBuffer … … 0 1 2 6 7 h16(y) offset:0 h16(s) offset:1 h16(f) offset:6 h16(k) offset:4 h16(g) offset:7 …
49. 49 05 Политика вытеснения ключей
50. 50 Ограничение на размер кэша Без ограничений 01
51. 51 Ограничение на размер кэша Без ограничений 01 Ограничение на количество элементов 02
52. 52 Ограничение на размер кэша Без ограничений 01 Ограничение на количество элементов 02 Ограничение на количество byte 03
53. 53 Ограничение на размер кэша Без ограничений 01 Ограничение на количество элементов 02 Ограничение на количество byte 03 Ограничение на MaxCost (для значения задаётся стоимость хранения) 04
54. 54 Выбираем политику вытеснения Без вытеснения 01 Random Subset 02 LRU 03 LFU 04 Window LFU 05 ARC 06 Segmented LRU 07 2Q 08 LRU-K … 09 10
55. 55 Выбираем политику вытеснения Без вытеснения 01 Random Subset 02 LRU 03 LFU 04 Window LFU 05 ARC 06 Segmented LRU 07 2Q 08 LRU-K … 09 10
56. 56 Выбираем политику вытеснения Без вытеснения 01 Random Subset 02 LRU 03 LFU 04 Window LFU 05 ARC 06 Segmented LRU 07 2Q 08 LRU-K … 09 10
57. 57 Выбираем политику вытеснения Без вытеснения 01 Random Subset 02 LRU 03 LFU 04 Window LFU 05 ARC 06 Segmented LRU 07 2Q 08 LRU-K … 09 10
58. 58 Выбираем политику вытеснения Без вытеснения 01 Random Subset 02 LRU 03 LFU 04 Window LFU 05 ARC 06 Segmented LRU 07 2Q 08 LRU-K … 09 10
59. 59 Выбираем политику вытеснения Без вытеснения 01 Random Subset 02 LRU 03 LFU 04 Window LFU 05 ARC 06 Segmented LRU 07 2Q 08 LRU-K … 09 10 Segmented LRU 07 2Q 08 LRU-K 09 … 10
60. 60 Выбираем политику вытеснения Random Subset Удаляем шард при определённой заполненности Ниже Hit-Rate Низкие затраты на конкурентный доступ Решение с Map + List требует Lock на каждую операцию Freecache использует LRU для каждого шарда LRU Выше Hit-Rate Нужно обновлять счётчики LFU Hit-Rate выше при Zipfian distribution
61. 61 TinyLFU в Ristretto
62. 62 TinyLFU в Ristretto shard1 Когда кэш заполнен 4>3 Х:4 Если счётчик меньше, чем у добавляемого ключа, происходит вытеснение Выбираем случайное подмножество ключей В подмножестве находим ключ с минимальным счётчиком А:3 В:4 С:8 D:4 Случайное подмножество — первые несколько ключей при итерации по map
63. 63 TinyLFU в Ristretto shard1 Когда кэш заполнен A:3 Если счётчик меньше, чем у добавляемого ключа, происходит вытеснение Выбираем случайное подмножество ключей В подмножестве находим ключ с минимальным счётчиком X:4 В:4 С:8 D:4 Случайное подмножество — первые несколько ключей при итерации по map
64. Идея: двухуровневая система 64 «Приблизительно» считаем частотности 1 уровень отсекает редкие ключи 2 уровень считает число обращений к популярным ключам Точные значения не нужны
65. 65 «Приблизительно» считаем частотности 1 уровень: фильтр Блума «Швейцар». Хранит только 0 или 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0
66. 66 «Приблизительно» считаем частотности 1 уровень: фильтр Блума «Швейцар». Хранит только 0 или 1 0 Вычисляем N хэш-функций 0 0 0 0 0 0 0 0 0 0 0 0 0 X h1(x) h2(x) h3(x)
67. 67 «Приблизительно» считаем частотности 1 уровень: фильтр Блума «Швейцар». Хранит только 0 или 1 1 Если бит не равен 1, заменяем его на 1 0 0 1 0 0 0 0 0 0 1 0 0 0 X h1(x) h2(x) h3(x)
68. 68 «Приблизительно» считаем частотности 1 уровень: фильтр Блума «Швейцар». Хранит только 0 или 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 Y h1(y) h2(y) h3(y)
69. 69 «Приблизительно» считаем частотности 1 уровень: фильтр Блума «Швейцар». Хранит только 0 или 1 0 1 0 0 0 0 0 0 0 0 1 0 0 1 Y h1(y) h2(y) h3(y)
70. 70 «Приблизительно» считаем частотности 1 уровень: фильтр Блума «Швейцар». Хранит только 0 или 1 1 0 1 0 0 1 0 1 0 1 1 1 1 0 X h1(x) h2(x) h3(x) Если хоть один бит != 1, то значение ещё не встречалось
71. 71 «Приблизительно» считаем частотности 1 уровень: фильтр Блума «Швейцар». Хранит только 0 или 1 1 0 1 1 0 1 0 1 0 1 1 1 1 0 X h1(x) h2(x) h3(x) Если элемент уже добавлен на 1-й уровень, считаем его частотность на втором уровне
72. 72 «Приблизительно» считаем частотности 1 уровень: фильтр Блума «Швейцар». Хранит только 0 или 1 1 0 1 1 0 1 0 1 0 1 1 1 1 0 X h1(x) h2(x) h3(x) 2 уровень: Считающий фильтр Блума. 4 бита на каждый счётчик. Увеличиваем самый маленький счётчик Если элемент уже добавлен на 1-й уровень, считаем его частотность на втором уровне 5 0 3 2 2 12 Глобальный счётчик X h1(x) h2(x) h3(x)
73. 73 «Приблизительно» считаем частотности 1 уровень: фильтр Блума «Швейцар». Хранит только 0 или 1 1 0 1 1 0 1 0 1 0 1 1 1 1 0 X h1(x) h2(x) h3(x) 2 уровень: Считающий фильтр Блума. 4 бита на каждый счётчик. Увеличиваем самый маленький счётчик Если элемент уже добавлен на 1-й уровень, считаем его частотность на втором уровне 5 0 3 3 3 13 Глобальный счётчик X h1(x) h2(x) h3(x)
74. 74 «Приблизительно» считаем частотности Когда глобальный счётчик превышает некоторое значение 14 Чтобы подстроиться под изменение распределения, нужно забыть старые инкременты 1 0 1 1 0 1 0 1 0 1 1 1 1 0 5 0 3 3 3
75. 75 «Приблизительно» считаем частотности Когда глобальный счётчик превышает некоторое значение 14 Уменьшаем все значения в считающем фильтре в 2 раза Чтобы подстроиться под изменение распределения, нужно забыть старые инкременты 1 0 1 1 0 1 0 1 0 1 1 1 1 0 2 0 1 1 1
76. 76 «Приблизительно» считаем частотности Когда глобальный счётчик превышает некоторое значение 14 Уменьшаем все значения в считающем фильтре в 2 раза Чтобы подстроиться под изменение распределения, нужно забыть старые инкременты 2 0 1 1 1 Обнуляем фильтр «Швейцар» 0 0 0 0 0 0 0 0 0 0 0 0 0 0
77. 77 Считаем частотности без блокировок Get-операция: нужно увеличить счётчик по ключу без блокировки
78. 78 Считаем частотности без блокировок Get-операция: нужно увеличить счётчик по ключу без блокировки Можно послать ключ в канал…
79. 79 Считаем частотности без блокировок Get-операция: нужно увеличить счётчик по ключу без блокировки Можно послать ключ в канал… но каналы — медленно
80. 80 Считаем частотности без блокировок Get-операция: нужно увеличить счётчик по ключу без блокировки Решение!
81. 81 Считаем частотности без блокировок Get-операция: нужно увеличить счётчик по ключу без блокировки Решение! Lossy Ring Buffers на основе sync.Pool sync.Pool хранит батчи ключей, которые ожидают инкремента
82. 82 Считаем частотности без блокировок Get-операция: нужно увеличить счётчик по ключу без блокировки Решение! Lossy Ring Buffers на основе sync.Pool sync.Pool хранит батчи ключей, которые ожидают инкремента sync.Pool К1 К4 К3 К1 К2 К2 К2 К4 К5 К7 К6 К9 К1
83. 83 Считаем частотности без блокировок Get-операция: нужно увеличить счётчик по ключу без блокировки Решение! Lossy Ring Buffers на основе sync.Pool sync.Pool хранит батчи ключей, которые ожидают инкремента sync.Pool К1 К4 К3 К1 К2 К2 К2 К4 К5 К7 К6 К9 К1 Берём из sync.Pool случайный батч
84. 84 Считаем частотности без блокировок Get-операция: нужно увеличить счётчик по ключу без блокировки Решение! Lossy Ring Buffers на основе sync.Pool sync.Pool хранит батчи ключей, которые ожидают инкремента sync.Pool К1 К4 К3 К1 К2 К2 К2 К4 К5 К7 К6 К9 К1 Добавляем в него ключ К5
85. 85 Считаем частотности без блокировок Get-операция: нужно увеличить счётчик по ключу без блокировки Решение! Lossy Ring Buffers на основе sync.Pool sync.Pool хранит батчи ключей, которые ожидают инкремента sync.Pool К1 К4 К3 К1 К2 К2 К2 К4 К5 К7 К6 К9 К1 Если батч заполнен — отправляем в канал К5 Buffered CH
86. 86 Считаем частотности без блокировок Get-операция: нужно увеличить счётчик по ключу без блокировки Решение! Lossy Ring Buffers на основе sync.Pool sync.Pool хранит батчи ключей, которые ожидают инкремента sync.Pool К1 К4 К3 К1 К2 К2 К2 К4 К5 К7 К6 К9 К1 И в background обновляем счётчики по ключам К5 Buffered CH Background: Update Keys from batch
87. 87 Считаем частотности без блокировок Get-операция: нужно увеличить счётчик по ключу без блокировки Решение! Lossy Ring Buffers на основе sync.Pool sync.Pool хранит батчи ключей, которые ожидают инкремента sync.Pool К1 К4 К3 К1 К2 К2 К2 К4 К5 К7 К6 К9 К1 Lossy: так как батчи могут удаляться из sync.Pool и при переполнении буфера канала К5
88. 88 Посмотрели на детали реализации! Теперь сравним
89. 89 Сравнение TinyLFU: Хорошо подходит под Zipf’s Law Ristretto Хороший baseline
90. 90 Сравнение TinyLFU: Хорошо подходит под Zipf’s Law Ristretto Хороший baseline Не оптимизирован под работу GC
91. 91 Сравнение Freecache/ BigCache/ FastCache TinyLFU: Хорошо подходит под Zipf’s Law Ristretto Хороший baseline Не оптимизирован под работу GC Оптимизированы под работу GC
92. 92 Сравнение Freecache/ BigCache/ FastCache TinyLFU: Хорошо подходит под Zipf’s Law Ristretto Хороший baseline Не оптимизирован под работу GC Оптимизированы под работу GC Требуется сериализация значений
93. 93 Сравнение Freecache/ BigCache/ FastCache TinyLFU: Хорошо подходит под Zipf’s Law Ristretto Самописный кэш Хороший baseline Не оптимизирован под работу GC Оптимизированы под работу GC Требуется сериализация значений Идеален под вашу задачу
94. 94 Сравнение Freecache/ BigCache/ FastCache TinyLFU: Хорошо подходит под Zipf’s Law Ristretto Самописный кэш Хороший baseline Не оптимизирован под работу GC Оптимизированы под работу GC Требуется сериализация значений Идеален под вашу задачу Но ещё не написан
95. 95 Наш опыт Хороший baseline, под большинство задач используем его Ristretto
96. 96 Наш опыт Freecache Хороший baseline, под большинство задач используем его Ristretto Помог нам справиться с проблемами с GC
97. 97 Наш опыт Freecache Хороший baseline, под большинство задач используем его Ristretto Самописный кэш Помог нам справиться с проблемами с GC Работает лучше всего в простом сценарии: когда все значения помещаются в память
98. 98 Наш опыт Freecache Хороший baseline, под большинство задач используем его Ristretto Самописный кэш Помог нам справиться с проблемами с GC Работает лучше всего в простом сценарии: когда все значения помещаются в память Смотрим на метрики, пишем бенчмарки
99. 99 Выводы Выяснили требования к In-memory-кэшам 01
100. 100 Выводы Выяснили требования к In-memory-кэшам 01 Рассмотрели эффективный способ хранения значений в памяти 02
101. 101 Выводы Выяснили требования к In-memory-кэшам 01 Рассмотрели эффективный способ хранения значений в памяти 02 Узнали, как приблизительно подсчитать частотности ключей без блокировок 03
102. 102 Выводы Выяснили требования к In-memory-кэшам 01 Рассмотрели эффективный способ хранения значений в памяти 02 Узнали, как приблизительно подсчитать частотности ключей без блокировок 03 НЕ выбрали лучший кэш, так как он всегда разный 04
103. Если нужно, размести тут QR-код или удали эту фигуру Спасибо за внимание! Артём Нургалиев, руководитель подгруппы «Сервисы эффективности рекламы» E-mail: anurgaliev@ozon.ru Tg: @FicrusS