Представлено простий, але кардинальний алгоритм веб-кешування

Новий алгоритм із відкритим вихідним кодом має потенціал для революції в управлінні великомасштабним веб-трафіком. Комп’ютерні вчені розробили дуже ефективний, але неймовірно простий алгоритм, щоб вирішити, які елементи викинути з веб-кешу, щоб звільнити місце для нових. Новий алгоритм із відкритим вихідним кодом, відомий як SIEVE, має потенціал для масштабної трансформації керування веб-трафіком.

SIEVE є спільним проектом комп’ютерників з Університету Еморі, Університету Карнегі-Меллона та Фонду Пелікан. Стаття команди про SIEVE буде представлена ​​на 21-му симпозіумі USENIX з проєктування та впровадження мережевих систем (NSDI) у Санта-Кларі, Каліфорнія, у квітні.

Препринт паперу вже набирає хвилі.

«SIEVE більший і більший, ніж ми самі», — каже Ячжуо Чжан, аспірант Еморі та один із авторів статті. «Він уже добре працює, але ми отримуємо багато хороших пропозицій, щоб зробити його ще кращим. У цьому краса світу з відкритим кодом».

Чжан ділиться першим автором статті з Цзюньченом (Джейсоном) Яном, який здобув ступінь магістра комп’ютерних наук в Еморі, а зараз є доктором філософії в Карнегі-Меллон.

«SIEVE — це просте вдосконалення перевіреного алгоритму видалення кешу, який використовується десятиліттями — це буквально як століття у світі обчислювальної техніки», — каже Імір Вігфуссон, доцент кафедри комп’ютерних наук Еморі.

Вігфуссон є співавтором статті разом із Рашмі Вінаяк, доцентом кафедри інформатики Карнегі-Меллона. Яо Юе, комп’ютерний інженер з Pelikan Foundation, також є співавтором.

Окрім швидкості та ефективності, ключовим фактором, що викликає інтерес до SIEVE, є його простота, що забезпечує масштабованість.

«Простота — це найвища витонченість», — каже Вігфуссон. «Чим простіші елементи в системі, призначеній для обслуговування мільярдів людей за частки секунди, тим легше ефективно впроваджувати та підтримувати цю систему».

Тримайте «гарячі предмети» під рукою

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

Кеш схожий на добре організовану шафу для комп’ютерних даних. Кеш заповнений копіями найпопулярніших об’єктів, запитуваних користувачами, або «гарячих об’єктів» в IT-термінології. Кеш зберігає цю невелику колекцію гарячих об’єктів окремо від основної бази даних комп’ютерної мережі, яка схожа на величезний склад, наповнений усією інформацією, яку може обслуговувати система.

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

«Кешування є всюди, — каже Чжан. «Це важливо для кожної компанії, великої чи малої, яка використовує веб-додатки. Кожен веб-сайт потребує кеш-системи».

І все ж, кешування є відносно недостатньо вивченим у галузі інформатики.

Як працює кешування

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

Швидка пам’ять кеша дорога в експлуатації, але критична для хорошої роботи веб-користувачів. Мета полягає в тому, щоб зберегти найбільш корисну майбутню інформацію в кеші. Інші об’єкти необхідно постійно відвіювати, або «виселяти» за технічною термінологією, щоб звільнити місце для мінливого масиву гарячих об’єктів. Алгоритми видалення кешу визначають, які об’єкти викидати та коли це робити.

FIFO, або «перший увійшов, перший вийшов», — це класичний алгоритм виселення, розроблений у 1960-х роках. Уявіть собі предмети, вишикувані на конвеєрі. Нові запитувані об’єкти входять зліва, а найстаріші об’єкти вилучаються, коли досягають кінця рядка справа.

У алгоритмі LRU, або алгоритмі «найменш нещодавно використовуваного», об’єкти також переміщуються вздовж лінії в напрямку вигнання в кінці. Однак, якщо об’єкт запитується знову, коли він рухається конвеєрною стрічкою, він повертається на початок лінії.

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

«Якщо алгоритм дуже складний, він, як правило, має більше помилок, і всі ці помилки потрібно виправляти», — пояснює Чжан.

Проста ідея

Подібно до LRU та деяких інших алгоритмів, SIEVE робить просте налаштування базової схеми FIFO. SIEVE спочатку позначає запитуваний об’єкт як «нуль». Якщо об’єкт запитується знову, коли він рухається вниз по поясу, його статус змінюється на «один». Коли об’єкт з позначкою «один» досягає кінця рядка, він автоматично скидається на «нуль» і вилучається.

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

«Важливо виселяти непопулярні об’єкти якомога швидше, і SIEVE дуже швидко справляється з цим завданням», — говорить Чжан.

На додаток до цього швидкого пониження об’єктів, SIEVE вдається підтримувати популярні об’єкти в кеші з мінімальними обчислювальними зусиллями, відомим як «ліниве просування» в комп’ютерній термінології. Дослідники вважають, що SIEVE є найпростішим алгоритмом видалення кеш-пам’яті для ефективного досягнення як швидкого пониження, так і лінивого просування.

Нижчий коефіцієнт промахів

Метою кешування є досягнення низького коефіцієнта промахів — частки запитуваних об’єктів, які потрібно отримати зі «складу».

Щоб оцінити SIEVE, дослідники провели експерименти на веб-кеші з відкритим кодом із Meta, Wikimedia, X та чотирьох інших великих наборів даних. Результати показали, що SIEVE досягає нижчого коефіцієнта промахів, ніж дев’ять найсучасніших алгоритмів на більш ніж 45% трас. Наступний найкращий алгоритм має нижчий коефіцієнт промахів лише 15%.

Легкість і простота SIEVE викликає питання, чому ніхто раніше не придумав цей метод. Зосередження команди SIEVE на тому, як змінилися моделі веб-трафіку за останні роки, могло змінити ситуацію, теоретизує Чжан.

«Наприклад, — каже вона, — нові предмети тепер швидко стають «гарячими», але також швидко зникають. Люди постійно втрачають інтерес до речей, тому що постійно з’являються нові речі».

Робочі навантаження веб-кешу зазвичай відповідають так званим узагальненим розподілам Zipfian, де невелика підмножина об’єктів відповідає за велику частку запитів. Можливо, SIEVE став найкращим місцем для Zipfian для поточних робочих навантажень.

«Це, безперечно, змінний момент для нашого розуміння видалення веб-кешу», — каже Вігфуссон. «Це змінює конструкцію, яку так довго використовували наосліп».

Навіть незначне вдосконалення системи веб-кешування, додає він, може заощадити мільйони доларів у великому центрі обробки даних. Чжан і Ян на шляху до отримання докторських ступенів у травні.

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

Зустріч: симпозіум USENIX з проектування та впровадження мережевих систем