== вполне. советую
https://youtu.be/gOB3hpAVIIQ

- Транзакция, транзакционная база данных
- Расшифровка ACID
- Atomicity (атомарность)
- Consistency (консистентность)
- Isolation (изоляция)
- Read committed
- Snapshot isolation (repeatable read)
- Демонстрация отличий read committed и repeatable read на примере MySQL
- MVCC
- Проблема lost update
- Durability

Так как я уже не могу закончить этот пост неделю, напишу, что есть. Главное -- писать, остальное не так важно.

Что такое хорошая хеш-функция?

Этот вопрос на первый взгляд всегда кажется более научным, чем практическим. Да, в теории есть какие-то критерии. Даже пытались выстроить 5 уровней хэш-функции. Что взломать сложно или какие-то c-way-collisions найти очень быстро нельзя.

Криптографические хэши очень давно устоялись в индустрии и если перформанс для вас не так важен, SHA-3 и вперед.

В науке практически ничего невозможно доказать про хэш-функции кроме universal hashing, поэтому индустрия здесь надеется на смысл, чтобы хоть как-то предсказать хэши было сложно в случае хэш-таблиц.

И я тут даже не хочу говорить о каких-то хэшах типа MurMur, Farmhash, Cityhash, Wyhash, и тд. Если вам интересно, можете посмотреть их сравнение на smhasher: этот репозиторий кстати очень недооценён, сравнивать хэш-функции на коллизии, случайность стоит, а вот мало кто такой неблагодарной работой занимается.

Вопрос, который я решал последние пару месяцев и о котором я всё не мог написать, а как находить хэш-функции с хорошим распределением и ещё желательно, чтобы они были быстрыми?

Мир как-то слишком мало ответов знает на этот вопрос. Можно даже проще сформулировать: даны не более 16 байт (hi, lo) и длина, какое минимальное количество инструкций надо, чтобы получить хороший хэш?

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

А что важно хэштаблице? Коллизии, потом скорее усложнение их поиска и чтобы "на проде" работало нормально. Коллизии чаще встречаются на размерах степеней двойки, как делают, скажем flat_hash_* в Abseil и Folly. Поэтому важно, чтобы нижние биты не сильно совпадали даже если нет коллизий :)

Итак, у нас есть хэш таблицы, у них не очень большие ключи и просто туча применений.

Попытка 1: crc

Инструкции CRC32 впаяны прям в процессоры x86 и Arm. Хоть это вычисление достаточно быстрое, CRC32C никогда не был сделан для хэш-таблиц, падает статистические тесты. Достаточно много коллизий, когда данные не слишком отличаются, это фактически означает, что если вы будете добавлять какие-нибудь указатели или числа/строки с одинаковым суффиксом, то коллизий будет достаточно много.

Этот факт я не особо знал. а вот ClickHouse повсеместно использует crc для хешей, можно идти ломать их join или что-нибудь ещё 😊 (не проверял, terms and conditions apply).

Ещё один страшный факт, что даже 64 битные crc32 инструкции возвращают 32 бита, если ваша хэштаблица приближается к 2^26 элементов, коллизий будет уже очень много.

Попытка 2: 128 битное умножение

Мы в abseil выбрали approach слегка другой, а название ему 128 битное умножение

(seed + number) * prime_number

Далее это число 128 битное, сделаем xor верхней и нижней части, это будет хэш для 8 байт. Для 16 повторить ещё раз c верхней частью и seed как результат нижней части.

На удивление это имеет достаточно хорошее распределение.

Зачем делать xor? Потому что если seed+number чётное, то умножение будет очень предсказуемым и нижние биты предсказуемы чаще. Считается, что при умножении средние и верхние биты числа не очень предсказуемы. Это хорошо на практике показано у PCG-random. Поэтому разбавить нижние биты всегда нужно чем-то.

Похожую идею можно увидеть даже у MurMur:

uint64_t fmix64 ( uint64_t k )
{
k ^= k >> 33;
k *= BIG_CONSTANT(0xff51afd7ed558ccd);
k ^= k >> 33;
k *= BIG_CONSTANT(0xc4ceb9fe1a85ec53);
k ^= k >> 33;
return k;
}

Попытка 3: перебор

Для 16 байт мы знаем, что есть хэш функция с хорошим распределением в 6 инструкций. Вопрос, а какое минимальное? Можно взять какой-нибудь set и перебрать. Вопрос в том, какие данные брать: я решил брать около 1000 входов, где есть случайные числа и все их соседи, где отличаются на 2 бита.

3 инструкции не работают совсем, лучшая 4 инстручная последовательность

r0 = hi - seed;
r1 = lo + 0x71b1a19b907d6e33;
r2 = r0 * r1;
r3 = r2 ^ r2_hi;
return r3;

Ломается на распределениях побольше. Всего перебор дал где-то 40 вариантов, все сломались на бОльших распределениях.

Можно перебирать 5 инструкций, но количество операций уже растёт слишком экспоненциально. На каждом шаге выбор где-то из 100 вариантов (все пары переменных * операции (+-^*,shift,rotate,crc,&,|)), в итоге даже если не разрешать все сдвиги или rotate, получается много. 115^n примерно, где n количество инструкций, на каждую итерацию надо проверить около 1000 входов на коллизии, что достаточно затратно. В итоге для n = 5, 10^15-10^16 итераций, ну можно запустить map reduce pipeline на часы. Ура, нашли 25k вариантов.

Дальше я пока сдался, потому что ощущение, что я схожу с ума. Чтобы отсеивать дальше, надо уметь больше распределений или запускать прям smhasher на все найденные.

Ну либо пойти к DeepMind, пусть их RL штуки находят хэш функции, наверное, можно поумнее.

Но мне кажется я вот вот либо докажу, что не существует хорошей 5 инстручной хеш функции для 16 байт, либо найду её наконец-то. Даже если все найденные свалятся, то никто не знает, может, я просто не добавил нужную инструкцию в перебор.

Мораль: перебирать ассемблер адски тяжело. Отсеивать плохие хэш-функции быстро адски тяжело. Ускорения в оба направления могут помочь нам дать лучшие хэш-функции. Пока вопрос открыт. Продолжаю рисёрч.

Сходство строк в Python

Метод ratio() возвращает меру подобия/схожести последовательностей в виде числа с плавающей точкой в диапазоне [0, 1].

Почему такой штуки у меня не было когда работал в КонструкторскомБюро ? Потому что бомж
https://youtu.be/u_Z3c9DXY4A

​Чего его не любить? Хороший язык программирования...

#кек #twitter

Повторение мать...
https://youtu.be/qb6l4B57Qmw

Знакомьтесь с генеративной архитектурой. Наконец-то можно будет выбирать дизайн шаурмичной по своему вкусу.

Если честно, это лучшее, что происходило с графикой за последнее время.

С нетерпением жду, когда всё это перейдёт в объём и будет продакшн реди.

== Тесты статистической проверки принадлежности нормальному распределению Python
https://telegra.ph/Testy-statisticheskoj-proverki-prinadlezhnosti-normalnomu-raspredeleniyu-Python-10-13
- Тест Шапиро-Уилка
- Тест Колмогорова-Смирнова
- Тест Андерсона-Дарлинга
- Тест Лиллиефорса
- Критерий К-квадрата Д'Агостино
- Тест Харке-Бера

Проверяем, является ли заданная дата – праздником

Установка модуля - pip install holidays

В нашем примере мы проверяем является ли 25 декабря 2021 в Великобритании праздником. Наша программа выдает нам, что в этот день отмечается Рождество.

Подробнее про данный модуль можно почитать здесь.

Порядок разрешения методов

В Python существует так называемый Method Resolution Order (MRO), или порядок разрешения методов в классе. Всё, что вам нужно знать – это порядок, в котором Python ищет нужный атрибут или метод.

Этот порядок можно получить при помощи атрибута __mro__. Он говорит о том, что если мы в примере выше попробуем обратиться к атрибуту value, Python будет искать сначала в классе A, далее в B, затем в C и в самом конце в object.

Отсюда становится понятно, что артибут первее будет найден именно в классе B и равен он будет значению 1.

Прочитал тут коммент на ютубе "Архитектор должен разрабатывать архитектуру, а не разработчик". У меня для вас плохая новость, так было лет 10 назад, сегодня программист в небольшой компании (если это синьер) должен разбираться в архитектуре на уровне приложения, уметь проводить архитектурные границы и использовать хотя бы базовые архитектурные шаблоны (как минимум чистая архитектура).

Требования росли, растут, и будут расти. Ну либо пишите на WordPress )))

Кажись, прощай Убунта) и XFCE. последние Кеды прям огонь

== Как поставить и насроить базовые пакеты в Монжаро. https://youtu.be/MH68As9TMKE

🛠 Инструмент для визуализация связей и структуры в базе данных, поддерживающий более 20 разных БД. Доступен как онлайн, так и для установки на собственном сервере:

- Онлайн: https://sqlflow.gudusoft.com/
- Селфхост: https://github.com/sqlparser/sqlflow_public/blob/master/install_sqlflow.md

#линк #sql

== The Art of Logging
https://betterprogramming.pub/creating-a-human-and-machine-freindly-logging-format-bb6d4bb01dca

еще один сервис по анализу EXPLAIN
https://explain.tensor.ru/about/#expanded

== Understanding a Kernel Oops!
https://www.opensourceforu.com/2011/01/understanding-a-kernel-oops/

прикольная тула
https://sqlflow.gudusoft.com/#/
анализирует SQL запрос и строит удобную визуализацию взаимосвязей

гниЛаб 😂😂

#autotomated

== Простые highload паттерны на Go
https://habr.com/ru/post/682618/

- Refresh-ahead caching
Если по бизнес логике вашего приложения допустимо отдавать данные не первой свежести, то кешируйте их в приложении и отдавайте как есть. А сами данные обновляйте в фоне

- Do once, give it to everyone
Если много пользователей приходят одновременно в сервис за одной и той же информацией, зачем ее выполнять в лучшем случае дважды, а в худшем тысячи раз?

- Worker pool
на старте приложения инициализировать N воркеров, которые будут выполнять полезную работу, и сбрасывать состояние объектов воркера после завершения задачи

== Средние highload паттерны на Go
https://habr.com/ru/post/684904/

- Stateless horizontal scaling
Есть приложение, которое крутится в бою и вполне себе успешно выполняет свою работу. Постепенно трафик растет, пользователи становятся ненасытнее и все активнее пользуются приложением. И вот настигает пик, при котором CPU/RAM физически уже не хватает и требуется принять меры. Решение простое и очень эффективное - создать реплики приложения

- Sync to async
Есть приложение, в котором активно растет трафик и помимо основных, оно выполняет еще и вспомогательные функции, которые с ростом трафика начинают влиять на пользовательский опыт. Так почему не выполнять вспомогательные функции асинхронно?

- SQL to NoSQL
Есть приложение, в котором есть одно хранилище под все и, как правило, это какая-нибудь реляционная база данных. Уезжать из него очень не хочется, но пользовательский трафик растет с такой скоростью, что поддержание одного такого хранилища обходится дорого. - заюзать витрину nosql