- Слухай, а мені сподобався трюк із масивом, де ми його зменьшили з двох мільярдів до одного. А за потреби на скільки завгодно.
- Так, у двічі то було тільки для прикладу, так-то ми можемо обмежитись і доволі невеликим масивом, а збільшувати лише за потреби. Там коли заповнився якийсь відсоток значень.
- Так, так, але я не про те. Ми ж за допомогою хешу і всього цього змогли навчитись дуже швидко відповідати, що елементу немає в колекції. При чому з абсолютною точністю. А от вже відповідь про наявність вже не настільки точна. Вірно?
- Саме так, тому для того, щоб не було помилково-істиних відповідей ми ще порівнюємо елементи.
- До діла. Мені поклали веб сервак, тупою DOS атакою. В мене є доступ до ресурсів по GUID. Раніше я бігав в базу за кожним і якщо його немає, то повертав 404.
- Дай вгадаю: зловмисники просто почали випадково генерувати GUID і це поклало базу, хоча жодний запит і не був по ресурс, що був в наявності? Тобто завжди були лише 404.
- Так. І я, поспілкувавшись оці два рази з тобою про хеші, подумав: а давай я їх складу всі у HashSet і буду швиденько віддавати 404, якщо GUID немає в HashSet, а якщо є, то вже тоді бігти в базу по ресурс.
- Звучить непогано, але?..
- В мене доволі кволий сервер, бо це мей pet проект і мені не вистачило оперативи на цей HashSet.
- І є якась шалена ідея. От прямо по очах бачу. Так?
- Ага. Виділяємо масив фіксованого розміру. Все по замовчуванню FALSE. При додаванні елементу рахуємо хеш і складаємо TRUE по індексу:
hash % array.Length
- Тоді, коли приходе запит, то обраховуємо хеш від GUID, беремо залишок від ділення і перевіряємо чи стоїть TRUE у цій позиції.
- Але можуть бути колізії, тож TRUE нам ще не гарантує наявність, але FALSE гарантує відсутність.
- Якщо TRUE, то можна вже сходити в базу і перевірити чи справді є такий елемент. Але купу запитів ми вже відсіємо. Це значно здорожчить атаку, якщо хтось ще спробує покласти твій сервіс, бо ти відсіїш більшість запитів ще до походу у базу.
- І найкрутіше: я можу строго зафіксувати розмір масиву. Не буде ані алокацій, ані непередбачуваності в плані розміру.
- Тебе часом не Блум звати?
Гугліть: Фільтр Блума для більшої кількості деталей.
#WrittenInTheJungle #HashSeries
P.S. Як модифікувати атаку таким чином, щоб вона все одно поклала сервіс?
Пишіть у коментах. Може футболку, комусь подарую за кльову відповідь. В мене одна ідея є.