программирование
Статьи по этой теме:
Программирование
Как разработать систему рекомендаций ★
Продолжим разговор о системе рекомендаций в S2. Эта система подбирает к каждой заметке набор других заметок, которые посетитель может почитать дальше. В прошлый раз я рассказал об этой системе в целом, сейчас же опишу алгоритм подбора самих рекомендаций.
За рекомендации в моем случае отвечает движок полнотекстового поиска Rose. Структура данных в полнотекстовом индексе как раз подходит для задачи подбора похожих заметок. Если совсем упростить, то получается, что обычный поиск — это подбор подходящих заметок к словам из поискового запроса, а рекомендации к заметке — это подбор других заметок по словам из нее. А теперь давайте погрузимся в детали.
Теория рекомендаций
Для начала давайте поймем, как вообще могут работать системы рекомендаций. Рассуждать будем на примере существовавшего
Оценки пользователей сохраняются как веса связи «многие-ко-многим» между пользователями и фильмами. Через эту связь по пользователю можно найти фильмы, которые ему понравились. По фильмам — других пользователей, которым понравились эти фильмы. И в качестве рекомендаций выдать другие понравившиеся пользователю фильмы. Но где на шкале оценок провести границу, отделяющую понравившиеся фильмы? И что делать с фильмами, которые не понравились?
Математика позволяет предложить более формальный и универсальный подход. Будем рассматривать оценки к фильмам как координаты некоторой точки во многомерном пространстве всех фильмов. И тогда всех пользователей можно представить как множество точек в таком пространстве. При достаточном количестве они начнут группироваться в кластеры по разным предпочтениям. После этого задача подбора рекомендаций сведется к поиску соответствующего кластера.
На самом деле, картина сложнее, так как никто не может поставить оценки всем фильмам. Поэтому вместо точек мы имеем дело с некоторыми подпространствами (прямыми, плоскостями и т. д.). И чтобы сформировать мои рекомендации, система проецирует все оценки на подпространство просмотренных мной фильмов, находит кластер в проекции, и по нему уже пытается восстановить кластер в полном пространстве.
Понятно, что процедура восстановления кластера из проекции неоднозначна, и в этом месте система рекомендаций может ошибаться, даже если в ней собраны оценки большого количества пользователей. Например, по оценкам фильмов, единогласно оцениваемых зрителями, нельзя восстановить предполагаемую оценку и однозначно рекомендовать фильм, мнения по которому разделились на два равновеликих полюса.
Эта теория прекрасно выглядит на листе бумаги. Но я уверен, что при практической реализации разработчики столкнулись с кучей проблем. Очевидная проблема — нормировка оценок. Например, у меня средняя оценка была около 7. Оценки меньше 4 я практически не ставил. Задумывался над тем, чем отличается оценка 9 от 10. Оценки других пользователей наверняка отличались по характеристикам. Кто-то, например, мог ставить только две оценки, 1 и 10. Чтобы рекомендации работали, оценки нужно нормализовать — привести к одному масштабу.
Теперь давайте посмотрим, как можно эти знания применить для подбора рекомендаций заметок.
Рекомендации на основе тегов
Как видно из предыдущего рассмотрения, систему рекомендаций можно сделать везде, где есть связь «многие-ко-многим». Именно так связаны заметки и теги. Если вы проставляете заметкам теги, то по тегам можно найти другие заметки с такими же тегами.
Недостатки подхода лежат на поверхности. Во-первых, тегов у каждой заметки должно быть много. Если, например, заметкам ставить только по одному тегу, рекомендации ничем от самих тегов отличаться не будут. Во-вторых, теги нужно проставлять единообразно. Если вы решили завести новый тег, вам нужно пройтись по старым заметкам и понять, к каким из них будет подходить этот новый тег.
Рекомендации на основе похожих текстов
В движке S2 есть другая связь «многие-ко-многим» — поисковый полнотекстовый индекс. Эта структура данных может вернуть по слову список проиндексированных элементов, содержащих такое слово. В библиотеке Rose полнотекстовый индекс хранится в отдельной таблице БД из трех колонок. Вот пример:
| word_id | toc_id | positions |
|---|---|---|
| 1 | 1 | 0,37 |
| 3 | 4 | 0,15,74,193,614 |
| 3 | 8 | 94 |
| 3 | 9 | 73 |
| 4 | 1 | 3,16,57 |
| ... |
В первой колонке хранится id «слова», во второй — внутренний id проиндексированного элемента (ToC — это сокращение от table of contents), в третьей — положения соответствующего слова в проиндексированном тексте.
При индексации исходный текст заметок очищается от html-тегов, разбивается на предложения и слова. Слова переводятся в нижний регистр. У слов удаляется окончание с помощью эвристического алгоритма (стеммер Портера). Оставшиеся основы слов заменяются на идентификаторы word_id и попадают в полнотекстовый индекс, при этом неизвестные основы добавляются в справочную таблицу word.
При поиске запрос преобразуется по такой же схеме: слова заменяются на идентификаторы word_id, и из поискового индекса мы получаем информацию о том, в каких проиндексированных текстах (toc_id) встречались эти слова. Положения слов (positions) нужны для вычисления релевантности: чем ближе слова из запроса друг к другу в тексте, тем выше окажется этот текст в выдаче.
Рекомендации на основе близости текста тоже используют эту таблицу. У меня получилось уместить все существенные вычисления в один SQL-запрос.
SELECT
relevance_info.*, -- информация из подзапроса
m.images, -- добавляем к ней информацию о картинках
t.*, -- добавляем к ней оглавление
-- и первые 2 предложения из текста
(SELECT snippet FROM snippet AS sn WHERE sn.toc_id = t.id ORDER BY sn.max_word_pos LIMIT 1) AS snippet,
(SELECT snippet FROM snippet AS sn WHERE sn.toc_id = t.id ORDER BY sn.max_word_pos LIMIT 1 OFFSET 1) AS snippet2
FROM (
SELECT -- Перебираем все возможные заметки и вычисляем релевантность каждой для подбора рекомендаций
i.toc_id,
round(sum(
original_repeat + -- доп. 1 за каждый повтор слова в оригинальной заметке
exp( - abn/30.0 ) -- понижение веса у распространенных слов
* (1 + length(positions) - length(replace(positions, ',', ''))) -- повышение при повторе в рекомендуемой заметке, конструкция тождественна count(explode(',', positions))
) * pow(m.word_count, -0.5), 3) AS relevance, -- тут нормировка на корень из размера рекомендуемой заметки. Не знаю, почему именно корень, но так работает хорошо.
m.word_count
FROM fulltext_index AS i
JOIN metadata AS m FORCE INDEX FOR JOIN(PRIMARY) ON m.toc_id = i.toc_id
JOIN (
SELECT -- достаем информацию по словам из оригинальной заметки
word_id,
toc_id,
(SELECT count(*) FROM fulltext_index WHERE word_id = x.word_id) AS abn, -- распространенность текущего слова по всем заметкам
length(positions) - length(replace(positions, ',', '')) AS original_repeat -- сколько раз слово повторяется в оригинальной заметке. Выше используется как доп. важность
FROM fulltext_index AS x FORCE INDEX FOR JOIN(toc_id)
JOIN toc AS t ON t.id = x.toc_id
WHERE t.external_id = :external_id AND t.instance_id = :instance_id
AND length(positions) - length(replace(positions, ',', '')) < 200 -- отсекаем слишком частые слова. Хотя 200 слишком завышенный порог, чтобы на что-то влиять
HAVING abn < 100 -- если слово встречается более чем в 100 заметках, выкидываем его, так как слишком частое. Помогает с производительностью
) AS original_info ON original_info.word_id = i.word_id AND original_info.toc_id <> i.toc_id
GROUP BY 1
HAVING count(*) >= :min_word_count -- количество общих слов, иначе отбрасываем
) AS relevance_info
JOIN toc AS t FORCE INDEX FOR JOIN(PRIMARY) on t.id = relevance_info.toc_id
JOIN metadata AS m FORCE INDEX FOR JOIN(PRIMARY) on m.toc_id = t.id
ORDER BY relevance DESC
LIMIT :limitОпишу ключевые шаги, которые здесь выполняются.
1. Взять все слова в заметке, к которой подбираем рекомендации. Я называю эту заметку оригинальной. Выбор слов происходит в самом внутреннем подзапросе.
2. Выкинуть распространенные слова. Это нужно делать для повышения точности и при поиске, и при подборе рекомендаций. Можно даже составить список игнорируемых слов вроде союзов или предлогов. Но вместо составления такого неизменяемого списка я вычисляю распространенность (abundance, сокращенно abn — количество заметок, в которых встречается это слово) для каждого слова в индексе. Например, в блоге о дизайне в каждой заметке будет слово «дизайн», и его тоже надо игнорировать.
Слова с распространенностью больше 100 наверняка окажутся слишком общими, и я отбрасываю их по соображениям производительности. Скорее всего порог должен
3. Найти одинаковые слова у оригинальной заметки с остальными заметками. Это происходит в промежуточном подзапросе. У заметок при этом должно быть достаточное количество общих слов (порог определяется параметром min_word_count).
Я пробовал разные значения параметра. Если увеличивать, количество рекомендаций падает. Если уменьшать, в рекомендации попадают не очень подходящие заметки за счет случайного использования общих слов. Я остановился на варианте, когда сначала выполняется со значением 4. Если результатов нет, как это часто бывает у коротких заметок, то запрос повторяется со значением параметра 2.
4. По повторяющимся словам вычислить релевантность. Это тоже происходит в промежуточном подзапросе за счет выражения в селекте и за счет group by. Релевантность я вычисляю как количество повторений общих слов. Чтобы понизить влияние распространенных слов, я добавил ослабление за счет веса exp(-abn/30.0). Хотел было использовать колоколообразную функцию типа exp(-sqr(abn/30.0)), но на практике линейное уменьшение веса при малых значениях распространенности повысило качество рекомендаций.
Кроме того, повторы в оригинальной заметке (original_repeat) и в рекомендуемых заметках влияют на релевантность несимметрично: повторяющиеся слова в оригинальной заметке не ослабляются, даже если они распространены. Объяснение можно предложить такое: если автор пишет одинаково часто о шахматах и шашках, то к оригинальной заметке с пятью словами «шахматы» и одним словом «шашки» лучше рекомендовать заметку с одним словом «шахматы», чем с пятью словами «шашки». Эффект несимметричности я не закладывал специально. Практика показала, что отсутствие ослабления у original_repeat субъективно улучшает качество рекомендаций.
Несимметричность веса оригинальной заметки и рекомендуемых может быть даже полезной, чтобы избежать «зацикливания» рекомендаций, когда к заметке А мы рекомендуем заметку Б, а к заметке Б — заметку А. Правда, у меня этот критерий не был обязательным, и я не проверял, как он выполняется. Применительно к моему сайту эффект зацикливания может ослабляться ещё и за счет последующего предпочтения в рекомендациях заметок с картинками.
Последний множитель в релевантности pow(m.word_count, -0.5) учитывает размер рекомендуемой заметки в словах. Без него в моем случае среди рекомендуемых оказывались очень длинные заметки, набиравшие релевантность за счет большого количества повторяющихся слов средней распространенности. Тогда я подумал, что сортировать рекомендации нужно не по абсолютному количеству общих слов, а по относительному, то есть надо поделить вычисленную релевантность на количество слов в рекомендуемой заметке. В рекомендации стали попадать короткие заметки всего из нескольких слов, а у нормальных заметок из нескольких сотен слов релевантность сильно просела. Чтобы было ни нашим ни вашим, я попробовал поделить абсолютную релевантность на корень из длины рекомендуемой заметки, и это сработало: с первых мест рекомендаций ушли как очень короткие, так и очень длинные заметки. Изменение показателя степени −0,5 в обе стороны приводило к некоторому повышению ранга одних и понижению ранга других таких нерелевантных заметок.
У меня не было объяснения, почему нормировка релевантности именно на корень из длины оказалась подходящей. Но в момент набора этого текста появилась гипотеза. Нормировка на длину рекомендуемых заметок не учитывает длину оригинальной заметки. Но для подбора рекомендаций к одной оригинальной заметке ее длина ни на что не влияет. Возможно, что для более общей задачи подбора рекомендаций к N оригинальным заметкам релевантность нужно нормировать на среднее геометрическое из длин оригинальной и рекомендуемой заметок. Тогда для одной оригинальной заметки ее длина превратится в несущественный постоянный коэффициент и уйдет за скобки, а длина рекомендуемой заметки как раз окажется в знаменателе под корнем.
5. Получить заголовок, картинки и фрагмент текста. Это неинтересная техническая задача, решаемая во внешней части запроса. Для «сниппетов» — коротких фрагментов текста — я достаю первые два предложения из заметок. Сначала думал выводить те предложения из текста, которые содержат общие слова. Зависимость сниппетов от контекста как раз бы показала, почему рекомендуется именно эта заметка. Но sql-запрос и так получился достаточно объемным, и пока я остановился на упрощенном варианте. Возможно движок как продукт с таким упрощенным вариантом будет даже лучше. Если писать заметки так, чтобы первые предложения давали понять, о чем будет заметка, то показывать лучше их, а не случайные предложения из самого текста.
Вопросы производительности
В запросе вы видите явное указание использовать конкретные индексы. Без них планировщик не использовал часть индексов. Почему он так решал — непонятно. За счет расстановки хинтов я оптимизировал запрос раз в 20 до нескольких десятков миллисекунд. Я последние 6 лет работаю с PostgreSQL, и он даже думать отучил, что в запросы можно добавить хинты. Но тут пришлось.
Производительность в несколько десятков миллисекунд я посчитал достаточной, чтобы выполнять sql-запрос подбора рекомендаций на лету, без какого-либо кеширования. Да и с алгоритмической, и с продуктовой точек зрения сохранять подобранные рекомендации смысла нет, потому что алгоритм детерминирован: при одинаковых входных данных всегда будет выдаваться одинаковый результат, и рекомендации всегда можно пересчитать.
При работе на настоящем сервере выяснилось, что в режиме невысокой нагрузки база данных может иногда выполнять запрос существенно дольше — несколько сот миллисекунд или даже больше секунды. Вот данные мониторинга по средней длительности запроса в миллисекундах:
Выбросы на графике означают, что иногда пользователи будут замечать, что страница долго открывается. И изредка приходящий гугл-бот будет жаловаться на долгую загрузку страниц и понижать сайт в выдаче.
Я добавил кеширование подбора рекомендаций. Кеш инвалидируется не по времени, а по обновлению заметок. Правда, мне пришлось удалять весь кеш рекомендаций при любом изменении опубликованных заметок. Действительно, изменение хотя бы одного слова в какой-либо заметке может привести к тому, что эта заметка может появиться или исчезнуть из рекомендаций к произвольному количеству заметок. Формально можно было бы уже знакомым нам образом пройтись по индексу и по словам из измененной заметки понять, в каких других заметках они встречаются. Но всё же проще инвалидировать весь кеш.
Надо отметить, что проблему с редкими выбросами кеш хорошо решает, если заметки редко обновляются. Если вы будете постоянно редактировать опубликованные заметки, кеш будет постоянно очищаться.
Я так и не понял, почему возникают такие всплески времени выполнения запроса. Не думаю, что конкуренция MySQL за процессорное время с PHP или веб-сервером может привести к таким всплескам более чем в 20 раз. На других запросах, правда, более простых, этого не видно. Возможно, MySQL выгружает страницы с нужными данными из памяти. Ну да ладно.
Направления развития
- Убрать из запроса захардкоженные числа.
- Если рекомендаций с четырьмя общими словами нет, делать повторный запрос с ослабленным ограничением. А вообще тут важно найти баланс: надо ли показывать неподходящие рекомендации, если нет подходящих?
- Получать сниппеты из релевантных предложений, а не первых двух.
Дополнение о нормальной форме
Внимательный читатель отметил, что таблица полнотекстового индекса не находится даже в первой нормальной форме: в одной ячейке positions через запятую перечислен список положений слова. Что хорошо в теории, не всегда хорошо в настоящем работающем софте. Раньше действительно структура этой таблицы была другой, и каждый элемент из positions располагался на своей строке. Для корректной работы алгоритма мне нужно было обеспечить уникальность строк, поэтому элементы (word_id, toc_id, position) я еще добавил в уникальный индекс.
Достаточно быстро в целях оптимизации я отказался от индекса по word_id и повесил первичный ключ сразу на все колонки (word_id, toc_id, position). В этом есть смысл, так как первичный индекс в InnoDB кластерный, то есть данные строк хранятся на диске вместе с первичным индексом.
Сейчас я пошел в оптимизации дальше и отказался от нормальной формы для хранения положений. Базы данных устроены так, что в таблицах в каждой строке хранится дополнительная служебная информация. Объединение нескольких строк с одинаковыми word_id и toc_id в одну дало экономию места в полтора раза (поисковый индекс в целом уменьшился с 22 до 14 мегабайт при суммарном объеме заметок 2,8 мегабайт). Кроме того, скорость индексации тоже выросла примерно в полтора раза, так как сократилось количество выполняемых запросов. Я не обнаружил какого-либо заметного влияния формата поля positions на объем (кроме строки через запятую пробовал json и бинарную последовательность int4).
Понятно, что отказ от нормальной формы — не универсальное решение. Так, в рассматриваемом примере пропала возможность фильтрации по полю position. Для задач поиска в этом ничего страшного нет, так как в них фильтрация по position не встречается. Хотя по большому счету мало что изменилось: фильтрацию всё еще можно делать через операции с поиском подстроки, и это не будет сильно медленнее, потому что и раньше по полю position отдельного индекса не было.
Мастер костылей, или сущности в DOMDocument
Я тут решил потратить некоторое время на собственные проекты. Сейчас перерабатываю движок для поиска Rose. На нем работает поиск на этом сайте, также его использует Илья Бирман в Эгее.
Для извлечения текста из
Как оказалось, DOM API не поддерживает HTML5. Это выливается в практическую проблему с непоследовательной обработкой сущностей HTML. Например, если в исходнике написать & ★, при получении текстового содержимого из & ★. Видим, что первая сущность из HTML предыдущих версий распознается и раскодируется, а вторая из HTML5 — нет. Такие ошибки приведут к искажениям при выводе сниппетов.
Моя первая идея — прогнать текстовое содержимое через html_entity_decode($a, ENT_HTML5);. Действительно, что не доделал встроенный парсер, доделает эта функция. Но проблема в том, что раскодирование неидемпотентно. Если на вход подать &bigstar;, то после DOM API мы получим ★. И на этапе повторного раскодирования мы не будем знать, нужно ли раскодировать ★ еще раз, или нет.
Поиск проблемы в гугле разумного решения не выявил. В классе DOMDocument есть
Для начала нужно все вхождения амперсанда заменить на его сущность:
$text = str_replace('&', '&', $text);После этого DOM API раскодирует копии только одой сущности — этого самого амперсанда. При рекурсивном обходе в текстовом содержимом узлов html_entity_decode($a, ENT_HTML5);.
Уже который раз убеждаюсь, что искусство программиста во многом заключается в умении подобрать нужный костыль. Так и живем.
Деление на код и данные в ООП
Любая программа, выполняемая на современных процессорах, состоит из данных и кода — набора инструкций, обрабатывающих эти данные. Такое деление четко прослеживается как в ассемблерном коде, так и в процедурных языках.
В объектно-ориентированных языках не всё так однозначно. Объекты содержат и данные, и действия с ними, и, казалось бы, нарушают деление программы на данные и инструкции. Раньше я, как и многие другие, писал «объектный» код, в котором данные и инструкции были смешаны в кашу.
Правильный код в стиле ООП разделяет объекты-данные и объекты-сервисы. Первые (сущности, объекты-значения и т. д.) — обобщение понятия структуры. Вторые — обобщение понятия процедуры и функции.
Читайте о правильном подходе в статье Дмитрия Елисеева «Структуры с процедурами или объекты?». Он подробно разобрал тезис о разном применении разных типов объектов и проиллюстрировал всё на примерах для PHP.
Связь между физикой и программированием: абстракции и язык — В кресле препода №6
Я заметил нетривиальную связь между физикой и программированием. Она находится в области используемых и там и там абстракций и обозначений. Записал видео с объяснением и примерами.
Придумал название «В кресле препода» для таких видео, где я обсуждаю какие-то вопросы и делюсь опытом. Встречайте выпуск №6.
00:00:47 Зачем слушать этот рассказ
00:01:33 Замечание о формате презентаций
00:03:15 План рассказа
00:04:01 Математический аппарат физических теорий
00:05:39 Механика Ньютона и двойной маятник
00:09:45 Уравнения Максвелла: векторная и компонентная форма записи
00:14:17 Четырехвекторы и скорость света
00:18:01 Принцип наименьшего действия
00:21:25 Разнообразие форм уравнений Максвелла
00:23:41 Причем здесь программирование?
00:28:28 Уровни абстракций в языках программирования: физический, процедурный, ООП
00:33:26 Кто создает больше абстракций: физик или программист?
00:37:23 Практический пример
00:41:21 Разбор примера обработки тач-событий из MDN
00:48:50 Переписывание примера из документации в объектном стиле и добавление функциональности на примере головоломки Арнольда (исходник на гитхабе)
01:17:58 О «пользе» MVC и что такое ООП на самом деле
01:20:35 Сравнение процедурного и объектного подходов и принцип High Cohesion Low Couping
01:23:42 Наследования и полиморфизма нет, а дух ООП есть
Описание головоломки Арнольда в предыдущем посте и на хабре.
Одновременная вставка уникальных значений в словарные таблицы — В кресле препода №3
Как правильно добавлять данные в словарную таблицу с уникальными строками одновременно из нескольких потоков? В PostgreSQL вот так:
CREATE TABLE words (
id SERIAL PRIMARY KEY,
word TEXT NOT NULL UNIQUE
);
BEGIN;
SELECT id FROM words WHERE word = 'a';
INSERT IGNORE INTO words (word) VALUES ('a');
SELECT id FROM words WHERE word = 'a';
COMMIT;В видео рассказываю, почему именно так, и показываю, как это работает.
00:25 Пример
01:34 Демонстрация наивной реализации вставки в словарные таблицы
02:32 Недостаток: появление дублей
03:45 Демонстрация уникального индекса
04:47 Недостаток одного только уникального индекса
05:55 Нет поддержки целостности ⇒ нужны транзакции
06:37 Демонстрация параллельной вставки в таблицу с уникальным индексом в транзакции
08:59 Вставка с игнорированием
09:17 Демонстрация вставки с игнорированием в транзакции с уровнем READ COMMITTED
12:15 Демонстрация дедлока при вставке с игнорированием в транзакции с уровнем REPEATABLE READ
13:44 Особенности метода в MySQL
Кеширование и условие гонки
Одна из важных идей в программировании — кеширование. Если какая-то долгая операция выполняется часто, ее результат запоминается и переиспользуется, пока не изменятся условия, в которых результат был получен.
Кеширование не только экономит ресурсы и делает систему более отзывчивой. Без кеширования долгих операций система в принципе не сможет работать в режиме высокой нагрузки. Если вы разрабатываете кеширование в такой системе, важно помнить об одной частой ошибке проектирования — условии гонки (race condition). Расскажу об этой проблеме на выдуманном примере главной страницы
Предположим, на главной странице
235 запросов в минуту — вроде как не очень мало. Но сайт быстро ляжет, если ссылку разместят на
Если запрос к базе данных выполнить один раз и запомнить список наиболее популярных товаров, скажем, на час, то сервер сможет выдержать до
Однако запомнить результаты выполнения запроса недостаточно. Рано или поздно они устареют, и список популярных товаров надо пересчитать заново. Здесь и кроется та самая ошибка — условие гонки. Если результаты выполнения запроса устареют сразу для всех посетителей, и этих посетителей много, тяжелый запрос начнет выполняться одновременно.
Одновременное выполнение тяжелого запроса — неприятная ситуация по многим причинам:
- Несколько конкурентных запросов могут нагружать базу данных и выполняться медленнее, чем один запрос.
- Процессы приложения вместо полезной работы будут ждать окончания выполнения долгих запросов (если, конечно, у вас не асинхронная архитектура; хотя я сомневаюсь, что в этом случае вы бы стали сейчас читать в интернете об условии гонки). При достаточном количестве посетителей 20 процессов израсходуются очень быстро, и сайт перестанет открываться, пока, наконец, не завершится выполнение долгих запросов.
- Кроме того, если вы еще и допустили ошибку при программировании самого кеша, и система записывает данные в него неатомарно (например, в файл с помощью fopen/fwrite, file_put_contents и т. д.), вы с большой вероятностью получите испорченные данные (записанные вперемешку байты из разных процессов). Если система не готова к некорректным данным в кеше, она может вообще перестать работать, пока не посчитает, что данные в кеше устарели. А если готова — продолжит пытаться выполнить тяжелый запрос в конкурентном режиме и не восстановится до тех пор, пока не посчастливится записать корректные данные в кеш, или пока не упадет нагрузка.
Как избежать условия гонки? Есть два способа.
Синхронизировать параллельные процессы. Один из процессов «прогревает кеш» (выполняет долгую операцию). Остальные понимают, что процесс прогрева идет, и всё еще используют устаревшие данные из кеша. Способ не требует глубокой переработки приложения и подходит в простых случаях. Но универсальных методов синхронизации процессов не существует. Придется подбирать подходящий: блокировка файлов (flock), блокировки в базе данных, редисе и т. д.
Прогревать кеш в фоне. Если вы хотите обновлять список популярных товаров каждый час, вычисляете его по расписанию и складываете в кеш из отдельного процесса, который не имеет отношения к обработке
Очередь на основе PHP-FPM
Применил на практике прием, когда асинхронная очередь обработки сообщений реализовывается через PHP-FPM по протоколу fastcgi. На удивление, всё заработало сразу, никакой наладки не потребовалось.
Обычно PHP-FPM обрабатывает запросы от веб-сервера, например, nginx. Но никто не запрещает обращаться к PHP-FPM напрямую. Если все доступные рабочие процессы заняты, сообщения в нем как раз и ждут своей очереди на обработку.
Положительные стороны:
- Не нужны дополнительные компоненты в системе.
- PHP-FPM сам заботится о запуске рабочих процессов, достаточно отредактировать конфиг.
Отрицательные стороны:
- Нет надежного хранения сообщений. Если процесс PHP-FPM упадет, сообщения потеряются.
- Нет мониторинга. Если нужен — придется делать самостоятельно.
Чтобы сделать такую очередь, возьмите готовые библиотеки для общения по протоколу fastcgi, например, hollodotme/fast-cgi-client.
Спагетти-код
Большой перевод на Хабре про спагетти-код. Считаю статью важной, особенно в разговорах с людьми с ООП головного мозга, и не понимаю, почему у нее рейтинг +6.
Автор рассказывает о спагетти-коде как об одном из самых худших видов «плохого кода». Повествование закономерно начинается с оператора goto. Затем утверждается, что и объектно-ориентированное программирование может порождать спагетти.
Объектно-ориентированное программирование, первоначально разработанное для предотвращения спагетти-кода, стало (из-за использования без полного понимания «паттернов проектирования») одним из худших его источников. «Объект» может спокойно совмещать в себе код и данные, имея при этом любое количество интерфейсов, в то же время класс может свободно порождать подклассы по всей программе. Объектно-ориентированное программирование таит в себе большую мощь, и при дисциплинированном использовании, оно может быть очень эффективно. Но большинство программистов не могут с этим справиться, и со временем их код превращается в спагетти.
Потом рассматривается «Большой код» вообще. Автор заявляет, что у нас вообще нет хороших методов разработки «Большого кода», и противопоставляет его философии Unix — сделай одну вещь, и сделай ее хорошо.
Современный рынок труда
Сегодня за обедом разговаривали с коллегой:
— Я чувствую спрос на себя как на программиста, а как на физика — не чувствую.
— И это в стране, первой запустившей человека в космос.
История программирования в СССР
История программирования в СССР (первая часть, вторая часть). Написано интересно и легко читается. Вот, например, про
Давным давно, еще в докомпьютерную эру (с двадцатых годов) применялись для изображения последовательных процессов или алгоритмов блок-схемы (flowcharts). На них отдельные элементарные (на данном уровне абстракции) шаги изображались прямоугольничками, последовательность шагов — стрелочками, а ветвления (проверки условий) ромбиками. В самом-самом начале, когда языков программирования еще не было, а программы непосредственно кодировались числовыми кодами или, в лучшем случае, писались в «содержательных обозначениях», как рекомендовал патриарх нашего ремесла Александр Львович Брудно, блок-схемы были важным подспорьем. В таковом качестве во время оно их и застандартизировали.
Прошли десятилетия, то есть минули целые эпохи. А от программистов по-прежнему требовали чертить эти чертовы стрелочки и ромбики. Смысла в этом было аж никакого. Во-первых, теоретически доказано, что любой алгоритм, записанный на языке высокого уровня (на любом языке) имеет эквивалентное графическое представление в виде блок-схемы и почти наоборот, любая правильная блок-схема (фишка тут в слове «правильная») эквивалентна некоторому тексту на том или ином языке программирования. Но текст программы завсегда лучше блок-схемы, хотя бы потому, что последней можно только любоваться, а первый — это реальный кусок программы, который компилируется и выполняется на машине. Есть разница? Во-вторых, блок-схема может показать только синхронный, строго последовательный процесс вычислений, а в жизни такое наблюдается разве что в небольших несложных программах. Реальные же системы — это не однопоточные алгоритмы, а целые искусственные миры, где множество населяющих их объектов-персонажей (как программных, так и аппаратных) взаимодействуют друг с другом, посылая в непредсказуемые моменты времени сигналы и возбуждая прерывания, и где множество потоков вычислений исполняются одновременно и асинхронно, порой еще и на множестве процессоров и машин. Получается, что блок-схемами можно проиллюстрировать только маленькие кирпичики, но никак не всю систему, но зачем дополнительно иллюстрировать то, что и так внятно и понятно (с комментариями) записывается в текстовом виде?
Казалось бы, не нужны, так не пользуйтесь. А действительно не нужны — любой программист, хоть разработчик, хоть представитель заказчика предпочтет посмотреть исходный текст программы, а не эти картинки. Непрограммисту они — тем более до лампочки. И только ГОСТу, в лице его полномочного представителя — нормоконтролера, они нужны. Дороги как произведения изобразительного искусства. Он их проверяет на соответствие требованием оформления — такая-то ширина линий, столько-то миллиметров длина стрелочки, такой-то отступ квадратика от ромбика... Смысл схемы контролеру совершенно недоступен. Можете себе представить, какая халтура там процветала? В нашей конторе (как и в сотнях и тысячах таких же контор по всему Союзу) сидели тетки-чертежницы и тушью на кальках рисовали никому не нужные стрелочки и ромбики. Зато безработицы не было! Уже Союз загибался, но в девяностом году, если не ошибаюсь, успели под занавес выпустить новый ГОСТ все на ту же тему рисования блок-схем. Какая-то навязчивая, неотвратимая мания. Ну да ладно...
Почему я никогда не стану настоящим программистом
Я не смогу стать настоящим программистом. Это было понятно давно. Но только что я смог сформулировать, почему. Потому, что я слишком консервативен и ленив для изучения новых технологий, если старые успешно работают.
Я заинтересовался Паскалем еще до того, как мы его начали проходить в школе, потому что это позволило мне кое-что вычислить. Я разобрался в Ассемблере, потому что замена часто выполняемого кода ассемблерными вставками сильно ускоряет программу. А вот разобраться с Си я заставлял себя долго (правда, Си мне приходилось использовать и я бы рано или поздно с ним разобрался).
Я начал программировать на Delphi, потому что это почти что Паскаль :) И еще потому, что на нем легко делать интерфейсы. Но вот делать что-либо в Visual Studio меня не тянет.
Я принялся за изучение PHP, потому что он был на моем хостинге и мне хотелось «оживить» свой сайт. Но браться за Python или Ruby я не вижу смысла.
То же самое и с объектно-ориентированным программированием. Я до сих пор в программах не создаю свои классы (или объекты, как там правильно?). Процедурного программирования пока хватает.
Для меня Java, .NET, MVC, XML, x64 и остальное X — пустой звук. Уж лучше играться с shell-скриптами.
Delphi 2009 и не только
Я давно уже собираюсь выпустить новую версию The Game of Life, 3.6. Внес ряд полезных изменений. Проблема, которую осталось решить, как ни странно, связана с Вистой :)
Кажется, микрософты сделали так, что GDI в Висте эмулируется через DirectX (я не специалист в этом вопросе, точно утверждать не берусь). Из-за этого прорисовка через Canvas.Pixels стала в Висте жутко тормозить (по сравнению с XP). Я прекрасно понимаю, что Canvas.Pixels — сам по себе не очень быстрый способ вывода на экран. Но когда на каждом шаге меняется несколько точек, проще вызвать именно Canvas.Pixels, а не создавать отдельный буфер.
Версию 3.6 я задумал как переходную — в ней я хотел разобраться с графикой, а переписывание алгоритма расчета оставить для следующих версий. Мой приятель, просивший не упоминать его имя, помог с OpenGL. Теперь некритичная к быстродействию часть кода выводит графику через Canvas, а критичная — через OpenGL.
В ходе тестирования выяснилось, что в Висте есть еще одна проблема, которая связана, вероятно, с тем, что Виста запоминает содержимое PaintBox'а. Виста считает себя умнее всех остальных систем, в которых посылается сообщение wmpaint, и без спроса восстанавливает то, что было PaintBox'е, хотя оно уже перезаписано более свежей картинкой.
Логично предположить, что всё дело в Делфи 7. Она вообще не подозревает о существовании Висты :) Вполне возможно, что подобные ошибки уже исправлены в последней версии Делфи. Не долго думая, установил Делфи 2009. После небольших изменений кода программа скомпилировалась, но заработать отказалась из-за непонятной ошибки «Stream read error» при запуске. Более того, похожая ошибка стала возникать и в Делфи 7, правда, сообщение там было другое: «List capacity out of bounds (%d)». Эта же ошибка стала возникать и при запуске ранее скомпилированных экзешников. Я не знаю, что Делфи 2009 сделала с Вистой, что отказались работать экзешники, скомпилированные до ее установки!
Делфи 2009 — какое-то жуткое говно. Она, наконец, научилась понимать картинки PNG. Но вот с альфа-прозрачностью у нее до сих пор проблемы. Алё, Embarcadero, 2009 год на дворе. Как можно не поддерживать альфа-прозрачность? Отладчик по сравнению с седьмой версией сильно не улучшился. В программе возникла ошибка, так покажите, где она! Почему Visual Studio это умеет, а Делфи — нет?
К счастью, после удаления Делфи 2009 проблема с ошибкой «List capacity out of bounds (%d)» исчезла. Баг, связанный с обновлением PaintBox'а, исправлю каким-нибудь другим способом.
Да, и еще. Вот объясните мне, как можно пользоваться последними версиями программных продуктов и технологий, если они настолько кривые?
Добавлено: Обычно я не склонен к поспешным выводам, однако Делфи 2009 произвела на меня совсем уж удручающее впечатление :) По всей видимости, проблема с ошибкой при старте программы не связана с Делфи 2009. И, может быть, в ней можно заставить PNG работать нормально. В общем, нужно еще раз ее поставить, чтобы разобраться до конца.
Стиль оформления кода
Как заставить неправильный код выглядеть неправильно. Описывается один из вариантов оформления кода. Даже если вы — опытный программист, статья будет полезна для вас.