如何解决翻页条目重复问题?

之前做糗百和暴漫的时候,由于帖子更新速度很快,所以当用户看完一页帖子之后,翻到下一页,则会发现有一些帖子是跟前一页是重复的。

如果短时间内翻页就出现这种情况,或是每次翻页都会出现这种情况,就非常恼人了,那么如何能解决这个问题?

原理分析

首先我们分析一下问题出现的原理(请原谅我其实不懂数学):

  1. 用户访问的是按id顺序排列的页面:
    这种情况下是不会出现翻页重复的
    当用户在t0时间访问服务器请求第P(P>=1)页时,服务器的帖子列表是a0, a1, a2 … an的一个序列A,服务器根据每页e进行分页,得到了一个A'[p]a[(p-1)*e] .. a[p*e-1]
    对于服务器帖子A来说,下标是单调增加的,然后t1时间(t1>t0),A增加了一个a[n+1]的帖子,对于用户来说,即使t2时间进入p+1页,也可以得到A'[p+1]a[p*e] .. a[(p+1)*e-1]帖子,与之前是没有任何重复的,因为帖子的增加都是在最后的

  2. 用户访问的是按id倒序排列的页面:
    这种排序方式,是最新的排序在最前,目前大部分网站的帖子排序都是这样的

当用户在t0时间访问服务器请求第P页时,服务器的帖子列表是a1, a2 ... an的一个序列A,服务器根据每页e进行分页
由于是id倒叙,则得到了一个A'[p]a[n-(p-1)*e] .. a[n-p*e+1]的序列
下一页p+1页d的记录A'[p+1]则为a[n-p*e] .. a[n-(p+1)*e+1]的序列
假如t1(t1>t0)时间,A增加了一个a[n+1]的帖子,则P和P+1页的序列都会变了
P+1页则会变成A''[p+1]a[n+1-p*e] .. a[n+1-(p+1)*e+1]的序列
如果增加了m条记录,则有可能变成 Am[p] = a[n+m-p*e] .. a[n+m-(p+1)*e+1]

我增加一个起始点s的概念,在t0时刻,s=n,而在t1之后,s=n+m

所以,如果要顺序不变,则需要保证该用户会话中,起始点s始终为n

这时候,可以为每个用户存一个自定义的s,用起作为偏移的参考。(怎么存下面会讲到)

  1. 用户访问的是按某个字段(如热度)排序的页面:
    对于暴漫和糗百首页而言,实际并不是前两种排序,而是按其文章的打分来排序,很多其他网站有按点击率进行排序,分数的计算公式也会很不相同。

这种情况相当复杂,因为这个字段并非单调增长,而且经常会变化,我们先来看一下:

当用户在t0时间访问服务器请求第P页时,服务器的帖子列表是a1, a2 ... an的一个序列A,排序算法为f,f(A)得到此时其排序为S,其第P页的内容为S(a,p)
t1之后,f让A的排序变为了S’,其第P页的内容为S'(a, p)

那么对于用户而言,根据A的对应的热度的变化频率,则翻页是内容变化的概率会很大,并不一定会重复
换句话说,如果用户想得到一个较为稳定的视图,那么我们必须假设用户始终在t0时间的角度来看内容
假设t1对应A的初始状态,t2的变更操作C将A的排序属性变成A’,令S也变成S’
那么我们必须保留t1和t2时候A状态的快照,同时当用户访问网站的时候,记录其所绑定的快照。
这样才能令用户看到一致的结果。

这种情况也可以完全涵盖第二种情况,第二种情况其实是本例的特例

实现方法

说完了原理之后,必须阐述一下实现方法。

首先是比较简单的第2种情况,需要为用户会话绑定一个起始id,这个id可以保存在每个用户的cookie中,或者是保存在服务器端session中,也可以是在翻页的链接上加上一个起始id,比如/articles/latest/page/1?s=100

由于用户在同一时间看到的内容都是相同的,所以其实我们并不需要针对每个不同的用户保存单独的起点信息。

而对于上节描述第三种情况来说,其实早在很久之前数据库就有一种称之为“游标”cursor,可以实现类似的功能。但如今大部分网站都不会使用数据库游标,因为游标会大量消耗数据库服务器的资源。

另一种方式是使用业务层的游标方式。我们可以观察到,对于每一个不同的排列顺序S,产生一个特定的快照,将记录的顺序存下来。
有些网站比如hacker news,便利用了基于continuation的方式,保存了针对每一个排列顺序产生的快照,它的下一页的链接是这种形式的 https://news.ycombinator.com/x?fnid=Y7HN9XBN2kRzQlD5LklRh4 如果用户在页面长时间没有动作,再次点击这个链接的时候,便会显示为“expired link”,表示这个排序方式的快照已经失效了,业务层服务会在每次排名变更之后丢弃之前的排序方式。
但是对于国内大部分网站而言,使用这种简单粗暴的方式是不可行的,可以根据业务需求,保存不同版本的快照,每个快照内的翻页链接都加上快照的版本号。当快照过期之后,把旧的链接重新定向到最新的链接。

如何保存快照?当需要排序的元素数量较小,比如几千几万条,就可以使用单独的数据库表,或者是Redis的Sorted Set,甚至使用Google的leveldb单独做一个Service都可以。

第三种方式是直接进行客户端排序,每次用户新访问的时候,便将排序的顺序都下载到客户端,当服务器端排序方式发生变化的时候通知客户端是否要重新加载最新的排序方式。
由于现在的浏览器都支持JavaScript,还支持localStorage,所以网站已经做成了纯的Web Application,那么如果当记录数量不是很大,一次性下载几千个id,也是可以考虑的方式。但这并不适合直接从服务器端取页面的方式。

综合考虑的解决方案

由于大部分网站的大部分用户,在同一时刻看到的页面是一样的,所以很多网站都会有缓存。同时仔细考虑,对于缓存来说,每个快照S,都会直接对应一组页面缓存C,而客户端则会有另一组缓存C’。

过去由于缓存的页面并没有绑定到快照,排序更新后,缓存的更新也并非同步,有的页面可能根据新的排序更新了,有的可能还没有。
所以,只需要增加一个缓存绑定到排序快照的机制,可以直接将页面缓存视为排序的快照,而无需保存实际的排序方式。
于是我们便可以使用类似于id逆序的方式,为分页的页面缓存增加一个快照id,形如/articles/latest/page/1?s=100,同时当排序发生变化时,把快照id增加1
对于页面缓存的失效时间,则可以根据可容忍的程度进行设置。当请求的快照id 不存在时,则可以跳转至最新的快照id。

这样不用额外保存排序快照,对于网站而言,大部分用户同一时间能复用同一套缓存,提高了性能和效率。

当然,其实对于用户而言,是否真的需要非常准确、无重复的翻页?首先也要从产品设计的层面来考虑。

发表评论

电子邮件地址不会被公开。 必填项已用*标注