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

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

В первой своей статье «измерение расстояния до объекта и его скорости» я рассмотрел захват изображений с веб-камер через Video4Linux2 и через DirectX. В следующей статье «захват видео с сетевых камер, часть 1» я рассмотрел как работать с сетевыми Motion-JPEG камерами. Сейчас я поведаю Вам о захвате изображений с сетевых RTSP камер, в частности поток Motion-JPEG по RTSP.

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

Обзор практически всех *top утилит под linux (atop, iotop, htop, foobartop и т.д.).

top

Все мы знаем top — самую простую и самую распространённую утилиту из этого списка. Показывает примерно то же, что утилита vmstat, плюс рейтинг процессов по потреблению памяти или процессора. Совсем ничего не знает про загрузку сети или дисков. Позволяет минимальный набор операций с процессом: renice, kill (в смысле отправки сигнала, убийство — частный случай). По имени top суффикс "-top" получили и все остальные подобные утилиты в этом обзоре.

atop

Atop имеет два режима работы — сбор статистики и наблюдение за системой в реальном времени. В режиме сбора статистики atop запускается как демон и раз в N времени (обычно 10 мин) скидывает состояние в двоичный журнал. Потом по этому журналу atop'ом же (ключ -r и имя лог-файла) можно бегать вперёд-назад кнопками T и t, наблюдая показания atop'а с усреднением за 10 минут в любой интересный момент времени.

В отличие от top отлично знает про существование блочных устройств и сетевых интерфейса, способен показывать их загрузку в процентах (на 10G, правда, процентов не получается, но хотя бы показывается количество мегабит).

Незаменимое средство для поиска источников лагов на сервере, так как сохраняет не только статистику загрузки системы, но и показатели каждого процесса — то есть «долистав» до нужного момента времени можно увидеть, кто этот счастливый момент с LA > 30 создал. И что именно было причиной — IO программ, своп (нехватка памяти), процесор или что-то ещё. Помимо большего количества информации ещё способен двумя цветами подсказывать, какие параметры выходят за разумные пределы.

Аннотация

В данной статье читателю предлагается опыт разработки алгоритма сжатия изображения, хранящегося в формате PNG. Сжатие осуществляется за счет квантования палитры с использованием классификатора К–внутригрупповых средних. Приводится исходный код алгоритма, написанный на языке Java. Указываются проблемы и дальнейшие пути улучшения алгоритма.

У меня для вас есть хорошая новость. Кажется, я сегодня уломал отцов Kerrighed дебианизировать свои труды.

Что это означает для нас, для обычных людей? У вас есть компьютер, где стоит Ubuntu или ещё какой-то Дебиан-подобный Linux? Назовём его Компьютер №1. На нём вы сможете сделать что-то обычное, типа

apt-get install kerrighed-kernel...

ну, вероятно, придётся уж потратить и пару минут на конфигурацию. Далее, перезагрузив Ubuntu, вы увидите новоиспечённое ядро в grub-меню. Выбираете и попадаете в обычную Ubuntu с одним необычным свойством, назовём его "SSI with DRBL"…

Что за зверь «SSI with DRBL»?

В последнее время веб-разработка из наколенного поделия превратилась в серьезную инженерную дисциплину. Все это стало возможным стараниями легиона специалистов, которые разработали общие практики, которые позволяют писать веб-проекты, с использованием некой архитектуры, а не подобно исследователю, сбрасывающему ящик типографского шрифта с крыши небоскреба, в надежде, что тот чудесным образом сложится в первый том «Войны и Мира». Самой распространенной парадигмой веб-программирования является, вне всякого сомнения, MVC — Model-View-Controller. Говоря примитивно, эта парадигма предусматривает разделение кода приложения на слой управления (Controller), слой представления (View) и слой управления данными (Model). При этом MVC предусматривает, что Controller и View могут (но не обязаны) зависеть от Model, в то время как Model ни при каких условиях не должен зависеть от них.
Есть много различных подходов, как отделить бизнес-логику приложения от логики отображения и управления. Все они предусматривают, что модель является частью приложения и взаимодействует с БД, использую последнюю лишь в качестве хранилища данных. Мы же попытаемся пойти иным путем и по возможности максимально вынести бизнес-логику приложения на уровень БД.
Предупреждение: лицам с тонкой душевной организацией лучше не видеть того, что будет твориться под катом.

Серию официальных постов в блоге компании про то, как работать с облаком я ещё продолжу, но параллельно мне хочется рассказать про те проблемы, с которыми мы столкнулись во время адаптации Xen Cloud Platform под нашу модель работы облака. Эти посты будут чуток сложнее и предполагают, что читатель хотя бы в общих чертах знает, как работает Xen.

Когда концепция «оплата по потреблению» только-только оформлялась, а я судорожно искал «как считать», мне казалось, что процессор и память — это два самых простых ресурса.

Действительно, у нас есть xencontrol (библиотека управления гипервизором Xen), которая может точно сказать про каждый домен (запущенную виртуальную машину), сколько у неё есть памяти, сколько наносекунд времени было потрачено. Эта библиотека запрашивает информацию напрямую (через xenbus) у гипервизора и подвергает её минимальной обработке.

Выглядит эта информация примерно так (вывод биндинга xencontrol для питона):

{
    'paused': 0, 
    'cpu_time': 1038829778010L, 
    'ssidref': 0, 
    'hvm': 0, 
    'shutdown_reason': 0, 
    'dying': 0, 
    'mem_kb': 262144L, 
    'domid': 3, 
    'max_vcpu_id': 7, 
    'crashed': 0, 
    'running': 0, 
    'maxmem_kb': 943684L, 
    'shutdown': 0, 
    'online_vcpus': 8, 
    'handle': [148, 37, 12, 110, 141, 24, 149, 226, 8, 104, 198, 5, 239, 16, 20, 25], 
    'blocked': 1
}

Как мы видим, есть поле mem_kb, соответствующее выделенной памяти для виртуальной машины и есть поле cpu_time, содержащее какое-то умопомрачительное число (хотя на самом деле это всего лишь 17 минут). cpu_time считает с точностью до наносекунд (точнее, величина, которая тут хранится считается в наносекундах, реальная точность около микросекунды). Память, как понятно, в килобайтах (хотя внутренней единицей учёта, что гипервизора, что ядра линукс является страница — её размер по-умолчанию 4 килобайта).

Казалось бы «бери и считай», однако, дьявол кроется в деталях…

Извините за жёлтый заголовок ниже, но именно так звучал вопрос в полемике в ходе обсуждения одной из проблем:

Hyper-threading + Xen = воровство денег у клиентов

IP-телефонией уже никого не удивишь, многие пользуются услугами Skype, SipNet, TelMe и многих, многих других. Объединив усилия с единомышленниками, решили не повторять существующие решения, а создать сервис для интеграции уже существующих провайдеров Интернет-телефонии.
Зачем? Основная задача нашего сервиса – собрать воедино всех провайдеров, и дать возможность использовать одновременно разные шлюзы по самым выгодным тарифам на данное время и по данному направлению.

В топике я расскажу о том, было за «кулисами»: о выбранной архитектуре, приятных решениях и инструментариях разработки. А самых любознательных хабраюзеров ждет небольшой подарок.

Поделюсь одним случаем из телекоммуникационной практики.
У нас стоит циска 26-й серии (2620XM). На ней заведено около четырёх десятков сабинтерфейсов. Большинство для локальных абонентов, расположенных в том же здании, и есть несколько линков на дальние точки. Среди них аэропорт, кирпичный завод, горнолыжный комплекс, совхоз. «Да это ж старьё непотребное» — скажете вы и будете правы, но так исторически сложилось. Однако суть не в этом.
И вот некоторое время назад оказалось что нагрузка слишком высока. Сначала это проявлялось в некоторых задержках при работе в консоли. Типа набираешь команду, а буквы появляются не сразу а немного с задержкой. Потом периодически стал увеличиваться пинг до циски с удалённых точек. Следующий симптом — иногда отваливающийся канал в интернет (при этом маршрутизация внутри локальной сети работала безупречно и потерь не было). А в логах тем временем жуткая картина о сильно активном использовании CPU. Загрузка процессора не опускается ниже 80%, а большую часть времени 95-99%. Теперь пинг стал теряться даже если ты находишься в той же подсети. Интернет захромал на обе ноги.

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

Для начала:
NAT (от англ. Network Address Translation — «преобразование сетевых адресов») — это механизм в сетях TCP/IP, позволяющий преобразовывать IP-адреса транзитных пакетов. Также имеет названия IP Masquerading, Network Masquerading и Native Address Translation.

Рассмотренные варианты:
— Демон Natd
— IPFilter (ipnat)
— PF nat
— ng_nat
— ipfw nat (kernel nat)

Очень часто необходимо реализовать простое легкое решение, которое должно отработать довольно быстро. А с использованием технологии AJAX это стало еще актуальнее. Это может быть как скрипт автокомплита, скрипт специфического поиска, вывод информации из справочника. Ранее использовались cgi скрипты. При больших нагрузках они оказались не очень эффективными и были разработаны протоколы fcgi и scgi. Следует заметить что производительность scgi сервера довольно-таки высокоя (более 1500 запр/сек) и памяти занимает всего 600K.

Протокол Simple Common Gateway Interface (SCGI) — это протокол по взаимодействию приложений с веб (http) серверами. Большинство современных WEB-серверов (Apache/nginx/lighttpd) имеют встроенную поддержку scgi. Ниже дано краткое описание использование простой библиотечки, которая представляет собой scgi сервер.

Исходники тут.

Вступление

В статье будет рассказано о том, как в кратчайшие сроки познакомиться с основами скриптинга в GIMP на языке Scheme и приступить непосредственно к решению простых практических задач. Данный материал предназначен лишь для тех, кто собирается автоматизировать рутинную обработку здесь и сейчас, не сильно вдаваясь в тонкости и не жертвуя драгоценным временем. Также, статью не рекомендуется использовать в качестве пособия по Scheme отдельно от Script-fu. Связано это с упрощённым стилем программирования в данном материале и отсутствием освещения других немаловажных фактов, которые нас сейчас волнуют гораздо меньше, чем скорость освоения.

Содержание:

1. Что нам понадобится?
2. Коротко о синтаксисе
3. Переменные
4. Функции
5. Списки
6. Регистрация скрипта в GIMP
7. Написание кода
8. Заключение

Чем можно заниматься в 0 часов 0 минут в Москве? Сидеть за праздничным столом и праздновать? Как бы не так. В этот праздничный миг я хочу поделиться с вами моими сегодняшними изысканиями по тюнингу производительности софтрейда в домашнем сервере. Можно пропустить теорию и сразу читать последний абзац где основная соль.

Почему RAID-6?

Как известно, RAID-5 выдерживает смерть одного веника, и после этой самой смерти – до момента когда закончится восстановление рейда с новым винчестером ваши данные под угрозой – восстановление обычно занимало до 70 часов для больших массивов и еще один веник может легко умереть в это время.
RAID-6 выдерживает смерть 2-х любых веников. Из минусов – общепризнанное мнение что тормозит, особенно запись, даже по сравнению с RAID-5. Что-ж, проверим.

По информации Дэна Гудина, американское зеркало офсайта Касперского в течение трёх с половиной часов в воскресенье занималось распространением вирусов. Причиной этого был взлом неизвестными хакерами.

В рамках проекта для одного из наших заказчиков в очередной раз встала задача построить систему конвертации/ хранения/ доставки видео в интернет. Типичная такая задача создания своего маленького (или не очень маленького) “Тьюба” только с профессиональным, а не UGC-контентом.

С момента создания первых “Тьюбов” технологии видео в интернете прошли некоторый путь развития, позволяют сейчас делать намного больше, да и требования к современному видео-сайту стали несколько иными.

Наиболее интересными трендами последнего времени, на наш взгляд, являются:

• возможность смотреть один видео-сайт с разных устройств,
• технология адаптивного HTTP стриминга

«Однажды, в студёную зимнюю пору,
Залили на сервер бэкдорчиков гору...»

Народное админское творчество



Вобщем как то раз на одном из серверов обнаружился php-shell, через который злобные хакеры поломали уютный дневничок™ хорошего человека.
После двухчасового ковыряния в логах Апача нашлась дыра, через которую залили шелл.
Дыру прикрыли, дневничок вернули к жизни из бэкапов, и сели думу думать.

Имею на администрировании несколько серверов, на которых хостятся восновном свои проекты, но кроме них ещё довольно много пришлось разместить левых сайтов — клиентов, знакомых, знакомых знакомых и т.п. За время администрирования встречались разные проблемы, поэтому настроены кое-какие мониторинги (zabbix и самописные скрипты).

И вот вчера на одном из серверов скрипт, проверяющий активные соединения, забил тревогу: постоянно висит исходящее соединение на неизвестный хост на порт 433, уже более 9 часов на момент когда я осилил прочитать почту в понедельник утром ;)

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

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

«Основной проблемой с использованием Linux в школе оказалась не „техническая сложность при установке“, не „конечная стоимость владения“ и даже не „отсутствие ставки системного администратора“. Основной проблемой использования Linux на уроках информатики в школе стало отсутствие методический материалов с грифом Министерства Образования „Допущено в качестве учебника по информатике для учащихся общеобразовательных школ“. Но ситуация начинает меняться!

Во второй части речь пойдет об использовании цифровых транков Е1 которые можно использовать для подключения маршрутизатора к АТС

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


Роутер превращается в компьютер, если к нему по UART подключить клавиатуру и дисплей

От телеграфа к COM-порту

Протокол UART (Universal asynchronous receiver/transmitter) или, по-русски, УАПП (универсальный асинхронный приемопередатчик) — старейший и самый распространенный на сегодняшний день физический протокол передачи данных. Наиболее известен из семейства UART протокол RS-232 (в народе – COM-порт, тот самый который стоит у тебя в компе). Это, наверное, самый древний компьютерный интерфейс. Он дожил до наших дней и не потерял своей актуальности.

Надо сказать, что изначально интерфейс УАПП появился в США как средство для передачи телеграфных сообщений, и рабочих бит там было пять (как в азбуке Морзе). Для передачи использовались механические устройства. Потом появились компьютеры, и коды ASCII, которые потребовали семь бит. В начале 60-х на смену пришла всем известная 8-битная таблица ASCII, и тогда формат передачи стал занимать полноценный байт, плюс управляющие три бита.