Ссылки: электроника

В браузере моего мобильного открыто множество страниц. И все интересные, и все хочется сохранить. Сюда скину ссылки на страницы об электронике.

• Видео Новые платформы и модули на канале voltNik. 
• Сообщество ремонтеров на Picabu.
• Супер-мега подробный рассказ о NodeMCU и WiFi розетке с этой железкой.
• О ремонте кабеля USB-microUSB
• Статья на ту же тему на кунг-фу-сайте мастер пайки 
• Видео Ремонт usb кабеля для зарядки телефона
• Доходчиво о чтении электрических схем
• Теор основы электротехники в блоге DI HALT
• Пайка разъема гарнитуры/наушников на Picabu

Курс по анализу данных на github

Какие-то добрые люди разместили краткий курс по науке о данных на гитхабе. Оглавление здесь. Почитал пока только про MapReduce (в последнем, 14м модуле) - очень занятно. Думаю, и остальной материал настолько же хорош.

Лучшие способы применения Redis

Компания RedisLabs, разрабатывающая Redis, собирает советы по использованию своего детища в разделе Best practices. Рассказывается, как использовать Redis в качестве индекса, для взаимодействия приложений, в статистических целях и, конечно же, как лучше хранить в Redis данные. Ознакомиться можно по ссылке, архивные записи здесь.

Модели согласованности

Хорошая картинка с иерархией моделей согласованности. Краткое описание сути нескольких моделей со ссылками на статьи. Пересказ раздела "Согласованность и репликация" из Таненбаума.

Целостное хэширование - наконец-то!

Наконец-то я понял идею целостного хэширования (consistent hashing)! Много чего читал - и никак.

Вот, например, замечательный пост, где объясняется идея этого вида хэширования, в контексте статьи о Amazon Dynamo (ссылка на саму статью). Хорошо все рассказано - и всё равно не понял.

Но Интернет большоооой. Вот, наконец, пост, который смог мне объяснить эту простую идею.

Итак. Есть функция хэширования f(). У нее есть некоторая область значений (fmin, fmax). Сворачиваем ее в кольцо. Берем имеющиеся сервера (по которым нужно равномерно распределить ключи), у каждого своё имя (IP-адрес, например). Хэшируем имена серверов, получаем точки на кольце (эти точки разбивают кольцо на отрезки). 

Теперь берем ключи, хэшируем их названия, получаем новые точки, которые распределяются по кольцу. На каком сервере будет размещен данный ключ? Берем ключ, его хэш - точка на кольце. Двигаемся по кольцу по часовой стрелке, находим первую точку, которая представляет сервер. На этом сервере и будет размещен данный ключ. При добавлении/удалении сервера будут перераспределено лишь небольшое количество ключей. В отличие от простейшей методике, где номер сервера определяется по формуле хэш(ключ) % количество_ключей. 

В описанной схеме каждый ключ хранится на одном сервере, что небезопасно. Поэтому данный сервер может разреплицировать свои ключи по T следующим серверам в кольце.
  

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

DHCP-сервер роутера отказал в аренде IP

Вот такую ошибку нашел в журнале событий планшета:
dhcp-сервер отказал в аренде IP-адреса (имеется ввиду dhcp роутера).

Советы из интернета:
Попробуйте увеличить время аренды адресов в DHCP-сервере роутера до хотя бы 7 дней вместо суток.  Вообще-то для сети, где используются постоянные устройства , лучше ставить аренду (Lease Time) хотя бы на месяц. Или вообще на год. А то мало ли по какой причине данное устройство долгое время будет не в сети...

Сатоши Накамото на русском

Знаменитую статью "Bitcoin: A Peer-to-Peer Electronic Cash System"  можно прочитать на русском. Вот здесь лежат переводы этой работы в том числе на наш Великий и Могучий.

Разработка игр

Игры - это замечательный тренажёр для программиста. Позволяет отточить все виды навыков - от компьютерной графики до сетевого взаимодействия.

Фундаментальный труд Multiplayer game programming. Cтек TCP/IP, сокеты, сериализация объектов, репликация объектов и ... сами игры :)

Статья Distributed Architectures for Massively-Multiplayer Online Games. Кратко даются основы распределенных систем, а затем рассматривается вопрос, как писать многопользовательские игры для архитектуры peer-to-peer.

И, наконец, книжка на русском (переводная) Шаблоны игрового программирования. Приемы решения типовых задач при написании игрового ПО. Меня пока больше всего заинтересовали глава 9 Игровой цикл (по-английски game loop, основной цикл программы, в котором считывается пользовательский ввод, обновляется состояние игры, производится отрисовка) и глава 10 Метод обновления

Etherium, Solidity, geth.

Вот такие интересные имена бывают. Брендон Арванаги. Это блоггер, который пишет о блокчейне. Интересно, подробно и с примерами.

Меня заинтересовала возможность попробовать блокчейн у себя на компьютере или на собственном маленьком кластере. Оказывается, для этого есть все возможности. На Golang написана реализация Эфирного блокчейна, называется geth. Арванаги написал статью How to Set Up a Private Ethereum Blockchain using Geth где рассказывает азы работы с этой штукой. А если захочется со смарт-контрактами поиграться - пожалуйста, пост  Testing Smart Contracts Locally using Geth.

Что же дальше? Как выглядят суровые будни разработчка смарт-контрактов в России ? Об этом можно почитать в статье Как я окунулся в смарт-контракты.

А могут ли хакнуть блокчейн ? Еще как. И смарт-контракты только помогают в этом злоумышленникам. Уже и Лаборатория Касперского заинтересовалась безопасностью блокчейна. Вот интересный пост от их сотрудника (с описанием крушения The DAO).

Блокчейн: византийский консенсус, установка в локалке и версия на Питоне

Давно уже слышал, что в блокчейне решена проблема византийского консенсуса и двойных трат, но подробного разбора этого момента не видел.

В серии статей Understanding Blockchain Fundamentals кратко объясняется в чем состоит проблема византийских генералов. В изначальной формулировке (1975 года)  говорилось о двух генералах. В 1982 году вышла статья Лэмпорта и других, где задача была обобщена на

случай n генералов. Было показано, что можно достичь консенсуса, если предателей не больше трети.

В третей статье кратко описывается протокол delegated proof of stake, о котором до этого не знал почти ничего. Основная идея, что майнеров (в PoS и DPoS их называют валидаторами) выбирают пользователи, причем больше голосов у тех, у кого больше местной криптовалюты.  А в обычном PoS каждый может быть валидатором, но больше шансов добавить блок у более "богатых" пользователей.

А про двойные траты я нашел информацию в статье A Practical Introduction to Blockchain with Python. Там же, разумеется, приводится реализация блокчейна на Питоне.

А есть еще реализация блокчейна Ethereum на Go, которую можно скачать и развернуть у себя, в своей сети.

Искусство тестирования ПО

Замечательная статья на Хабре Юнит-тестирование для чайников. Моки, стабы и прочие интересные штуки. Вот еще статья на эту тему, там побольше примеров. Вот здесь обсуждается классификация тестирующих объектов (Dummy, Fake, Stub, Mock) 

А вообще информации про тестировании полно. Что еще раз подтверждает необходимость тщательной отладки ПО. 

Роботы и блокчейн в России

Отличная статья у Фриц Моргена Роботизация нашей промышленности.  ОС для киберзавода (Газпромовский Центр Цифровых Исследований делает), беспилотные погрузчики, роботы-заправщики,  цепочка поставок на блокчейне (Газпром-Нефть), нейросети для проведения ледокольных караванов. Красота. Кстати, в Газпромовской ОС в качестве СУБД использует Apache Cassandra.

8 заблуждений - всё? Реальное воплощение PAXOS а

Мир меняется так стремительно, что остаётся только разводит руками.

Решил получше разобраться с известными 8ю заблуждениями, которые сформулировал в 1994 году Дойч (8е добавил Гослинг, создатель Java). Есть небольшая статья в Вики. А есть..

еще одна статья, которая называется "The 8 fallacies of distributed computing are becoming irrelevant". 

В этой второй статье говорится, что все эти заблуждения уже в общем и не заблуждения. И сети надёжны, и с латентностью разобрались, и т.д., и т.п.. А всё благодаря репликации, конкретно - благодаря технологии Active Transactional Data Replication. В самом конце статьи приводится в качестве примера гуглопродукт под название Cloud Spanner.

Стал копать. Active Transactional Data Replication - это технология, используемая в IBMвском Big Replicate (версия продукта Fusion от WANDisco). И там есть репликация типа active-active (это типа master-master?). Вот интервью с разработчиками. 

Что интересно, в Big Replicate используется протокол PAXOS. Хм. Вообще-то я раньше читал, 

что PAXOS слишком сложен для реализации, собственно из-за этого и возник Raft (есть, кстати, ещё Zab). 

Так вот, оказывается, PAXOS реализован и используется в коммерческом (не академическом) проекте. И не одном! Упомянутый выше Google Spanner тоже его использует.

А что такое Google Spanner ? Нууу, это полное великолепие. Взять хотя бы это описание. Это NewSQL СУБД, со строгой согласованностью, масштабируемая в глобальном масштабе, с синхронизацией времени с помощью GPS и атомных часов. Т.е. расхождения времени (clock skew), получается, вообще нет. И всё благодаря паксосу...?

В общем, с PAXOSом имеет смысл ознакомиться. Вот здесь интересное сравнение PAXOS и Raft.  Иииии... конечно есть альтернативная точка зрения на могущество PAXOSа . "Why would you use blockchain over a distributed consensus protocol like Paxos or Raft?",- задают вопрос на Quora. И в комментах пишут, что PAXOS плохо масштабируется по сравнению с блокчейновским консенсусом (напр., выборы лидера и отслеживание "живости" процессов требуют слишком большого количество пересылок).

Вот так. Хоть стой, хоть падай. Протокол консенсуса, который считался слишком абстрактным и сложным, вдруг лёг в основу коммерческих софтин Big Replicate и Spanner. А в этих софтинах решены чуть ли не все проблемы теории распределённых систем.    

Как написать свою ОС?

Как я уже писал, материалов по поводу написания своей (хотя б маленькой учебной) СУБД в сети маловато. А вот руководств по созданию ОС - предостаточно.

Вбиваем в Гугл "how to write an operating system" (в подсказках еще "simple operating system source code" всплывает, но это потом посмотрю). И находим массу интересных текстов. 

Скажем, вот неплохая пдфка - Writing a Simple Operating System from Scratch. Кратко описано написание загрузочного сектора в 16-битном режиме, в 32-битном защищённом режиме; написание драйверов, файловой системы, создание ядра. 

Вот  гит-книжка How to Make a Computer Operating System. А вот The little book about OS development (по аналогии с "маленькими книжками" о Redis и Mongo). Разлюли-малина. Почему ж тему написания СУБД так обделили?

Thrift, Avro и Protobuf

Ссылка за ссылкой - двигаюсь по просторам Интернета, нахожу новую информацию.

В замечательном блоге eax.me нашел упоминание о книге Designing Data-Intensive Applications за авторством Мартина Клеппманна. Блоггер отозвался о книге положительно, посоветовал подписаться на журнал Мартина.

Ну а в блоге Клеппманна обнаружилась хорошая статья, где сравниваются форматы Thrift, Avro и Protobuf. Будет время - почитаю, очень хочется в этой теме разобраться.  

GDB

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

Можно почитать быстрый старт, а можно - подробную документацию.

Крамер и Маги: Concurrency

Нашел еще одну книгу по теории распределенных систем двух Джеффов: Concurrency: State models & Java programs (Jeff Magee, Jeff Kramer). По ней есть хорошая презентация Software Architecture: Modeling and Analysis, rigourous approach.   Таким образом, Джеффы подходят к вопросу с точки зрения моделирования, а не, скажем, отладки распределенных программ.

Классификации СУБД

Некто Себастьян Меньер в своем посте 2016 года привел очень хорошую, наглядную классификацию распределенных СУБД, в которую поместил в том числе и новомодный блокчейн.

А вот еще методичка по распределенным СУБД, в которой объясняется, чем отличаются между собой параллельные, сетевые и распределенные СУБД. А также есть еще масса интересной информации по распределенным СУБД.

Почему стоит писать СУБД?

Я уже упоминал статью Тома Кроули "Never Write Your Own Database". Так почему не стоит писать СУБД? А просто потому, что это очень сложное ПО, достаточно взглянуть на схему в моем предыдущем посте.

А почему, тем не менее, так много новых СУБД?  Во-первых, в "больших" СУБД масса возможностей, которые многим пользователям не нужны ("Wow, there’s a lot of stuff there that I don’t need. I wonder what I’m paying for that?"). Поэтому новая СУБД, в которой меньше лишнего, может оказаться востребованной. А во-вторых, СУБД, заточенная под какую-то конкретную задачу оказывается эффективней (в своей области), чем СУБД общего назначения.

Архитектура реляционной СУБД

О внутреннем устройстве СУБД информации не так уж и много. Но вот обнаружилась замечательная статья "Architecture of a Database System", где обозначен недостаток структурированных текстов на эту тему ("for a number of reasons, the lessons of database systems architecture are not as broadly known as they should be") и предпринята попытка дать развернутое описание темы. Один из авторов, кстати, - Майкл Стоунбрейкер, спец по эксплуатации БД на многопроцессорных машинах.

Статья большая (119 стр) и подробная. Но я здесь хочу привести из неё только схему, на которой отражены основные компоненты СУБД (щёлкните, чтоб увеличить) : 

Собственно, вот. Можно отталкиваться от этой картинки - и начинать погружение в архитектуру СУБД. Помня при этом правило "никогда не пишите свою СУБД".

Как написать свою СУБД?

Именно такой запрос я вбил в Гугл - "how to write a simple database program". И нашёл не так уж много информации.

В статье на Quora просто описали схему. Парсер разбирает запрос, создает дерево на основе реляционной алгебры. Далее при обработке запроса это дерево нужно будет рекурсивно обойти. Для ускорения поиска по БД нужны индексы. Для реализации индексов чаще всего используют хэш-таблицы и деревья. Существуют статические индексы, которые не меняются при добавлении/удалении/модификации данных (примеры - StaticHash и ISAM),

а также динамические, которые, соответственно, меняются при упомянутых операциях (примеры - DynamicHash и B-деревья).

В обсуждении на Stackexchange советуют учить матчасть, изучать исходный код открытых СУБД (таких как redis, flockdb и RavenDB), а также дают ссылки на книжки.

А потом оказалось, что среди разработчиков есть пословица (adage), которая звучит так "never write your own database". Именно такое название дал некто Терри Кроули своей статье. И объяснил, почему при работе над OneNote он с соратниками это правило нарушил.  Терри говорит:писать СУБД - дело крайне непростое, почитайте, говорит, хотя бы статью в Вики про ESENT.  Но если говорить об эффективности.... 

Кстати, а не почитать ли про ESENT?

Распределенные системы - схематично

Нашел  статью на tech.willhaben.at,  где хорошо выделили некоторые моменты теории распределенных систем. Приведу здесь эту информацию тезисно.

Две важные задачи для любой распределенной среды - выбор лидера и автоматическая отказоустойчивость.

Распределенная система может создаваться по разным причинам:

1. балансировка нагрузки
2. горячее резервирование (hot standby)
3. у каждого узла может быть своя задача

Сделать архитектуру ведущий-ведомые проще, чем абсолютно распределенную (когда все  узлы равноправны). У нас могут быть пакетные задачи (batch jobs), скажем, чистка БД, которые лучше выделить для одного узла - скорее всего, это будет мастер.

Некоторые вопросы, которые возникают в такой архитектуре:

•     Как выбирать лидера?
•     Что делать, если лидер упал? (автоматич отказоустойчивость) 
•     Что будет, если лидер отключится от других сервисов?
•     Что случится, если он переподключится? 
•     Что делать, если лидер не отвечает?

 Все эти вопросы лучше не решать с нуля. В упомянутой статье рекомендуется использовать Apache Zookeeper. Это некий фреймворк, который умеет решать типовые проблемы распределенных систем. Например, именование, конфигурирование и синхронизацию сервисов (service synchronization). Кстати, а в чем состоит проблема именования? Об этом ниже.

Если коротко, Zookeper предлагает концепцию узлов. Каждому физическому узлу соотвествует узел зукипера со своим уникальным идентификатором. Как только физич узел системы отключается (или падает) - соответствующий ему узел зукипера исчезает. Таким образом, выбрать лидера очень просто - берется физич узел, которому соответствует узел зукипера с минимальным идентификатором.

Во время прочтения статьи, задался вопросом- а чем же собственно сложна проблема именования? В лекции Мохаммада Хаммуда об этом говорится довольно подробно. Плоское именование, структурированное, основанное на атрибутах и всё такое прочее..

Каузальная согласованность на сайте MariaDB

MariaDB - это ветка MySQL. 

У них на сайте нашел неплохую статью про каузальную согласованность (causal consistency). 

Итак, каузальная с. сильнее с. в конечном счете, но слабее последовательной. Суть этой модели заключается в следующем:  чтения и записи, связанные причинно-следственными отношениями, будут увидены каждым узлом в одинаковом порядке, а вот параллельные записи могут быть увидены разными узлами в разном порядке.

Когда транзакция выполняет сначала операцию чтения R, а затем операцию записи W (даже на разных объектах), эти операции оказываются связаны (т.к. значение, записанное W, м.б. создано на основе прочитанного R). Также будут связаны операция чтения и записи, если чтение произошло после записи  на том же объекте.

Кроме того, две записи, выполненные одним узлом, будут связаны. Ведь записав значение v в объект x узел будет знать, что чтение x даст v, поэтому более поздняя запись будет (потенциально) зависеть от более раннего.

  

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

Векторные часы описываются так. Каждый узел хранит вектор длины N , где N - число узлов.

Элемент с номером i содержит число, равное количеству сообщений, принятых с i-го хоста (хмм, по-моему, это расходится с классическим определением). Использование часов позволяет упорядочивать сообщения или откладывать прием сообщений.

Векторы версий. Нам нужно следить за обновлением M объектов, поэтому каждый узел хранит вектор длины M. Элемент с номером i - это количество записей в i-й объект. Когда какой-то узел обновляет   i-й объект, он увеличивает соотв элемент вектора, затем рассылает вектор и новое значение объекта всем остальным узлам. При приеме такого сообщения хост откладывает его доставку до тех пор, пока все элементы его вектора не станут больше или равны принятого вектора. Только после этого обновление применяется к объекту. Накладные расходы составляют O(M) и не зависят от количества узлов. 

В качестве приложений рассматриваются MMORPG и Facebook - но это как-нибудь потом. 

Гай о согласованности

Еще одна статья о согласованности в конечном счете - в блоге Гая Харрисона (кто это - мне неведомо).

Здесь интересно то, что сausal consistency, read your own writes, monotonic consistency рассматриваются как дополнительные опции, которые может предложить согласованность в конечном счете.

Много сказано об обозначении NRW (N копий данных, при чтении читаем с R реплик, при записи необходимо чтоб записалось как минимум на W реплик). 

Соотношение N=W означает, что пишем сразу на все реплики - это подход традиционных СУБД. Если делаем W=1 - получаем высокую производительность при записи. В этом случае стоит поставить R=N - тогда при чтении мы сможем понять, какая из копий данных верная (наиболее свежая).

В NoSQL обычно делают N>W>1. Т.е. должна произойти запись более чем на одну реплику, но не обязательно сразу писать на все. Поышение уровня согласованности в три этапа:

1. при R=1 получим, что БД считаем верной первую считанную копию данных;

2. при R>1 происходит чтение более одной копии, их можно сравнить и взять самую свежую;

3. при R+W>N у нас есть гарантия, что мы считаем хотя бы одну самую свежую копию данных (quorum assembly).  

Модели согласованности на ML Wiki

Перескажу на русском запись о консистентности в БД.

Согласованность (консистентность) в БД - это соблюдение всех ограничений (constraints). Например, в столбце Зарплата не м.б. записей в формате Дата.

Пример с банковскими счетами. Мы храним данные о счетах и общей сумме на всех счетах, обозначим ее T (от TOTAL). В любой момент времени сумма денег на всех счетах должна быть равна T. Но - в результате наших действий может возникнуть несогласованность. Мы кладем деньги на первый счет (скажем, 100 рублей). Далее обновится и T, но между обновлением первого счета и T данные будут несогласованы.

Здесь возникает понятие транзакции. Это набор действий, переводящих данные из одного согласованного состояние в другое (буква С в ACID). Но в процессе выполнения транзакции данные могут (имеют право) быть несогласованы. Соответственно, нам необходимо обновление счета и обновление T объединить в транзакцию.

Но что если в процессе транзакции произойдет сбой? Данные могут остаться в несогласованном состоянии. Избежать этого позволяют транзакционные логи СУБД, о которых тоже есть статья на ML Wiki.

В распределенных БД с согласованностью сложнее. Модели согласованности определяют правила видимости (visibility) и порядка обновлений (order of updates). 

Строгая согласованность. Все реплики видят обновления в одинаковом порядке. Любая операция чтения выдает самые свежие данные, в независимости от того, с какой реплики идет чтение. Необходим некий механизм распространения фиксаций (ommit propagation), например, двухфазная фиксация. Согласно CAP теореме невозможно достичь строгой согласованности одновременно с устойчивостью к разделению сети (partition-tolerance).

Согласованность в конечном счете (eventual consistency). Важен порядок получения обновлений. При  t→∞ все читатели увидят записи. Но обновления не атомарны, как в 

строгой согласованности.

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

HyperDex побил Mongo?

Нашел блог некоего Emin Gün Sirer. Человек занимается разработкой всякого софта (в т.ч. относящегося к биткоину), да ещё и  профессор в Корнуолльском университете.

Так вот, у него есть пост под названием On the Futility of Custom Consistency Models. Futility, кстати, переводится как тщетность. В посте Эмин пнул ученых, которые выдумывают разные модели согласованности и пишут про БигДату, приводя примеры структур данных длиной в байт.

Досталось и Монге. Она, оказывается, теряет данные. Из-за того, что жертвует согласованностью в угоду производительности. А вот детище Эмина HyperDex предлагает строгую согласованность (сериализуемые ACID транзакции) при скорости втрое выше, чем Монга. 

Увы, как отмечает сам автор, про Монгу знает куда больше людей, чем про великолепный ХиперДекс... Такова жизнь.