Форум dkLab и Denwer

[Дмитрий Кóтеров]

Уже в который раз мне приходит в голову идея практически во сне, я включаю компьютер и записываю ее, чтобы не забыть. Хочу заметить, что на данном форуме применяется не этот алгоритм, а его давний-давний медленный, кривой (по последним сведениям) глючный. Перепишу «в виду паттерна (-;», как только руки дойдут.

Итак, алгоритм: отслеживание изменений по четырем градациям (не-просмотрена-не-интересна, просмотрена-не-изменена, просмотрена-изменена, не-просмотрена-и-новая) в большом (размер не ограничен) массиве однотипных элементов (записей в БД, например, или топиков в форуме).

Основные свойства и достоинства:

1. малый размер для хранения промежуточных данных (в большинстве случаев умещается в куки)
2. необязательность использования СУБД, если число измененных-записей невелико (алгоритм без JOIN)
3. возможность работы в форумах без регистрации пользователей
4. исключительно быстрый поиск
5. простота алгоритма
6. возможность «пропуска» топика, взглянув на одно его название, чтобы дальнейшем не отслеживать его изменение

Предметная область:

1. Таблица топиков — таблица очень большого размера, хранящего записи, для которых производится отслеживание.
2. Снимок — структура, состоящая из трех целочисленных массивов, в которых хранятся ID:
   1. массив неизменных топиков (топики, посещенные пользователем, но не изменившиеся с тех пор
   2. массив измененных топиков (топики, которые изменились с момента последнего прочтения)
   3. массив новых топиков (топики, созданные после последнего посещения)
   а также одного числа — временной метки актуальности.

Снимок назовем актуальным, если на тот момент, который соответствует его временной метке, данные о топике в нем отражают реальное положение дел в форуме. Например, снимок актуален сразу же после его построения или через 10 дней, если за это время ничего не изменилось.

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

Каждый пользователь имеет ассоциированный с ним снимок. Если снимок невелик (содержит около 5000 записей), он хранится в куках в запакованном виде (можно использовать GZip). Если же список велик, можно использовать таблицу в БД (но для этого обязательно нужна регистрация пользователя).

Ясно, что, имея снимок, мы можем легко дать ответ на поставленную задачу — вывести все измененные и новые топики.

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

1. Запрашиваем все топики, время создания которых превышает время последней синхронизации. Добавляем их ID с список новых.
2. Запрашиваем все топики, время изменения которых превышает время последней синхронизации, но время создания меньше времени синхронизации. Для каждого ID в цикле:
   1. В случае, если ID присутствует в списке неизменных топиков, переносим его в список измененных.
   2. А если ID не было в списке неизменных, ничего не делаем.
3. Если текущая страница — страница просмотра топика с ID=id, удаляем id из списков измененных и новых топиков и добавляем — в список неизменных.

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

Реализация возможности "пометки всех топиков прочитанными" (друксование) несколько усложняет алгоритм. Добавим к снимку еще одно поле — момент врмени друксования.

Заметим, что массив новых топиков можно не хранить в снимке, а строить каждый раз динамически. Это происходит потому, что:

1. новый топик — это топик, созданный после последнего друксования
2. новый топик — это топик, отсутствующий в списке измененных
3. новый топик — это топик, отсутствующий в списке неизменных

Таким образом, получить все новые топики можно при помощи одного-единственного SQL-запроса, в части NOT IN (...) которого перечислить все ID из первых двух массивов снимка.

При друксовании необходимо лишь установить время метки друксования равным текущему. Кроме того, при показе измененных топиков следует проверять, не меньше ли дата изменения даты друксования. Если меньше, топик считается неизменным и удаляется из списка измененных (но не добавляется в список неизменных!).

Итак, размер снимка строго пропорционален количеству посещенных топиков. Очевидно, что еще компактнее хранить его невозможно (при расчете на случайный характер изменения топиков), а значит, алгоритм оптимален по данным.

Реализация разбтия топиков на группы-форумы тривиальна и достигается путем хранения нескольких меток друксования в снимке.

Last edited by Дмитрий Кóтеров on Sun Jan 25, 2004 5:31 pm; edited 1 time in total

[Юрий Насретдинов]

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

Из этого следует, что можно удалять все записи о просмотрах темдо последнего друксования - они все равно являются "неизмененными", как после нажатия кнопки "отметить все как прочитанное".

[Дмитрий Кóтеров]

Поправил чуть-чуть алгоритм (ошибся я там выше немного).

yUAC:
Нельзя. Тогда они при следующем изменении либо вообще не проявятся (в нынешнем варианте), либо проявятся как новые. А должны появиться как измененные.

Это и понятно — информация о просмотрах тоиков не должна теряться. Она нужна на всем протяжении существования пользователя.

[Юрий Насретдинов]

Дмитрий Кóтеров:
Но ! Если проводить эту оптимизацию совместно со смещением пометки друксования форума (а это можно делать, когда все темы этого являются прочтенными), то этого не произойдет. Я уже помнится это много раз говорил :)

[Дмитрий Кóтеров]

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

[Юрий Насретдинов]

Дмитрий Кóтеров:
В том-то и дело, что покраснеть они должны оба, а не только первая. В Вашей системе получается, что слежение идет только за теми топиками, которые пользователь уже посещал, а те, которые пользователь не посещал, либо будут светиться как новые (если дата_создания>дата_друкса), либо не будут подсвечиваться вообще (дата_создания<дата_друкса && дата_последнего_ответа>дата_друкса), но ведь это неправильно - логичнее было бы предположить, что в этой теме есть сообщения, которые он не видел, и => тема тоже является модифицированной.

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

Надеюсь, понятно объяснил :)

[Дмитрий Кóтеров]

yUAC wrote:

идет только за теми топиками, которые пользователь уже посещал

Именно так, и никак иначе. Это единственно логичный способ. Если пользователь ни разу не видел топика, ему все равно, что там изменилось. Например, Вы ни разу не видели типичную семью аборигена Австралии, а потому Вам все равно, что у них вчера родился двенадцатый ребенок.

То же самое — можно сделать возможность «отписаться от топика» — например, пользователь посмотрел топик, понял, что он ему не интересен, нажал кнопку, и больше за изменениями топика не следит.

[Юрий Насретдинов]

Дмитрий Кóтеров:
В любом случае можно сдвигать дату друксования форума при отсутсвии новых тем ?

[Дмитрий Кóтеров]

Можно. Но определение того, что ее можно сдвинуть, весьма ресурсоемко само по себе.

[Юрий Насретдинов]

Дмитрий Кóтеров:
Не факт. Можно ограничиться предположением, что если в последних 50 темах нет ни одной непрочитанной, то вся тема является непрочитанной. В таком случае это отнюдь не ресурсоемко - нужно всего-лишь ввести еще одну переменную changed, которая будет устанавливаться в true если будет хотя бы одна новая/измененная тема...

[Дмитрий Кóтеров]

Вы сами-то поняли, что написали? (-;
Я — нет.

[Юрий Насретдинов]

Дмитрий Кóтеров wrote:

Вы сами-то поняли, что написали

Я понял что я имел ввиду.
Имеется ввиду, что если на первой странице форума нет ни одной "новой" и ни одной "изменненной" темы, то в этом форуме нет новых/изменных тем, и следовательно, можно сдвинуть отметку друксования этого форума в time(). Так понятнее ?

[Дмитрий Эсс]

yUAC:
А что это даст?

[Дмитрий Кóтеров]

yUAC wrote:

Так понятнее ?

Так понятнее. Да, это верно.

[Дмитрий Эсс]

yUAC:
Извеняюсь, невнимательно читал.