时间戳的原理和意义
两个问题的解决
带宽和查询压力
每个client都会拉取一系列列表数据，典型的如好友列表、群列表、阻止列表、分组列表
等等。这些列表数据与用户的体验密切相关，属于非常重要的数据。为了保证数据的正确拉
取，client最开始采取的做法是，每次登陆拉取这些列表。
后来我们发现用户的列表很少发生改变，于是希望client能够通过某种方式捕捉数据改变
的事件，从而触发拉取动作。这么处理所带来的好处是，client与server之间的流量被减少
了，同时server面临的压力会被减轻。
我们采取的做法是为每个列表数据分配用于标识版本的时间戳。Client在拉取列表数据之
前，先拉取时间戳与本地时间戳进行对比，如果server的数据有更新，client才会发起拉取
操作。
为什么时间戳需要存放在server端呢？考虑如下情况： 机器A
机器BServer版本1
版本2Step 1
Step 2Step 1 用户从机器A迁移至机器B
Step 2 用户从机器B迁移至机器A State 1 用户在机器A使用client，然后拥有数据版本1作为本地存储
State 2 用户在机器B使用client，然后操作了列表数据，拥有数据版本2作为本地存储
State 3 用户回到机器A使用client，本地存储的数据版本实际上已经很低了，需要与server
做一次同步
综上所述，server端需要为每个用户存储时间戳数据，它实际上是由多个时间戳所组成，
每个时间戳代表着一类数据。
通常情况下，列表型的数据拥有自己的时间戳。此外，我们按照变化频率，把用户的属性
数据（如签名档、头像等），分为了不同的时间戳。这里分类的依据是：
1. 基本不变或很少变化的数据合用一个时间戳
2. 变化频率较高的数据合用一个时间戳
对于情况1，可以预料时间戳的版本基本不会发生变化，所以它的确可以起到节省流量的
作用。对于情况2，则对流量的节约作用很有限。
时序问题
对于两台服务器而言，例如chat-dbcache： Chatdbcache
R-f
W-f
cache
drop
inR-bW-b数据版本发生更新
时间时间 1. R-f(read-forward)表示发出读请求
2. W-f(write-forward)表示发出写请求
3. R-b(read-backward)表示读请求处理完毕返回
4. W-b(write-backward)表示写请求处理完毕返回
由上图可知，读请求携带了一份旧数据返回给请求方（这里是chat）。当请求方含有cache
时，由于没有对cache做额外的保护，旧数据会进入cache。这时除了等待cache超时，没
有什么好的办法把旧数据从cache中清除掉。
这个问题的本质是，对于请求方，当write操作返回成功之后，携带旧数据返回的read
操作可能入cache，导致逻辑出现异常。这个问题的解决方案依赖于bitmap+时间戳。首先
介绍bitmap，它在应用程序启动时初始化为0：
Chatdbcache
R-f
W-f
cache
drop
Can’t inR-bW-b数据版本发生更新
时间时间Bitmap <- 0
Bitmap <- 1
clientR-f2Bitmap <- 0
1. R-f之前，把bitmap置为0
2. W-b之后，把bitmap置为1，然后清空cache
3. 把数据加载至cache之前，需要检查bitmap。如果为0，则可以入cache；否则不入cache
第1点的意思是：
性质1 只有r-f才能使bitmap变为0
第2点的意思是：
性质2 只有w-b才能使bitmap变为1
第3点的意思是：
性质3 只有bitmap为0时，数据才能入cache
Bitmap的引入保证了：
定理1 数据入cache的充分必要条件是：
1. 没有w-b 或者
2. w-b之后有r-f2发出
充分性：
由性质3，数据入cache可以推断r-b时bitmap为0。由性质2，应用程序收到r-b的上一
个操作，肯定不是w-b（因为如果是w-b，则bitmap会变为1）。
1） 如果r-b的上一个操作是r-f，则说明没有w-b。
2） 如果r-b的上一个操作是r-fx，由性质1，是否存在w-b不会对bitmap的值造成影响，
因为即使w-b存在，它也一定是在r-fx之前被应用程序接收，那么r-fx发出的时候，
一定会把bitmap置为0
必要性：
1） 没有w-b。由性质2，bitmap不会变为1。则只要有r-f被发起，可以肯定r-b时bitmap
为0，数据入cache
2） W-b之后有r-f2发出，则由性质1，bitmap在r-f2发出之后会变为1，于是r-b时bitmap
为0，数据入cache
综上所述，命题成立。【证毕】
假设服务方保证：
性质4 w-b之后处理的所有r-fx，都拥有最新版本的数据
那么w-b之后发起的r-f2所得到的数据一定是一份新数据。
Bitmap的意义在于写操作之后，应用程序可以获得一次读数据的机会，进而获得一份新
数据，但是bitmap并不能保证这份新数据，可以进入cache中。考虑如下情况： Chatdbcache
R-f
W-f
cache
drop
inR-bW-b数据版本发生更新
时间时间Bitmap <- 0
Bitmap <- 1
clientR-f2Bitmap <- 0
R-b2
由图可知，r-f2的确得到了一份新数据，并在r-b2携带返回。然而由于r-b先返回，且进
入了cache，如果cache的进入是“先入为主”，那么r-b2无法进入cache。
为了解决这个问题，再次引入时间戳的概念。假设r-bx携带的数据都具有一个时间戳作
为版本的标识，那么我们可以依赖这个时间戳限制cache的使用，即：
定理2 “高版本的r-bx可以进入cache” 是cache中的数据不会长时间错误的充分条件。其
中“长时间错误”的意思是，如果cache不超时，则数据会永远存在于cache中。
根据bitmap的时序图，因为高版本r-bx可以进入cache，所以即使低版本r-bx进入cache，
也会被新数据淘汰。因此cache中的数据不会长时间错误。
时间戳的混乱
对比上述两种时间戳。为简单起见，我称它们为A型和B型时间戳。
A型时间戳：解决client-server的流量/查询压力问题
B型时间戳：配合bitmap解决时序问题
这两类时间戳的差异在于，是否关心数据内容。
A型时间戳严格的表示数据的版本。对于client而言，为了保证功能正常，不同版本的数
据必须对应不同版本的时间戳（否则无法获得新数据）；对于server而言，为了保证性能，
相同版本的数据不允许有不同版本的时间戳（否则client会拉取数据，从而破坏提高性能的
初衷）。
B型时间戳不需要关注它所代表的数据版本。由时序问题的背景，我们可以推断出B型时
间戳只是为了解决如下问题：
假设有三个时间点，分别做了三件事情：r-f / w-b / r-f2，其中
r-f 早于 w-b 早于 r-f2
如何标记r-b2比r-b的数据版本新。
一个解决办法是，令r-bx的时间戳等于r-fx的时间戳。对于每次r-fx，都增加B型时间戳的值。这么做的缺点是相同版本的数据，会在cache中不停的被切换；然而优点是，应用程
序可以自己分配B型时间戳，不需要借助服务方的支持。
初看起来觉得这个做法值得推敲。但是这个解决方法可以满足定理2，所以它是正确的：
1） 在没有wb操作的前提下，允许读操作的时序翻转。比如r-f和r-f2的时序发生了翻
转，由于没有wb操作，cache的数据一定是正确的
2） 存在wb操作的前提下，因为r-f2在w-b之后发出，那么由性质4可知，r-f2一定可
以获得一份新数据，这就表示它的数据版本一定大于或等于r-f的数据版本，因此可
以使用r-b2替换r-b