Джерело: Architecture Notes
Redis став основою сучасної розробки програмного забезпечення, завдяки своїй продуктивності, універсальності та простоті використання. У цій статті ми розглянемо основи Redis, дослідимо його внутрішню роботу та зрозуміємо розширене використання, зокрема використання Bloom фільтрів для ефективної обробки великих обсягів даних.
Що таке база даних?
Перед тим, як поринути в Redis, давайте коротко пригадаємо, що таке база даних. База даних — це організована колекція даних, зазвичай збережених та доступних електронним шляхом. Бази даних можуть зберігати дані на диску (традиційні бази даних, як MySQL) або в пам'яті (такі бази даних, як Redis).
Що таке Redis?
Redis (Remote Dictionary Server) — це відкритий сервер зберігання даних у пам'яті, який використовується як база даних, кеш, брокер повідомлень та поточний потік. На відміну від традиційних баз даних, Redis зберігає всі свої дані в оперативній пам'яті, що робить його неймовірно швидким. Redis підтримує різні структури даних, такі як рядки, списки, множини, хеші, відсортовані множини та багато інших.
Redis є кращим вибором, коли додатки потребують надзвичайно низької затримки та високої пропускної здатності.
Чому Redis такий швидкий?
-
База даних в пам'яті: Всі операції виконуються в пам'яті, що усуває затримку, викликану операціями з диском.
-
Оптимізовані структури даних: Redis пропонує ефективні структури даних, що підходять для високошвидкісних операцій.
-
Однопотокова архітектура: Хоча це здається контрінтуїтивним, однопотокова природа Redis усуває накладні витрати на управління потоками та синхронізацію.
Таємниця однопотокової архітектури
Redis використовує однопотоковий цикл обробки подій для виконання команд. Це може здаватися обмеженням, але ось чому це працює:
-
Мультиплексування вводу/виводу: Redis використовує мультиплексування вводу/виводу для моніторингу тисяч з'єднань одночасно без блокувань. Він використовує системні виклики, такі як select() або epoll(), для ефективної обробки декількох запитів.
-
Зменшена затримка: Уникаючи проблем із контенцією потоків і синхронізацією, Redis гарантує, що команди обробляються послідовно та атомарно.
Як Redis обробляє тисячі з'єднань
Redis використовує програмування на основі подій (Event-driven programming):
• Коли клієнт надсилає запит, Redis додає його до циклу обробки подій.
• Використовуючи мультиплексування вводу/виводу, Redis визначає, які з'єднання готові до читання або запису.
- Він обробляє запит, виконує його та надсилає відповідь — все це в межах однопотокового циклу.
Розширене використання: Пошук одного мільярда імен користувачів
Уявіть ситуацію, коли потрібно перевірити, чи існує ім’я користувача в базі даних з одного мільярда імен. Традиційні методи, такі як запити до реляційної бази даних, занадто повільні. Навіть використання Redis як кеша може споживати значну кількість пам'яті.
Bloom фільтри на допомогу
Bloom фільтр — це ймовірнісна структура даних, яка дозволяє визначити, чи може елемент існувати або точно не існує. Вона використовує:
• Бітовий масив для зберігання даних.
• Хеш-функції для відображення даних на біти в масиві.
Як це працює
- Коли ви додаєте ім’я користувача, Bloom фільтр використовує кілька хеш-функцій для встановлення бітів у масиві.
2.
Щоб перевірити, чи існує ім’я користувача:
• Застосуйте ті ж самі хеш-функції.
• Якщо всі відповідні біти встановлені в 1, то ім’я користувача може існувати.
• Якщо хоча б один біт 0, то ім’я користувача точно не існує.
Переваги
• Ефективність використання пам'яті: Bloom фільтр для одного мільярда імен користувачів з рівнем помилок 0,1% вимагає лише ~1.67GB пам'яті.
• Швидкість: Пошук і вставка швидкі (O(1)).
Обмеження
• Помилкові спрацьовування: Фільтр може неправильно повідомити, що елемент існує.
- Немає можливості видалення (якщо не використовувати Counting Bloom Filter).
Покращення Bloom фільтрів
Щоб уникнути помилкових спрацьовувань, ви можете поєднати Bloom фільтр з базою даних:
• Перевірка Bloom фільтра: Якщо фільтр повідомляє, що ім’я користувача не існує, пропустіть запит до бази даних.
• Перевірка в базі даних: Якщо фільтр повідомляє, що ім’я користувача існує, підтвердіть це в базі даних.
Цей гібридний підхід дозволяє збалансувати використання пам'яті, швидкість та точність.
Дякую!
Перекладено з: Redis Simplified: From Basics to Advanced Concepts like Bloom Filters