一个按时间戳排序导致的 Bug

文章讨论了自己曾经编写分页代码时遇到的一个时间戳相关的排序 BUG。作者发现 PostgreSQL 的时间戳类型的精度为微秒级，这可能导致同一用户创建了多条拥有相同时间戳的记录。这会导致在进行分页查询时，客户端可能遗漏一些记录。作者建议添加一个排序列以解决这个问题。

原文链接：[https://adam-p.ca/blog/2023/12/sort-by-timestamp/](https://adam-p.ca/blog/2023/12/sort-by-timestamp/)

未经允许，禁止转载！

作者 | Adam Pritchard 译者 | 明明如月

责编 | 夏萌

出品 | CSDN（ID：CSDNnews）

在审查同事的分页代码设计时，我回想起自己几年前编写的分页代码中存在一个微妙且不易察觉的错误。尽管这个错误不容易暴露，我仍觉得有必要在这里进行说明，以便其他从事类似编程工作的人（包括将来的我自己）可以规避该问题。

示例表结构如下：

CREATE TABLE item(   id TEXT PRIMARY KEY DEFAULT generate_unique_id(),  created TIMESTAMPTZ NOT NULL DEFAULT NOW(),  -- 省略其他内容

需要注意的是，我们的表中没有类似SERIAL这样的列，因此按时间顺序遍历记录的唯一方法是使用created字段。

客户端将请求 item 表的分页数据，并进行本地持久化存储，随后检查是否存在新的 item。分页查询的基本形式如下：

-- last_known_id is inputSELECT * FROM itemWHERE created > (SELECT created FROM item WHERE id = last_known_id) ORDER BY created ASC LIMIT 10

如果以下两个条件针对每个用户都成立，那么这种方法的确可行：

创建时间戳能够保证唯一性
创建时间戳能够保证单调递增

在编写代码时，我本能地认为这两点是成立的。但几天前，经过深入思考，我很快意识到这些是错误的假设。让我们来探讨它们存在的一些问题……

PostgreSQL 的时间戳类型是微秒级。虽然这个区分度已经非常高，但并非没有重复的可能。理论上，即便是对同一用户，也可能在事务序列化的约束下创建多个具有相同时间戳的记录（这可能需要在一毫秒内启动并提交事务，但这并非不可能）。如果你的数据库操作没有明确的事务约束，这种情况就更常见了。

在 PostgreSQL 中，对于相同值的排序并不具有稳定性。尽管我对 B-tree 索引的理解有限，但据我所知，除非使用特殊类型的索引，或对现有索引进行重建和重新排序，否则对于相同索引值的排序可能不稳定。然而，我们并不应该依赖这一特性。

考虑到操作系统的时钟可能因为网络时间协议（NTP）的更新而被调整回拨（除非采用了缓慢调整时间的 now()方法），在这种情况下，我们就会失去时间的单调性。即使服务重启能比时钟变化快，从而在实际操作中实现时钟的回拨，单调性仍然无法保证。

在数据库服务器配置为一写多读的集群环境中，如果发生故障转移至一个落后于之前写入者的服务器，也会出现类似问题。在时间差异消除之前，now()的值可能会回退到过去。

因此，我们的时间戳既不唯一也不是单调递增的，我们甚至不能保证相同值的稳定排序。这意味着，在进行分页操作时，客户端可能会遗漏某些 item。

单调性失败的场景：如果用户已经下载了时间戳为 X 的 item，但他们在时间戳为 X-1 的时刻创建了一个新 item，那么这个新 item 将无法被用户获取，除非进行全面的重新同步。

唯一性失败的场景：假设用户在时间戳 X 有两个 item，他们检索的最后一个页面包含了这两个 item 中的第一个。那么在后续的分页中，由于查询只寻找时间戳更大的 item，第二个 item 就会被跳过。如果我们修改查询条件为寻找时间戳大于或等于当前 item 的数据，虽然可以解决跳过问题，但可能导致重复 item 的出现。即使这种方式在某些情况下更为合理，但特殊情况下会出现整页的重复 item，这仍然不是一个理想的解决方案。

虽然同一用户在同一微秒内创建两个位于分页边界的 item 的概率很低，且服务器时钟出现严重漂移的可能性也很小，但这种情况仍可能发生，并且一旦发生，后果极其严重。

为了解决这个问题，我建议添加一个排序列。在我们的案例中，这个列只需根据用户进行排序即可，但可能最简单的方法是使用BIGSERIAL类型，并对整个表进行排序。我们可以使用这个新列而不是created字段来进行排序，这样可以确保唯一性和单调性。

以下是几点重要的思考：

时间问题是非常复杂，详见这里。
努力识别自己对事物的基础假设和隐含假设，这是一项艰巨的任务，因为这些假设往往是潜意识中的。
审查别人的代码，当然也要审查自己的代码。这可以迫使你以更广泛、更深入和更多样化的视角思考问题，从而有助于优化自己的代码。

关于这篇文章在 Hacker News 上引发了网友广泛讨论。有网友建议使用“ORDER BY created, id” 来实现稳定排序，而不仅仅是“ORDER BY created”。也有人指出如果 id 是 UUID，按 id 排序也不合适，它不具有连续性。还有网友强调，时间戳的精度不仅仅取决于时间戳类型存储的精度，还取决于获取时间戳的系统调用的准确性。还有网友强调一旦时间是指“特定位置的时间”，就需要存储位置或时区。

你在开发中是否遇到过这个 BUG？你还遇到过哪些类似的 BUG？

本文文字及图片出自 CSDN

一个按时间戳排序导致的 Bug

一个按时间戳排序导致的 Bug

Recommend

时间不对导致vSAN服务无法启动-王春海的博客

各种排序算法时间复杂度和空间复杂度表

JDK的BUG导致的内存溢出续集！

调试实战 | 缺少 const 导致的 bug

antd拖拽列导致触发table排序问题，解决方案

【包管理器】一个由第三方包管理器与npm冲突导致的bug

JVM 锁 bug 导致 G1 GC 挂起问题分析和解决

Android中的严重bug可导致用户媒体文件被访问

tomcat8.x parseHost bug导致的性能损耗

iOS 17 新 Bug ，导致 iPhone 彻底死机!

About Joyk