Consensus

2021-06-13 11:11:04 Paxos Raft

Много споров, статей, постов на тему Raft vs Paxos(Multi-Paxos). Многие полагают, что Raft и Paxos это разные алгоритмы. Также считается, что Raft лучше для понимания, чем Paxos.

На мой взгляд Diego Ongaro(автор диссертации про Raft) не придумал принципиально нового алгоритма. Он описал инженерную реализацию Multi-Paxos и добавил туда некоторые улучшения.

Вот два неплохих обзора на статью Heidi Howard «Paxos vs Raft: Have we reached consensus on distributed consensus?», чтобы быстро понять отличия Raft от Paxos:
http://charap.co/reading-group-paxos-vs-raft-have-we-reached-consensus-on-distributed-consensus/
https://emptysqua.re/blog/paxos-vs-raft/
Авторы постов пробегаются по основным различиям алгоритмов и дают кучу полезных ссылок.

Для того, чтобы глубоко разобраться в различиях этих алгоритмов надо читать оригинальный paper Heidi Howard. Открыть/Комментировать

2021-05-27 18:07:01 Онлайн конференция по разработке параллельных и распределенных систем — Hydra 2021

Несколько десятков докладов о распределенных базах данных, распределенной обработке потоков, блокчейне, отказоустойчивости распределенных систем, моделях памяти и многом другом, что относится к работе с подобными технологиями.

Среди докладов:
– Маркус Куппе, «Workshop: TLA+»
Огромный воркшоп по работе с языком для дизайна распределенных систем под руководством основного разработчика среды TLA+ toolbox.
— Энди Павло, «The Official Ten-Year Retrospective of NewSQL Databases»
Обзор десятилетней истории NewSQL от зарождения до современного состояния и попробует предсказать, как NewSQL изменится в будущем.
– Нейтан ВанБеншотен, «Fearless Global Transactions with CockroachDB»
Доклад о том, как CockroachDB помогает работать приложениям с распределенной архитектурой.

Смотрите всю программу и покупайте билеты на https://bit.ly/3bSQ8DS

Если решили сходить, то используйте промокод на Personal-Standard билет: Consensus2021JRGpc Открыть/Комментировать

2021-03-24 09:07:01 Если изобретаете свой RPC протокол поверх TCP, то крайне желательно добавлять CRC32 в каждое сообщение и проверять чексуммы. CRC в TCP слабое и вероятность коллизий высокая. CRC в Ethernet более надежный, но свитчи пересчитывают эти чексуммы.

Две статьи, которые хорошо объясняют почему важно добавлять CRC:
https://www.evanjones.ca/checksum-failure-is-a-kernel-bug.html
https://www.evanjones.ca/tcp-and-ethernet-checksums-fail.html

P.S. Если всегда используете шифрование, то можно забить на дополнительные CRC. Открыть/Комментировать

2021-03-02 09:04:01 На прошлой неделе прошла одна из моих любимых конференций — FAST(File and Storage Technologies). Обычно, там достаточно суровые и интересные доклады с инженерной точки зрения.

Много докладов про то, как оптимизируют key-value базы данных под современные диски. Например, кладут WAL и первые уровни LSM дерева от RocksDB на Intel Optane, а остальное хранят на более дешевых дисках. Получается такой гибридный RocksDB(доклад про SpanDB).

Есть доклады про то, как можно делать IO шедулеры или маппинг логических блоков в физический для NVMe дисков.

Netflix показал как они делают свой CDN, но что-то мало технических деталей на слайдах.

Я пока что бегло ознакомился с докладами. Чтобы вникнуть в каждый пейпер, его надо перечитывать несколько раз, правда и это не всегда приводит к пониманию .
Но парочку интересных для себя точно отложил:
Facebook's Tectonic Filesystem: Efficiency from Exascale. Фейсбук представил свой новый сторадж Tectonic.
High Velocity Kernel File Systems with Bento. Написали FUSE на Rust. Теперь можно писать файловые системы на расте. Первый раз вижу в ядре что-то +- полезное на расте.

Полный список докладов с пейперами, слайдами и видео:
https://www.usenix.org/conference/fast21/technical-sessions Открыть/Комментировать

2021-02-08 09:30:06 Современное железо безумно быстрое!

Прошли те времена, когда софт упирался в медленные диски. Сегодня любой пользователь может собрать PC с NVMe дисками, который будет выдавать 11M IOPS на рандомных операциях чтения и 66 GB/s throughput. Узкое место сегодня — это CPU, неэффективный софт, ну и сетка, естественно, если гонять данные между разными хостами.

Еще хочется отметить, что писать софт для 100% утилизации NVMe дисков крайне нетривиально. Нужно точно избегать lock contention, правильно аллоцировать память, учитывая NUMA, избегать лишнего копирования памяти, использовать io_uring, DPDK и т.д.

https://tanelpoder.com/posts/11m-iops-with-10-ssds-on-amd-threadripper-pro-workstation/#hardware Открыть/Комментировать

2021-01-25 10:28:14 Классный open source курс по распределенным системам от PingCap:
https://github.com/pingcap/talent-plan

В этом курсе можно зафигачить Raft и Percolator на rust.
Либо на golang сделать распределенную key-value или relational базу данных.

В курсе все подробно расписано по шагам. Подойдет для тех, кто имеет минимальный опыт на golang/rust и умеет пользоваться гитом. Курс не подойдет тем, кто хочет выучить язык с нуля(вначале придется прочитать Rust Book или пройти A Tour of Go, этого будет достаточно). Открыть/Комментировать

2021-01-12 10:49:48 Awesome list of distributed transactions protocols

https://github.com/rystsov/awesome-distributed-transactions Открыть/Комментировать

2020-12-17 09:49:30 Я уже писал пост про FLP теорему, которая говорит, что в любом алгоритме консенсуса есть ситуация, когда система не может совершать прогресс.

Вот Clouflare как раз недавно наступила на эти грабли и их etcd сервис ушел в себя на 6 часов, когда случился network partition.
Их post-mortem анализ:
https://blog.cloudflare.com/a-byzantine-failure-in-the-real-world/

Cloudflare называет это Byzantine faiulure, но это не совсем корректно. Это обычный network partition и лечится он с помощью PreVote фазы и дополнительной CheckQuorum проверки на лидере.
Подробнее про PreVote и CheckQuorum можно почитать здесь:
https://decentralizedthoughts.github.io/2020-12-12-raft-liveness-full-omission/

Есть подозрение, что Cloudflare неправильно приготовила etcd с рафтом и флажки CheckQuorum и PreVote были false по умолчанию. Если юзаете etcd, советую проверить этот момент. Открыть/Комментировать

2020-12-15 10:21:01 Простое объяснение алгоритма распределенных транзакций Google Percolator(применяется в Bigtable).

https://tikv.org/deep-dive/distributed-transaction/percolator/ Открыть/Комментировать

2020-12-02 10:51:47 Amazon S3 теперь Strong Consistency

Пишут, что strong consistency будет бесплатная и включится автоматически для всех существующих и новых объектов.

P.S. Представляю сколько костылей выпилится из приложений, которые используют S3. И сколько разработчиков S3 совместимых стораджей сейчас думают как сделать strong consistency

https://aws.amazon.com/ru/s3/consistency/ Открыть/Комментировать