Привет, Хабр! Какое-то время назад люди осознали, что увеличивать мощность сервера в соответствии с ростом нагрузки просто невозможно. Тогда-то мы и узнали слово «кластер». Но как бы красиво это слово не звучало, всё равно приходится технически объединять разрозненные серверы в единое целое – тот самый кластер. По городам и весям мы добрались до наших узлов в моём предыдущем опусе. А сегодня мой рассказ пойдёт о том, как делят нагрузку между членами кластера системные интеграторы, и как это сделали мы.



Внутри публикации вас также ждёт бонус в виде трёх сертификатов на месячную подписку ivi+.

Высоконагруженные системы, построенные по модели акторов – это тренд сегодняшнего времени. Вот далеко неполный перечень статей на хабре, в которых, в той или иной степени, упоминается данная модель или одна из ее реализаций, например,1, 2, 3, 3, 4, 5, 6, 7. Есть хорошая статья в википедии, рассказывающая про акторы. К сожалению, после ее прочтения, у меня осталось много вопросов, ответы на которые я смог найти только в первоисточниках. Результаты этого обзора я и хочу представить Вашему вниманию.

Сейчас в тематических интернетах модно слово «Node.js». В этой небольшой статье мы попробуем понять («на пальцах»), откуда всё это взялось, и чем такая архитектура отличается от привычной нам архитектуры с «синхронным» и «блокирующим» вводом/выводом в коде приложения (обычный сайт на PHP + MySQL), запущенного на сервере приложений, работающем по схеме «по потоку (или процессу) на запрос» (классический Apache Web Server).

Последние несколько недель я использую все свободное время, которое могу найти, чтобы обдумать, какие технологии мы будем использовать, чтобы реализовать первую версию BankSimple. Многие люди, вероятно, предположат, что я сразу же предпочёл Scala, в связи с тем, что я был соавтором книги об этом языке, но я подхожу к решению инженерных задач совершенно иначе. Каждая проблема имеет соответствующий набор применяемых технологий, и задача разработчика, — обосновать необходимость их использования.

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

Одной из самых обсуждаемых технологий среди Hacker News является Node, окружение для разработки и запуска событийно-управляемых приложений JavaScript на виртуальной машине V8. В рамках выбора технологий для реализации проекта я выполнил оценку Node. Вчера я выразил некоторый общий скепсис относительно Node, и автор этого окружения, Райан Дал, попросил, чтобы я изложил свои мысли более подробно. Так вот, приступаю.

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

Message passing является одной из популярных концепций параллельного программирования. Она часто используется при создании сложных распределенных систем с высокой степенью параллелизма. Реализация этой концепции представлена в языках программирования в качестве актёров (actor) или агентов (agent).


Расспределенные агенты HostTracker. Быстрая проверка с http://updownchecker.com

Питон изумителен.

Удивительно, но это довольно неоднозначное заявление. Что я имею ввиду под “Питоном”? Может, абстрактный интерфейс Питона? Или CPython, распространенная реализация Питона (не путать с похожим по названию Cython)? Или я имею ввиду что-то совсем иное? Может, я косвенно ссылаюсь на Jython, или IronPython, или PyPy. Или может я отвлекся так сильно, что говорю о RPython или RubyPython (которые очень сильно отличаются).

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

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

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

Все начинается с понимания того, чем на самом деле является “Питон”.

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

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

Все примеры приведены на Java, но содержат комментарии и я надеюсь будут понятны программистам не знакомым c Java. Данная статья носит обзорный характер и не претендует на полноту. В то же время она наполнена ссылками, которые дают более подробное объяснение терминам и утверждениям.

Сегодня мы предлагаем вашему вниманию очередную публикацию в рамках постоянной рубрики «Лекции Техносферы». В этот раз вы можете изучить материалы по курсу «Методы использования СУБД в интернет-приложениях». Цель курса — изучение топологии, многообразия и основных принципов функционирования систем хранения данных, а также алгоритмов, заложенных в основу как централизованных, так и распределённых систем, демонстрация фундаментальных компромиссов присущих тем или иным решениям. Преподаватели курса: Константин Осипов kostja, Евгений Блих bigbes, Роман Цисык.

Взаимодействие с системами, которые реагируют на запросы пользователя быстро (в течение 100 мс), ощущается тем же пользователем, как более плавное и естественное, чем взаимодействие с системами, которые реагируют долго. Развитие Интернета и возникновение датацентр-масштабных вычислительных систем (warehouse-scale computing systems) дало возможность появлению появлению веб-сервисов, обладающих высокой скоростью реакции и в тоже время, обрабатывающих терабайтные массивы данных, расположенные на тысячах серверов. Например, поисковая система Google обновляет результаты выдачи в ответ запроса одновременно с тем, как пользователь печатает, при этом система предсказывает наиболее вероятный запрос, основываясь на напечатанном префиксе, и осуществляет поиск и отображение результатов за десятки милисекунд. Устройствам дополненной реальности (таким как, например, Google Glass), которые только-только начали выходить на рынок, понадобятся веб-сервисы с еще более высокой скоростью реакции, дабы гарантировать естественность взаимодействия.

Девять лет назад я начал «в свободное от основной работы время» преподавать компьютерные дисциплины в одном из университетов Санкт-Петербурга. И только сравнительно недавно к своему удивлению обнаружил, что в наших вузах практически отсутствуют курсы с фокусом на проблематику распределённых вычислений. И даже на Хабре эта тема не раскрыта в достаточной мере! Надо прямо сейчас исправлять ситуацию.

Этой теме я и хотел посвятить статью или даже серию статей. Но потом решил выложить своё учебное пособие по основам распределённых вычислений, вышедшее в свет в этом году (читай, небольшую книгу объемом 155 страниц). В итоге получился гибрид – статья со ссылкой на книгу. Книга распространяется бесплатно и доступна в электронном виде.

Вместо пролога. Приступив к тексту статьи, я в очередной раз задумался, а зачем программисту нужно знать теоретические основы распределённых вычислений. Этот вопрос я неоднократно слышал (и продолжаю слышать) от студентов и специалистов, уже работающих в области ИТ. Действительно, зачем, например, знать, что «множество событий распределённого вычисления упорядочено частично, а не линейно»? В чем, так сказать, каждодневная практическая польза этого фундаментального знания?

Должен признать, что у меня нет готового заученного ответа, который я могу выдать не задумываясь. Поэтому каждый раз приходится напрягаться извилинами, и каждый раз ответы и аргументы получаются разными. Вот и сейчас всё как впервые…

Предлагаю читателям «Хабрахабра» перевод статьи «16 Months of Functional Programming». Все мои замечания будут выделены курсивом.

В этой статье я хочу поделиться с вами моим опытом в функциональном программировании. Я чувствую, что в целом за прошедшие 16 месяцев стал лучше разбираться в информатике и компьютерах, чем за предыдущие 10 лет и всё это благодаря моему погружению в Scala и мир функционального программирования. Причина по которой функциональное программирование побуждает вас к постоянному развитию заключается в том, что каждую задачу необходимо переосмысливать заново. Порой невозможно поверить в то, что большинство стандартных задач могут быть решены иным путём и — бум! — функциональный подход предлагает лучшее решение и это шокирует.

Cтэнфордский курс CS183B: How to start a startup. Стартовал в 2012 году под руководством Питера Тиля. Осенью 2014 года прошла новая серия лекций ведущих предпринимателей и экспертов Y Combinator:

Я совсем не долго изучаю и использую git практически везде, где только можно. Однако, за это время я успел многому научиться и хочу поделиться своим опытом с сообществом.

Я постараюсь донести основные идеи, показать как эта VCS помогает разрабатывать проект. Надеюсь, что после прочтения вы сможете ответить на вопросы:

• можно ли git «подстроить» под тот процесс разработки, который мне нужен?
• будет ли менеджер и заказчик удовлетворён этим процессом?
• будет ли легко работать разработчикам?
• смогут ли новички быстро включиться в процесс?
• можно ли процесс относительно легко и быстро изменить?

Конечно, я попытаюсь рассказать обо всём по-порядку, начиная с основ. Поэтому, эта статья будет крайне полезна тем, кто только начинает или хочет разобраться с git. Более опытные читатели, возможно, найдут для себя что-то новое, укажут на ошибки или поделятся советом.

Тим Петерс разработал гибридный алгоритм сортировки Timsort в 2002 году. Алгоритм представляет собой искусную комбинацию идей сортировки слиянием и сортировки вставками и заточен на эффективную работу с реальными данными. Впервые Timsort был разработан для Python, но затем Джошуа Блох (создатель коллекций Java, именно он, кстати, отметил, что большинство алгоритмов двоичного поиска содержит ошибку) портировал его на Java (методы java.util.Collections.sort и java.util.Arrays.sort). Сегодня Timsort является стандартным алгоритмом сортировки в Android SDK, Oracle JDK и OpenJDK. Учитывая популярность этих платформ, можно сделать вывод, что счёт компьютеров, облачных сервисов и мобильных устройств, использующих Timsort для сортировки, идёт на миллиарды.

Но вернёмся в 2015-й год. После того как мы успешно верифицировали Java-реализации сортировки подсчётом и поразрядной сортировки (J. Autom. Reasoning 53(2), 129-139) нашим инструментом формальной верификации под названием KeY, мы искали новый объект для изучения. Timsort казался подходящей кандидатурой, потому что он довольно сложный и широко используется. К сожалению, мы не смогли доказать его корректность. Причина этого при детальном рассмотрении оказалась проста: в реализации Timsort есть баг. Наши теоретические исследования указали нам, где искать ошибку (любопытно, что ошибка была уже в питоновской реализации). В данной статье рассказывается, как мы этого добились.

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

Классика

Самый обычный код.

    $size = sizeof($arr)-1;
    for ($i = $size; $i>=0; $i--) {
        for ($j = 0; $j<=($i-1); $j++)
            if ($arr[$j]>$arr[$j+1]) {
                $k = $arr[$j];
                $arr[$j] = $arr[$j+1];
                $arr[$j+1] = $k;
            }
    }

Барокко

Барокко (итал. barocco — «причудливый», «странный», «склонный к излишествам»)
Барокко свойственны контрастность, напряженность, стремление к величию и пышности как в именовании, так и в комментариях, к слиянию разных стилей кодирования. Обычно уже на продакшене обнаруживаются скрытые «детонаторы».

Чаще всего используется в: JavaScript, C++, Java.

    $SIZE = SIZEof($A_R__R)-1;
    for ($i = $SIZE; $i>=0; $i--) {
        for ($j = 0; $j<=($i-1); $j++)
            if ($A_R__R[$j]>$A_R__R[$j+1]) {
                //используем хитрый манёвр
                $A_R__R[$j+1]  = $A_R__R[$j];  + $A_R__R[$j+1];
                $A_R__R[$j]    = $A_R__R[$j+1] - $A_R__R[$j];
                $A_R__R[$j+1]  = $A_R__R[$j+1] - $A_R__R[$j];

            }
    }

Потоки ввода-вывода в стандартной библиотеке C++ просты в использовании, типобезопасны, устойчивы к утечке ресурсов, и позволяют простую обработку ошибок. Однако, за ними закрепилась репутация «медленных». Этому есть несколько причин, таких как широкое использование динамической аллокации и виртуальных функций. Вообще, потоки — одна из самых древних частей стандартной библиотеки (они начали использоваться примерно в 1988 году), и многие решения в них сейчас воспринимаются как «спорные». Тем не менее, они широко используются, особенно когда надо написать какую-то простую программу, работающую с текстовыми данными.

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

Сегодня в комментариях у посту возникло обсуждение о медленности iostreams. В частности, freopen пишет

Забавно смотреть на ваши оптимизации, расположенные по соседству со считыванием через cin :)

а aesamson даёт такую рекомендацию

Можно заменить на getchar_unlocked() для *nix или getchar() для всех остальных.
getchar_unlocked > getchar > scanf > cin, где ">" означает быстрее.

В этом посте я развею и подтвержу некоторые мифы и дам пару рекомендаций.

Довольно часто в программе, работающей с базой данных, в качестве идентификаторов сущностей используются значения целочисленного типа (например, long). Но людям свойственно ошибаться, и программист может по ошибке использовать идентификатор одного типа сущности для адресации другой. Такая проблема может долго оставаться незамеченной, если идентификаторы сущностей пересекаются, а такое бывает довольно часто. К счастью, в языках, позволяющих манипулировать типами, коим является C++, есть довольно простое решение этой проблемы.

Это первый пост из блога Surfingbird, который я выношу в общие хабы алгоритмов и искусственного интеллекта; честно говоря, раньше просто не догадался. Если интересно, заходите к нам, чтобы прочесть предыдущие тексты, – я не знаю, что произойдёт, если просто добавить новые хабы к постам несколькомесячной давности.

Краткое содержание предыдущих серий о рекомендательных системах:

• рекомендательные системы: постановка задачи;
• user-based и item-based коллаборативная фильтрация;
• SVD, часть I;
• SVD и базовые предикторы;
• SVD на Perl;
• оверфиттинг и регуляризация;
• теорема Байеса и наивный Байес;
• LDA (Latent Dirichlet allocation, тематическое моделирование).

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

Задача: в массиве длиной N найти элемент, который повторяется больше N/2 раз.

Казалось бы, чего тут думать? Возьмём Dictionary<значение элемента, число появлений>, за один проход по массиву сосчитаем появления каждого элемента, потом выберем из словаря искомый элемент. Решение за O(N), куда может быть ещё быстрее?

Есть один нюанс: для словаря нам потребуется O(N) дополнительной памяти — в несколько раз больше размера исходного массива, и это при реализации словаря хоть хэш-таблицей, хоть деревом. Что будем делать, если наша цель — обработка сигнала неким устройством с маленькой памятью? Массив — замеры уровня сигнала, из которых один — «настоящий» передаваемый уровень, а остальные — шум и помехи. Неужели придётся для определения «настоящего» уровня возиться с хэш-таблицами и деревьями?

К счастью, нет: достаточно O(1) дополнительной памяти, и по-прежнему одного прохода по массиву.

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

Ниже представлен «проект NULL», тот самый костяк, с которого обычно все и начинается. У меня.

Данный пост скорее всего не будет интересен тем кто уже матерый и тем кто на прямую не связан с разработкой на С++, т.к. ниже представленные материл несет одну единственную цель — дать готовый фундамент для начала.