Попытайтесь повторить это сами

Как правило, настроенный должным образом сервер Nginx на Linux, может обрабатывать 500,000 — 600,000 запросов в секунду. Но этот показатель можно весьма ощутимо увеличить. Хотел бы обратить внимание на тот факт, что настройки описанные ниже, применялись в тестовой среде и, возможно, для ваших боевых серверов они не подойдут.

Минутка банальности.

yum -y install nginx

На всякий пожарный, создадим бэкап исходного конфига.

cp /etc/nginx/nginx.conf /etc/nginx/nginx.conf.orig
vim /etc/nginx/nginx.conf

А теперь можно и похимичить!

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

Всем привет.
У нас снова появилась необходимость узнать мнение пользователей Хабры по поводу издания книги «RESTful Web APIs».

Давно хотел написать этот пост с подборкой полезных ссылок, так как очень часто спрашивают подобное (думаю, у многих, кто в этой (да и в других) сфере). Ссылки разбиты на категории.

Хочу поделиться проделанной работой по исследованию производительности различных библиотек для работы с memcached в Node.JS. Для исследования были отобраны 4 кандидата.

Краткие описания взяты прямо из источников и приведены в оригинале. Вот получившийся список с версиями и ссылками.

• mc v1.0.6 — The Memcache Client for Node.js (mc)
• node-memcache v0.3.0 — A pure-JavaScript memcached library for node. (node-memcache)
• node-memcached v0.2.6 — Fully featured Memcached client for Node.js (node-memcached)
• memjs v0.8.0 — MemJS is a pure Node.js client library for using memcache. (memjs)

UPD: игра вышла.

Привет!

Тут такая история. Я заметил, что в какой-то момент стал отмечать для себя важные вещи для развития ребёнка. Например, у меня в детстве был сначала модульный конструктор с мотором, колёсами, батарейками и так далее, а потом – модульный же радиоконструктор. Эти два предмета очень сильно повлияли на то, чем я потом интересовался в будущем.

Ещё пример – в детстве надо обязательно сходить в политехнический и археологический музеи Москвы. Или, например, запомнились такие штуки: первая хорошая НФ, подаренная в 8 лет; дед, научивший меня чертёжному почерку за 15 минут; шахматы каждые выходные; огромная коробка Лего и так далее. И таких событий – тысячи.

У меня просьба. Давайте накидаем важные и интересные вещи, которые можно и нужно сделать с ребёнком до примерно 10 лет. Наверняка ведь у вас есть такие «чекпоинты», которые запомнились.

Однажды вечером я почувствовал, что пришло время расширить 97‐ й параграф «Ководства» Артемия Лебедева.

На клавиатуре одна чёрточка, она обычно правее нуля и повыше букв «З» и «Х». Неосведомлённые люди называют её попеременно то дефисом, то минусом, то тире. Лебедев объясняет нам, что это четыре (учитывая две разновидности тире) различных символа. На самом деле их как минимум девять, и об этом я и расскажу вам сейчас.

Вступление

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

Начальное описание

Алгоритм Ахо-Корасик реализует эффективный поиск всех вхождений всех строк-образцов в заданную строку. Был разработан в 1975 году Альфредом Ахо и Маргарет Корасик.
Опишем формально условие задачи. На вход поступают несколько строк pattern[i] и строка s. Наша задача — найти все возможные вхождения строк pattern[i] в s.

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

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

А мы идем далее.

Безлимит

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

Но как всегда есть одно «НО», это самое «НО» — ограничение размера БД на машине пользователя в размере 5 МБ, что отнюдь нас не устраивало. Так как данная технология планировалась использоваться в админке нашего проекта и все юзеры использовали в качестве дефолтного браузера Google Chrome, то было принято решение поиска обхода того самого ограничение через расширение-прокси. Перелопатив много инфы мы пришли к выводу, что ограничение на размер БД можно убрать использовав специальные флаги в манифесте нашего расширения:

IndexedDB – стандарт хранения больших объемов структурированных данных на клиенте – был ожидаем также как и WebSocket (ну может самую малость меньше). В свете выхода FireFox 4 я нашёл время и силы всё-таки разобраться, как им пользоваться, и попытаться написать что-то больше, чем пример с адресной книгой, гуляющий по интернетам (в процессе поиска информации у меня сложилось впечатление, что это был единственный пример).

Одной из причин слабого использования Linked Data-баз знаний в обычных, ненаучных приложениях является то, что мы не привыкли придумывать юзкейсы, видя перед собой только данные. Трудно спорить с тем, что сейчас в России производится крайне мало взаимосвязанных данных. Однако это не значит, что разработчик, создающий приложение для русскоязычной аудитории совсем уж отрезан от мира семантического веба: кое-что всё-таки у нас есть.

Основными источниками данных для нас являются международные базы знаний, включающие русскоязычный контент: DBpedia, Freebase и Wikidata. В первую очередь это справочные, лингвистические и энциклопедические данные. Каждый раз когда вам в голову приходит мысль распарсить кусочек википедии или викисловаря — ущипните себя как следует и вспомните о том, что всё, что хранится в категориях, инфобоксах или таблицах, уже распарсено и доступно через API с помощью SPARQL или MQL-интерфейса.

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

Эта статья — первая из цикла Базы знаний. Следите за обновлениями.

• Часть 1 — Введение
• Часть 2 — Freebase: делаем запросы к Google Knowledge Graph
• Часть 3 — Dbpedia — ядро мира Linked Data
• Часть 4 — Wikidata — семантическая википедия

Как только я заинтересовался lock-free алгоритмами, меня стал мучить вопрос – а откуда взялась необходимость в барьерах памяти, в «наведении порядка» в коде?
Конечно, прочитав несколько тысяч страниц руководств по конкретной архитектуре, мы найдем ответ. Но этот ответ будет годен для этой конкретной архитектуры. Есть ли общий? В конце концов, мы же хотим, чтобы наш код был портабелен. Да и модель памяти C++11 не заточена под конкретный процессор.
Наиболее приемлемый общий ответ дал мне мистер Paul McKenney в своей статье 2010 года Memory Barriers: a Hardware View of Software Hackers. Ценность его статьи – в общности: он построил некоторую упрощенную абстрактную архитектуру, на примере которой и разбирает, что такое барьер памяти и зачем он был введен.
Вообще, Paul McKenney – известная личность. Он является разработчиком и активным пропагандистом технологии RCU, которая активно используется в ядре Linux, а также реализована в последней версии libcds в качестве ещё одного подхода к безопасному освобождению памяти (вообще, о RCU я хотел бы рассказать отдельно). Также принимал участие в работе над моделью памяти C++11.
Статья большая, я даю перевод только первой половины. Я позволил себе добавить некоторые комментарии, [которые выделены в тексте так].

Краткий синопсис

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

P.S. Весьма «сухой язык», но вполне читабельно после университетской программы. По большей части определения парадоксов брались из Википедии (упрощённая формулировка и готовая TeX-разметка).

Введение

Как сама теория множеств, так и парадоксы, ей присущие, появились не так уж и давно, чуть более ста лет назад. Однако за этот период был пройден большой путь, теория множеств так или иначе фактически стала основой большинства разделов математики. Парадоксы же её, связанные с бесконечностью Кантора, были успешно объяснены буквально за половину столетия.

Следует начать с определения.

Что есть множество? Вопрос достаточно простой, ответ на него вполне интуитивен. Множество это некий набор элементов, представляемый единым объектом. Кантор в своей работе Beiträge zur Begründung der transfiniten Mengenlehre даёт определение: под «множеством» мы понимаем соединение в некое целое M определённых хорошо различимых предметов m нашего созерцания или нашего мышления (которые будут называться «элементами» множества M)[1]. Как видим, суть не изменилась, разница лишь в той части, которая зависит от мировоззрения определяющего. История же теории множеств как в логике так и в математике весьма противоречива. Фактически начало ей положил Кантор в XIX веке, далее Рассел и остальные продолжили работу.

Парадоксы (логики и теории множеств) — (греч. — неожиданный) — формально-логические противоречия, которые возникают в содержательной множеств теории и формальной логике при сохранении логической правильности рассуждения. Парадоксы возникают тогда, когда два взаимоисключающих (противоречащих) суждения оказываются в равной мере доказуемыми. Парадоксы могут появиться как в пределах научной теории, так и в обычных рассуждениях (например, приводимая Расселом перифраза его парадокса о множестве всех нормальных множеств: «Деревенский парикмахер бреет всех тех и только тех жителей своей деревни, которые не бреются сами. Должен ли он брить самого себя?»). Поскольку формально-логическое противоречие разрушает рассуждение как средство обнаружения и доказательства истины (в теории, в которой появляется парадокс, доказуемо любое, как истинное, так и ложное, предложение), возникает задача выявления источников подобных противоречий и нахождения способов их устранения. Проблема философского осмысления конкретных решений парадоксов — одна из важных методологических проблем формальной логики и логических оснований математики.

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

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

«Мы построили его через ущелье, на дне которого протекала река», — рассказывал он своему другу. «Оно было широким и глубоким. Мы потратили два года на одно только изучение рельефа, выбор архитектуры и материалов. Мы наняли лучших инженеров и спроектировали этот мост, на что ушло ещё пять лет. Мы заключили договор с самой большой строительной фирмой на изготовление опор, конструкций и постройку дорог, соединяющих будущий мост с близлежащими магистралями. Десятки людей погибли при постройке моста. Наш мост был многоуровневым — под основной трассой могли ходить поезда, и ещё у нас были отдельные дорожки для велосипедистов. Этот мост олицетворяет значительную часть моей жизни».

Эта статья задумана мной как сборник некоторых интересных моментов по использованию и оптимизации SQL запросов в БД MySQL, на мой взгляд, плохо освещенных в интернете. Так, из статьи вы узнаете о конструкции with rollup, и о том, как переписать подзапросы in и not in на join'ы, а так же обновление и удаление данных в нескольких таблицах — одним запросом, и многое другое. Начнем по порядку.

От переводчика: данный текст даётся с незначительными сокращениями по причине местами излишней «разжёванности» материала. Автор абсолютно справедливо предупреждает, что отдельные темы покажутся чересчур простыми или общеизвестными. Тем не менее, лично мне этот текст помог упорядочить имеющиеся знания по анализу сложности алгоритмов. Надеюсь, что он будет полезен и кому-то ещё.
Из-за большого объёма оригинальной статьи я разбила её на части, которых в общей сложности будет четыре.
Я (как всегда) буду крайне признательна за любые замечания в личку по улучшению качества перевода.

Введение

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

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

От переводчика: Это пятая статья из цикла о Node.js от команды Mozilla Identity, которая занимается проектом Persona.

Все статьи цикла:

1. "Охотимся за утечками памяти в Node.js"
2. "Нагружаем Node под завязку"
3. "Храним сессии на клиенте, чтобы упростить масштабирование приложения"
4. "Производительность фронтэнда. Часть 1 — конкатенация, компрессия, кэширование"
5. "Пишем сервер, который не падает под нагрузкой"
6. "Производительность фронтэнда. Часть 2 — кешируем динамический контент с помощью etagify"
7. "Приручаем конфигурации веб-приложений с помощью node-convict"
8. "Производительность фронтенда. Часть 3 — оптимизация шрифтов"
9. "Локализация приложений Node.js. Часть 1"
10. "Локализация приложений Node.js. Часть 2: инструментарий и процесс"
11. "Локализация приложений Node.js. Часть 3: локализация в действии"
12. "Awsbox — PaaS-инфраструктура для развёртывания приложений Node.js в облаке Amazon"

---

Как написать приложение Node.js, которое будет продолжать работать даже под невозможной нагрузкой? В этой статье показана методика и библиотека node-toobusy, её воплощающая, суть которой наиболее кратко может быть передана этим фрагментом кода:

var toobusy = require('toobusy');
 
app.use(function(req, res, next) {
  if (toobusy()) res.send(503, "I'm busy right now, sorry.");
  else next();
});

В чём заключается проблема?

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

Это может быть и злонамеренный всплеск трафика, например от DoS-атаки. Первый шаг к борьбе с такими атаками — написание сервера, который не падает.

Я полагаю что все в общих чертах знают о существовании такого замечательного математического инструмента как преобразование Фурье. Однако в ВУЗах его почему-то преподают настолько плохо, что понимают как это преобразование работает и как им правильно следует пользоваться сравнительно немного людей. Между тем математика данного преобразования на удивление красива, проста и изящна. Я предлагаю всем желающим узнать немного больше о преобразовании Фурье и близкой ему теме того как аналоговые сигналы удается эффективно превращать для вычислительной обработки в цифровые.

(с) xkcd

Без использования сложных формул и матлаба я постараюсь ответить на следующие вопросы:

• FT, DTF, DTFT — в чем отличия и как совершенно разные казалось бы формулы дают столь концептуально похожие результаты?
• Как правильно интерпретировать результаты быстрого преобразования Фурье (FFT)
• Что делать если дан сигнал из 179 сэмплов а БПФ требует на вход последовательность по длине равную степени двойки
• Почему при попытке получить с помощью Фурье спектр синусоиды вместо ожидаемой одиночной “палки” на графике вылезает странная загогулина и что с этим можно сделать
• Зачем перед АЦП и после ЦАП ставят аналоговые фильтры
• Можно ли оцифровать АЦП сигнал с частотой выше половины частоты дискретизации (школьный ответ неверен, правильный ответ — можно)
• Как по цифровой последовательности восстанавливают исходный сигнал

Я буду исходить из предположения что читатель понимает что такое интеграл, комплексное число (а так же его модуль и аргумент), свертка функций, плюс хотя бы “на пальцах” представляет себе что такое дельта-функция Дирака. Не знаете — не беда, прочитайте вышеприведенные ссылки. Под “произведением функций” в данном тексте я везде буду понимать “поточечное умножение”

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

С каждым годом алгоритмы ранжирования совершенствуются: добавляются новые факторы, усложняются механизмы обработки информации – и все для того, чтобы идти в ногу со временем и отвечать на запрос пользователя всегда актуальной и действительно релевантной выдачей. Как спрос определяет предложение, так и алгоритмы ранжирования стимулируют развитие сайта в направлении, востребованном посетителем.
Отсутствие механизма ранжирования привело бы к хаосу в выдаче, когда нужная информация находилась бы далеко за первой десяткой, а наличие собственного сайта не имело бы смысла, кроме как лишний штрих в визитке. Тоже касается и усложнения алгоритмов определения ранга релевантности: если бы определение происходило по индексу цитируемости и ключевым вхождениям, то мы до сих пор бы смотрели на одностраничные сайты без дизайна, не задумываясь о юзабилити.
На определение ранга релевантности влияют различные факторы ранжирования, которых очень много на сегодняшний день и которые можно объединить между собой в группы. Поисковые системы оперируют одними понятиями группировки, оптимизаторы другими. При этом влияние фактора остается неизменным в алгоритме ранжирования. Некоторые факторы могут быть равноценными, что не позволяет линейно сравнивать между собой конкурентов. Однако основные направления задать и определить можно.

В данной статье речь пойдет преимущественно о текстовой и ссылочной составляющей.

Поисковая система Яндекс является наиболее интересным исследуемым объектом в данном плане не только потому, что в ней чаще, чем в других происходят сильные изменения в алгоритме, но и потому, что данная система является первой в Рунете по работе с коммерческими или продающими запросами.

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