Pull to refresh
  • by relevance
  • by date
  • by rating

Алгоритмы на графах — Часть 1: Поиск в глубину и проблема взаимоблокировок

Algorithms *
Недавно на Хабре была статья, посвященная алгоритмам на графах. С позволения автора, мой первый хабратопик продолжит цикл.

Хотелось бы осветить вопросы применения некоторых алгоритмов, для решения задач программирования.
Достаточно жизненный пример, с которым сталкивался не один разработчик — это deadlock. По сути deadlock – это взаимоблокировка, в результате которой система, или какие-то отдельные процессы начинают конкурировать за один ресурс.
В жизни такие ситуации встречаются, например, когда два человека желают пропустить друг друга на входе, предположим, в аудиторию. Однако после 3-4 фраз «только после вас!», кто-нибудь всё же пройдет первым.
На уровне программного обеспечения всё сложнее, пока программы не способны думать, машинный аналог фразы «только после вас!» будет повторяться вплоть до перезагрузки.
Как исполняющая система может повлиять на этот процесс? Вот тут нам на помощь и приходят алгоритмы на графах.
Для начала определимся, что же будет элементами нашего графа, и как его составить.
Читать дальше →
Total votes 61: ↑50 and ↓11 +39
Views 62K
Comments 20

Отчет о DeadLock'ах в работающем приложении

Java *
Привет тебе хабражитель!
В данной статье, точнее примере я хочу показать как можно получить информацию о залоченных потоках Вашего многопоточного java приложения. Под катом будет представлен пример простейшей ситтуации DeadLock'а, а также способы получения информации о нем.
Под кат
Total votes 32: ↑28 and ↓4 +24
Views 3.8K
Comments 10

Немного про Deadlock

MySQL *SQL *
Recovery mode
Это совсем краткий пост о причинах возникновения Deadlock

В более менее нагруженных проектах, использующих транзакции InnoDB, в любой момент может возникнуть ошибка вида

«Deadlock found when trying to get lock; try restarting transaction»

Главное не паниковать при виде этих страшных слов, сейчас мы разберемся почему это происходит.
Читать дальше →
Total votes 31: ↑29 and ↓2 +27
Views 105K
Comments 50

Боремся с deadlock-ами: паттерн unlocked callbacks

Нордавинд corporate blog Designing and refactoring *

Ситуации взаимной блокировки


В Википедии дается следующее определение взаимной блокировки: «Взаимная блокировка (англ. deadlock) — ситуация в многозадачной среде или СУБД, при которой несколько процессов находятся в состоянии бесконечного ожидания ресурсов, занятых самими этими процессами».

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

Классический пример взаимной блокировки: первый поток (A) захватывает мьютекс M1 и следом мьютекс M2. Второй поток (B) захватывает мьютекс M2, а уже после этого – мьютекс M1. Взаимная блокировка этих двух потоков может произойти следующим образом: поток A захватывает M1, поток B захватывает M2, после этого оба потока «обречены»: ни поток A не может захватить M2, ни поток B не может захватить M1; попытки захвата мьютексов заблокируют оба потока.

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

Данная ситуация очень распространена в сложных многопоточных системах. Как правило, мьютексы-участники расположены далеко друг от друга (в различных компонентах системы), и выявить участников взаимной блокировки оказывается достаточно сложно.
Читать дальше →
Total votes 11: ↑5 and ↓6 -1
Views 12K
Comments 15

Класс дедлоков про дедлок классов

Одноклассники corporate blog Java *


Знаете ли вы, как избежать дедлоков в своей программе? Да, этому учат, про это спрашивают на собеседованиях… И тем не менее, взаимные блокировки встречаются даже в популярных проектах серьёзных компаний вроде Google. А в Java есть особый класс дедлоков, связанный с инициализацией классов, простите за каламбур. Такие ошибки легко допустить, но трудно поймать, тем более, что сама виртуальная машина вводит программиста в заблуждение.

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

Читать дальше →
Total votes 45: ↑45 and ↓0 +45
Views 36K
Comments 16

Типичные взаимные блокировки в MS SQL и способы борьбы с ними

Mindbox corporate blog Programming *SQL *Designing and refactoring *Microsoft SQL Server *
Чаще всего deadlock описывают примерно следующим образом:
Процесс 1 блокирует ресурс А.
Процесс 2 блокирует ресурс Б.
Процесс 1 пытается получить доступ к ресурсу Б.
Процесс 2 пытается получить доступ к ресурсу А.
В итоге один из процессов должен быть прерван, чтобы другой мог продолжить выполнение.
Но это простейший вариант взаимной блокировки, в реальности приходится сталкиваться с более сложными случаями. В этой статье мы расскажем с какими взаимными блокировками в MS SQL нам приходилось встречаться и как мы с ними боремся.


Читать дальше →
Total votes 20: ↑20 and ↓0 +20
Views 89K
Comments 18

Мы делили ООО

Зарцын и партнеры corporate blog Legislation in IT
Tutorial
По заявкам телезрителей мы продолжаем тему уставного капитала и говорим о долях в нем. Действия учредителей, если один из фаундеров решил выйти из компании, или, более того, что делать, если он из состава учредителей выходить не хочет. Расскажем обо всем на примерах (все персонажи вымышлены).

Читать дальше →
Total votes 11: ↑6 and ↓5 +1
Views 10K
Comments 11

Как мы ловим Deadlock`и на PostgreSQL и чиним их

Wargaming corporate blog Python *PostgreSQL *

Предисловие


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

Всё это неизбежно приводит к дедлокам. Так вот, хочу вам поведать историю о том, как мы эти периодические проблемы держим в допустимых рамках.


Читать дальше →
Total votes 35: ↑32 and ↓3 +29
Views 42K
Comments 27

Тестирование параллельных процессов

IT systems testing *PHP *Programming *SQL *Concurrent computing *
image

Вы встречались с ошибками, которые возникают время от времени в продакшне, но никак не воспроизводятся локально? Бывает, изучаешь такой баг и вдруг понимаешь, что он проявляется только при одновременном параллельном выполнении скриптов. Изучив код, понимаешь как это исправить, чтобы такого больше не повторялось. Но на такое исправление хорошо бы написать тест…

В статье я расскажу о своем подходе к тестированию таких ситуаций. А также приведу несколько наглядных (и наверное даже классических) примеров багов, которые удобно протестировать с помощью этого подхода. Все примеры багов живые — то, что встречается в работе.

Забегая вперед сразу скажу, что в конце статьи будет ссылка на github, куда я выложил готовое решение, позволяющее тестировать параллельные консольные процессы легко и просто.
Читать дальше →
Total votes 16: ↑15 and ↓1 +14
Views 9K
Comments 12

Доклады с прошедшей JiraMania: про обновления, зависимости и дедлоки

ЮMoney corporate blog System administration *IT Infrastructure *Server optimization *DevOps *


В августе Яндекс.Деньги провели митап Jiramania. На нем разработчики и администраторы рассказали про отмычки и ноу-хау по работе с Jira.


Помимо неспешных бесед за кофе и круассанами, Гончик Цымжитов из ITIVITI поделился перцовыми пластырями от боли обновления Jira. После чего на сцену вышел Вадим Гаузяк из СберТеха с результатами своего исследования дедлока в agile-плагине Jira 7.


Но хватит интриг — под катом вы найдете оба доклада.

Total votes 6: ↑6 and ↓0 +6
Views 2.5K
Comments 1

Concurrency и паттерны ошибок, скрытые в коде: Deadlock

Programming *
Наверняка, многие слышали, а кто-то встречал на практике, такие слова, как взаимные блокировки(deadlock) и гонки(race condition). Эти понятия относятся к разряду ошибок в использовании concurrency. Если я задам вам вопрос, что такое дедлок, вы с большой вероятностью без доли сомнения начнете рисовать классическую картинку дедлока или его представление в псевдокоде. Что-то вроде этого:



Эту информацию мы получаем в институте, можно найти в книжках и статьях на просторах интернета. Такой дедлок с использованием, например, двух мьютексов, во всей своей красе можно встретить в коде. Но в большинстве случаев не все так просто, и не каждый может увидеть классический паттерн ошибки в коде, если он представлен не в привычном виде.
Читать дальше →
Total votes 21: ↑21 and ↓0 +21
Views 9.2K
Comments 2

Борем deadlock при пакетных UPDATE

Тензор corporate blog High performance *PostgreSQL *SQL *Database Administration *

Однажды при выполнении достаточно тривиального запроса:

UPDATE tbl SET val = val + 1 WHERE id IN (1, 2, 3)

... вы получаете ошибку ERROR: deadlock detected

Но почему? Ведь еще вчера все успешно работало!

И что с этим теперь делать? Давайте разбираться.

Читать далее
Total votes 27: ↑26 and ↓1 +25
Views 5.8K
Comments 12

Безопасная многопоточность в Rust

OTUS corporate blog Programming *Designing and refactoring *Rust *

Представьте ситуацию: вы решили добавить функционал в некоторую сущность (класс, структуру, ...). Для этого вам понадобилось хранить внутри сущности дополнительные данные. Вы добавляете приватные поля, меняете и читаете их внутри методов, интерфейс методов не изменяется, и всё выглядит хорошо. И не просто выглядит, а компилируется, запускается и проходит тесты. Красота... А потом, в один прекрасный день, прод падает. И может быть даже, теряет часть важных данных. Вы с коллегами начинаете искать причину поломки. И оказывается, что та сущность, которую вы дополняли год назад, делится между несколькими потоками, а поля добавленные вами не потокобезопасны и поэтому гонка за доступ к ним в какой-то момент вызывает их повреждение. Неприятно, согласитесь? Хотелось бы иметь инструмент, позволяющий избегать подобных ситуаций. И язык программирования Rust такой инструмент предоставляет.

Читать далее
Total votes 49: ↑46 and ↓3 +43
Views 9K
Comments 3

Взаимное автоматическое распечатывание двух Vault кластеров в Kubernetes

Nixys corporate blog System administration *IT Infrastructure *IT Standards *DevOps *
Translation

Введение


Когда я устанавливаю Vault в Kubernetes, я держу в голове, что очень важно иметь возможность сделать автоматическое распечатывание(Auto-Unseal), чтобы кластер Vault был по настоящему высокодоступным.


В моей предыдущей статье "Highly available Vault cluster in Kubernetes" (ссылка), несмотря на то, что я изо всех сил пытался сделать кластер Vault максимально доступным, без автоматического распечатывания кластер Vault мог бы выдержать частичный отказ подов, но не пережил бы перезагрузку всего кластера.


В этой статье хорошо объяснено, почему это произошло. Для меня проблема заключается в том, что я не пользуюсь "службой AWS KMS", которую можно было бы использовать, или подобной службы безопасности от "облачного" провайдера, потому что я управляю Kubernetes на self-hosted "облаке" (в этой статье объясняется моя настройка).


В Vault версии 1.1 добавлена поддержка "Transit Auto Unseal", которая заключается в использовании второго Vault кластера B для автоматического распечатывания (Auto-Unseal) кластера А.


Итак, вот идея: развернуть 2 кластера Vault A и B и настроить их так, чтобы они делали автоматическое распечатывание друг для друга.

Читать дальше →
Total votes 4: ↑4 and ↓0 +4
Views 1.5K
Comments 1