Как вести списки «наиболее популярных в настоящее время» элементов для каждой категории элементов в веб-приложении?

Question

Мне нужно поддерживать списки из 40 недавно добавленных, наиболее популярных / наиболее понравившихся элементов для каждой категории элементов (всего категорий около 2000) в моем приложении. Я храню количество просмотров и нет лайков для каждого элемента. Для этой цели я, вероятно, собираюсь поддерживать структуру в памяти на сервере приложений, чтобы хранить и извлекать этот список элементов.

Есть ли у вас какие-либо идеи о том, как реализовать эту структуру данных в памяти, & , что важно , учитывая связанную с этим занимаемую площадь памяти и сводя ее к минимуму до минимума)?

---

Использование:

Java 1.6

Answer 1

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

In-Memory

Потоки процессора Apache не разделяютпамяти, поэтому лучший способ сделать это, вероятно, установить что-то вроде memcached .Каждый раз, когда вы хотите получить текущие предметы, вы звоните на определенный ключ («topforty»).Memcached остается постоянным, и любой из ваших потоков может вызывать его одновременно.Это хорошо масштабируемое решение.

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

Доменный объект

Если постоянство является более важным,и вы готовы передать согласие с вашей средой веб-приложения, а затем создать службу, которая обрабатывает это:

public interface PopularityService {
  public List<Item> getTopItems(int count);//gets n top items

  //lets the service know someone liked a thing
  public void registerLike(Item item, Person liker);

  //lets the service know someone viewed a 
  public void registerView(Item item, Person viewer);thing
}

Для этого потребуется некоторый объект поддержки:

public class PopularStuff {
  public List<Item> popularItems
  ...
}

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

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

Answer 2

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

Answer 3

Я собираюсь сделать довольно большое предположение, которое заключается в том, что когда вы говорите, что «сохраняете количество просмотров и никаких лайков», вы имеете в виду, что они хранятся в удобном для запросов формате (то есть в базе данных SQL). или эквивалент). Основная причина, по которой вы хотите хранить информацию в памяти, заключается в том, чтобы кэшировать данные, тем самым уменьшая количество вызовов базы данных, необходимых для генерации страницы. Это предположение верно?

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

class TopXCache extends Runnable
{
  Object[] cachedData;

  int secondsToTimeOut;
  String sqlQueryToRefreshCache;

  boolean killSwitch = false;

  constructor(int itemsToKeepInCache, int secondsToTimeOut, String sqlQueryToRefreshCache)
  {
     this.secondsToTimeOut = secondsToTimeOut;
     this.sqlQueryToRefreshCache = sqlQueryToRefreshCache;

     this.cachedData = new Object[itemsToKeepInCache];
  }

  void run() // The method the thread will execute
  {
     while(!killSwitch) // Allows for "poison pill" shutdown
     {
       cachedData = executeQuery(sqlQueryToRefreshCache);
       wait(secondsToTimeOut);
     }
  }

  void kill()
  {
     killSwitch = true;
  }
}

Чтобы создать список, создайте для него экземпляр с временем опроса (secondsToTimeOut), запросом SQL для запуска, который вернет последнюю копию данных (sqlQueryToRefresh) и количество элементов, которые вы хотите в своем списке (itemsToKeepInCache, в ваш случай, 40).

Затем запустите поток, который может выполнить вышеупомянутое (или запланированное задание, или задание библиотеки cron, все, что вы используете для управления синхронизированными событиями в вашем приложении), и ваш кэш периодически обновляется. Если ваша система неожиданно завершает работу, то она будет автоматически перестраиваться из базы данных после перезапуска потока.

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

Кэширование - нормальное решение проблемы такого рода, и обычно ее легче понять и поддерживать в долгосрочной перспективе.

Answer 4

Я делаю то же предположение @Erica, но предоставляю другое решение:

также предполагал, что отношение предмет-категория много ко многим.

import java.util.List;
import java.util.Map;
import java.util.TreeSet;
import javax.ejb.EJB;

@ManagedBean
@RequestScoped
public class ItemBean
{
    @EJB
    private DbService dbService;

    @ManagedProperty("#{categoryCache}")
    private CategoryCache cache;

    public void incrementViewCounter(Item item)
    {
        item.setViewCount(item.getViewCount() + 1);
        dbService.update(item);
        cache.update(item);
    }

    public void incrementLikeCounter(Item item)
    {
        item.setLikeCount(item.getViewCount() + 1);
        dbService.update(item);
        cache.update(item);
    }
}


@ManagedBean
@ApplicationScoped
class CategoryCache
{
    private Map<Integer, ItemSet> categoryMap;

    public void update(Item item)
    {
        ItemReference ref = new ItemReference(item);

        for(Category c : item.getCategoryList())
        {
            ItemSet set = categoryMap.get(c.getId());
            if(set == null)
            {
                set = new ItemSet();
                categoryMap.put(c.getId(), set);
            }

            set.add(ref);
        }
    }
}

class ItemSet extends TreeSet<ItemReference>
{
    private static final int MAX_ENTRIES = 40;

    @Override
    public boolean add(ItemReference ref)
    {
        if(contains(ref)) remove(ref);

        super.add(ref);

        if(size() > MAX_ENTRIES)
        {
            remove(last());
        }

        return true;
    }
}

class ItemReference implements Comparable<ItemReference>
{
    private final Integer id;
    private final Double rank;

    public ItemReference(Item item)
    {
        this.id = item.getId();
        this.rank = item.getViewCount().doubleValue() * 0.1 + item.getLikeCount().doubleValue();
    }

    @Override
    public int compareTo(ItemReference that)
    {
        return -this.getRank().compareTo(that.getRank());
    }

    @Override
    public int hashCode()
    {
        return id.hashCode();
    }

    @Override
    public boolean equals(Object that)
    {
        if(that instanceof ItemReference)
        {
            return this.getId().equals(((ItemReference)that).getId());
        }

        return false;
    }

    public Integer getId()
    {
        return id;
    }

    public Double getRank()
    {
        return rank;
    }
}