开发笔记(1) - Count 问题

July 13, 2016

我们现在的生产环境里面最大的表数据量大概是 1kw 左右。我们这里有一个页面是将这张表里面的数据以列表的方式呈现出来。这个列表的功能有:上一页/下一页、跳页、总数页、数据的总条目数。这是一个很常见的 web 列表拥有的功能,这一系列的功能在数据量 10w 以下工作得很好。超过 10w 后页面 load 就会变得很慢。慢的主要原因是每次刷新操作和跳页操作都会去 Count 整个表,而且是精确的 Count,算法的复杂度为 O(n)。这种方式对于经常需要使用列表页查看数据的用户是完全不可接受的。

我们开始着手优化这个问题。羊毛出在羊身上,我们用的是 Postgresql 的数据库,当然会想到使用 Postgres 的一些功能去做这个事情。很快我们在 Google 搜索到了 Postgresql 的 Count estimate 机制。它通过获取 pg_class 这张元表纪录的信息来得到一个表里面大致的数据量。这种方法非常快,速度可达到毫秒级。但它有以下缺点:1.无法精确统计(从 estimate 这个词的意思就能看出来) 2.只能获取整张表的大致数量,无法做 where 条件过滤。问题到这里似乎还是没有解决。

从程序开发的角度来看,这个问题最好的解决方式是使用一个变量用来保存表的 Count,每次插入删除时需要对这个 Count 变量进行 +1/-1 操作。这样每次需要获取的 Count 时算法复杂度就会降到 O(1),但从整体上看这个问题其实根本没有得到解决。数据库里面一张大表在做 Insert/Remove 时本身已经很慢了,维护这个 Count 变量需要保证原子操作。这么做不仅非常麻烦,还会增加 Insert/Remove 的开销。这里是具体的做法。事情到这里已经很明显了,对于数据库精确的 Count,我们是没有办法开发出一种低于 O(n) 复杂度的算法。但这个问题真的无解了吗?

现在的问题焦点全部都集中在 Count 上面,这个问题看起来是只要 Count 的性能快了,就能解决这个问题。但上面已经说,我们是无法开发出低于 O(n) 复杂度的 Count 算法。1kw 的数据量 O(n) 是无论如何也快不到哪里去的。跳出这个点来看,我们最终要解决的问题是什么?这个 count 的精确数字对用户来说真的能重要到牺牲等待时间来获取吗?其实在这个功能里面我们只所以需要 Count 这个数字仅仅是在做分页时精确需要计算出有多少页,尾页的数字是多少。所以影响这个问题的关键根本不是用户的需求,而是我们在程序开发时所追求的精确。只需要把这个 count 数字去掉就可以了,这将会让列表的操作速度大大的提升。实际上搜索引擎就是这么干的。以 Google 搜索为例,我们在搜索引擎随便输入点东西进行搜索得到得结果是海量的,它只会告诉你“大约”得到多少个结果,结果页展示一页,你并不会知道尾页在哪里(也不需要知道)。