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

Bzr-репозиторий http://softwaremaniacs.org/code/cicero/
Работающий форум http://softwaremaniacs.org/forum/

Идея

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

class Profile(Model):
  # ...
  read_articles = ManyToManyField(Article)

Проблема же его в том, что оно получается очень накладным. Если форум читают 100 пользователей и в день появляется по 10 статей, то за год в этой табличке накопится 100 * 10 * 365 = 365 000 записей. А еще эта табличка будет все время join'иться со статьями, и хотя я понимаю, что современные СУБД все таки не составляют реально в памяти больше миллиарда записей, все равно это уже немало. Но самое плохое, что эта нагрузка будет всегда только расти, и это будет чувствоваться на всех SELECT'ах форумных страниц.

Поэтому я придумал другое решение. Вместо того, чтобы у юзера хранить ссылки на каждую прочтенную статью, они заменяются на диапазоны id'шек вида:

[(1, 20), (25, 30), (32, 100)]

Каждый диапазон получается из идущих подряд прочтенных ID. Заново прочтенные статьи аккуратно вливаются в диапазоны. Если юзер прочитал статью с ID=31, то его список диапазонов станет таким:

[(1, 20), (25, 100)]

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

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

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

Реализация хранения

Первый вопрос — как эти диапазоны хранить. В самом Питоне это удобнее всего представить именно как список tuple'ов (как я выше и рисовал). В Django же никакого встроенного поля для такой вещи нет. Поэтому я придумал просто pickle'ить их в строку и хранить в TextField.

В Питоне словом "pickle" называется сериализация — превращение объектов в некое строковое представление. Для него есть стандартный модуль pickle

Сам процесс сериализации и десериализации оформил в отдельные методы, а их привязал к свойству:

class Profile(models.Model):
  # ...
  read_articles = models.TextField()

  def _get_read_ranges(self):
    from cPickle import loads
    if not self.read_articles:
      return [(0, 0)]
    return loads(self.read_articles)

  def _set_read_ranges(self, ranges):
    from cPickle import dumps
    self.read_articles = dumps(ranges)

  read_ranges = property(_get_read_ranges, _set_read_ranges)

# чтение:
# profile.read_ranges  --> выдает [(,)..(,)]
# запись:
# profile.read_ranges = [(,)..(,)]

У профиля также есть два публичных метода для собственно работы со всем хозяйством

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

Поэтому появилась хитрая функция set_news, которая принимает набор топиков (или форумов), берет их ID и составлят один SQL-запрос статей, принадлежащих топикам (или форумам). В тот же запрос в качестве ограничения запихиваются прочитанные диапазоны пользователя. В итоге, БД делает все работу по выфильтровыванию нечитанных статей за один запрос. Этот запрос еще и группируется по переданному списку топиков (или форумов), и на выходе в итоге получается табличка вида "ID топика (форума) — количество нечитанных статей". Последнее, что функция делает — это проставляет эти количества прямо тем объектам, которые были в нее переданы.

Тяжело? :-). Может быть в виде кода будет понятней (сокращенный вариант без проверок и только для топиков):

def set_news(self, topics):

  # полчить список ID
  ids = [str(t.id) for t in topics]

  # условие "только принадлежащие переданным топикам"
  condition = 'topic_id in (%s)' % ','.join(ids)

  # составляем ограничение по диапазонам
  ranges = ''
  for range in self.read_ranges:
    if ranges:
      ranges += ' or '
    # range (N, M) очень удобно годится для подстановки в строку
    ranges += 'a.id between %s and %s' % range

  # условие с диапазонами целиком отрицатется, нам нужны *не*прочитанные
  condition += ' and not (%s)' % ranges

  # финальный запрос
  query = 'select topic_id, count(1) as c from cicero_article a where %s group by 1' % condition

  # выполняется вручную, используя текущее соединение с БД из Django
  from django.db import connection
  cursor = connection.cursor()
  cursor.execute(query)

  # получаемые пары (topic_id, count) составляются в dict для поиска
  counts = dict(cursor.fetchall())

  # проставляем всем топикам атрибут new с количеством нечитанных,
  # используем 0 для топиков, которые не попали в запрос (прочитаны целиком)
  for topic in topics:
    topic.new = counts.get(topic.id, 0)

Вообще, если не лезть в подробности, то с фильтрацией по диапазонам все более-менее понятно: SQL'ная операция "between" подходит для них как нельзя лучше. А вот слияние диапазонов — та еще магия. Пойду, чайку налью, подумаю, насколько подробно про них писать...

Сама функция довольно короткая, получает articles — queryset со статьями, которые надо "прочитать". Это могут быть topic.article_set.all(), Article.objects.filter(topic_forum=forum) и Article.objects.all() для отметки топика, всего форума или вообще всего соответственно.

def add_read_articles(self, articles):

  # составляется условие по прочитанным диапазонам
  from django.db.models import Q
  query = Q()
  for range in self.read_ranges:
    query = query | Q(id__range=range)

  # из переданных статей исключаются уже прочтенные, 
  # выбираются их id
  ids = [a['id'] for a in articles.exclude(query).values('id')]

  from cicero.utils.ranges import compile_ranges, merge_range
  ranges = self.read_ranges

  # compile_ranges из переданных id составляет диапазоны, 
  # проверяя идущие подряд
  for range in compile_ranges(ids):
    # merge_ranges умно вливает каждый диапазон 
    # в результирующий набор
    ranges = merge_range(range, ranges)
  self.read_ranges = ranges

Те, кто действительно читает весь этот код, могут заметить, что здесь условие, исключающее диапазоны, составляется джанговским API, а в предыдущей функции составлялось строчками врчуную:

query = query | Q(id__range=range)

# vs.

ranges += ' or a.id between %s and %s' % range

Единственная тому причина в том, что первый запрос нужно было делать с "GROUP BY", которого Django по-нормальному не умеет. Обидно...

Вспомогательные функции "compile_ranges" и "merge_range" описывать не буду. Это довольно нудные циклы с проверками, кому интересно, посмотрите в исходниках в utils/ranges.py. Заодно поругайте, потому что алгоритмизация таких вещей, наверное, не самая сильная моя сторона :-)

Реализация расцветки в шаблонах

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

<ol>
{% for topic in object_list %}
  <li {% if topic.new %}class="new"{% endif %}> (ссылка на топик)
{% endfor %}
</ol>

topic.new, содержащий количество непрочитанных как раз будет в if'е отзываться как нужно.

Интересно только, где эти "new" им проставлять. Другими словами, где вызывать profile.set_news(object_list). Правильный ответ — view. Но только не потому, что это некая "бизнес-логика". Причина чисто практическая: в Django именно во view сходятся вместе понятия "Модель" и "пользователь веб-запроса". Поэтому именно здесь логично их друг с другом связывать.

Но вот проблема:

def forum(request, slug, **kwargs):
  # ...
  kwargs['queryset'] = forum.topic_set.all()
  return object_list(request, **kwargs)

Это завершающий кусок view, которая выводит топики форума. Она создает запрос и отправляет его в джанговскую object_list. И object_list делает там еще одну важную вещь: ограничивает запрос, чтобы выводилась текущая страница. Следовательно, если делать "set_news" до этого, то он будет вынужден тянуть все топики форума, а не только те, которые будут показаны, что нехорошо по производительности. А делать что-то после уже нет смысла, потому что object_list уже все отрендерит.

Здесь я с чисто практическими целями слегка поломал идеологию и Django, и заодно всего MVC :-). Я сделал шаблонный тег, который дизайнер шаблона должен будет вызывать перед выводом списка:

<ol>

{% setnews object_list %}

{% for topic in object_list %}
  <li {% if topic.new %}class="new"{% endif %}> (ссылка на топик)
{% endfor %}
</ol>

Сам тег тупой: он просто вызывает set_news текущего юзера.

Это, конечно, дико некрасиво, потому что заставляет дизайнера думать о каких-то деталях реализации, которые не имеют никакого отношения к отображению. Но это а) работает б) кажется мне легче, чем альтернативы, а именно — отказаться от использования object_list и сделать паджинацию вручную во view. Другими словами, это еще один случай, где мне кажется, что "practicality beats purity".

Комментарии: 46

  1. MajestiC

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

  2. lveagle

    Без тестов, непонятно пока какой эффект будет, ведь работа со строками это тоже небыстро..

  3. bogus

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

  4. Иван Сагалаев

    По дате — это один из основных минусов, который есть в PunBB, и который заставил меня писать свое. Потому что это заставляет меня, просто зайдя на форум, обязательно прямо сейчас просмотреть все непрочтенные и с ними разобраться. А "разобраться" для меня значит "подумать и скорее всего ответить". А думать я могу день-другой. И за это время уже все само отмечается "прочитанным", хотя я успел просмотреть только что-то одно, например.

  5. bogus

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

  6. Иван Сагалаев

    Такая идея тоже была :-). Теперь представьте себе форум, просуществовавший лет 5, на который просто пришел новый пользователь. Ему мгновенно должно при регистрации создаться большая куча линков. А большинство пользователей посмотрит и уйдет — куча линков вечно будет висеть мертвым грузом.

  7. Денис Барушев

    Иван, а ты поинтересуйся, как у коллег в Яндекс.Ленте сделано. Там ведь тоже есть прочитанные (или прочтенные? :)/непрочитанные сообщения (которые частенько глючат). Произведение юзеры*сообщения выходит в ней даже сложно представить какое большое.

    Я пробывал такие запросы explain'ом смотреть. Там как надо срабатывают индекы и вся таблица никогда не просматривается. Интересно, как долго будут индексы при insert'ах пересчитываться, когда размер таблицы достигнет пары миллионов записей.

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

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

  8. Ринат Измаилов

    http://forum.dklab.ru/about/todo/UniversalAlgorithmOfTrackingOfChanges.html - вот еще для размышлений оригинальный способ

  9. dark-demon

    надеюсь ты хотябы читаешь мои сообщения перед удалением...

    в твоей схеме есть одна серьёзная заковырка - при всплытии темы (то есть при каждом посте) нужно искать пользователей и обновлять для них диапазоны. или новые сообщения нас не интересуют?

    Потому что это заставляет меня, просто зайдя на форум, обязательно прямо сейчас просмотреть все непрочтенные и с ними разобраться. А “разобраться” для меня значит “подумать и скорее всего ответить”.

    в таком случае нужно вести информацию не о "прочтённых", а о "разобранных". это принципиасльно различные механизмы.

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

  10. Dreamer

    А чем тебя не устраивает вариант хранения прочтенных индексов в куках?
    Юзеры нечасто меняют броузеры и куки почти всегда включены.
    В крайнем случае можно делать иногда их дамп в файл на случай если юзер перебьет браузер ;)

  11. Григорий

    А если совместить два метода?
    Любая статья, дата написания которой на неделю меньше времени последнего посещения форума, считается прочитанной.
    При чтении статьи, её номер добавляется в таблицу прочитанных статей.
    Формат таблицы прочитанных сообщений: id пользователя, id статьи, дата добавления записи.
    Таблица прочитанных статей периодически чистится: в цикле для каждого юзверя удаляем из этой таблицы те записи, дата добавления которых минимум на неделю меньше времени последнего посещения форума.
    Таким образом размер таблицы прочитанных сообщений увеличивается медленно и то только, если новые пользователи появляются )
    Другими словами, это модификация подхода, применённого в PunBB. Сообщения за прошедшую неделю отслеживаются нормально, а более ранние предаются забвению. В принципе, ничто не мешает увеличить таймаут до месяца. Зависит от тормозов, которые это повлечёт за собой.

  12. Иван Сагалаев

    Денис Барушев:

    Иван, а ты поинтересуйся, как у коллег в Яндекс.Ленте сделано

    Коллега, который занимается этой проблемой сидит прямо напротив меня :-). Join'ить огромные таблицы действительно дорого, но тот способ, который придумали в Яндексе у меня не сработает, масштабы не те. Подробности, правда, разгласить не могу.

    dark-demon:

    надеюсь ты хотябы читаешь мои сообщения перед удалением…

    О, да... Зато Вы, похоже, не читаете статьи. Потому и комментарии бессмысленные. Потому и удаляю. Этот решил оставить исключительно в показательных целях:

    dark-demon:

    в твоей схеме есть одна серьёзная заковырка - при всплытии темы (то есть при каждом посте) нужно искать пользователей и обновлять для них диапазоны. или новые сообщения нас не интересуют?

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

    Причем, даже если лень вчитаться, можно было просто сходить на форум и проверить.

    Dreamer:

    А чем тебя не устраивает вариант хранения прочтенных индексов в куках?
    Юзеры нечасто меняют броузеры и куки почти всегда включены.

    Если привязывать к браузеру, то кукесы вообще не нужны: посещенные ссылки справляются в большинстве случаев. У Джоэла Спольского так и сделано. Вообще, я советую прочитать ее всю всем, кто интересуется написанием форума.

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

    Григорий:

    А если совместить два метода?
    Любая статья, дата написания которой на неделю меньше времени последнего посещения форума, считается прочитанной.

    Да, я думал про такое безусловное устаревание. Может и сделаю, в итоге, если текущая реализация начнет тормозить.

  13. Sergey

    To Dreamer

    А чем тебя не устраивает вариант хранения прочтенных индексов в куках?

    Кука имеет ограничение в 4K

  14. Денис Барушев

    Коллега, который занимается этой проблемой сидит прямо напротив меня :-). Join’ить огромные таблицы действительно дорого, но тот способ, который придумали в Яндексе у меня не сработает, масштабы не те. Подробности, правда, разгласить не могу.

    Жаль, что нельзя разгласить. Очень, очень интересно. Но, по крайней мере, это доказывает, что join'ы на больших масштабах - это тупик.
    А имя коллеги нельзя разгласить? Дело в том, что Лента - мой любимый сервис Яндекса, я вижу какие, у него проблемы, есть идеи как его улучшить. Когда-то пробывал писать в "обратную связь", но менеджер на том конце своими "не вижу проблемы" и "спасибо, мы подумаем" всячески отбил охоту писать что-то. Ну, и скажу, что тема rss-агрегации мне очень интересна и я планирую защитить в июне месяце по не диплом :)

    Извини, что сильно отошел от темы.

  15. EntropyHacker

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

  16. Alex Efros

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

    +\1

    А для решения проблемы "подумать/ответить позже" сделать отдельную фичу для помечания сообщений "важное" или что-то в этом роде.

    P.S. Извини, если коммент получился в стиле dark-demon - я сейчас дико сонный и до конца в суть не въехал. :(

  17. Yura Ivanov

    Мне тоже такой подход кажется странным. Строки == тормоза.
    1. Топик и сообщения не равны по сути. Открытие топика не говорит, что юзер посмотрел все двадцать страниц сообщений. Может он захочет потом ознакомиться с остальными, а может они ему вообще не нужны (например, слишком старые или ушли в офтоп). Однако получается, этот топик он явно прочитал и явно все сообщения в нем. Т.е. не решает проблемы новизны или заинетересованности в топике (не знаю предполагается ли такая задача в каком-либо плане).
    2. Диапазоны. Фрагментация будет в любом случае и немаленькая. Т.к. новые, например, юзеры читают топиками, в которых номера статей явно будут не по порядку; старые юзеры читают новые сообщения во всех топиках (или топиках с первой-второй страницы при большом трафике) и число интервалов может довольно быстро расти (во-первых, не все интересует, во-вторых, "давно тут сидит").

    Вариант со срезом по дате, имхо, предпочтительней. И join'ить придется не число сообщений_число юзеров, а число топиков_число юзеров. Т.е. фактически результат будет тот же, но проще...

    ЗЫ А вообще я выбрал бы :visited, ща мне скажут, что не гик и попросят на выход :)

  18. Василий Ставенко

    В качестве скромного предложения:

    А может быть выдать каждому форуму определенный диапазон айдишников тем? Для того чтобы диапазоны просмотренных тем меньше фрагментировались.

  19. Иван Сагалаев

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

    Строки == тормоза.

    Это обычно верно до тех пор, пока не померяешь :-).

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

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

    Фрагментация будет в любом случае и немаленькая

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

    ЗЫ А вообще я выбрал бы :visited, ща мне скажут, что не гик и попросят на выход :)

    По-моему, это наоборот гиковость :-). А для синхронизации между компьютерами можно history.mab в subversion закатать :-))

  20. Nvc

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

  21. EntropyHacker

    Хозяин - барин, но все равно излишне сложно :). Лично для меня время последнего просмотренного сообщения в топике (если топик разбит на несколько страниц, то по мере просмотра страниц запоминаем для пользователя дату последнего сообщения на последней просмотренной странице), плюс Watch для топика и Bookmark для статьи (оба на AJAX без перегрузки страницы), более чем достаточно.

  22. koder

    Есть вариант хранить прочитанные статьи в виде битовых масок (1 -прочитанная статья,0 непрочитанная ;). И еще 8 байт - номер
    первой прочитанной статьи статьи и номер первой
    статьи в битовой маске. Дальше нужно обязательно архивировать перед записью в ДБ
    (bz2, а лучше 7z прикрутить). На длину строки после архивации поставить ограничение, например 1k(кстати такую можно и в куках хранить, если что). Если строка в размер не влезает - исходная уменьшается например на 10% и корректируется
    номер первой статьи. Все статьи от первой прочитанной до первой в списке имеют статус "неизвестно". Кстати архивировать имеет смысл и данные в других методах(после пиклинга-то). Если статьям для разных разделов давать различные диапазоны, то для каждого раздела нужна будет отдельная строка, при этом так-же маски для часто читаемых и редко читаемых форумов сильно пожмутся.

  23. Jungle
        <p>Предложу свой вариант хранения прочитанных статей.<br />
    

    Метод основан на свойстве представления чисел 2 в степени n и побитового ИЛИ сложения.

    Объясню на примере:
    имеется список прочитанных статей/сообщений

    list_of_art = [1,2,4,8,128,1024]
    

    создадим битовую маску:

    mask = 0
    for i in list_of_art:
        mask |= i</p>
    

    будем хранить маску в БД
    далее для проверки является статья прочитаной или нет будем использовать следующее:

    if mask == mask | art_id:
        print 'Статья #%d прочитана' # art_id
    else:
        print 'Статья #%d не прочитана' # art_id
    

    да но этот метод годится только для чисел 2 в степени n, но можно сделать таблицу ассоциаций. Таблица ассоциаций - это метод, который ассоциирует числа в 2 в степени n числа:

    пример:

    3 -> 1
    5 -> 2
    6 -> 4
    7 -> 8
    9 -> 16
    10 -> 32
    

    и т.д.

    тогда в таблице появятся 2 поля (маски): одно для 2 в степени n чисел, а другое для ассоциированных чисел

    далее пример кода:

    def assoc_table(n):
        from math import log
        m = long(log(n, 2))

    b = count_of(m + 1)
    x = b - (2**(m + 1) - n)
    
    return 2**x
    

    def value_in(val, mask): return mask == mask | assoc_table(val)

    if name == 'main': list_of_art = [45,86,1023,99999] mask = 0 for i in list_of_art: mask |= assoc_table(i)

    list_of_art.append(46)
    for i in list_of_art:
        if value_in(i, mask):
            print '%d in mask' % i
        else:
            print '%d not in mask' % i
    

  24. Voldemar
        <p>Выскажу свои идеи "ЗА" привязку истории просмотров к топикам.<br />
    

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

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

    Если мы храним список всех просмотренных пользователем статей
    в отношении M:M между статьями и пользователями, нам действительно
    придется их join'ить. Но, при привязке списка статей (в виде единого
    объекта - сериализованного списка, например) к топику мы будем
    join'ить лишь сам список.
    При отображении списка статей одного топика можно сделать даже круче:
    одним запросом вытащить из базы топик, пользователя и список
    прочитанных им статей топика. Тогда, если я правильно отследил
    механику форума, мы получаем одно обращение к форуму вместо
    двух (пользователь каждый раз вытягивается отдельно от текущего объекта -
    кажется, ты упоминал о такой проблеме). Я слишком плохо знаю Django,
    чтобы судить, насколько такой финт вписывается в его идеологию.
    Но по идее должно быть реализуемо, так как подобные "несовместимые"
    связки встречаются в реальных проектах на каждом шагу.

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

    Посмотрим, что происходит с пользователями, которые
    читают только интересующие их топики.
    Примем гипотезу, что число одновременно "активных" тем в форуме
    значительно. Тогда велика вероятность того, что две статьи с
    последовательными идентификаторами будут написаны в два разных
    топика. Иначе говоря, две последовательных статьи одного топика
    редко будут иметь последовательные идентификаторы. Получается,
    что для рассматриваемой категории пользователей множество
    интервалов в действительности будет вырождаться в множество точек:

    [(25, 25), (55, 55), (66,66), (80, 80), (97, 97)]

    Красный Белый Красный Красный Белый топик топик топик топик топик

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

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

    [(25, 80)] для трех последовательных статей "Красного топика"
    [(55, 97)] для двух последовательных статей "Белого топика"
    

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

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

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

    А насчет того, что при хранении интервалов по каждому топику
    СУБД придется разбираться с отношением M:M,
    так это и есть ее работа. "Это именно то, что СУБД умеют делать хорошо", -
    как говаривал мне в молодости один умный человек. Так почему бы
    не переложить эту заботу на плечи "профессионала".

    На самом деле лично я вижу всего пару причин, оправдывающих ведение
    единого списка просмотренных статей всего форума:

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

    2. Желание читать непрочитанные сообщения всех топиков за
      определенный период времени. Но я не помню, упомянута ли она в ТЗ?

    3. Пометка наличия непрочитанных статей в топике при выводе списка топиков.
      Твоя реализация проще. Но и при хранении "разреженных интервалов"
      для каждого топика можно сделать требуемую выборку за один SQL-запрос.
      Правда в запросе будет по OR-у на топик, что в общем случае не есть хорошо.
      С другой стороны, количество топиков на одной странице ограничено.
      (И, кстати, тут вообще надо думать, интересуют ли пользователя
      новые сообщения со времени последнего посещения топика,
      либо именно непрочитанные сообщения в этом топике?)

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

    Хм, а причин-то оказалось аж четыре! Значит, надо думать. Особенно над тем
    как все это будет масштабироваться для "промышленных объемов". А также,
    о том, как работать с группами топиков (в ТЗ-шных определениях - с отдельными
    форумами).

  25. funny_falcon

    Пара идей:
    - хранить/загружать интервалы можно с помощью repr/eval. Не знаю быстрее/медленнее ли, но работать будет, и потом это можно будет прочесть без питона.
    - по поводу непрерывности и кучи форумов:
    если база PostgreSQL, то можно заморочиться с созданием sequence под каждый форум в триггере на создание форума

    execute 'create sequnce "forum_'||NEW.id||'<em>topic_id_seq";'
    

    в статье создать поле forum_topic_id и заполнять его в триггере:

    NEW.forum_topic_id := NEW.forum_id*10000000 + nextval('forum</em>'||NEW.forum_Id||'_topic_id_seq')
    

    и соответственно интервалы завязать на это поле.
    Как создавать триггеры используя Django - извини, не знаю. Может через connection.

  26. funny_falcon

    Не суди меня строго, но я бы

    ranges = ''
    for range in self.read_ranges:
      if ranges:
        ranges += ' or '
    # range (N, M) очень удобно годится для подстановки в строку
      ranges += 'a.id between %s and %s' % range
    

    записал бы как

    ranges = ' or '.join('a.id between %s and %s' % range
                         for range in self.read_ranges)
    

    но это дело вкуса.

  27. Иван Сагалаев

    Да, ' or '.join — это хорошо, поменял на него. В моем первом решении видны уши старого делфиста :-).

  28. Дамир

    Меня как-то посещала немного параноидальная идея, похожая на диапазоны id. Только группировку хотел сделать не по порядковым номерам, а по "популярным группам" id'шек. Правда, специфика немного другая, не форумная - надо было запоминать кто какой профайл (а их за 200 тысяч) уже смотрел.
    Правда руки дошли только до написания анализатора, выявляющего эти самые группы раз в сутки - нашлись группы из 5-10 профайлов (глубже 10 не искал), которые просматривали около 70% пользователей. Про эффективность пока ничего сказать не могу.

  29. kirbak

    На форумах xpoint.ru есть отличная фича, можно отмечать до какого сообщения ты дочитал)

  30. Иван Сагалаев

    Ok, я много думал :-). Только что реализовал aging — статьи старше определенного периода безусловно помечаются прочитанными. Реализовано прямо в методе, который "прочитывает" статьи: делается еще один запрос, который вынимает статью на границе устаревания и диапазон (0, эта статья) вливается юзеру:

    from datetime import date, timedelta
    cut_date = date.today() - timedelta(settings.UNREAD_TRACKING_PERIOD)
    article = Article.objects.filter(created__lt=cut_date).order_by('-created')[0]
    ranges = merge_range((0, article.id), ranges)
    

    Это решает, в общем-то, все проблемы, включая "выколотые точки".

  31. Yura Ivanov
        <p>Давай посчитаем :)</p>
    

    1. При хранении даты среза. На каждый клик по топику будет по инсерту/апдейту, вне зависимости от длины топика. Кстати эту идею развивать довольно просто дополнительными полями в таблице:

      • последнее прочитанное сообщение - из паджинации или мануальным указанием где остановился
      • подписка на новые сообщения в топике - мыло отправлять
      • оценка топика как возможно полезного для себя и других
    2. При хранении строк с интервалами. Тот же 1 апдейт, только сначала... Если топик длинный (ну скажем 10 страниц по 25 сообщений) и топиков много (ну скажем 1000). При первом (новый читатель) клике на топик сгенерится фрагментированная последовательность вида (1,1),(10,10),(12,12)... длиной 250 пар.
      Ладно, первый раз генерить эти пары не долго, т.к. объединять будем с пустым интервалом. При клике на второй топик объединение даст дополнительные 150-200 (а то и все) пары в этот список. Только придется сначала разобрать строку и объединить фрагментарно-пересекающиейся интервалы (а то и не пересегающиеся вовсе). В итоге получается, что эффективность данной модели хранения можно будет увидеть только для читателей всех без исключения тем/статей или для закрытого форума, где нет новых читателей.

    В итоге отобрали часть работы у СУБД, переложили на джанго, притом переложили явно больше, чем отобрали.

    ЗЫ я пользуюсь wiki, а не subversion. :) Хотя в trac (http://trac.edgewall.org/) оно тесно связано... Ну да в джанго им тоже пользуются, думаю ты в курсе :)

  32. Alexander Solovyov

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

  33. Иван Сагалаев

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

    • если не делать aging, то это вечное накопление, а это основная проблема, которую я хочу решить
    • если делать aging, то старый топик становится старым навсегда, и новые сообщения в нем никто никогда не увидит

    Текущая схема вторую проблему, кстати, тоже решает.

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

    Новые читатели... С ними тоже не вижу проблемы. Как только он прочитает первый топик, ему в ranges тут же запишется большая старая часть форума, и все — он становится таким же счастливым, как и остальные читатели.

    Ну и касаемо обработки строк... Я честно не понимаю, почему это всех так напрягает :-). Это очень маленькие строки, и обрабатываются они мгновенно. Что важно — они обрабатываются O(1) раз при клике на топик, то есть независимо от количества статей в нем или статей вообще. Я бы и рад, может быть, повесить эту работу на БД, но она этого не умеет (или я не знаю как).

    ЗЫ я пользуюсь wiki, а не subversion. :) Хотя в trac (http://trac.edgewall.org/) оно тесно связано… Ну да в джанго им тоже пользуются, думаю ты в курсе :)

    Эту часть не понял вообще :-)

  34. Иван Сагалаев

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

    Это догма. И как любая догма плоха как раз тем, что отключает желание думать через нее :-).

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

  35. Jungle

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

    И рост БД очень маленький. К примеру, чтобы хранить статью с номером 999999 нужно всего 125,006 байт (при использовании cPickle протокола версии 2, а если применить сжатие, то ещё меньше места займёт) при этом если хранить статьи с номерами меньше 999999, то роста БД не происходит.

    Так же можно вытащить номера статей из битовой маски.

    P.S. Жду комментариев :)

  36. Иван Сагалаев

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

  37. Yura Ivanov

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

    Ладно, если связываться с aging, т.е. выполнять какой-либо регламент без участия самих читателей, то тут любой подход подойдет.
    И с интервалами у всех читателей будет (1,1000),(1002,1004)... а для варианта с датой достаточно хранить глобальную дату для 1000 статьи.

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

  38. Иван Сагалаев

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

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

  39. funny_falcon

    Еще вариант неразбавленности статей из разных топиков - форумов

    class Topic(models.Model):
      ...
      forum_topic = models.IntegerField(db_index=True)
      def save(self):
        sv = super(Topic, self).save
        sv()
        if not self.forum_topic:
          self.forum_topic = self.id + self.forum*1000000
          sv()
    
    class Article(models.Model):
      ...
      article_topic = models.FloatField(max_digits=20, decimal_places=0,db_index=True)
      def save(self):
        sv = super(Topic, self).save
        sv()
        if not self.article_topic:
          self.article_topic = self.id + self.topic.forum_topic * 10000
          sv()
    
  40. funny_falcon

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

    select at.article_topic,
        (select max(article_topic) from articles a where a.article_topic < at.article_topic and a.topic_id = at.topic_id) as prev_ar,
        (select min(article_topic) from articles a where a.article_topic > at.article_topic and a.topic_id = at.topic_id) as next_ar
    from articles at where ......
    

    И тогда:

    def compile_ranges(ids):
      ids.sort()
      left = right = None
      for id, iprev, inext  in ids:
        iprev = iprev or id
        inext = inext or id
        if not left:
          left, right = iprev+1, inext-1
        elif iprev >= right: # думаю здесь всё-таки правильно :-)
          right = inext-1
        else:
          yield (left, right)
          left, right = iprev+1, inext-1
      if left:
        yield (left, right)
    
  41. funny_falcon

    Поправка:

    def compile_ranges(ids):
      ids.sort()
      left = right = None
      for id, iprev, inext  in ids:
        i_prev = iprev and iprev+1 or id
        i_next = inext and inext-1 or id
        iprev = iprev or id
        if not left:
          left, right = i_prev, i_next
        elif iprev >= right: # думаю здесь всё-таки правильно :-)
          right = i_next
        else:
          yield (left, right)
          left, right = i_prev, i_next
      if left:
        yield (left, right)
    
  42. GRAy

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

  43. Yura Ivanov

    Много думал... Никак не могу понять, почему рост базы - это плохо?
    - Места на диске жаль? Ну дык сообщения в базе же хранятся, тоже вроде как никуда не собираются деваться, база растет. Пусть служебная инфа будет занимать столько же места, сколько полезная. Ну и что? Чтобы случайный новый читатель стал постоянным посетителем, надо чтоб ему было интересно и удобно тоже. Когда база превысит пару гигов (или сколько там для платного хостинга вменяемая квота?) тогда и чистить ее. Я не знаю, ну например, закрыть старые топики и убить все лишние служебные записи...
    - Тормоза базы? Да ладно... Читаю закрытый форум с 4500 хостов в день. Никаких тормозов в помине нет. Форум до кучи еще и древовидный. Существует 5 лет. Трафик 300-800 поднятых топиков (т.е. по крайней мере одно сообщение в каждом топике добавляется, обычно не менее двух) в день. SQL справляется как-то. Прочитанность хранится именно в базе, и именно для каждого топика и юзера, и именно по дате (новые сообщения подсвечиваются в топике - факт).

    Идеального решения здесь не будет. Слишком жесткие условия ты поставил. Если устраивает отсутствие роста базы в ущерб юзабилити...

  44. Bonart

    Комбинированная схема...
    1. В виде диапазона хранятся читанные топики.
    2. В виде отношения M->M хранятся только топики, не дочитанные до конца, остальные подсвечиваются по дате.
    3. Aging делается для пункта 2.

  45. guest

    По реализации диапазонов: почему бы хранить не тупли, а просто числа:

    [id_последнего_прочитанного в диапазоне, id_последнего_непрочитанного, ...]

    изначально [0,]. выколотая точка будет по прежнему давать два числа, зато на диапазонах будет экономия.

    По задаче: проще всё же делать битмап для каждого пользователя (для 2^10 статей это оверхед в 128кб) + к этому можно добавить номер статьи, с которой начинается битмап. Всякие штуки типа компрессии уже на любителя.

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

  46. Михаил

    сталкивался с подобной проблемой как то. только в больших масштабах.
    сделал чисто на строках вида "1-4,6,8,9-14,17..."
    т.к. даже на тестовых данных у меня было ~5 млн. записей выигрыш от обработки на стороне клиента оказался значительным. правда там в строке больше сотни ID быть не могло в реальной эксплуатации...

Добавить комментарий