在GAE上实现按“最热门”排序

2009 12 22 10:54 PM 1423次查看

分类：Google App Engine 标签：Google App Engine, Python

在Nick的博客看到一篇《'Most popular' metrics in App Engine》，读了几天终于断断续续地读完了，于是又转载了过来。

首先介绍下“最热门”吧。对一个网站来说，每篇文章都有浏览数和评论数等数据，这些是由浏览者产生的。而这些数目越高，就表明它的流行度越高，也就越热门。网站可以通过给出当前最热门的文章列表，吸引浏览者阅读更多文章，这就是“最热门”的用意。

不过在GAE上它却不是很容易实现的，因为datastore有很无语的限制：
  • 不能对2个属性进行不等于查询。
  • 一旦对某1属性使用不等于操作，必须先对该属性进行排序。
考虑到流行是有时间性的，几年前发表的文章，可能浏览数和评论数都很多，但没有太多新意或者过时了，浏览者反而没兴趣看，所以查询时肯定是要选择近期的文章，例如本周或本月热门。
但这就表示要对时间进行不等于操作，排序就必须先按时间顺序了，于是流行度就只好靠边站了…

要解决这个问题，在查询时必然不能对时间进行不等于查询，那么将流行度实现为关于时间的函数，并直接对流行度来排序即可。
而Nick正是这样实现的，他采用了Exponential decay（有兴趣的可以读读指数衰减），所用的公式是：N(t) = N0e-t/r。其中，N0是初始值，t是经过的时间，r是衰退率。可以看出，随着时间t的增大，N(t)将迅速减小，这就可以排除过期文章了；而r则可以用于控制过期的快慢。
用Python来表达就是：
def timedelta_to_seconds(delta):
  return delta.days * 86400 + delta.seconds + delta.microseconds / 1000000.0

MEAN_DOWNLOAD_LIFETIME = timedelta_to_seconds(datetime.timedelta(days=7)) # 这个就是r，这里以7天为例

def decay(value, elapsed):
  decay_fraction = timedelta_to_seconds(elapsed) / MEAN_DOWNLOAD_LIFETIME
  return value * (math.e ** -decay_fraction)
注意decay里的elapsed参数，它指的是上一次计算到现在为止经过的时间。由于这个算法的可以将上次的结果作为这次的初始值N0，所以不需要维护一个很长期的数据，这也可以算是一个好处吧。

不过遗憾的是：datastore不支持对函数的查询，因此需要手动更新。
于是接下来就来定义模型了，这是一个文件类，而流行度应该和它的下载量相关：
class File(db.Model):
  popularity = db.FloatProperty(required=True, default=0.0)
  last_decay = db.DateTimeProperty(required=True, auto_now_add=True)

  def update_popularity(self, delta):
    now = datetime.datetime.now()
    self.popularity = decay(self.popularity, now - self.last_decay) + delta
    self.last_decay = now
每次下载时，还需要调用update_popularity方法，这个方法会自动更新它的流行度。（注意计数可以用很多种策略，你可以看看Nick的unsharded counter方法。）

不过这种方法只在下载时才会更新，而有些文件可能很久没下载了，于是流行度就不会变化。
要解决的话可以用计划任务，找出所有较长时间（例如超过6小时）没更新的实体，将它们更新即可：
def decay_old_entities():
  age_threshold = datetime.datetime.now() - datetime.timedelta(hours=6)
  q = File.all().filter('last_decay <', age_threshold).order('last_decay')
  entities = q.fetch(500)
  for entity in entities:
    entity.update_popularity(0)
  db.put(entities)
然而这仍不太好，因为当你的文件很多时，你会不断更新它们的流行度，而实际上你根本不需要更新不流行的文件的流行度。
于是再增加一个is_popular字段，用于标记是否流行即可。
因为懒得去手动计算，所以这里用了个aetycoon的TransformProperty来实现。这个类可以将一个callable对象转成实体的属性，也就是说可以用一个方法来表示属性值。
于是修改如下：
class File(db.Model):
  popularity = db.FloatProperty(required=True, default=0.0)
  last_decay = db.DateTimeProperty(required=True, auto_now_add=True)
  is_popular = aetycoon.TransformProperty(popularity, lambda p: p >= 1.0) # 小于1表示不流行了，例如t大于r了
  # ...
而计划任务也要相应地改下，只选取流行的实体：
def decay_old_entities():
  age_threshold = datetime.datetime.now() - datetime.timedelta(hours=6)
  q = File.all().filter('is_popular', True).filter('last_decay <', age_threshold).order('last_decay')
  entities = q.fetch(500)
  for entity in entities:
    entity.update_popularity(0)
  db.put(entities)
最后，Nick还给了个netboot.me的代码。
其中BootConfiguration类的downloads就相当于popularity，deprecated相当于is_popular。
而下载代码里也是使用unsharded counter方法。

顺带一提，使用memcache时，也可根据流行度来设定失效时间，流行度越高的，就将失效时间设得更长，这样可以提高缓存效率。

0条评论 你不来一发么↓

    想说点什么呢？