Dev Jungles

Ідемпотентність

Складне словце, що мене спитали років п'ять тому на співбесіді.

На практиці це всього лише:
Це така властивість операції, що приводе систему в однаковий стан вне залежності від того була операція виконана один чи кілька разів.

Як і більшість визначень воно абсолютно точне і майже повністю непригодне до використання.

Давайте думати що нам може давати мислення про операції в системі як ідемпотентні і не ідемпотентні?

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

Так подумали і виробники купи мережевого заліза і софту.
В HTTP є методи: GET, POST, PUT, PATCH, DELETE

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

GET запити
можуть бути повторени браузером чи, навіть якоюсь з залізяк між вашим
комп'ютером і сервером: вишки зв'язку, супутники старлінк,
маршрутезатори провайдеру, чи маршрутезатори в датацентрі.

PUT і DELETE теж рахуються ідемпотентними, хоча це дуже легко зломати в реалізації.

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

Ключова відмінність PUT і PATCH як раз в ідемпотентності.
Тож PUT це щось типу x = 10. Таку зміну скільки не повторюй система все одно приходе до одного і того самого стану.
А PATCH це вже щось типу x++, котрий повторювати може бути небезпечно.

Дуже часто буває корисним зробити метод POST також ідемпотентним, вже не через мережеве залізо і софт. Нажаль це не завжди просто.

Якщо у вас є обмеження в системі на однакові об'єкти, то ви можете використовувати хеш від об'єкту (я
про хеші багато писав у попередніх постах) для перевірки присутності
об'єкту в таблиці чи колекції: якщо він там вже є, то повертати успіх
вне залежності від того коли і чого він там був створений. Такий підхід зробе POST ідемпотентним.

Але що робити, якщо в системі можуть бути однакові об'єкти?
Це ускладнює задачу, але не робить її неможливою.
В цілому все зводиться до того, щоб зробити з однакових об'єктів унікальні, а потім заборонити повтор унікальних об'єктів.

Як саме?
Додавши до об'єкта якусь унікальну випадкову послідовність, або дата до микросекунд.
Якщо не буде впевненості, що запит був оброблений успішно, то його можна буде повторити.

Якщо запит таки не був оброблений, то сервер його обробить.
Якщо вже був, то на сервері спрацює перевірка що такий об'єкт вже є і він просто нічого не стане робити.

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

Але ідемпотентність не тільки про мережу і не надійне середовище. Іноді це просто спрощує код. В .NET правильною реалізацією Dispose вважається
ідемпотентна. Це дозволяє уникнути додаткових перевірок на володіння в
ієрархіях об'єктів і менше думати про порядок знищення об'єктів.

#WrittenInTheJungle #Misc

NULL as Billion Dollar Mistake: чи можливо було уникнути?

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

Така одна з версій подій.
Не суть чи було так, чи ні, краще подумати про те:
- А чи могло бути інакше?
- Як це могло б бути?
- Чи було б це краще?

Коротко про NULL.
NULL це таке спеціальне значення, що є аналогом нічого.
Навіщо нам спеціальне значення для "нічого"? Бо є принципова різниця у відповідях на питання: "Скільки грошей в гаманці?". Відповідь "не знаю" дуже відрізняється від відповіді "нуль". А ми можемо хотіти створювати алгоритми з урахуванням цього: в одному випадку, наприклад, перерахувати, а в іншому вигнати з магазину. Ну, наприклад.

Для більш складних об'єктів різниця може бути ще більш значущою. Ми намагаємось з'ясувати кількість грошей в гаманці у людини, а в людини навіть немає гаманця, або навіть немає самої людини.

Якщо додати до цьго колекції, то все стає ще складнішим: відсутність колекції, тобто NULL, пуста колекція, колекція з NULL замість людини, людина з NULL замість гаманця і людина гроші в гаманці котрої ми ще не рахували - тобто теж NULL.

Звучить як халепа. Чи не так?
І от що було б, якби такого особливого значення не було? Як це могло б бути?

Деякі мови зараз, намагаються проектувати саме таким чином. АЛе в кожній з них все одно з'являється щось схоже на той саме NULL. Бо нам він потрібен на рівні СУТІ РЕЧЕЙ!

Маючи таке особливе значення, ще можливо надресерувати компілятор таким чином, щоб ті значення, що допускають NULL було неможливо використати без попередньої перевірки.

Непоганий варіант.

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

А що якщо геть позбутись цих NULL values і всюди робити якісь об'єкти за замовчанням?
Цей підхід теж буде до певної міри працювати, аж до того часу як ви замість NullReferenceException отримаєте некоретну поведінку програми. Можливо ще й не сразу, а далеко в проді для багатьох користувачів.

Неправильну поведінку завжди важче помітити аніж crash програми. Це легше пропустити на усіх етапах тестування. Така помилка може виявитись значно дорожчою.

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

Тож, я не впевнений, що без NULL життя було б кращим.

#WrittenInTheJungle #Misc

На першому приближені, перед тим як починати будувати програму зручно проаналізувати те що має вийти з точки зору inputs and outputs.
Тоді сам застосунок буде чорним ящиком посередені.

Такий аналіз гарно помагає і на етапі перших думок про архітектуру і про дизайн і плануванні бази.

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

Іноді, може бути зручно розбити все на кілька категорій:
- Як представити данні, щоб користувачу їх було зручно вводити? (Edit ViewModel)
Тобто нам як програмістам зручно відобразити інтерфейс для їх вводу і заповнити його базовими значеннями.
- Як представити данні, щоб їх було зручно відображати? (Presentation ViewModel)
Іноді це може бути те саме що і ввод, а іноді геть інше. До того ж іноді нам треба відображати множини об'єктів, якось між ними навігуватись, будувати агрегати чи проекції.
- Як представити данні, щоб на їх осонові було зручно виконувати обчислення? (Model)
Бувають і суто інформаційні застосунки, де цього майже і не треба, а буває і навпаки.
- Як представити данні, щоб їх було зручно зберігати у базі (чи деінде)? (Entity)

Тоді немало коду, іноді навіть не найпростішого, доведеться написати для перетворення одних сутностей в інші.
Але я кілька разів значно знижував складність кожної з частин(ввод, відображення, обчислення, збереження) застосунку просто завдяки вдалому проектуванню цих об'єктів, а не спробам проводити обчислення на тих самих сутностях, що і бачить користувач, або тих самих, що прийшли з базі.

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

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

#WrittenInTheJungle #Architecture

- Слухай, а можеш мені розказати як працює цифровий підпис. Там теж щось з хешами пов'язано?
- Так, але там додається ще й асиметрична криптографія.
- А це що ще за звір?
- Симетрична криптографія, це коли одним і тим самим ключем і шифруємо і розшифровуємо, а асиметрична, це коли ключі для шифровки і розшифровки різні.
- Щось я вже тут перестав розуміти.
- Із паршивого, що в мене навіть немає простого прикладу як це пояснити. Там вже іде хитріша математика. Тож давай зосередемося на властивостях: в асиметрічній криптографії одним ключем шифруємо, іншим розшифровуємо.
- Здається запом'ятав.
- Добре. А тепер уяви, що всі знають ключ яким можна щось розшифрувати, а лише ти знаєш ключ, котрим шифрувати.
- Звучить дико, якщо чесно, ало що нам це дає?
- А те, що якщо нам приходить шифрований документ і він розшифровується саме твоїм ключем, то значить його зашифрував ти.
- Точно. І правда. Але ж от мені надсилають підписані документи і я їх можу бачити, вони геть не зашифровані.
- Все вірно. Бо сам документ може бути і відкритий, просто до нього дописали об'єкт додатковий - цифровий підпис.
- А якщо цей підпис скопіюють до іншого документу... Це ж ненадійно.
- Вгадай що може це забороти?
- Хеші?
- Саме вони.
- Але як?
- Давай розглянемо цифровий підпис як об'єкт: там є хеш від документу котрий ми підписуємо, щоб не можливо було підсунути інший документ до того ж самого підпису. Цей хеш зашифрован приватним ключем - тим самим, що відомий лише одній людині.
- Чорт, а це прямо красиво.

#WrittenInTheJungles #HashSeries

- Да, майже. Зараз буде цікаве. Коли додаємо ще один елемент ми обов'язково вказуємо хеш попередника, потім власне елемент і потім хеш від усього цього.
- Так. І що нам це дає?
- А те, що якщо хоч один елемент змінюється десь внизу, то летить все до біса. І ми можемо це перевірити.
- Все ще не розумію.
- Ну от зібрали ми колекцію з таких елементів: якісь корисні данні, хеш попередника і хеш від корисних даних і хеша попередника. Зібрали масив з сотні таких записів.
- Так
- І тепер уявляємо, що якийсь зловмисник змінює щось в корисних даних двадцятого елементу. Ми можемо перевірити весь ланцюжок і знайти це!
- А, це тому що хеш не зійдеться?
- Саме так. Ми перевіримо хеші елементів з першого по 19 і все буде чудово. А потім обчислемо хеш від корисних даних і хеша попередника 20го і він не зійдеться з тим, що написано в його хеші.
- А якщо зловмисник змінив і його?
- Добре, тоді звалимось на наступній перевірці: у 21го елемента у якості батьківського хеша буде старий хеш.
- Стоп. Якщо ми вважаємо, що зловмисник може переписувати данні якимось чином, то він же може переписати і його?
- Так. При чому йому доведеться змінити кожен елемент після.
- Простий цикл має впоратись. Хіба ні?
- Десь так, але от... Уяви, що ти робиш Code Review і бачиш одну маленьку зміну: таке можна пропустити, можна непомітити, а от якщо змін багато, то може і не кожна з них захопу увагу, але сумарна увага точно буде більше.
- І все ж таки де тут безпека?
- Звісно, якщо ми одні і в нас є повний контроль над даними і ми самі собі зловмисник, то це фундаментально неможливо захистити. Але згадуємо що база розподілена: це значить, що тобі доведеться змусити усіх прийняти не одну твою маленьку зміну, а величезну купу змін. І обгрунутвати їх для них.
- А як це робиться?
- Ух. Це точно вже не сьогодні.

#WrittenInTheJungles #HashSeries

- Ти казав, що хеші, ще використовуються якось в біткойні. Так?
- Я сказав не так. Хеші використовуються в блокчейні.
- В чому різниця?
- Блокчейн це структура даних. Біткойн програма(а також ще валюта), що викорстовує цю структуру даних. Миж не називаємо усі програми масивами тільки тому, що вони там використовуються?
- Зрозумів. Так а хеші так навіщо?
- Я колись дуже докладно це розбирав в одному з відео, але тобі ще може бути зарано таке дивитись, тож давай коротенько
- А це обідно було...
- Проігнорую. Так от. Є структури даних - це такі алгоритми, що описують як ці данні зберігати. Те що виходить в результаті має свої властивості: сильні, слабки сторони, обмеження, тощо. Ті самі хештаблиці, що ми розбирали до цього, наприклад, які мали властивості?
- Швидкий пошук по ключу, швидка вставка, швидке видалення і не супер по пам'яті.
- Так. А тут інша структура. І її властивостю буде можливість виявити підміну даних.
- І навіщо це може бути потрібно?
- Для того щоб збудувати надійну розподілену базу даних в середовищі де те не знаєш кому довіряти.
- Вау
- Тут звісно згадуємо біткойн, як валюту без центробанка і взагалі без банка хто б її обслуговував.
- Так і де тут хеші?
- А дуже просто: я ж вже сказав, що це структура даних, тобто так чи інакше колекція елементів з можливістю туди щось додати.
- Так
- Додаючи елемент ми додаємо не лише його, а ще й його хеш.
- Як в TCP протоколі?

Більше двох років тому, вже писав тут про хеші і їх засолювання.

- А те що ти казав, що хеші дозволяють і в швидкість і безпеку це і були контрольні суми в пакетах в TCP чи є ще щось?
- Так є і ще багато трюків.
- Наприклад?
- Давай почнемо з чогось простого: пом'ятаєш архівчики з паролями?
- Так.
- Я завжди ломав голову як вони роблять безпечно функцію: ругнутись модальним вікном на невірний пароль.
- ..., - (Замислився)
- Ну да, мені прямо спокою не давало: бо якщо його дописати в сам файл, то його можна буде вскрити. Якщо зашифрувати, то як дізнатись, що це він, а не мусор?
- Мабуть можна було б дописувати якусь кодову фразу в шифрований зміст і після розшифровки перевіряти її наявність: якщо є, то все добре.
- Доречі непоганий варіант, але має один недолік. Якщо архів великий, то не швидко ти зможеш ругнутись на те що пароль не вірний: аж після всієї розшифровки.
- Можна її складати десь в початок
- А знаєш, я тут зрозумів, що варіант твій паршивий: це знижує криптостікість. Якщо ти знаєш що зашифровано, то це легше взломати. Але і це не єдина проблема.
- А яка ще?
- Багато з сучасних хешів перемішують вмсіст інформації, що шифрують: тож можуть або розшифрувати повністю, або ніяк. Можна, звичайно бити на шматки, але тоді повертаємось до криптостікості.
- Добре, а як тоді?
- А ми до шифротексту(так називають результат шифрування) додаємо ще й хеш паролю(сам хеш у відкритому вигляді).
- Вау. І тоді ми можемо звірити хеш введеного паролю, доволі швидко і якщо він правильний, то іти розшифровувати, а якщо ні, то йти показати це користувачу.
- Саме так, але і це має свої проблеми з безпекою
- ..., - (замислився надовго), - Які?
- А те, що гарних хеш функцій в нас небагато і робити їх важко, паролей хоч і багато, але не настільки, щоб разок не сісти і не свторити словник(да-да саме словник як хештаблицю, де ключем буде хеш, а значенням пароль.) з ними усіма (ті що люди релально використовували). Тоді: якщо пароль один із таких, то ти дуже швидко це з'ясуємо і вскриємо
- Від цього вже не захиститись? Тільки унікальні паролі всюди?
- Да чого ж. Трішки можна. Це називається підсолювання хешів.
- Кулінарно...
- Диви: ми до паролю додаємо унікальну випадкову сіль(просто якийсь не дуже довгий унікальний рядок) і хешуємо вже з нею.
- Вау.
- А тоді, звісно паролі що люди колись використовували перебрати знаючи сіль можна, але ж це під кожен архів треба робити окрему таблицю.
- Це все цікаво, але щось від тебе нафталіном тхне. Хто ще використовує шифровані архіви сьогодні?
- Біс його хто, але підхід той саме і з паролями користувачів на сайтах: не зберігай пароль, а зберігай хеш. І не забудь кожен унікально підсолити.
- Вау втретє! Тоді, навіть якщо зловмисник заволодіє базою, то він не зможе дістати з неї паролі
- Зможе, якщо пароль не дуже довгий, або не дуже унікальний: тобто суттєво зменьшить кількість можливих варіантів. Але ще: за рахунок того, що сіль унікальна для кожного користувача йому доведеть витрачати достобіса потужної потужності на кожного з користувачів. Не вийде один раз зробити таблицю хешей популярних паролей вже з сіллю і нею вскрити усіх, щоб потім побігти на інші популярні ресурсі очікуючі, що у людини всюди один і той саме пароль.
(Ще трохи тут)

#WrittenInTheJungle #HashSeries

Якщо комусь це цікаво чи корисно, то закиньте йому чи їй цей допис. Мені буде приємно.

Як робиться надійність за допомогою хешів?

- Я второпав як хеші допомогають покращувати швидкість застосунку до шалених значень, але жеруть порядком так пам'яті, побачив як зробити таку структуру, що може жерти рівно стільки пам'яті скільки ти їй даси, але ти казав, що хеші ще якось використовуються в безпеці і надійності?
- Так.
- Але ж вони самі по собі не дуже надйні. Колізії і всі діла.
- Так, проте це все одно може покращити надійність, коли її небагато. От уяви, що в нас є швидкий, але паршивий за якістю канал зв'язку.
- Що значить: "паршивий за якістю"?
- Дані або губляться зовсім, або частково, або просто псуються: тобто частина даних ті(вірне), а частина інші(невірні). І треба налагодити надійний зв'язок по такому каналу.
- Хіба це можливо?
- Цілком. Нам треба лише виявляти ті випадки, коли дані загубились чи зіпсувались і мати можливість запросити втрачені заново.
- І тут нам стануть в нагоді хеші?
- Можна і без них звісно. Давай навіть спробуємо. От ти відправляєш повідомлення, але ти не впевнений, що воно не зіпсується. Тому ти береш і пишеш одне й те саме повідомлення двічі. Якщо перше не співпадає з другим, то значить щось не так. Яке з них вірне не з'ясувати, тож треба запитувати все заново.
- Ага. Зрозумів. Подвійне навантаження з якого лише половина корисного. А значить замість дублювання повідомлення можна дописати до повідомлення хеш. Потім обчислити хеш повідомлення, що прийшло і порівняти з тим що було дописане.
- Саме так. Якщо не співпало, то просимо повторити. Є звісно імовірність колізії, але важко уявити, що випадково зламене повідомлення зламається саме таким чином, щоб дати колізію хешу. Ну звісно, окрім випадків, коли наша хеш функція дуже паршива і на всі, чи майже всі вхідні параметри дає один і той саме результат. В цілому: ми на пів дороги до винайдення TCP.
- Чому на пів?
- Бо ми ще не вирішили проблеми повної втрати повідомлення. Коли немає з чим порівнювати.
- Щось не можу придумати як тут може бути внагоді хеш.
- Насправді може і бути: наприклад ми будемо дописувати до пакету хеш попереднього повідомлення. Потім перевіряти чи те повідомлення, що ми вважаємо останнім має такий саме хеш. Але то вже майже якийсь blockchain виходить. В TCP воно вирішено значно простіше.
- І як?
- Да просто нумеруються пакети да і все.
- Вау, а це дійсно просто.
- Плюс коли ти отримуєш пакет, ти ще відправляєш один назад з номером того пакету що отримав. Якщо з номерами щось не те, то частина пакетів буде відправлена заново.
- А що як наступного пакету так і не буде?
- Поперше такого не може бути: бо ти все одно змушений надіслати підтвердження в отриманні на кожний пакет. А по друге, часто щоб зробити протокол ще надійнішим додають ще механізм серцебиття (heartbeat).
- Це що таке?
- Да просто пусті повідомлення з цими номерами, що мають відправлятись протягом певного часу. Якщо такого немає в зазначений час і ще якийсь час додатково, то значить з'єднання протухло: його можна викидати і створювати нове.
- Про час не дуже зрозумів.
- Приклад: обидві сторони відправляють пакети серцебиття щосекунди, але є там затримки мережі і таке інше, тож якщо рівно за секунду пакету немає, то ще не факт, що все пагано: але якщо пакету немає вже 5 секунд, то точно все пагано.
- Второпав.

#WrittenInTheJungle #HashSeries

Якщо комусь це цікаво чи корисно, то закиньте йому чи їй цей допис. Мені буде приємно.

- Слухай, а мені сподобався трюк із масивом, де ми його зменьшили з двох мільярдів до одного. А за потреби на скільки завгодно.
- Так, у двічі то було тільки для прикладу, так-то ми можемо обмежитись і доволі невеликим масивом, а збільшувати лише за потреби. Там коли заповнився якийсь відсоток значень.
- Так, так, але я не про те. Ми ж за допомогою хешу і всього цього змогли навчитись дуже швидко відповідати, що елементу немає в колекції. При чому з абсолютною точністю. А от вже відповідь про наявність вже не настільки точна. Вірно?
- Саме так, тому для того, щоб не було помилково-істиних відповідей ми ще порівнюємо елементи.
- До діла. Мені поклали веб сервак, тупою 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. Як модифікувати атаку таким чином, щоб вона все одно поклала сервіс? Пишіть у коментах. Може футболку, комусь подарую за кльову відповідь. В мене одна ідея є.

- Почекай. Давай трохи назад. Масив на два мільярди значень звучить не дуже професійно... І якщо один такий на сучасному залізі ми ще можемо собі дозволити, то купу вже навряд.
- О да. Але ми вже навчились боротись з колізіями, тож давай просто скоротемо масив вдвічі, а замість того щоб в якості індексу використовувати сам хеш використаємо залишок від ділення на мільярд.
- А це спрацює. Плюс в нас вже збережений хеш, тож у випадку якщо хеші різні, але залишок однаковий, то ми зможемо не порівнювати самі елементи.
- В точку.
- І так само можна зменьшити масив наскільки завгодно.
- Саме так.
- А через те, що в нас вже є заздалегіть виділиний масив, а, навіть якщо трапляється колізія, то вставка в нього буде дуже швидка.
- Дуже швидка.

І тут я епічно ломаю п'яту стіну не гірше за Френка Андервуда і кажу, що саме так і працює велика політика HashSet у більшості мов програмування. Так само працюють і HashTable і Dictionary, тільки додають до Entry ще саме значення.

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

Закиньте будь ласка, це комусь, кому це може бути корисним.

#WrittenInTheJungle #HashSeries

Завдяки чому все може працювати швидко? (HashSet, HashTable, Dictionary)

- Так до чого хеші і перфоменс застосунка?!
- Спрва в тому, що в нас фундаментально усього два способи зробити щось швидше: або робити меньше обчислень, хоча б у більшості випадків, або ж залучити більше потужності для обчислень. Більше потужності, то краще залізо, більше грошей клауду за крутішу вірталку, чи навіть спробувати витиснути більше з того що є завдяки обробці у кілька потоків.
- Все ще не може второпати до чого тут хеші? Залізо додаткове вони не дадуть, а роботи наче як навпаки додають.
- Не без цього. Можна, якщо знати куди бити, навіть ушатати застосунок і покласти сервери когось, хто тобі не подобається, але здебільшого ми все ж таки виграємо.
- Як?
- Пам'ятаєш властивіть хеш функції: якщо хеш не співпав, то об'єкти точно різні, а якщо співпав, то імовірно однакові.
- Так. І?
- Тобто порівнявши хеші ми можемо уникнути порівняння самих об'єктів якщо вони не співпали.
- Це вже щось... Деякі об'єкти порівнювати довго і шукати по хешам було б значно швидше.
- Саме так. Навіть якщо ми просто додамо до об'єкту хеш як поле і будемо видавати FALSE, якщо вони не співпадають, то ми вже значно виграємо на складних об'єктах з купою полів.
- Звучить не погано, але для них і хеш треба прорахувати відносно всіх цих полів, тож це теж часу займе добряче.
- Ну звісно: якщо тобі треба пошукати усього лише пару разів, то це точно не стане в нагоді. Але уяви, що в тебе повно тих об'єктів і шукати по ним доводеться часто.
- Не погано, але все одно наче не так і багато де застосуєш: часто треба шукати по імейлу, логіну чи якомусь ID, що порівнюються може і довже за хеші, але не суттєво. А тут ще й треба десь заздалегіть всі хеші обрахувати, зберігати, та слідкувати, щоб додавати туди нові об'єкти та видаляти старі.
- Саме так. Все вірно, але є ще один трюк, що вирішує усе. Нам треба розкласти об'єкти, разом із хешами особливим чином, щоб ще значно скоротити пошук. Тобто робити суттєво меньше.
- Як саме розкласти?
- Давай уявимо, що в нас хеш це інт. Для простоти скажемо, що він не може мати від'ємних значень. Тобто від 0 і до 2х з гаком мільярдів. А тепер трохи поїдемо дахом і зробимо масив на ті самі два з гаком мільярди елементів. Всі за замовчуванням пусті, але обраховуючі хеш ми використаємо його як індекс у цьому масиві і покладемо сам елемент на його місто.
- І тоді ми можемо перевірити наявність елементу у колекції просто перевіривши відповидний елемент масиву на пустоту. Умовно на null. Це буде швидко, але що робити з колізіями?
- Щоб не сказати на алемент котрого насправді нема, що він є ми таки збережемо оригінальний елемент і порівняємо з ним перед тим як остаточно повернути TRUE.
- Ага. І це буде усього лише одне порівняння вне залежності від кількості елементів в масиві.
- Нууу... Майже. Колізії несуть дві загрози:
1. Можливість видати помилково TRUE, це ми вирішуємо збереженням елементу і порівнянням при пошуку.
2. Нам може буде потрібно зберігти два різних елементи з однаковим хешем.
- Ох
- Ага. Тому ми змушені зберігати у кожному елементі нашого велитенського масиву на два мільярди значень.
- Це ж скільки на це все пам'яті на це піде.
- До біса, якщо робити все неправильно і не так вже багато, якщо трохи потрюкачити. Наприклад ми можемо використати у якості типу нашого масиву щось таке:
record Entry(int Hash, object Value, Entry? Next);
- Типу зв'язаного списку?
- Так. Ми не будемо витрачати пам'ять, якщо елементу геть немає і не будмо одразу виділяти пам'ять під якусь там колекцію, якщо колізій так і не станеться. А якщо хеш функція добра, то вони не дуже й часті.
- Стоп... А якщо погана?
- Тоді буде цікаво. Це буде працювати хахливо, бо ми витратимо час на обчислювання хешів і нам все одно доведеться порівнювати всі елементи. Але це буде працювати. На цьому побудована одна з можливих атак: якщо знаєш багато колізій для якогось хеша і знаєш де він використовується, то можна спробувати змусити їх використовувати до біса обчислювальної потужності.

Не відкладай на "потім прочитати": там вже і так багато усього.

Зовсім трошки про хешфункції.

- Що це таке?
- Це такі функції, що:
1. Перетворюють одне значення будь якого розміру на інше значення фіксованого.
2. Для одного і того самого значення завжди повертають одне й те саме значення.
- Тобто це хеш фкнція?
int GetHash(object o) {
return 77;
}
- Так, але паршива
- Що таке гарні хеш функції?
- Це такі функції, що:
1. Що для різних значень частіше за все повертають різні значення
2. Значення в яких розподіленні рівномірно по всьому діапазону можливих значень
- Чому частіше за все?
- Не треба бути дуже розумним, щоб придумати таку хеш функцію для кожного з булєвих значень буде повертати різне ціле число(int).
- Чому?
- Тому що булєвих значень усього 2, а цілих чисел(int) ~4 мільярди.
- Так чому не повертати для всіх об'єктів завжди для різні значення?
- Тому що різних об'єктів може бути більше 4 мільярдів.
- Чому не обрати щось більше за int для хешу? Long чи decimal?
- Бо різних об'єктів ще більше. Що як ми обрали decimal як тип хешу, а нам прийшов об'єкт що може бути decimal, але ще й може бути null, або об'єкт з двох decimal, або decimal і bool?
- Гм.. І що робити?
- Змиритись. Нам не вистачить діапазону можливих значень, тож можуть існувати два різних значення для котрих хеш функція буде давати одні й ті самі результати. Це називають колізією.
- При наявності колізій зі 100% впевненостю ні. Уявимо, що в нас 256 можливих значень хеш функція і 65536 можливих значень. Кожному хешу відповідає 256 різних значень. Хтозна яке з них було орігінальним.
- Щось важко
- Ну давай уявимо, що наша хеш фкнкція просто складає розряди числа: на вхід отримали 12 345, то хешем буде 15. Але такий саме хеш і для 96 і 69 і 159 і купи ще інших чисел.
- Добре. Так і що з цим можна робити?
- Зробити систему, або дуже швидкою, або безпечною, чи навіть все разом, але то наступним разом.


#WrittenInTheJungle #HashSeries

А і ще одне.
Жодного відео з каналу ніколи не було видалено: всі доступні в плейлістах.

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

Доброго дня, починаємо збір коштів на РЕБ для 127ї бригади ТрО Харкова, в котрій зараз служить мій вітчим.
РЕБи - занадто важлива річ для захисту особистого складу та автівок від FPV-дронів, збираємо на РЕБ сьогодні, щоб не збирати на нові корчі завтра.

Чепель Михайло
Банка:
https://send.monobank.ua/jar/6yw1jstqjq
Номер картки банки:
5375411218204712

Кому як не тим хто боронить Харківщину зараз закидати, вірно?

Це прохання від мого доброго друга і однокласника.

Сам вже долучився.

Як і обіцяв в останньому відео викладаю для своїх любих спонсорів лекцію з далекого 2019 року, "Уроки контролостроения"
А хто ще не спонсор, але хоче подивитись, тож бігом підписуватись на новий рівень!

Можете вірити, можете ні, але це нове відео на Dev Jungles!
А тема така, що його б треба було випускати на перше квітня, але насправді там все дуже серйозно.
Тож нумо дивитись, коли ще таке буде?

https://youtu.be/3nx_zThOBWo?si=NHWoC_4CAh1TaHcX

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

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

Він у ППО Харкова, тож думаю зрозуміло, що це важливо зараз навіть більше ніж будь коли.
Збирають на шини для кразів і то виявилась, на диво для мене, до біса дорога штука.

Тож долучайтесь.
Я вже закинув на це 5к грн.

🎯Ціль: 173 000.00 ₴

🔗Посилання на банку
https://send.monobank.ua/jar/28VxcUgNjA

💳Номер картки банки
5375 4112 1551 2612

Оригінальний пост Валентина (того самого колеги):
https://www.facebook.com/story.php?id=100001081793764&story_fbid=7393666907345962

Друзі, вас вітає монтажер і режисер документалки, яка скоро вийде на цьому каналі.
Я знаю як ви всі чекаєте нових відео і вже дуже дуже скоро вони також будуть!
Але зараз я звертаюсь до вас за допомогою!
Ми з Андрієм з Луганська і намагаємось максимально допомагати нашим хлопцям.
Покажіть донатами, як ви хочете нові відоси!

Для військовослужбовців
❗️луганської бойової бригади, які захищають незалежність України на Авдіївському напрямку
👉🏻потрібно 300 000 грн
для закупівлі матеріалів для дообладнання БРДМ противокумулятивним захистом від дронів.

🎯Ціль: 300 000.00 ₴

🔗Посилання на банку
https://send.monobank.ua/jar/Af4ztjkKYq

💳Номер картки банки
5375 4112 1674 8421