AI大模型与向量库 PGVector

新 AI 应用在过去一年中出现了指数爆炸的增长态势,而这些应用面临的一个共同挑战是如何大规模地存储查询以向量表示的 AI Embedding。本文聚焦被 AI 炒火了的向量数据库,介绍了AI嵌入与向量存储检索的基本原理,并用一个具体的知识库检索案例来串联介绍向量数据库插件 PGVECTOR 的功能、性能、获取与应用。


AI是怎么工作的

GPT 展现出来了强大的智能水平,它的成功有很多因素,但在工程上关键的一步是:神经网络与大语言模型将一个语言问题转化为数学问题,并使用工程手段高效解决了这个数学问题

对于AI来说,各种各样的知识与概念在内部都使用数学向量来存储表示输入输出。将词汇/文本/语句/段落/图片/音频各种对象转换为数学向量的这个过程被叫做嵌入Embedding)。

例如 OpenAI 就使用 1536 维的浮点数向量空间。当你问 ChatGPT 一个问题时,输入的文本首先被编码转换成为一个数学向量,才能作为神经网络的输入。而神经网络的直接输出结果,也是一个向量,向量被重新解码为人类的自然语言或其他形式,再呈现到人类眼前。

llm-pgvector-1.jpeg

人工智能大模型的“思考过程”,在数学上就是一系列向量与矩阵之间的加乘正逆运算。这种向量对于人类来说过于抽象,无法理解。但这种形式很适合使用 GPU/FPGA/ASIC 这样的专用硬件来高效实现 —— AI 有了一个硅基的仿生大脑,带有更多的神经元,更快的处理速度,以及更强大的学习算法,惊人的智能水平,高速自我复制与永生的能力。

语言大模型解决的是 编码 - 运算 - 输出 的问题,但是只有计算是不够的,还有一个重要的部分是记忆。大模型本身可以视作人类公开数据集的一个压缩存储,这些知识通过训练被编码到了模型中,内化到了模型的权重参数里。而精确性的,长期性的,过程性的,大容量的外部记忆存储,就需要用到向量数据库了。

llm-pgvector-2.png

所有的概念都可以用向量来表示,而向量空间有一些很好的数学性质,比如可以计算两个向量的“距离”。这意味着任意两个抽象概念之间的“相关性”,都可以用对应编码向量的距离来衡量

这个看上去简单的功能却有着非常强大的效果,例如最经典的应用场景就是搜索。比如,您可以预处理你的知识库,将每个文档都是用模型转换成抽象向量存储在向量数据库中,当你想要检索时,只需要将您的问题也用模型编码成为一个一次性的查询向量,并在数据库中找到与此查询向量“**距离最近“**的文档作为回答返回给用户即可。

llm-pgvector-3.jpeg

通过这种方式,一个模糊而困难的自然语言处理问题,转换成为了一个简单清晰的数学问题。而向量数据库,就可以用来高效地解决这个数学问题。


向量数据库能干什么?

数据库有事务处理(OLTP)与数据分析(OLAP)两大核心场景,向量数据库自然也不例外。典型的事务处理场景包括:知识库,问答,推荐系统,人脸识别,图片搜索,等等等等。知识问答:给出一个自然语言描述的问题,返回与这些输入最为接近的结果;以图搜图:给定一张图片,找出与这张图片在逻辑上最接近的其他相关图片。

这些功能说到底都是一个共同的数学问题:**向量最近邻检索(KNN):**给定一个向量,找到距离此向量最近的其他向量。

典型的分析场景是聚类:将一系列向量按照距离亲疏远近分门别类,找出内在的关联结构,并对比急簇之间的差异。

llm-pgvector-4.jpeg


PG向量插件 PGVECTOR

市面上有许多向量数据库产品,商业的有 Pinecone,Zilliz,开源的有 Milvus,Qdrant 等,基于已有流行数据库以插件形式提供的则有 pgvector 与 Redis Stack。

在所有现有向量数据库中,pgvector 是一个独特的存在 —— 它选择了在现有的世界上最强大的开源关系型数据库 PostgreSQL 上以插件的形式添砖加瓦,而不是另起炉灶做成另一个专用的“数据库” [1]。pgvector 有着优雅简单易用的接口,不俗的性能表现,更是继承了PG生态的超能力集合。

llm-pgvector-5.png

一个合格的向量数据库,首先得是一个合格的数据库,而从零开始做到这一点并不容易比起使用一种全新的独立数据库品类,为现有数据库加装向量搜索的能力显然是一个更为务实,简单,经济的选择


PGVECTOR 知识检索案例

下面我们通过一个具体的例子演示 PGVECTOR 这样的向量数据库是如何工作的。

模型

OpenAI 提供了将自然语言文本转换为数学向量的 API :例如 text-embedding-ada-002 ,便可以将最长2048~8192个字符的句子/文档转换为一个 1536 维的向量。但是这里我们选择使用 HuggingFace 上的 shibing624/text2vec-base-chinese 模型替代 OpenAI 的 API 完成文本到向量的转换。

这个模型针对中文语句进行了优化,尽管没有 OpenAI 模型有那样深入的语义理解能力,但它是开箱即用的,使用 pip install torch text2vec 即可完成安装,而且可以在本地CPU上运行,完全开源免费。您可以随时换用其他模型:基本用法是类似的。

from text2vec import SentenceModel 
# 自动下载并加载模型
model = SentenceModel('shibing624/text2vec-base-chinese')
sentence = '这里是你想编码的文本输入'
vec = model.encode(sentence)

使用以上代码片段即可将任意长度在512内的中文语句编码为 768 维的向量。拆分后只需要调用模型的编码(encode)方法,即可将文本转换为数学向量。对于很长的大文档,您需要合理地将文档与知识库拆分成一系列长度得当的段落。

存储

编码后的结果,在 PostgreSQL 中使用形如 ARRAY[1.1,2.2,...] 这样的浮点数组形式表示。这里我们跳过数据清洗灌入的琐碎细节,总之在一番操作后有了一张语料数据表 sentences,一个 txt 字段来存储原始文本表示,并使用一个额外的 vec 字段存储文本编码后的 768 维向量。

CREATE EXTENSION vector;
CREATE TABLE sentences(id    BIGINT PRIMARY KEY,  -- 标识    txt   TEXT NOT NULL,       -- 文本    vec   VECTOR(768) NOT NULL -- 向量);

这张表和普通的数据库表并没有任何区别,你可以用一模一样的增删改查语句。特殊的地方在于 pgvector 扩展提供了一种新的数据类型 VECTOR ,以及相应的几种距离函数、运算符与对应的索引类型,允许您高效地完成向量最近邻搜索。

查询

这里我们只需要用一个简易的 Python 小脚本,就可以制作一个全文模糊检索的命令行小工具:

# !/usr/bin/env python3
from text2vec import SentenceModel
from psycopg2 import connect

model = SentenceModel('shibing624/text2vec-base-chinese')

def query(question, limit=64):
    vec = model.encode(question)  # 生成一个一次性的编码向量,默认查找最接近的64条记录
    item = 'ARRAY[' + ','.join([str(f) for f in vec.tolist()]) + ']::VECTOR(768)'
    cursor = connect('postgres:///').cursor()
    cursor.execute("""SELECT id, txt, vec <-> %s AS d FROM sentences ORDER BY 3 LIMIT %s;""" % (item, limit))
    for id, txt, distance in cursor.fetchall():
        print("%-6d [%.3f]\t%s" % (id, distance, txt))

llm-pgvector-6.png


PGVECTOR 的性能

当功能、正确性、安全性满足需求后,用户的目光就会转向性能。PGVECTOR 有着不错的性能表现,尽管比起专用的高性能向量计算Library来说有些差距,但性能对于生产环境中使用已经是绰绰有余了。

对于向量数据库来说,最近邻查询的延迟是一个重要的性能指标,ANN-Benchmark 则是一个相对权威的最近邻性能评测基准[2]。pgvector 的索引算法是 ivfflat ,在几个常见的基准测试中表现如下图所示:

llm-pgvector-7.png

为了对 pgvector 的性能表现在直觉上有一个把握,在 M1 Max 芯片 Macbook 下单核运行一些简单的测试:从1百万条随机 1536 维向量(正好是 OpenAI 的输出向量维度)中找出余弦距离最近的TOP 1 ~ 50 条向量,每次耗时大约 8ms 。从 1 亿条随机 128 维向量 (SIFT图像数据集的维度)中找出 L2 欧几里得距离 TOP 1 向量耗时 5ms,TOP 100 耗时也只要 21ms 。

-- 1M 个 1536 维向量,随机取 TOP1~50,余弦距离, 单核:插入与索引耗时均为5~6分钟,大小8GB左右。随机向量最近邻 Top1 召回:8ms
DROP TABLE IF EXISTS vtest; 
CREATE TABLE vtest ( id BIGINT, v  VECTOR(1536) ); 
TRUNCATE vtest;

INSERT INTO vtest SELECT i, random_array(1536)::vector(1536) FROM generate_series(1, 1000000) AS i;
CREATE INDEX ON vtest USING ivfflat (v vector_cosine_ops) WITH(lists = 1000);
WITH probe AS (SELECT random_array(1536)::VECTOR(1536) AS v) 
  SELECT id FROM vtest ORDER BY v <=> (SELECT v FROM probe) limit 1;


-- 简易SIFT ,1亿个128维向量,测试L2距离,召回1个最近向量, 5 ms, 召回最近100个向量:21ms
DROP TABLE IF EXISTS vtest;
CREATE TABLE vtest( id BIGINT, v  VECTOR(128) );
TRUNCATE vtest;

INSERT INTO vtest SELECT i, random_array(128)::vector(128) FROM generate_series(1, 100000000) AS i;
CREATE INDEX ON vtest USING ivfflat (v vector_l2_ops) WITH(lists = 10000);
WITH probe AS (SELECT random_array(128)::VECTOR(128) AS v) 
  SELECT id FROM vtest ORDER BY v <-> (SELECT v FROM probe) limit 1; -- LIMIT 100

使用真实的 SIFT 1M 数据集来测试,找出测试集中1万条向量在1百万条基础向量集中的最近邻单核总共只需18秒,单次查询的延迟在 1.8 ms ,折合单核500 QPS,可以说是相当不错了。当然对于 PostgreSQL 这样的成熟数据库来说,你总可以简单地通过加核数与拖从库来近乎无限地扩容其QPS吞吐量。

-- SIFT 1M 数据集,128维embedding,使用ivfflat索引, L2距离,10K测试向量集。
DROP TABLE IF EXISTS sift_base;
CREATE TABLE sift_base  (id BIGINT PRIMARY KEY , v VECTOR(128));
DROP TABLE IF EXISTS sift_query; 
CREATE TABLE sift_query (id BIGINT PRIMARY KEY , v VECTOR(128));
CREATE INDEX ON sift_base USING ivfflat (v vector_l2_ops) WITH(lists = 1000);

-- 一次性寻找 sift_query 表中 10000 条向量在 sift_base 表中的最近邻 Top1: 单进程 18553ms / 10000 Q = 1.8ms
explain analyze SELECT q.id, s.id FROM sift_query q ,LATERAL (SELECT id FROM sift_base ORDER BY v <-> q.v limit 1) AS s; 

-- 单次随机查询耗时在 个位数毫秒
WITH probe AS (SELECT v AS query FROM sift_query WHERE id =  (random() * 999)::BIGINT LIMIT 1)
  SELECT id FROM sift_base ORDER BY v <-> (SELECT query FROM probe) LIMIT 1;

如何获取 PGVECTOR?

最后,我们来聊一聊,如何快速获取一个可用的 PGVECTOR ?

在以前,PGVECTOR 需要自行下载编译安装,所以我提了一个 Issue 把它加入到 PostgreSQL 全球开发组的官方仓库中[5]。你只需要正常使用 PGDG 源即可直接 yum install pgvector_15 完成安装。在安装了 pgvector 的数据库实例中使用 CREATE EXTENSION vector 即可启用此扩展。

CREATE EXTENSION vector;
CREATE TABLE items (vec vector(2));
INSERT INTO items (vec) VALUES ('[1,1]'), ('[-2,-2]'), ('[-3,4]');
SELECT *, vec <=> '[0,1]' AS d FROM items ORDER BY 2 LIMIT 3;

更简单的选择是本地优先的开源 RDS PostgreSQL 替代 —— Pigsty ,在三月底发布的v2.0.2 中, pgvector 已经默认启用,开箱即用。您可以在一台全新虚拟机上一键完成安装,自带时序地理空间向量插件,监控备份高可用齐全。分文不收,立等可取。

llm-pgvector-8.png

Supabase,Neon 也提供了带有 pgvector 插件的付费托管 PostgreSQL 服务,AWS RDS for PostgreSQL 也已经在五月初刚刚支持了此扩展 。提供托管服务的完整供应商列表可以参考 pgvector 的 Github Issue [6]。


参考

[1] PGVECTOR GitHub仓库

[2] ANN性能评测基准

[3] 使用 PGVECTOR 存储 OpenAI 嵌入

[4] 文本与代码嵌入

[5] Add official RPM package and inclusion in PGDG YUM repository

[6] PGVector Hosted Providers

高级模糊查询的实现

如何在PostgreSQL中实现比较复杂的模糊查询逻辑?

日常开发中,经常见到有模糊查询的需求。今天就简单聊一聊如何用PostgreSQL实现一些高级一点的模糊查询。

当然这里说的模糊查询,不是LIKE表达式前模糊后模糊两侧模糊,这种老掉牙的东西。让我们直接用一个具体的例子开始吧。

问题

现在,假设我们做了个应用商店,想给用户提供搜索功能。用户随便输入点什么,找出所有与输入内容匹配的应用,排个序返回给用户。

严格来说,这种需求其实是需要一个搜索引擎,最好还是用专用软件,例如ElasticSearch来搞。但实际上只要不是特别复杂的逻辑,也可以很好的用PostgreSQL实现。

数据

样例数据如下所示,一张应用表。抽除了所有无关字段,就留下一个应用名称name作为主键。

CREATE TABLE app(name TEXT PRIMARY KEY); 
-- COPY app FROM '/tmp/app.csv';

里面的数据差不多长这样,中英混杂,共计150万条。

Rome travel guide, rome italy map rome tourist attractions directions to colosseum, vatican museum, offline ATAC city rome bus tram underground train maps, 罗马地图,罗马地铁,罗马火车,罗马旅行指南"""
Urban Pics - 游戏俚语词典
世界经典童话故事大全(6到12岁少年儿童睡前故事英语亲子软件) 2 - 高级版
星征服者
客房控制系统
Santa ME! - 易圣诞老人,小精灵快乐的脸效果!

输入

用户在搜索框可能输入的东西,差不多就跟你自己在应用商店搜索框里会键入的东西差不多。“天气”,“外卖”,“交友”……

而我们想做到的效果,跟你对应用商店查询返回结果的期待也差不多。当然是越准确越好,最好还能按相关度排个序。

当然,作为一个生产级的应用,还必须能及时响应。不可以全表扫描,得用到索引。

那么,这类问题怎么解呢?

解题思路

针对这一问题,有三种解题思路。

  • 基于LIKE的模式匹配。
  • 基于pg_trgm的字符串相似度的匹配
  • 基于自定义分词与倒排索引的模糊查询

LIKE模式匹配

最简单粗暴的方式就是使用 LIKE '%' 模式匹配查询。

老生常谈,没啥技术含量。把用户输入的关键词前后加一个百分号,然后执行这种查询:

SELECT * FROM app WHERE name LIKE '%支付宝%';

前后模糊的查询可以通过常规的Btree索引进行加速,注意在PostgreSQL中使用 LIKE查询时不要掉到LC_COLLATE的坑里去了,详情参考这篇文章:PG中的本地化排序规则

CREATE INDEX ON app(name COLLATE "C");          -- 后模糊
CREATE INDEX ON app(reverse(name) COLLATE "C"); -- 前模糊

如果用户的输入非常精准清晰,这样的方式也不是不可以。响应速度也不错。但有两个问题:

  • 太机械死板,假设应用厂商发了个名字,在原来的关键词里面加了个空格或者什么符号,这种查询立刻就失效了。

  • 没有距离度量,我们没有一个合适的度量,来排序返回的结果。说如果返回几百个结果没有排序,那很难让用户满意的。

  • 有时候准确度还是不行,比如一些应用做SEO,把各种头部应用的名字都嵌到自己的名字中来提高搜索排名。

PG TRGM

PostgreSQL自带了一个名为pg_trgm的扩展,提供的基于三字符语素的模糊查询。

pg_trgm模块提供用于决定基于 trigram 匹配的字母数字文本相似度的函数和操作符,以及支持快速搜索相似字符串的索引操作符类。

使用方式

-- 使用trgm操作符提取关键词素,并建立gist索引
CREATE INDEX ON app USING gist (name gist_trgm_ops);

查询方式也很直观,直接使用% 运算符即可,比如从应用表中查到与支付宝相关的应用。

SELECT name, similarity(name, '支付宝') AS sim FROM app 
WHERE name % '支付宝'  ORDER BY 2 DESC;

         name          |     sim
-----------------------+------------
 支付宝 - 让生活更简单 | 0.36363637
 支付搜                | 0.33333334
 支付社                | 0.33333334
 支付啦                | 0.33333334
(4 rows)

Time: 231.872 ms

Sort  (cost=177.20..177.57 rows=151 width=29) (actual time=251.969..251.970 rows=4 loops=1)
"  Sort Key: (similarity(name, '支付宝'::text)) DESC"
  Sort Method: quicksort  Memory: 25kB
  ->  Index Scan using app_name_idx1 on app  (cost=0.41..171.73 rows=151 width=29) (actual time=145.414..251.956 rows=4 loops=1)
        Index Cond: (name % '支付宝'::text)
Planning Time: 2.331 ms
Execution Time: 252.011 ms

该方式的优点是

  • 提供了字符串的距离函数similarity,可以给出两个字符串之间相似程度的定性度量。因此可以排序。
  • 提供了基于3字符组合的分词函数show_trgm
  • 可以利用索引加速查询。
  • SQL查询语句非常简单清晰,索引定义也很简单明了,维护简单

该方式的缺点是:

  • 关键词很短的情况(1-2汉字)的情况下召回率很差,特别是只有一个字时,是无法查询出结果的
  • 执行效率较低,例如上面这个查询使用了200ms
  • 定制性太差,只能使用它自己定义的逻辑来定义字符串的相似度,而且这个度量对于中文的效果相当存疑(中文三字词频率很低)
  • LC_CTYPE有特殊的要求,默认LC_CTYPE = C 无法正确对中文进行分词。

特殊问题

pg_trgm的最大问题是,无法在LC_CTYPE = C的实例上针对中文使用。因为 LC_CTYPE=C 缺少一些字符的分类定义。不幸的是LC_CTYPE一旦设置,基本除了重新建库是没法更改的

通常来说,PostgreSQL的Locale应当设置为C,或者至少将本地化规则中的排序规则LC_COLLATE 设置为C,以避免巨大的性能损失与功能缺失。但是因为pg_trgm的这个“问题”,您需要在创建库时,即指定LC_CTYPE = <non-C-locale>。这里基于i18n的LOCALE从原理上应该都可以使用。常见的en_USzh_CN都是可以的。但注意特别注意,macOS上对Locale的支持存在问题。过于依赖LOCALE的行为会降低代码的可移植性。

高级模糊查询

实现一个高级的模糊查询,需要两样东西:分词倒排索引

高级模糊查询,或者说全文检索基于以下思路实现:

  • 分词:在维护阶段,每一个被模糊搜索的字段(例如应用名称),都会被分词逻辑加工处理成一系列关键词。
  • 索引:在数据库中建立关键词到表记录的倒排索引
  • 查询:将查询同样拆解为关键词,然后利用查询关键词通过倒排索引找出相关的记录来。

PostgreSQL内建了很多语言的分词程序,可以自动将文档拆分为一系列的关键词,是为全文检索功能。可惜中文还是比较复杂,PG并没有内建的中文分词逻辑,虽然有一些第三方扩展,诸如 pg_jieba, zhparser等,但也年久失修,在新版本的PG上能不能用还是一个问题。

但是这并不影响我们利用PostgreSQL提供的基础设施实现高级模糊查询。实际上上面说的分词逻辑是为了从一个很大的文本(例如网页)中抽取摘要信息(关键字)。而我们的需求恰恰相反,不仅不是抽取摘要进行概括精简,而且需要将关键词扩充,以实现特定的模糊需求。例如,我们完全可以在抽取应用名称关键词的过程中,把这些关键词的汉语拼音,首音缩写,英文缩写一起放进关键词列表中,甚至把作者,公司,分类,等一系列用户可能感兴趣的东西放进去。这样搜索的时候就可以使用丰富的输入了。

基本框架

我们先来构建整个问题解决的框架。

  1. 编写一个自定义的分词函数,从名称中抽取关键词(每个字,每个二字短语,拼音,英文缩写,放什么都可以)
  2. 在目标表上创建一个使用分词函数的函数表达式GIN索引。
  3. 通过数组操作或 tsquery 等方式定制你的模糊查询
-- 创建一个分词函数
CREATE OR REPLACE FUNCTION tokens12(text) returns text[] as $$....$$;

-- 基于该分词函数创建表达式索引
CREATE INDEX ON app USING GIN(tokens12(name));

-- 使用关键词进行复杂的定制查询(关键词数组操作)
SELECT * from app where split_to_chars(name) && ARRAY['天气'];

-- 使用关键词进行复杂的定制查询(tsquery操作)
SELECT * from app where to_tsvector123(name) @@ 'BTC &! 钱包 & ! 交易 '::tsquery;

PostgreSQL 提供了GIN索引,可以很好的支持倒排索引的功能,比较麻烦的是寻找一种比较合适的中文分词插件。将应用名称分解为一系列关键词。好在对于此类模糊查询的需求,也用不着像搞搜索引擎,自然语言处理那么精细的语义解析。只要参考pg_trgm的思路把中文也给手动一锅烩了就行。除此之外,通过自定义的分词逻辑,还可以实现很多有趣的功能。比如使用拼音模糊查询,使用拼音首字母缩写模糊查询

让我们从最简单的分词开始。

快速开始

首先来定义一个非常简单粗暴的分词函数,它只是把输入拆分成2字词语的组合。

-- 创建分词函数,将字符串拆为单字,双字组成的词素数组
CREATE OR REPLACE FUNCTION tokens12(text) returns text[] AS $$
DECLARE
    res TEXT[];
BEGIN
    SELECT regexp_split_to_array($1, '') INTO res;
    FOR i in 1..length($1) - 1 LOOP
            res := array_append(res, substring($1, i, 2));
    END LOOP;
    RETURN res;
END;
$$ LANGUAGE plpgsql STRICT PARALLEL SAFE IMMUTABLE;

使用这个分词函数,可以将一个应用名称肢解为一系列的语素

SELECT tokens2('艾米莉的埃及历险记');
-- {艾米,米莉,莉的,的埃,埃及,及历,历险,险记}

现在假设用户搜索关键词“艾米利”,这个关键词被拆分为:

SELECT tokens2('艾米莉');
-- {艾米,米莉}

然后,我们可以通过以下查询非常迅速地,找到所有包含这两个关键词素的记录:

SELECT * FROM app WHERE tokens2(name) @> tokens2('艾米莉');
 美味餐厅 - 艾米莉的圣诞颂歌
 美味餐厅 - 艾米莉的瓶中信笺
 小清新艾米莉
 艾米莉的埃及历险记
 艾米莉的极地大冒险
 艾米莉的万圣节历险记
 6rows / 0.38ms

这里通过关键词数组的倒排索引,可以快速实现前后模糊的效果。

这里的条件比较严格,应用需要完整的包含两个关键词才会匹配。

如果我们改用更宽松的条件来执行模糊查询,例如,只要包含任意一个语素:

SELECT * FROM app WHERE tokens2(name) && tokens2('艾米莉');

 AR艾米互动故事-智慧妈妈必备
 Amy and train 艾米和小火车
 米莉·马洛塔的涂色探索
 给利伴_艾米罗公司旗下专业购物返利网
 艾米团购
 记忆游戏 - 米莉和泰迪
 (56 row ) / 0.4 ms

那么可供近一步筛选的应用候选集就更宽泛了。同时执行时间也并没有发生巨大的变化。

更近一步,我们并不需要在查询中使用完全一致的分词逻辑,完全可以手工进行精密的查询控制。

我们完全可以通过数组的布尔运算,控制哪些关键词是我们想要的,哪些是不想要的,哪些可选,哪些必须。

-- 包含关键词 微信、红包,但不包含 ‘支付’ (1ms | 11 rows)
SELECT * FROM app WHERE tokens2(name) @> ARRAY['微信','红包'] 
AND NOT tokens2(name) @> ARRAY['支付'];

当然,也可以对返回的结果进行相似度排序。一种常用的字符串似度衡量是L式编辑距离,即一个字符串最少需要多少次单字编辑才能变为另一个字符串。这个距离函数levenshtein 在PG的官方扩展包fuzzystrmatch中提供。

-- 包含关键词 微信 的应用,按照L式编辑距离排序 ( 1.1 ms | 10 rows)
-- create extension fuzzystrmatch;
SELECT name, levenshtein(name, '微信') AS d 
FROM app WHERE tokens12(name) @> ARRAY['微信'] 
ORDER BY 2 LIMIT 10;

 微信           | 0
 微信读书       | 2
 微信趣图       | 2
 微信加密       | 2
 企业微信       | 2
 微信通助手     | 3
 微信彩色消息   | 4
 艺术微信平台网 | 5
 涂鸦画板- 微信 | 6
 手写板for微信  | 6

改进全文检索方式

接下来,我们可以对分词的方式进行一些改进:

  • 缩小关键词范围:将标点符号从关键词中移除,将语气助词(的得地,啊唔之乎者也)之类排除掉。(可选)
  • 扩大关键词列表:将已有关键词的汉语拼音,首字母缩写一并加入关键词列表。
  • 优化关键词大小:针对单字,3字短语,4字成语进行提取与优化。中文不同于英文,英文拆分为3字符的小串效果很好,中文信息密度更大,单字或双字就有很大的区分度了。
  • 去除重复关键词:例如前后重复出现,或者通假字,同义词之类的。
  • 跨语言分词处理,例如中西夹杂的名称,我们可以分别对中英文进行处理,中日韩字符采用中式分词处理逻辑,英文字母使用常规的pg_trgm处理逻辑。

实际上也不一定用得着这些逻辑,而这些逻辑也不一定非要在数据库里用存储过程实现。比较好的方式当然是在外部读取数据库然后使用专用的分词库和自定义业务逻辑来进行分词,分完之后再回写到数据表的另一列上。

当然这里出于演示目的,我们就直接用存储过程直接上了,实现一个比较简单的改进版分词逻辑。

CREATE OR REPLACE FUNCTION cjk_to_tsvector(_src text) RETURNS tsvector AS $$
DECLARE
    res TEXT[]:= show_trgm(_src);
    cjk TEXT; -- 中日韩连续文本段
BEGIN
    FOR cjk IN SELECT unnest(i) FROM regexp_matches(_src,'[\u4E00-\u9FCC\u3400-\u4DBF\u20000-\u2A6D6\u2A700-\u2B81F\u2E80-\u2FDF\uF900-\uFA6D\u2F800-\u2FA1B]+','g') regex(i) LOOP
            FOR i in 1..length(cjk) - 1 LOOP
                    res := array_append(res, substring(cjk, i, 2));
                END LOOP; -- 将每个中日韩连续文本段两字词语加入列表
        END LOOP;
    return array_to_tsvector(res);
end
$$ LANGUAGE PlPgSQL PARALLEL SAFE COST 100 STRICT IMMUTABLE;


-- 如果需要使用标签数组的方式,可以使用此函数。
CREATE OR REPLACE FUNCTION cjk_to_array(_src text) RETURNS TEXT[] AS $$
BEGIN
    RETURN tsvector_to_array(cjk_to_tsvector(_src));
END
$$ LANGUAGE PlPgSQL PARALLEL SAFE COST 100 STRICT IMMUTABLE;

-- 创建分词专用函数索引
CREATE INDEX ON app USING GIN(cjk_to_array(name));

基于 tsvector

除了基于数组的运算之外,PostgreSQL还提供了tsvectortsquery类型,用于全文检索。

我们可以使用这两种类型的运算取代数组之间的运算,写出更灵活的查询来:

CREATE OR REPLACE FUNCTION to_tsvector123(src text) RETURNS tsvector AS $$
DECLARE
    res TEXT[];
    n INTEGER:= length(src);
begin
    SELECT regexp_split_to_array(src, '') INTO res;
    FOR i in 1..n - 2 LOOP res := array_append(res, substring(src, i, 2));res := array_append(res, substring(src, i, 3)); END LOOP;
    res := array_append(res, substring(src, n-1, 2));
    SELECT array_agg(distinct i) INTO res FROM (SELECT i FROM unnest(res) r(i) EXCEPT SELECT * FROM (VALUES(' '),(','),('的'),('。'),('-'),('.')) c ) d; -- optional (normalize)
    RETURN array_to_tsvector(res);
end
$$ LANGUAGE PlPgSQL PARALLEL SAFE COST 100 STRICT IMMUTABLE;

-- 使用自定义分词函数,创建函数表达式索引
CREATE INDEX ON app USING GIN(to_tsvector123(name));

使用tsvector进行查询的方式也相当直观

-- 包含 '学英语' 和 '雅思'
SELECT * from app where to_tsvector123(name) @@ '学英语 & 雅思'::tsquery;

-- 所有关于 'BTC' 但不含'钱包' '交易'字样的应用
SELECT * from app where to_tsvector123(name) @@ 'BTC &! 钱包 & ! 交易 '::tsquery;

参考文章:

PostgreSQL 模糊查询最佳实践 - (含单字、双字、多字模糊查询方法)

https://developer.aliyun.com/article/672293

前后端通信线缆协议

了解PostgreSQL服务器与客户端通信使用的TCP协议,并使用Go语言打印消息

了解PostgreSQL服务器与客户端通信使用的TCP协议


启动阶段

启动阶段的基本流程如下所示:

  • 客户端发送一条StartupMessage (F)向服务端发起连接请求

    载荷包括0x30000的Int32版本号魔数,以及一系列kv结构的运行时参数(NULL0分割,必须参数为user),

  • 客户端等待服务端响应,主要是等待服务端发送的ReadyForQuery (Z)事件,该事件代表服务端已经准备好接收请求。

上面是连接建立过程中最主要的两个事件,其他事件包括包括认证消息 AuthenticationXXX (R) ,后端密钥消息 BackendKeyData (K),错误消息ErrorResponse (E),一系列上下文无关消息(NoticeResponse (N)NotificationResponse (A)ParameterStatus(S)

我们可以编写一个go程序模拟这一过程:

package main

import (
	"fmt"
	"net"
	"time"

	"github.com/jackc/pgx/pgproto3"
)

func GetFrontend(address string) *pgproto3.Frontend {
	conn, _ := (&net.Dialer{KeepAlive: 5 * time.Minute}).Dial("tcp4", address)
	frontend, _ := pgproto3.NewFrontend(conn, conn)
	return frontend
}

func main() {
	frontend := GetFrontend("127.0.0.1:5432")

	// 建立连接
	startupMsg := &pgproto3.StartupMessage{
		ProtocolVersion: pgproto3.ProtocolVersionNumber,
		Parameters:      map[string]string{"user": "vonng"},
	}
	frontend.Send(startupMsg)

	// 启动过程,收到ReadyForQuery消息代表启动过程结束
	for {
		msg, _ := frontend.Receive()
		fmt.Printf("%T %v\n", msg, msg)
		if _, ok := msg.(*pgproto3.ReadyForQuery); ok {
			fmt.Println("[STARTUP] connection established")
			break
		}
	}

	// 简单查询协议
	simpleQueryMsg := &pgproto3.Query{String: `SELECT 1 as a;`}
	frontend.Send(simpleQueryMsg)
	// 收到CommandComplete消息代表查询结束
	for {
		msg, _ := frontend.Receive()
		fmt.Printf("%T %v\n", msg, msg)
		if _, ok := msg.(*pgproto3.CommandComplete); ok {
			fmt.Println("[QUERY] query complete")
			break
		}
	}
}

输出结果为:

*pgproto3.Authentication &{0 [0 0 0 0] [] []}
*pgproto3.ParameterStatus &{application_name }
*pgproto3.ParameterStatus &{client_encoding UTF8}
*pgproto3.ParameterStatus &{DateStyle ISO, MDY}
*pgproto3.ParameterStatus &{integer_datetimes on}
*pgproto3.ParameterStatus &{IntervalStyle postgres}
*pgproto3.ParameterStatus &{is_superuser on}
*pgproto3.ParameterStatus &{server_encoding UTF8}
*pgproto3.ParameterStatus &{server_version 11.3}
*pgproto3.ParameterStatus &{session_authorization vonng}
*pgproto3.ParameterStatus &{standard_conforming_strings on}
*pgproto3.ParameterStatus &{TimeZone PRC}
*pgproto3.BackendKeyData &{35703 345830596}
*pgproto3.ReadyForQuery &{73}
[STARTUP] connection established
*pgproto3.RowDescription &{[{a 0 0 23 4 -1 0}]}
*pgproto3.DataRow &{[[49]]}
*pgproto3.CommandComplete &{SELECT 1}
[QUERY] query complete

连接代理

可以在jackc/pgx/pgproto3的基础上,很轻松地编写一些中间件。例如下面的代码就是一个非常简单的“连接代理”:

package main

import (
	"io"
	"net"
	"strings"
	"time"

	"github.com/jackc/pgx/pgproto3"
)

type ProxyServer struct {
	UpstreamAddr string
	ListenAddr   string
	Listener     net.Listener
	Dialer       net.Dialer
}

func NewProxyServer(listenAddr, upstreamAddr string) *ProxyServer {
	ln, _ := net.Listen(`tcp4`, listenAddr)
	return &ProxyServer{
		ListenAddr:   listenAddr,
		UpstreamAddr: upstreamAddr,
		Listener:     ln,
		Dialer:       net.Dialer{KeepAlive: 1 * time.Minute},
	}
}

func (ps *ProxyServer) Serve() error {
	for {
		conn, err := ps.Listener.Accept()
		if err != nil {
			panic(err)
		}
		go ps.ServeOne(conn)
	}
}

func (ps *ProxyServer) ServeOne(clientConn net.Conn) error {
	backend, _ := pgproto3.NewBackend(clientConn, clientConn)
	startupMsg, err := backend.ReceiveStartupMessage()
	if err != nil && strings.Contains(err.Error(), "ssl") {
		if _, err := clientConn.Write([]byte(`N`)); err != nil {
			panic(err)
		}
		// ssl is not welcome, now receive real startup msg
		startupMsg, err = backend.ReceiveStartupMessage()
		if err != nil {
			panic(err)
		}
	}

	serverConn, _ := ps.Dialer.Dial(`tcp4`, ps.UpstreamAddr)
	frontend, _ := pgproto3.NewFrontend(serverConn, serverConn)
	frontend.Send(startupMsg)

	errChan := make(chan error, 2)
	go func() {
		_, err := io.Copy(clientConn, serverConn)
		errChan <- err
	}()
	go func() {
		_, err := io.Copy(serverConn, clientConn)
		errChan <- err
	}()

	return <-errChan
}

func main() {
	proxy := NewProxyServer("127.0.0.1:5433", "127.0.0.1:5432")
	proxy.Serve()
}

这里代理监听5433端口,并将消息解析并转发至在5432端口的真实的数据库服务器。在另一个Session中执行以下命令:

$ psql postgres://127.0.0.1:5433/data?sslmode=disable -c 'SELECT * FROM pg_stat_activity LIMIT 1;'

可以观察到这一过程中的消息往来:

[B2F] *pgproto3.ParameterStatus &{application_name psql}
[B2F] *pgproto3.ParameterStatus &{client_encoding UTF8}
[B2F] *pgproto3.ParameterStatus &{DateStyle ISO, MDY}
[B2F] *pgproto3.ParameterStatus &{integer_datetimes on}
[B2F] *pgproto3.ParameterStatus &{IntervalStyle postgres}
[B2F] *pgproto3.ParameterStatus &{is_superuser on}
[B2F] *pgproto3.ParameterStatus &{server_encoding UTF8}
[B2F] *pgproto3.ParameterStatus &{server_version 11.3}
[B2F] *pgproto3.ParameterStatus &{session_authorization vonng}
[B2F] *pgproto3.ParameterStatus &{standard_conforming_strings on}
[B2F] *pgproto3.ParameterStatus &{TimeZone PRC}
[B2F] *pgproto3.BackendKeyData &{41588 1354047533}
[B2F] *pgproto3.ReadyForQuery &{73}
[F2B] *pgproto3.Query &{SELECT * FROM pg_stat_activity LIMIT 1;}
[B2F] *pgproto3.RowDescription &{[{datid 11750 1 26 4 -1 0} {datname 11750 2 19 64 -1 0} {pid 11750 3 23 4 -1 0} {usesysid 11750 4 26 4 -1 0} {usename 11750 5 19 64 -1 0} {application_name 11750 6 25 -1 -1 0} {client_addr 11750 7 869 -1 -1 0} {client_hostname 11750 8 25 -1 -1 0} {client_port 11750 9 23 4 -1 0} {backend_start 11750 10 1184 8 -1 0} {xact_start 11750 11 1184 8 -1 0} {query_start 11750 12 1184 8 -1 0} {state_change 11750 13 1184 8 -1 0} {wait_event_type 11750 14 25 -1 -1 0} {wait_event 11750 15 25 -1 -1 0} {state 11750 16 25 -1 -1 0} {backend_xid 11750 17 28 4 -1 0} {backend_xmin 11750 18 28 4 -1 0} {query 11750 19 25 -1 -1 0} {backend_type 11750 20 25 -1 -1 0}]}
[B2F] *pgproto3.DataRow &{[[] [] [52 56 55 52] [] [] [] [] [] [] [50 48 49 57 45 48 53 45 49 56 32 50 48 58 52 56 58 49 57 46 51 50 55 50 54 55 43 48 56] [] [] [] [65 99 116 105 118 105 116 121] [65 117 116 111 86 97 99 117 117 109 77 97 105 110] [] [] [] [] [97 117 116 111 118 97 99 117 117 109 32 108 97 117 110 99 104 101 114]]}
[B2F] *pgproto3.CommandComplete &{SELECT 1}
[B2F] *pgproto3.ReadyForQuery &{73}
[F2B] *pgproto3.Terminate &{}

事务隔离等级注意事项

PostgreSQL实际上只有两种事务隔离等级:读已提交(Read Commited)可序列化(Serializable)

PostgreSQL实际上只有两种事务隔离等级:读已提交(Read Commited)可序列化(Serializable)


基础

SQL标准定义了四种隔离级别,但PostgreSQL实际上只有两种事务隔离等级:读已提交(Read Commited)可序列化(Serializable)

SQL标准定义了四种隔离级别,但实际上这也是很粗鄙的一种划分。详情请参考并发异常那些事

查看/设置事务隔离等级

通过执行:SELECT current_setting('transaction_isolation'); 可以查看当前事务隔离等级。

通过在事务块顶部执行 SET TRANSACTION ISOLATION LEVEL { SERIALIZABLE | REPEATABLE READ | READ COMMITTED | READ UNCOMMITTED } 来设定事务的隔离等级。

或者为当前会话生命周期设置事务隔离等级:

SET SESSION CHARACTERISTICS AS TRANSACTION transaction_mode

Actual isolation level P4 G-single G2-item G2
RC(monotonic atomic views) - - - -
RR(snapshot isolation) - -
Serializable

隔离等级与并发问题

创建测试表 t ,并插入两行测试数据。

CREATE TABLE t (k INTEGER PRIMARY KEY, v int);
TRUNCATE t; INSERT INTO t VALUES (1,10), (2,20);

更新丢失(P4)

PostgreSQL的 读已提交RC 隔离等级无法阻止丢失更新的问题,但可重复读隔离等级则可以。

丢失更新,顾名思义,就是一个事务的写入覆盖了另一个事务的写入结果。

在读已提交隔离等级下,无法阻止丢失更新的问题,考虑一个计数器并发更新的例子,两个事务同时从计数器中读取出值,加1后写回原表。

T1 T2 Comment
begin;
begin;
SELECT v FROM t WHERE k = 1 T1读
SELECT v FROM t WHERE k = 1 T2读
update t set v = 11 where k = 1; T1写
update t set v = 11 where k = 1; T2因T1阻塞
COMMIT T2恢复,写入
COMMIT T2写入覆盖T1

解决这个问题有两种方式,使用原子操作,或者在可重复读的隔离等级执行事务。

使用原子操作的方式为:

T1 T2 Comment
begin;
begin;
update t set v = v+1 where k = 1; T1写
update t set v = v + 1 where k = 1; T2因T1阻塞
COMMIT T2恢复,写入
COMMIT T2写入覆盖T1

解决这个问题有两种方式,使用原子操作,或者在可重复读的隔离等级执行事务。

在可重复读的隔离等级

读已提交(RC)

begin; set transaction isolation level read committed; -- T1
begin; set transaction isolation level read committed; -- T2

update t set v = 11 where k = 1; -- T1
update t set v = 12 where k = 1; -- T2, BLOCKS
update t set v = 21 where k = 2; -- T1

commit; -- T1. This unblocks T2
select * from t; -- T1. Shows 1 => 11, 2 => 21
update t set v = 22 where k = 2; -- T2


commit; -- T2
select * from test; -- either. Shows 1 => 12, 2 => 22
T1 T2 Comment
begin; set transaction isolation level read committed;
begin; set transaction isolation level read committed;
update t set v = 11 where k = 1;
update t set v = 12 where k = 1; T2会等待T1持有的锁
SELECT * FROM t 2:20, 1:11
update pair set v = 21 where k = 2;
commit; T2解锁
select * from pair; T2看见T1的结果和自己的修改
update t set v = 22 where k = 2
commit

提交后的结果

1

 relname | locktype | virtualtransaction |  pid  |       mode       | granted | fastpath
---------+----------+--------------------+-------+------------------+---------+----------
 t_pkey  | relation | 4/578              | 37670 | RowExclusiveLock | t       | t
 t       | relation | 4/578              | 37670 | RowExclusiveLock | t       | t
 relname | locktype | virtualtransaction |  pid  |       mode       | granted | fastpath
---------+----------+--------------------+-------+------------------+---------+----------
 t_pkey  | relation | 4/578              | 37670 | RowExclusiveLock | t       | t
 t       | relation | 4/578              | 37670 | RowExclusiveLock | t       | t
 t_pkey  | relation | 6/494              | 37672 | RowExclusiveLock | t       | t
 t       | relation | 6/494              | 37672 | RowExclusiveLock | t       | t
 t       | tuple    | 6/494              | 37672 | ExclusiveLock    | t       | f
 relname | locktype | virtualtransaction |  pid  |       mode       | granted | fastpath
---------+----------+--------------------+-------+------------------+---------+----------
 t_pkey  | relation | 4/578              | 37670 | RowExclusiveLock | t       | t
 t       | relation | 4/578              | 37670 | RowExclusiveLock | t       | t
 t_pkey  | relation | 6/494              | 37672 | RowExclusiveLock | t       | t
 t       | relation | 6/494              | 37672 | RowExclusiveLock | t       | t
 t       | tuple    | 6/494              | 37672 | ExclusiveLock    | t       | f

Testing PostgreSQL transaction isolation levels

These tests were run with Postgres 9.3.5.

Setup (before every test case):

create table test (id int primary key, value int);
insert into test (id, value) values (1, 10), (2, 20);

To see the current isolation level:

select current_setting('transaction_isolation');

Read Committed basic requirements (G0, G1a, G1b, G1c)

Postgres “read committed” prevents Write Cycles (G0) by locking updated rows:

begin; set transaction isolation level read committed; -- T1
begin; set transaction isolation level read committed; -- T2
update test set value = 11 where id = 1; -- T1
update test set value = 12 where id = 1; -- T2, BLOCKS
update test set value = 21 where id = 2; -- T1
commit; -- T1. This unblocks T2
select * from test; -- T1. Shows 1 => 11, 2 => 21
update test set value = 22 where id = 2; -- T2
commit; -- T2
select * from test; -- either. Shows 1 => 12, 2 => 22

Postgres “read committed” prevents Aborted Reads (G1a):

begin; set transaction isolation level read committed; -- T1
begin; set transaction isolation level read committed; -- T2
update test set value = 101 where id = 1; -- T1
select * from test; -- T2. Still shows 1 => 10
abort;  -- T1
select * from test; -- T2. Still shows 1 => 10
commit; -- T2

Postgres “read committed” prevents Intermediate Reads (G1b):

begin; set transaction isolation level read committed; -- T1
begin; set transaction isolation level read committed; -- T2
update test set value = 101 where id = 1; -- T1
select * from test; -- T2. Still shows 1 => 10
update test set value = 11 where id = 1; -- T1
commit; -- T1
select * from test; -- T2. Now shows 1 => 11
commit; -- T2

Postgres “read committed” prevents Circular Information Flow (G1c):

begin; set transaction isolation level read committed; -- T1
begin; set transaction isolation level read committed; -- T2
update test set value = 11 where id = 1; -- T1
update test set value = 22 where id = 2; -- T2
select * from test where id = 2; -- T1. Still shows 2 => 20
select * from test where id = 1; -- T2. Still shows 1 => 10
commit; -- T1
commit; -- T2

Observed Transaction Vanishes (OTV)

Postgres “read committed” prevents Observed Transaction Vanishes (OTV):

begin; set transaction isolation level read committed; -- T1
begin; set transaction isolation level read committed; -- T2
begin; set transaction isolation level read committed; -- T3
update test set value = 11 where id = 1; -- T1
update test set value = 19 where id = 2; -- T1
update test set value = 12 where id = 1; -- T2. BLOCKS
commit; -- T1. This unblocks T2
select * from test where id = 1; -- T3. Shows 1 => 11
update test set value = 18 where id = 2; -- T2
select * from test where id = 2; -- T3. Shows 2 => 19
commit; -- T2
select * from test where id = 2; -- T3. Shows 2 => 18
select * from test where id = 1; -- T3. Shows 1 => 12
commit; -- T3

Predicate-Many-Preceders (PMP)

Postgres “read committed” does not prevent Predicate-Many-Preceders (PMP):

begin; set transaction isolation level read committed; -- T1
begin; set transaction isolation level read committed; -- T2
select * from test where value = 30; -- T1. Returns nothing
insert into test (id, value) values(3, 30); -- T2
commit; -- T2
select * from test where value % 3 = 0; -- T1. Returns the newly inserted row
commit; -- T1

Postgres “repeatable read” prevents Predicate-Many-Preceders (PMP):

begin; set transaction isolation level repeatable read; -- T1
begin; set transaction isolation level repeatable read; -- T2
select * from test where value = 30; -- T1. Returns nothing
insert into test (id, value) values(3, 30); -- T2
commit; -- T2
select * from test where value % 3 = 0; -- T1. Still returns nothing
commit; -- T1

Postgres “read committed” does not prevent Predicate-Many-Preceders (PMP) for write predicates – example from Postgres documentation:

begin; set transaction isolation level read committed; -- T1
begin; set transaction isolation level read committed; -- T2
update test set value = value + 10; -- T1
delete from test where value = 20;  -- T2, BLOCKS
commit; -- T1. This unblocks T2
select * from test where value = 20; -- T2, returns 1 => 20 (despite ostensibly having been deleted)
commit; -- T2

Postgres “repeatable read” prevents Predicate-Many-Preceders (PMP) for write predicates – example from Postgres documentation:

begin; set transaction isolation level repeatable read; -- T1
begin; set transaction isolation level repeatable read; -- T2
update test set value = value + 10; -- T1
delete from test where value = 20;  -- T2, BLOCKS
commit; -- T1. T2 now prints out "ERROR: could not serialize access due to concurrent update"
abort;  -- T2. There's nothing else we can do, this transaction has failed

Lost Update (P4)

Postgres “read committed” does not prevent Lost Update (P4):

begin; set transaction isolation level read committed; -- T1
begin; set transaction isolation level read committed; -- T2
select * from test where id = 1; -- T1
select * from test where id = 1; -- T2
update test set value = 11 where id = 1; -- T1
update test set value = 11 where id = 1; -- T2, BLOCKS
commit; -- T1. This unblocks T2, so T1's update is overwritten
commit; -- T2

Postgres “repeatable read” prevents Lost Update (P4):

begin; set transaction isolation level repeatable read; -- T1
begin; set transaction isolation level repeatable read; -- T2
select * from test where id = 1; -- T1
select * from test where id = 1; -- T2
update test set value = 11 where id = 1; -- T1
update test set value = 11 where id = 1; -- T2, BLOCKS
commit; -- T1. T2 now prints out "ERROR: could not serialize access due to concurrent update"
abort;  -- T2. There's nothing else we can do, this transaction has failed

Read Skew (G-single)

Postgres “read committed” does not prevent Read Skew (G-single):

begin; set transaction isolation level read committed; -- T1
begin; set transaction isolation level read committed; -- T2
select * from test where id = 1; -- T1. Shows 1 => 10
select * from test where id = 1; -- T2
select * from test where id = 2; -- T2
update test set value = 12 where id = 1; -- T2
update test set value = 18 where id = 2; -- T2
commit; -- T2
select * from test where id = 2; -- T1. Shows 2 => 18
commit; -- T1

Postgres “repeatable read” prevents Read Skew (G-single):

begin; set transaction isolation level repeatable read; -- T1
begin; set transaction isolation level repeatable read; -- T2
select * from test where id = 1; -- T1. Shows 1 => 10
select * from test where id = 1; -- T2
select * from test where id = 2; -- T2
update test set value = 12 where id = 1; -- T2
update test set value = 18 where id = 2; -- T2
commit; -- T2
select * from test where id = 2; -- T1. Shows 2 => 20
commit; -- T1

Postgres “repeatable read” prevents Read Skew (G-single) – test using predicate dependencies:

begin; set transaction isolation level repeatable read; -- T1
begin; set transaction isolation level repeatable read; -- T2
select * from test where value % 5 = 0; -- T1
update test set value = 12 where value = 10; -- T2
commit; -- T2
select * from test where value % 3 = 0; -- T1. Returns nothing
commit; -- T1

Postgres “repeatable read” prevents Read Skew (G-single) – test using write predicate:

begin; set transaction isolation level repeatable read; -- T1
begin; set transaction isolation level repeatable read; -- T2
select * from test where id = 1; -- T1. Shows 1 => 10
select * from test; -- T2
update test set value = 12 where id = 1; -- T2
update test set value = 18 where id = 2; -- T2
commit; -- T2
delete from test where value = 20; -- T1. Prints "ERROR: could not serialize access due to concurrent update"
abort; -- T1. There's nothing else we can do, this transaction has failed

Write Skew (G2-item)

Postgres “repeatable read” does not prevent Write Skew (G2-item):

begin; set transaction isolation level repeatable read; -- T1
begin; set transaction isolation level repeatable read; -- T2
select * from test where id in (1,2); -- T1
select * from test where id in (1,2); -- T2
update test set value = 11 where id = 1; -- T1
update test set value = 21 where id = 2; -- T2
commit; -- T1
commit; -- T2

Postgres “serializable” prevents Write Skew (G2-item):

begin; set transaction isolation level serializable; -- T1
begin; set transaction isolation level serializable; -- T2
select * from test where id in (1,2); -- T1
select * from test where id in (1,2); -- T2
update test set value = 11 where id = 1; -- T1
update test set value = 21 where id = 2; -- T2
commit; -- T1
commit; -- T2. Prints out "ERROR: could not serialize access due to read/write dependencies among transactions"

Anti-Dependency Cycles (G2)

Postgres “repeatable read” does not prevent Anti-Dependency Cycles (G2):

begin; set transaction isolation level repeatable read; -- T1
begin; set transaction isolation level repeatable read; -- T2
select * from test where value % 3 = 0; -- T1
select * from test where value % 3 = 0; -- T2
insert into test (id, value) values(3, 30); -- T1
insert into test (id, value) values(4, 42); -- T2
commit; -- T1
commit; -- T2
select * from test where value % 3 = 0; -- Either. Returns 3 => 30, 4 => 42

Postgres “serializable” prevents Anti-Dependency Cycles (G2):

begin; set transaction isolation level serializable; -- T1
begin; set transaction isolation level serializable; -- T2
select * from test where value % 3 = 0; -- T1
select * from test where value % 3 = 0; -- T2
insert into test (id, value) values(3, 30); -- T1
insert into test (id, value) values(4, 42); -- T2
commit; -- T1
commit; -- T2. Prints out "ERROR: could not serialize access due to read/write dependencies among transactions"

Postgres “serializable” prevents Anti-Dependency Cycles (G2) – Fekete et al’s example with two anti-dependency edges:

begin; set transaction isolation level serializable; -- T1
select * from test; -- T1. Shows 1 => 10, 2 => 20
begin; set transaction isolation level serializable; -- T2
update test set value = value + 5 where id = 2; -- T2
commit; -- T2
begin; set transaction isolation level serializable; -- T3
select * from test; -- T3. Shows 1 => 10, 2 => 25
commit; -- T3
update test set value = 0 where id = 1; -- T1. Prints out "ERROR: could not serialize access due to read/write dependencies among transactions"
abort; -- T1. There's nothing else we can do, this transaction has failed

CDC 变更数据捕获机理

数据变更捕获是一种很有趣的ETL替代方案。

在实际生产中,我们经常需要把数据库的状态同步到其他地方去,例如同步到数据仓库进行分析,同步到消息队列供下游消费,同步到缓存以加速查询。总的来说,搬运状态有两大类方法:ETL与CDC。


前驱知识

CDC与ETL

数据库在本质上是一个状态集合,任何对数据库的变更(增删改)本质上都是对状态的修改。

在实际生产中,我们经常需要把数据库的状态同步到其他地方去,例如同步到数据仓库进行分析,同步到消息队列供下游消费,同步到缓存以加速查询。总的来说,搬运状态有两大类方法:ETL与CDC。

  • ETL(ExtractTransformLoad)着眼于状态本身,用定时批量轮询的方式拉取状态本身。

  • CDC(ChangeDataCapture)则着眼于变更,以流式的方式持续收集状态变化事件(变更)。

ETL大家都耳熟能详,每天批量跑ETL任务,从生产OLTP数据库 拉取(E)转换(T) 格式, 导入(L) 数仓,在此不赘述。相比ETL而言,CDC算是个新鲜玩意,随着流计算的崛起也越来越多地进入人们的视线。

变更数据捕获(change data capture, CDC)是一种观察写入数据库的所有数据变更,并将其提取并转换为可以复制到其他系统中的形式的过程。 CDC很有意思,特别是当变更能在被写入数据库后立刻用于后续的流处理时。

例如用户可以捕获数据库中的变更,并不断将相同的变更应用至搜索索引(e.g elasticsearch)。如果变更日志以相同的顺序应用,则可以预期的是,搜索索引中的数据与数据库中的数据是匹配的。同理,这些变更也可以应用于后台刷新缓存(redis),送往消息队列(Kafka),导入数据仓库(EventSourcing,存储不可变的事实事件记录而不是每天取快照),收集统计数据与监控(Prometheus),等等等等。在这种意义下,外部索引,缓存,数仓都成为了PostgreSQL在逻辑上的从库,这些衍生数据系统都成为了变更流的消费者,而PostgreSQL成为了整个数据系统的主库。在这种架构下,应用只需要操心怎样把数据写入数据库,剩下的事情交给CDC即可。系统设计可以得到极大地简化:所有的数据组件都能够自动与主库在逻辑上保证(最终)一致。用户不用再为如何保证多个异构数据系统之间数据同步而焦头烂额了。

实际上PostgreSQL自10.0版本以来提供的逻辑复制(logical replication)功能,实质上就是一个CDC应用:从主库上提取变更事件流:INSERT, UPDATE, DELETE, TRUNCATE,并在另一个PostgreSQL主库实例上重放。如果这些增删改事件能够被解析出来,它们就可以用于任何感兴趣的消费者,而不仅仅局限于另一个PostgreSQL实例。

逻辑复制

想在传统关系型数据库上实施CDC并不容易,关系型数据库本身的预写式日志WAL 实际上就是数据库中变更事件的记录。因此从数据库中捕获变更,基本上可以认为等价于消费数据库产生的WAL日志/复制日志。(当然也有其他的变更捕获方式,例如在表上建立触发器,当变更发生时将变更记录写入另一张变更日志表,客户端不断tail这张日志表,当然也有一定的局限性)。

大多数数据库的复制日志的问题在于,它们一直被当做数据库的内部实现细节,而不是公开的API。客户端应该通过其数据模型和查询语言来查询数据库,而不是解析复制日志并尝试从中提取数据。许多数据库根本没有记录在案的获取变更日志的方式。因此捕获数据库中所有的变更然后将其复制到其他状态存储(搜索索引,缓存,数据仓库)中是相当困难的。

此外,仅有 数据库变更日志仍然是不够的。如果你拥有 全量 变更日志,当然可以通过重放日志来重建数据库的完整状态。但是在许多情况下保留全量历史WAL日志并不是可行的选择(例如磁盘空间与重放耗时的限制)。 例如,构建新的全文索引需要整个数据库的完整副本 —— 仅仅应用最新的变更日志是不够的,因为这样会丢失最近没有更新过的项目。因此如果你不能保留完整的历史日志,那么你至少需要包留一个一致的数据库快照,并保留从该快照开始的变更日志。

因此实施CDC,数据库至少需要提供以下功能:

  1. 获取数据库的变更日志(WAL),并解码成逻辑上的事件(对表的增删改而不是数据库的内部表示)

  2. 获取数据库的"一致性快照",从而订阅者可以从任意一个一致性状态开始订阅而不是数据库创建伊始。

  3. 保存消费者偏移量,以便跟踪订阅者的消费进度,及时清理回收不用的变更日志以免撑爆磁盘。

我们会发现,PostgreSQL在实现逻辑复制的同时,已经提供了一切CDC所需要的基础设施。

  • 逻辑解码(Logical Decoding),用于从WAL日志中解析逻辑变更事件
  • 复制协议(Replication Protocol):提供了消费者实时订阅(甚至同步订阅)数据库变更的机制
  • 快照导出(export snapshot):允许导出数据库的一致性快照(pg_export_snapshot
  • 复制槽(Replication Slot),用于保存消费者偏移量,跟踪订阅者进度。

因此,在PostgreSQL上实施CDC最为直观优雅的方式,就是按照PostgreSQL的复制协议编写一个"逻辑从库" ,从数据库中实时地,流式地接受逻辑解码后的变更事件,完成自己定义的处理逻辑,并及时向数据库汇报自己的消息消费进度。就像使用Kafka一样。在这里CDC客户端可以将自己伪装成一个PostgreSQL的从库,从而不断地实时从PostgreSQL主库中接收逻辑解码后的变更内容。同时CDC客户端还可以通过PostgreSQL提供的复制槽(Replication Slot)机制来保存自己的消费者偏移量,即消费进度,实现类似消息队列一至少次的保证,保证不错过变更数据。(客户端自己记录消费者偏移量跳过重复记录,即可实现"恰好一次 “的保证 )

逻辑解码

在开始进一步的讨论之前,让我们先来看一看期待的输出结果到底是什么样子。

PostgreSQL的变更事件以二进制内部表示形式保存在预写式日志(WAL)中,使用其自带的pg_waldump工具可以解析出来一些人类可读的信息:

rmgr: Btree       len (rec/tot):     64/    64, tx:       1342, lsn: 2D/AAFFC9F0, prev 2D/AAFFC810, desc: INSERT_LEAF off 126, blkref #0: rel 1663/3101882/3105398 blk 4
rmgr: Heap        len (rec/tot):    485/   485, tx:       1342, lsn: 2D/AAFFCA30, prev 2D/AAFFC9F0, desc: INSERT off 10, blkref #0: rel 1663/3101882/3105391 blk 139

WAL日志里包含了完整权威的变更事件记录,但这种记录格式过于底层。用户并不会对磁盘上某个数据页里的二进制变更(文件A页面B偏移量C追加写入二进制数据D)感兴趣,他们感兴趣的是某张表中增删改了哪些行哪些字段。逻辑解码就是将物理变更记录翻译为用户期望的逻辑变更事件的机制(例如表A上的增删改事件)。

例如用户可能期望的是,能够解码出等价的SQL语句

INSERT INTO public.test (id, data) VALUES (14, 'hoho');

或者最为通用的JSON结构(这里以JSON格式记录了一条UPDATE事件)

{
  "change": [
    {
      "kind": "update",
      "schema": "public",
      "table": "test",
      "columnnames": ["id", "data" ],
      "columntypes": [ "integer", "text" ],
      "columnvalues": [ 1, "hoho"],
      "oldkeys": { "keynames": [ "id"],
        "keytypes": ["integer" ],
        "keyvalues": [1]
      }
    }
  ]
}

当然也可以是更为紧凑高效严格的Protobuf格式,更为灵活的Avro格式,抑或是任何用户感兴趣的格式。

逻辑解码 所要解决的问题,就是将数据库内部二进制表示的变更事件,解码(Decoding)成为用户感兴趣的格式。之所以需要这样一个过程,是因为数据库内部表示是非常紧凑的,想要解读原始的二进制WAL日志,不仅仅需要WAL结构相关的知识,还需要系统目录(System Catalog),即元数据。没有元数据就无从得知用户可能感兴趣的模式名,表名,列名,只能解析出来的一系列数据库自己才能看懂的oid。

关于流复制协议,复制槽,事务快照等概念与功能,这里就不展开了,让我们进入动手环节。


快速开始

假设我们有一张用户表,我们希望捕获任何发生在它上面的变更,假设数据库发生了如下变更操作

下面会重复用到这几条命令

DROP TABLE IF EXISTS users;
CREATE TABLE users(id SERIAL PRIMARY KEY, name TEXT);

INSERT INTO users VALUES (100, 'Vonng');
INSERT INTO users VALUES (101, 'Xiao Wang');
DELETE FROM users WHERE id = 100;
UPDATE users SET name = 'Lao Wang' WHERE id = 101;

最终数据库的状态是:只有一条(101, 'Lao Wang')的记录。无论是曾经有一个名为Vonng的用户存在过的痕迹,抑或是隔壁老王也曾年轻过的事实,都随着对数据库的删改而烟消云散。我们希望这些事实不应随风而逝,需要被记录下来。

操作流程

通常来说,订阅变更需要以下几步操作:

  • 选择一个一致性的数据库快照,作为订阅变更的起点。(创建一个复制槽)
  • (数据库发生了一些变更)
  • 读取这些变更,更新自己的的消费进度。

那么, 让我们先从最简单的办法开始,从PostgreSQL自带的的SQL接口开始

SQL接口

逻辑复制槽的增删查API:

TABLE pg_replication_slots; -- 查
pg_create_logical_replication_slot(slot_name name, plugin name) -- 增
pg_drop_replication_slot(slot_name name) -- 删

从逻辑复制槽中获取最新的变更数据:

pg_logical_slot_get_changes(slot_name name, ...)  -- 消费掉
pg_logical_slot_peek_changes(slot_name name, ...) -- 只查看不消费

在正式开始前,还需要对数据库参数做一些修改,修改wal_level = logical,这样在WAL日志中的信息才能足够用于逻辑解码。

-- 创建一个复制槽test_slot,使用系统自带的测试解码插件test_decoding,解码插件会在后面介绍
SELECT * FROM pg_create_logical_replication_slot('test_slot', 'test_decoding');

-- 重放上面的建表与增删改操作
-- DROP TABLE | CREATE TABLE | INSERT 1 | INSERT 1 | DELETE 1 | UPDATE 1

-- 读取复制槽test_slot中未消费的最新的变更事件流
SELECT * FROM  pg_logical_slot_get_changes('test_slot', NULL, NULL);
    lsn    | xid |                                data
-----------+-----+--------------------------------------------------------------------
 0/167C7E8 | 569 | BEGIN 569
 0/169F6F8 | 569 | COMMIT 569
 0/169F6F8 | 570 | BEGIN 570
 0/169F6F8 | 570 | table public.users: INSERT: id[integer]:100 name[text]:'Vonng'
 0/169F810 | 570 | COMMIT 570
 0/169F810 | 571 | BEGIN 571
 0/169F810 | 571 | table public.users: INSERT: id[integer]:101 name[text]:'Xiao Wang'
 0/169F8C8 | 571 | COMMIT 571
 0/169F8C8 | 572 | BEGIN 572
 0/169F8C8 | 572 | table public.users: DELETE: id[integer]:100
 0/169F938 | 572 | COMMIT 572
 0/169F970 | 573 | BEGIN 573
 0/169F970 | 573 | table public.users: UPDATE: id[integer]:101 name[text]:'Lao Wang'
 0/169F9F0 | 573 | COMMIT 573

-- 清理掉创建的复制槽
SELECT pg_drop_replication_slot('test_slot');

这里,我们可以看到一系列被触发的事件,其中每个事务的开始与提交都会触发一个事件。因为目前逻辑解码机制不支持DDL变更,因此CREATE TABLEDROP TABLE并没有出现在事件流中,只能看到空荡荡的BEGIN+COMMIT。另一点需要注意的是,只有成功提交的事务才会产生逻辑解码变更事件。也就是说用户不用担心收到并处理了很多行变更消息之后,最后发现事务回滚了,还需要担心怎么通知消费者去会跟变更。

通过SQL接口,用户已经能够拉取最新的变更了。这也就意味着任何有着PostgreSQL驱动的语言都可以通过这种方式从数据库中捕获最新的变更。当然这种方式实话说还是略过于土鳖。更好的方式是利用PostgreSQL的复制协议直接从数据库中订阅变更数据流。当然相比使用SQL接口,这也需要更多的工作。

使用客户端接收变更

在编写自己的CDC客户端之前,让我们先来试用一下官方自带的CDC客户端样例——pg_recvlogical。与pg_receivewal类似,不过它接收的是逻辑解码后的变更,下面是一个具体的例子:

# 启动一个CDC客户端,连接数据库postgres,创建名为test_slot的槽,使用test_decoding解码插件,标准输出
pg_recvlogical \
	-d postgres \
	--create-slot --if-not-exists --slot=test_slot \
	--plugin=test_decoding \
	--start -f -

# 开启另一个会话,重放上面的建表与增删改操作
# DROP TABLE | CREATE TABLE | INSERT 1 | INSERT 1 | DELETE 1 | UPDATE 1

# pg_recvlogical输出结果
BEGIN 585
COMMIT 585
BEGIN 586
table public.users: INSERT: id[integer]:100 name[text]:'Vonng'
COMMIT 586
BEGIN 587
table public.users: INSERT: id[integer]:101 name[text]:'Xiao Wang'
COMMIT 587
BEGIN 588
table public.users: DELETE: id[integer]:100
COMMIT 588
BEGIN 589
table public.users: UPDATE: id[integer]:101 name[text]:'Lao Wang'
COMMIT 589

# 清理:删除创建的复制槽
pg_recvlogical -d postgres --drop-slot --slot=test_slot

上面的例子中,主要的变更事件包括事务的开始结束,以及数据行的增删改。这里默认的test_decoding插件的输出格式为:

BEGIN {事务标识}
table {模式名}.{表名} {命令INSERT|UPDATE|DELETE}  {列名}[{类型}]:{取值} ...
COMMIT {事务标识}

实际上,PostgreSQL的逻辑解码是这样工作的,每当特定的事件发生(表的Truncate,行级别的增删改,事务开始与提交),PostgreSQL都会调用一系列的钩子函数。所谓的逻辑解码输出插件(Logical Decoding Output Plugin),就是这样一组回调函数的集合。它们接受二进制内部表示的变更事件作为输入,查阅一些系统目录,将二进制数据翻译成为用户感兴趣的结果。

逻辑解码输出插件

除了PostgreSQL自带的"用于测试"的逻辑解码插件:test_decoding 之外,还有很多现成的输出插件,例如:

当然还有PostgreSQL自带逻辑复制所使用的解码插件:pgoutput,其消息格式文档地址

安装这些插件非常简单,有一些插件(例如wal2json)可以直接从官方二进制源轻松安装。

yum install wal2json11
apt install postgresql-11-wal2json

或者如果没有二进制包,也可以自己下载编译。只需要确保pg_config已经在你的PATH中,然后执行make & sudo make install两板斧即可。以输出SQL格式的decoder_raw插件为例:

git clone https://github.com/michaelpq/pg_plugins && cd pg_plugins/decoder_raw
make && sudo make install

使用wal2json接收同样的变更

pg_recvlogical -d postgres --drop-slot --slot=test_slot
pg_recvlogical -d postgres --create-slot --if-not-exists --slot=test_slot \
	--plugin=wal2json --start -f -

结果为:

{"change":[]}
{"change":[{"kind":"insert","schema":"public","table":"users","columnnames":["id","name"],"columntypes":["integer","text"],"columnvalues":[100,"Vonng"]}]}
{"change":[{"kind":"insert","schema":"public","table":"users","columnnames":["id","name"],"columntypes":["integer","text"],"columnvalues":[101,"Xiao Wang"]}]}
{"change":[{"kind":"delete","schema":"public","table":"users","oldkeys":{"keynames":["id"],"keytypes":["integer"],"keyvalues":[100]}}]}
{"change":[{"kind":"update","schema":"public","table":"users","columnnames":["id","name"],"columntypes":["integer","text"],"columnvalues":[101,"Lao Wang"],"oldkeys":{"keynames":["id"],"keytypes":["integer"],"keyvalues":[101]}}]}

而使用decoder_raw获取SQL格式的输出

pg_recvlogical -d postgres --drop-slot --slot=test_slot
pg_recvlogical -d postgres --create-slot --if-not-exists --slot=test_slot \
	--plugin=decoder_raw --start -f -

结果为:

INSERT INTO public.users (id, name) VALUES (100, 'Vonng');
INSERT INTO public.users (id, name) VALUES (101, 'Xiao Wang');
DELETE FROM public.users WHERE id = 100;
UPDATE public.users SET id = 101, name = 'Lao Wang' WHERE id = 101;

decoder_raw可以用于抽取SQL形式表示的状态变更,将这些抽取得到的SQL语句在同样的基础状态上重放,即可得到相同的结果。PostgreSQL就是使用这样的机制实现逻辑复制的。

一个典型的应用场景就是数据库不停机迁移。在传统不停机迁移模式(双写,改读,改写)中,第三步改写完成后是无法快速回滚的,因为写入流量在切换至新主库后如果发现有问题想立刻回滚,老主库上会丢失一些数据。这时候就可以使用decoder_raw提取主库上的最新变更,并通过一行简单的Bash命令,将新主库上的变更实时同步到旧主库。保证迁移过程中任何时刻都可以快速回滚至老主库。

pg_recvlogical -d <new_master_url> --slot=test_slot --plugin=decoder_raw --start -f - |
psql <old_master_url>

另一个有趣的场景是UNDO LOG。PostgreSQL的故障恢复是基于REDO LOG的,通过重放WAL会到历史上的任意时间点。在数据库模式不发生变化的情况下,如果只是单纯的表内容增删改出现了失误,完全可以利用类似decoder_raw的方式反向生成UNDO日志。提高此类故障恢复的速度。

最后,输出插件可以将变更事件格式化为各种各样的形式。解码输出为Redis的kv操作,或者仅仅抽取一些关键字段用于更新统计数据或者构建外部索引,有着很大的想象空间。

编写自定义的逻辑解码输出插件并不复杂,可以参阅这篇官方文档。毕竟逻辑解码输出插件本质上只是一个拼字符串的回调函数集合。在官方样例的基础上稍作修改,即可轻松实现一个你自己的逻辑解码输出插件。


CDC客户端

PostgreSQL自带了一个名为pg_recvlogical的客户端应用,可以将逻辑变更的事件流写至标准输出。但并不是所有的消费者都可以或者愿意使用Unix Pipe来完成所有工作的。此外,根据端到端原则,使用pg_recvlogical将变更数据流落盘并不意味着消费者已经拿到并确认了该消息,只有消费者自己亲自向数据库确认才可以做到这一点。

编写PostgreSQL的CDC客户端程序,本质上是实现了一个"猴版”数据库从库。客户端向数据库建立一条复制连接(Replication Connection) ,将自己伪装成一个从库:从主库获取解码后的变更消息流,并周期性地向主库汇报自己的消费进度(落盘进度,刷盘进度,应用进度)。

复制连接

复制连接,顾名思义就是用于复制(Replication) 的特殊连接。当与PostgreSQL服务器建立连接时,如果连接参数中提供了replication=database|on|yes|1,就会建立一条复制连接,而不是普通连接。复制连接可以执行一些特殊的命令,例如IDENTIFY_SYSTEM, TIMELINE_HISTORY, CREATE_REPLICATION_SLOT, START_REPLICATION, BASE_BACKUP, 在逻辑复制的情况下,还可以执行一些简单的SQL查询。具体细节可以参考PostgreSQL官方文档中前后端协议一章:https://www.postgresql.org/docs/current/protocol-replication.html

譬如,下面这条命令就会建立一条复制连接:

$ psql 'postgres://localhost:5432/postgres?replication=on&application_name=mocker'

从系统视图pg_stat_replication可以看到主库识别到了一个新的"从库”

vonng=# table pg_stat_replication ;
-[ RECORD 1 ]----+-----------------------------
pid              | 7218
usesysid         | 10
usename          | vonng
application_name | mocker
client_addr      | ::1
client_hostname  |
client_port      | 53420

编写自定义逻辑

无论是JDBC还是Go语言的PostgreSQL驱动,都提供了相应的基础设施,用于处理复制连接。

这里让我们用Go语言编写一个简单的CDC客户端,样例使用了jackc/pgx,一个很不错的Go语言编写的PostgreSQL驱动。这里的代码只是作为概念演示,因此忽略掉了错误处理,非常Naive。将下面的代码保存为main.go,执行go run main.go即可执行。

默认的三个参数分别为数据库连接串,逻辑解码输出插件的名称,以及复制槽的名称。默认值为:

dsn := "postgres://localhost:5432/postgres?application_name=cdc"
plugin := "test_decoding"
slot := "test_slot"
go run main.go postgres:///postgres?application_name=cdc test_decoding test_slot

代码如下所示:

package main

import (
	"log"
	"os"
	"time"

	"context"
	"github.com/jackc/pgx"
)

type Subscriber struct {
	URL    string
	Slot   string
	Plugin string
	Conn   *pgx.ReplicationConn
	LSN    uint64
}

// Connect 会建立到服务器的复制连接,区别在于自动添加了replication=on|1|yes|dbname参数
func (s *Subscriber) Connect() {
	connConfig, _ := pgx.ParseURI(s.URL)
	s.Conn, _ = pgx.ReplicationConnect(connConfig)
}

// ReportProgress 会向主库汇报写盘,刷盘,应用的进度坐标(消费者偏移量)
func (s *Subscriber) ReportProgress() {
	status, _ := pgx.NewStandbyStatus(s.LSN)
	s.Conn.SendStandbyStatus(status)
}

// CreateReplicationSlot 会创建逻辑复制槽,并使用给定的解码插件
func (s *Subscriber) CreateReplicationSlot() {
	if consistPoint, snapshotName, err := s.Conn.CreateReplicationSlotEx(s.Slot, s.Plugin); err != nil {
		log.Fatalf("fail to create replication slot: %s", err.Error())
	} else {
		log.Printf("create replication slot %s with plugin %s : consist snapshot: %s, snapshot name: %s",
			s.Slot, s.Plugin, consistPoint, snapshotName)
		s.LSN, _ = pgx.ParseLSN(consistPoint)
	}
}

// StartReplication 会启动逻辑复制(服务器会开始发送事件消息)
func (s *Subscriber) StartReplication() {
	if err := s.Conn.StartReplication(s.Slot, 0, -1); err != nil {
		log.Fatalf("fail to start replication on slot %s : %s", s.Slot, err.Error())
	}
}

// DropReplicationSlot 会使用临时普通连接删除复制槽(如果存在),注意如果复制连接正在使用这个槽是没法删的。
func (s *Subscriber) DropReplicationSlot() {
	connConfig, _ := pgx.ParseURI(s.URL)
	conn, _ := pgx.Connect(connConfig)
	var slotExists bool
	conn.QueryRow(`SELECT EXISTS(SELECT 1 FROM pg_replication_slots WHERE slot_name = $1)`, s.Slot).Scan(&slotExists)
	if slotExists {
		if s.Conn != nil {
			s.Conn.Close()
		}
		conn.Exec("SELECT pg_drop_replication_slot($1)", s.Slot)
		log.Printf("drop replication slot %s", s.Slot)
	}
}

// Subscribe 开始订阅变更事件,主消息循环
func (s *Subscriber) Subscribe() {
	var message *pgx.ReplicationMessage
	for {
		// 等待一条消息, 消息有可能是真的消息,也可能只是心跳包
		message, _ = s.Conn.WaitForReplicationMessage(context.Background())
		if message.WalMessage != nil {
			DoSomething(message.WalMessage) // 如果是真的消息就消费它
			if message.WalMessage.WalStart > s.LSN { // 消费完后更新消费进度,并向主库汇报
				s.LSN = message.WalMessage.WalStart + uint64(len(message.WalMessage.WalData))
				s.ReportProgress()
			}
		}
		// 如果是心跳包消息,按照协议,需要检查服务器是否要求回送进度。
		if message.ServerHeartbeat != nil && message.ServerHeartbeat.ReplyRequested == 1 {
			s.ReportProgress() // 如果服务器心跳包要求回送进度,则汇报进度
		}
	}
}

// 实际消费消息的函数,这里只是把消息打印出来,也可以写入Redis,写入Kafka,更新统计信息,发送邮件等
func DoSomething(message *pgx.WalMessage) {
	log.Printf("[LSN] %s [Payload] %s", 
             pgx.FormatLSN(message.WalStart), string(message.WalData))
}

// 如果使用JSON解码插件,这里是用于Decode的Schema
type Payload struct {
	Change []struct {
		Kind         string        `json:"kind"`
		Schema       string        `json:"schema"`
		Table        string        `json:"table"`
		ColumnNames  []string      `json:"columnnames"`
		ColumnTypes  []string      `json:"columntypes"`
		ColumnValues []interface{} `json:"columnvalues"`
		OldKeys      struct {
			KeyNames  []string      `json:"keynames"`
			KeyTypes  []string      `json:"keytypes"`
			KeyValues []interface{} `json:"keyvalues"`
		} `json:"oldkeys"`
	} `json:"change"`
}

func main() {
	dsn := "postgres://localhost:5432/postgres?application_name=cdc"
	plugin := "test_decoding"
	slot := "test_slot"
	if len(os.Args) > 1 {
		dsn = os.Args[1]
	}
	if len(os.Args) > 2 {
		plugin = os.Args[2]
	}
	if len(os.Args) > 3 {
		slot = os.Args[3]
	}

	subscriber := &Subscriber{
		URL:    dsn,
		Slot:   slot,
		Plugin: plugin,
	}                                // 创建新的CDC客户端
	subscriber.DropReplicationSlot() // 如果存在,清理掉遗留的Slot

	subscriber.Connect()                   // 建立复制连接
	defer subscriber.DropReplicationSlot() // 程序中止前清理掉复制槽
	subscriber.CreateReplicationSlot()     // 创建复制槽
	subscriber.StartReplication()          // 开始接收变更流
	go func() {
		for {
			time.Sleep(5 * time.Second)
			subscriber.ReportProgress()
		}
	}()                                    // 协程2每5秒地向主库汇报进度
	subscriber.Subscribe()                 // 主消息循环
}

在另一个数据库会话中再次执行上面的变更,可以看到客户端及时地接收到了变更的内容。这里客户端只是简单地将其打印了出来,实际生产中,客户端可以完成任何工作,比如写入Kafka,写入Redis,写入磁盘日志,或者只是更新内存中的统计数据并暴露给监控系统。甚至,还可以通过配置同步提交,确保所有系统中的变更能够时刻保证严格同步(当然相比默认的异步模式比较影响性能就是了)。

对于PostgreSQL主库而言,这看起来就像是另一个从库。

postgres=# table pg_stat_replication; -- 查看当前从库
-[ RECORD 1 ]----+------------------------------
pid              | 14082
usesysid         | 10
usename          | vonng
application_name | cdc
client_addr      | 10.1.1.95
client_hostname  |
client_port      | 56609
backend_start    | 2019-05-19 13:14:34.606014+08
backend_xmin     |
state            | streaming
sent_lsn         | 2D/AB269AB8     -- 服务端已经发送的消息坐标
write_lsn        | 2D/AB269AB8     -- 客户端已经执行完写入的消息坐标
flush_lsn        | 2D/AB269AB8     -- 客户端已经刷盘的消息坐标(不会丢失)
replay_lsn       | 2D/AB269AB8     -- 客户端已经应用的消息坐标(已经生效)
write_lag        |
flush_lag        |
replay_lag       |
sync_priority    | 0
sync_state       | async

postgres=# table pg_replication_slots;  -- 查看当前复制槽
-[ RECORD 1 ]-------+------------
slot_name           | test
plugin              | decoder_raw
slot_type           | logical
datoid              | 13382
database            | postgres
temporary           | f
active              | t
active_pid          | 14082
xmin                |
catalog_xmin        | 1371
restart_lsn         | 2D/AB269A80       -- 下次客户端重连时将从这里开始重放
confirmed_flush_lsn | 2D/AB269AB8       -- 客户端确认完成的消息进度

局限性

想要在生产环境中使用CDC,还需要考虑一些其他的问题。略有遗憾的是,在PostgreSQL CDC的天空上,还飘着两朵小乌云。

完备性

就目前而言,PostgreSQL的逻辑解码只提供了以下几个钩子:

LogicalDecodeStartupCB startup_cb;
LogicalDecodeBeginCB begin_cb;
LogicalDecodeChangeCB change_cb;
LogicalDecodeTruncateCB truncate_cb;
LogicalDecodeCommitCB commit_cb;
LogicalDecodeMessageCB message_cb;
LogicalDecodeFilterByOriginCB filter_by_origin_cb;
LogicalDecodeShutdownCB shutdown_cb;

其中比较重要,也是必须提供的是三个回调函数:begin:事务开始,change:行级别增删改事件,commit:事务提交 。遗憾的是,并不是所有的事件都有相应的钩子,例如数据库的模式变更,Sequence的取值变化,以及特殊的大对象操作。

通常来说,这并不是一个大问题,因为用户感兴趣的往往只是表记录而不是表结构的增删改。而且,如果使用诸如JSON,Avro等灵活格式作为解码目标格式,即使表结构发生变化,也不会有什么大问题。

但是尝试从目前的变更事件流生成完备的UNDO Log是不可能的,因为目前模式的变更DDL并不会记录在逻辑解码的输出中。好消息是未来会有越来越多的钩子与支持,因此这个问题是可解的。

同步提交

需要注意的一点是,有一些输出插件会无视BeginCommit消息。这两条消息本身也是数据库变更日志的一部分,如果输出插件忽略了这些消息,那么CDC客户端在汇报消费进度时就可能会出现偏差(落后一条消息的偏移量)。在一些边界条件下可能会触发一些问题:例如写入极少的数据库启用同步提交时,主库迟迟等不到从库确认最后的Commit消息而卡住)

故障切换

理想很美好,现实很骨感。当一切正常时,CDC工作流工作的很好。但当数据库出现故障,或者出现故障转移时,事情就变得比较棘手了。

恰好一次保证

另外一个使用PostgreSQL CDC的问题是消息队列中经典的恰好一次问题。

PostgreSQL的逻辑复制实际上提供的是至少一次保证,因为消费者偏移量的值会在检查点的时候保存。如果PostgreSQL主库宕机,那么重新发送变更事件的起点,不一定恰好等于上次订阅者已经消费的位置。因此有可能会发送重复的消息。

解决方法是:逻辑复制的消费者也需要记录自己的消费者偏移量,以便跳过重复的消息,实现真正的恰好一次 消息传达保证。这并不是一个真正的问题,只是任何试图自行实现CDC客户端的人都应当注意这一点。

Failover Slot

对目前PostgreSQL的CDC来说,Failover Slot是最大的难点与痛点。逻辑复制依赖复制槽,因为复制槽持有着消费者的状态,记录着消费者的消费进度,因而数据库不会将消费者还没处理的消息清理掉。

但以目前的实现而言,复制槽只能用在主库上,且复制槽本身并不会被复制到从库上。因此当主库进行Failover时,消费者偏移量就会丢失。如果在新的主库承接任何写入之前没有重新建好逻辑复制槽,就有可能会丢失一些数据。对于非常严格的场景,使用这个功能时仍然需要谨慎。

这个问题计划将于下一个大版本(13)解决,Failover Slot的Patch计划于版本13(2020)年合入主线版本。

在那之前,如果希望在生产中使用CDC,那么务必要针对故障切换进行充分地测试。例如使用CDC的情况下,Failover的操作就需要有所变更:核心思想是运维与DBA必须手工完成复制槽的复制工作。在Failover前可以在原主库上启用同步提交,暂停写入流量并在新主库上使用脚本复制复制原主库的槽,并在新主库上创建同样的复制槽,从而手工完成复制槽的Failover。对于紧急故障切换,即原主库无法访问,需要立即切换的情况,也可以在事后使用PITR重新将缺失的变更恢复出来。

小结一下:CDC的功能机制已经达到了生产应用的要求,但可靠性的机制还略有欠缺,这个问题可以等待下一个主线版本,或通过审慎地手工操作解决,当然激进的用户也可以自行拉取该补丁提前尝鲜。

PostgreSQL中的锁

详细介绍PostgreSQL中的各种锁

PostgreSQL的并发控制以 快照隔离(SI) 为主,以 两阶段锁定(2PL) 机制为辅。PostgreSQL对DML(SELECT, UPDATE, INSERT, DELETE等命令)使用SSI,对DDL(CREATE TABLE等命令)使用2PL。

PostgreSQL有好几类锁,其中最主要的是 表级锁行级锁,此外还有页级锁,咨询锁等,表级锁 通常是各种命令执行时自动获取的,或者通过事务中的LOCK语句显式获取;而行级锁则是由SELECT FOR UPDATE|SHARE语句显式获取的。执行数据库命令时,都是先获取表级锁,再获取行级锁。本文主要介绍PostgreSQL中的表锁。


表级锁

  • 表级锁通常会在执行各种命令执行时自动获取,或者通过在事务中使用LOCK语句显式获取。
  • 每种锁都有自己的冲突集合,在同一时刻的同一张表上,两个事务可以持有不冲突的锁,不能持有冲突的锁。
  • 有些锁是 自斥(self-conflict) 的,即最多只能被一个事务所持有。
  • 表级锁总共有八种模式,有着并不严格的强度递增关系(例外是Share锁不自斥)
  • 表级锁存在于PG的共享内存中,可以通过pg_locks系统视图查阅。

表级锁的模式

如何记忆这么多类型的锁呢?让我们从演化的视角来看这些锁。

表级锁的演化

最开始只有两种锁:ShareExclusive,共享锁与排它锁,即所谓读锁写锁。读锁的目的是阻止表数据的变更,而写锁的目的是阻止一切并发访问。这很好理解。

多版本并发控制

后来随着多版本并发控制技术的出现(PostgreSQL使用快照隔离实现MVCC),读不阻塞写,写不阻塞读(针对表的增删改查而言)。因而原有的锁模型就需要升级了:这里的共享锁与排他锁都有了一个升级版本,即前面多加一个ACCESSACCESS SHARE是改良版共享锁,即允许ACCESS(多版本并发访问)的SHARE锁,这种锁意味着即使其他进程正在并发修改数据也不会阻塞本进程读取数据。当然有了多版本读锁也就会有对应的多版本写锁来阻止一切访问,即连ACCESS(多版本并发访问)都要EXCLUSIVE的锁,这种锁会阻止一切访问,是最强的写锁。

引入MVCC后,INSERT|UPDATE|DELETE仍然使用原来的Exclusive锁,而普通的只读SELECT则使用多版本的AccessShare锁。因为AccessShare锁与原来的Exclusive锁不冲突,所以读写之间就不会阻塞了。原来的Share锁现在主要的应用场景为创建索引(非并发创建模式下,创建索引会阻止任何对底层数据的变更),而升级的多版本AccessExclusive锁主要用于除了增删改之外的排他性变更(DROP|TRUNCATE|REINDEX|VACUUM FULL等),这个模型如图(a)所示。

当然,这样还是有问题的。虽然在MVCC中读写之间相互不阻塞了,但写-写之间还是会产生冲突。上面的模型中,并发写入是通过表级别的Exclusive锁解决的。表级锁虽然可以解决并发写入冲突问题,但这个粒度太大了,会影响并发度:因为同一时刻一张表上只能有一个进程持有Exclusive锁并执行写入,而典型的OLTP场景是以单行写入为主。所以常见的DBMS解决写-写冲突通常都是采用行级锁来实现(下面会讲到)。

行级锁和表级锁不是一回事,但这两种锁之间仍然存在着联系,协调这两种锁之间的关系,就需要引入意向锁

意向锁

意向锁用于协调表锁与行锁之间的关系:它用于保护较低资源级别上的锁,即说明下层节点已经被加了锁。当进程想要锁定或修改某表上的某一行时,它会在这一行上加上行级锁。但在加行级锁之前,它还需要在这张表上加上一把意向锁,表示自己将会在表中的若干行上加锁。

举个例子,假设不存在意向锁。假设进程A获取了表上某行的行锁,持有行上的排他锁意味着进程A可以对这一行执行写入;同时因为不存在意向锁,进程B很顺利地获取了该表上的表级排他锁,这意味着进程B可以对整个表,包括A锁定对那一行进行修改,这就违背了常识逻辑。因此A需要在获取行锁前先获取表上的意向锁,这样后来的B就意识到自己无法获取整个表上的排他锁了(但B依然可以加一个意向锁,获取其他行上的行锁)。

因此,这里RowShare就是行级共享锁对应的表级意向锁(SELECT FOR SHARE|UPDATE命令获取),而RowExclusiveINSERT|UPDATE|DELETE获取)则是行级排他锁对应的表级意向锁。注意因为MVCC的存在,只读查询并不会在行上加锁。引入意向锁后的模型如图(c)所示。而合并MVCC与意向锁模型之后的锁模型如图(d)所示。

自斥锁

上面这个模型已经相当不错,但仍然存在一些问题,譬如自斥:这里RowExclusiveShare锁都不是自斥的。

举个例子,并发VACUUM不应阻塞数据写入,而且一个表上不应该允许多个VACUUM进程同时工作。因为不能阻塞写入,因此VACUUM所需的锁强度必须要比Share锁弱,弱于Share的最强锁为RowExclusive,不幸的是,该锁并不自斥。如果VACUUM使用该锁,就无法阻止单表上出现多个VACUUM进程。因此需要引入一个自斥版本的RowExclusive锁,即ShareUpdateExclusive锁。

同理,再比如执行触发器管理操作(创建,删除,启用)时,该操作不应阻塞读取和锁定,但必须禁止一切实际的数据写入,否则就难以判断某条元组的变更是否应该触发触发器。Share锁满足不阻塞读取和锁定的条件,但并不自斥,因此可能出现多个进程在同一个表上并发修改触发器。并发修改触发器会带来很多问题(譬如丢失更新,A将其配置为Replica Trigger,B将其配置为Always Trigger,都反回成功了,以谁为准?)。因此这里也需要一个自斥版本的Share锁,即ShareRowExclusive锁。

因此,引入两种自斥版本的锁后,就是PostgreSQL中的最终表级锁模型,如图(e)所示。

表级锁的命名与记忆

PostgreSQL的表级锁的命名有些诘屈聱牙,这是因为一些历史因素,但也可以总结出一些规律便于记忆。

  • 最初只有两种锁:共享锁(Share)与排他锁(Exclusive)。
    • 特征是只有一个单词,表示这是两种最基本的锁:读锁与写锁。
  • 多版本并发控制的出现,引入了多版本的共享锁与排他锁(AccessShareAccessExclusive)。
    • 特征是Access前缀,表示这是用于"多版本并发控制"的改良锁。
  • 为了处理并发写入之间的冲突,又引入了两种意向锁(RowShareRowExclusive
    • 特征是Row前缀,表示这是行级别共享/排他锁对应的表级意向锁。
  • 最后,为了处理意向排他锁与共享锁不自斥的问题,引入了这两种锁的自斥版本(ShareUpdateExclusive, ShareRowExclusive)。这两种锁的名称比较难记:
    • 都是以Share打头,以Exclusive结尾。表示这两种锁都是某种共享锁的自斥版本。
    • 两种锁强度围绕在Share前后,Update弱于ShareRow强于Share
    • ShareRowExclusive可以理解为Share + Row Exclusive,因为Share不排斥其他Share,但RowExclusive排斥Share,因此同时加这两种锁的结果等效于ShareRowExclusive,即SIX。
    • ShareUpdateExclusive可以理解为ShareUpdate + ExclusiveUPDATE操作持有RowExclusive锁,而ShareUpdate指的是本锁与普通的增删改(持RowExclusive锁)相容,而Exclusive则表示自己和自己不相容。
  • Share, ShareRowUpdate, Exclusive 这三种锁极少出现,基本可以无视。所以实际上主要用到的锁是:
    • 多版本两种:AccessShare, AccessExclusive
    • 意向锁两种:RowShare,RowExclusive
    • 自斥意向锁一种:ShareUpdateExclusive

显式加锁

通常表级锁会在相应命令执行中自动获取,但也可以手动显式获取。使用LOCK命令加锁的方式:

LOCK [ TABLE ] [ ONLY ] name [ * ] [, ...] [ IN lockmode MODE ] [ NOWAIT ]
  • 显式锁表必须在事务中进行,在事务外锁表会报错。
  • 锁定视图时,视图定义中所有出现的表都会被锁定。
  • 使用表继承时,默认父表和所有后代表都会加锁,指定ONLY选项则继承于该表的子表不会自动加锁。
  • 锁表或者锁视图需要对应的权限,例如AccessShare锁需要SELECT权限。
  • 默认获取的锁模式为AccessExclusive,即最强的锁。
  • LOCK TABLE只能获取表锁,默认会等待冲突的锁被释放,指定NOWAIT选项时,如果命令不能立刻获得锁就会中止并报错。
  • 命令一旦获取到锁, 会被在当前事务中一直持有。没有UNLOCK TABLE命令,锁总是在事务结束时释放。

例子:数据迁移

举个例子,以迁移数据为例,假设希望将某张表的数据迁移到另一个实例中。并保证在此期间旧表上的数据在迁移期间不发生变化,那么我们可以做的就是在复制数据前在表上显式加锁,并在复制结束,应用开始写入新表后释放。应用仍然可以从旧表上读取数据,但不允许写入。那么根据锁冲突矩阵,允许只读查询的锁要弱于AccessExclusive,阻止写入的锁不能弱于ShareRowExclusive,因此可以选择ShareRowExclusiveExclusive锁。因为拒绝写入意味着锁定没有任何意义,所以这里选择更强的Exclusive锁。

BEGIN;
LOCK TABLE tbl IN EXCLUSIVE MODE;
-- DO Something
COMMIT

锁的查询

PostgreSQL提供了一个系统视图pg_locks,包含了当前活动进程持锁的信息。可以锁定的对象包括:关系,页面,元组,事务标识(虚拟的或真实的),其他数据库对象(带有OID)。

CREATE TABLE pg_locks
(
    -- 锁针对的客体对象
    locktype           text, -- 锁类型:关系,页面,元组,事务ID,对象等
    database           oid,  -- 数据库OID
    relation           oid,  -- 关系OID
    page               integer, -- 关系内页号
    tuple              smallint, -- 页内元组号
    virtualxid         text,     -- 虚拟事务ID
    transactionid      xid,      -- 事务ID
    classid            oid,      -- 锁对象所属系统目录表本身的OID
    objid              oid,      -- 系统目录内的对象的OID
    objsubid           smallint, -- 列号
  
    -- 持有|等待锁的主体
    virtualtransaction text,     -- 持锁|等待锁的虚拟事务ID
    pid                integer,  -- 持锁|等待锁的进程PID
    mode               text,     -- 锁模式
    granted            boolean,  -- t已获取,f等待中
    fastpath           boolean   -- t通过fastpath获取
);
名称 类型 描述
locktype text 可锁对象的类型: relationextendpagetupletransactionidvirtualxidobjectuserlockadvisory
database oid 若锁目标为数据库(或下层对象),则为数据库OID,并引用pg_database.oid,共享对象为0,否则为空
relation oid 若锁目标为关系(或下层对象),则为关系OID,并引用pg_class.oid,否则为空
page integer 若锁目标为页面(或下层对象),则为页面号,否则为空
tuple smallint 若锁目标为元组,则为页内元组号,否则为空
virtualxid text 若锁目标为虚拟事务,则为虚拟事务ID,否则为空
transactionid xid 若锁目标为事务,则为事务ID,否则为空
classid oid 若目标为数据库对象,则为该对象相应系统目录的OID,并引用pg_class.oid,否则为空。
objid oid 锁目标在其系统目录中的OID,如目标不是普通数据库对象则为空
objsubid smallint 锁的目标列号(classidobjid指向表本身),若目标是某种其他普通数据库对象则此列为0,如果目标不是一个普通数据库对象则此列为空。
virtualtransaction text 持有或等待这个锁的虚拟ID
pid integer 持有或等待这个锁的服务器进程ID,如果此锁被一个预备事务所持有则为空
mode text 持有或者等待锁的模式
granted boolean 为真表示已经获得的锁,为假表示还在等待的锁
fastpath boolean 为真表示锁是通过fastpath获取的

样例数据

这个视图需要一些额外的知识才能解读。

  • 该视图是数据库集簇范围的视图,而非仅限于单个数据库,即可以看见其他数据库中的锁。
  • 一个进程在一个时间点只能等待至多一个锁,等待锁用granted=f表示,等待进程会休眠至其他锁被释放,或者系统检测到死锁。
  • 每个事务都有一个虚拟事务标识virtualtransaction(以下简称vxid),修改数据库状态(或者显式调用txid_current获取)的事务才会被分配一个真实的事务标识transactionid(简称txid),vxid|txid本身也是可以锁定的对象
  • 每个事务都会持有自己vxid上的Exclusive锁,如果有txid,也会同时持有其上的Exclusive锁(即同时持有txidvxid上的排它锁)。因此当一个事务需要等待另一个事务时,它会尝试获取另一个事务txid|vxid上的共享锁,因而只有当目标事务结束(自动释放自己事务标识上的Exclusive锁)时,等待事务才会被唤醒。
  • pg_locks视图通常并不会直接显示行级锁信息,因为这些信息存储在磁盘磁盘上(),如果真的有进程在等待行锁,显示的形式通常是一个事务等待另一个事务,而不是等待某个具体的行锁。
  • 咨询锁本质上的锁对象客体是一个数据库范畴内的BIGINT,classid里包含了该整数的高32bit,objid里包含有低32bit,objsubid里则说明了咨询锁的类型,单一Bigint则取值为1,两个int32则取值为2
  • 本视图并不一定能保证提供一个一致的快照,因为所有fastpath=true的锁信息是从每个后端进程收集而来的,而fastpath=false的锁是从常规锁管理器中获取的,同时谓词锁管理器中的数据也是单独获取的,因此这几种来源的数据之间可能并不一致。
  • 频繁访问本视图会对数据库系统性能产生影响,因为要对锁管理器加锁获取一致性快照。

虚拟事务

一个后端进程在整个生命周期中的每一个事务都会有一个自己的虚拟事务ID

PG中事务号是有限的(32-bit整型),会循环使用。为了节约事务号,PG只会为实际修改数据库状态的事务分配真实事务ID,而只读事务就不分配了,用虚拟事务ID凑合一下。txid是事务标识,全局共享,而vxid是虚拟事务标识,在短期内可以保证全局唯一性。因为vxid由两部分组成:BackendIDLocalTransactionId,前者是后端进程的标识符(本进程在内存中进程数组中的序号),后者是一个递增的事务计数器。因此两者组合即可获得一个暂时唯一的虚拟事务标识(之所以是暂时是因为这里的后端ID是有可能重复的)

typedef struct {
	BackendId	backendId;		/* 后端ID,初始化时确定,其实是后端进程数组内索引号 */
	LocalTransactionId localTransactionId;	/* 后端内本地使用的命令标ID,类似自增计数器 */
} VirtualTransactionId;

应用

常见操作的冲突关系

  • SELECTUPDATE|DELETE|INSERT不会相互阻塞,即使访问的是同一行。
  • I|U|D写入操作与I|U|D写入操作在表层面不会互斥,会在具体的行上通过RowExclusive锁实现。
  • SELECT FOR UPDATE锁定操作与I|U|D写入在表层级也不会互斥,仍然是通过具体元组上的行锁实现。
  • 并发VACUUM,并发创建索引等操作不会阻塞读写,但它们是自斥的,即同一时刻只会有一个(所以同时在一个表上执行两个CREATE INDEX CONCURRENTLY是没有意义的,不要被名字骗了)
  • 普通的索引创建CREATE INDEX,不带CONCURRENTLY会阻塞增删改,但不会阻塞查,很少用到。
  • 任何对于触发器的操作,或者约束类的操作,都会阻止增删改,但不会阻塞只读查询以及锁定。
  • 冷门的命令REFRESH MATERIALIZED VIEW CONCURRENTLY允许SELECT和锁定。
  • 大多数很硬的变更:VACUUM FULL, DROP TABLE, TRUNCATE, ALTER TABLE的大多数形式都会阻塞一切读取。

注意,锁虽有强弱之分,但冲突关系是对等的。一个持有AccessShare锁的SELECT会阻止后续的DROP TABLE获得AccessExclusive锁。后面的命令会进入锁队列中。

锁队列

PG中每个锁上都会有一个锁队列。如果事务A占有一个排他锁,那么事务B在尝试获取其上的锁时就会在其锁队列中等待。如果这时候事务C同样要获取该锁,那么它不仅要和事务A进行冲突检测,也要和B进行冲突检测,以及队列中其他的事务。这意味着当用户尝试获取一个很强的锁而未得等待时,已经会阻止后续新锁的获取。一个具体的例子是加列:

ALTER TABLE tbl ADD COLUMN mtime TIMESTAMP;

即使这是一个不带默认值的加列操作(不会重写整个表,因而很快),但本命令需要表上的AccessExclusive锁,如果这张表上面已经有不少查询,那么这个命令可能会等待相当一段时间。因为它需要等待其他查询结束并释放掉锁后才能执行。相应地,因为这条命令已经在等待队列中,后续的查询都会被它所阻塞。因此,当执行此类命令时的一个最佳实践是在此类命令前修改lock_timeout,从而避免雪崩。

SET lock_timeout TO '1s';
ALTER TABLE tbl ADD COLUMN mtime TIMESTAMP;

这个设计的好处是,命令不会饿死:不会出现源源不断的短小只读查询无限阻塞住一个排他操作。

加锁原则

  • 够用即可:使用满足条件的锁中最弱的锁模式
  • 越快越好:如果可能,可以用(长时间的弱锁+短时间的强锁)替换长时间的强锁
  • 递增获取:遵循2PL原则申请锁;越晚使用激进锁策略越好;在真正需要时再获取。
  • 相同顺序:获取锁尽量以一致的顺序获取,从而减小死锁的几率

最小化锁阻塞时长

除了手工锁定之外,很多常见的操作都会"锁表",最常见的莫过于添加新字段与添加新约束。这两种操作都会获取表上的AccessExclusive锁以阻止一切并发访问。当DBA需要在线维护数据库时应当最小化持锁的时间。

例如,为表添加新字段的ALTER TABLE ADD COLUMN子句,根据新列是否提供易变默认值,会重写整个表。

ALTER TABLE tbl ADD COLUMN mtime TIMESTAMP DEFAULT CURRENT_TIMESTAMP;

如果只是个小表,业务负载也不大,那么也许可以直接这么干。但如果是很大的表,以及很高的负载,那么阻塞的时间就会很可观。在这段时间里,命令都会持有表上的AccessExclusive锁阻塞一切访问。

可以通过先加一个空列,再慢慢更新的方式来最小化锁等待时间:

ALTER TABLE tbl ADD COLUMN mtime TIMESTAMP;
UPDATE tbl SET mtime = CURRENT_TIMESTAMP; -- 可以分批进行

这样,第一条加列操作的锁阻塞时间就会非常短,而后面的更新(重写)操作就可以以不阻塞读写的形式慢慢进行,最小化锁阻塞。

同理,当想要为表添加新的约束时(例如新的主键),也可以采用这种方式:

CREATE UNIQUE INDEX CONCURRENTLY tbl_pk ON tbl(id); -- 很慢,但不阻塞读写
ALTER TABLE tbl ADD CONSTRAINT tbl_pk PRIMARY KEY USING INDEX tbl_pk;  -- 阻塞读写,但很快

替代单纯的

ALTER TABLE tbl ADD PRIMARY KEY (id); 

GIN搜索的O(n2)负载度

GIN索引如果使用很长的关键词列表进行搜索,会导致性能显著下降。本文解释了为什么GIN索引关键词搜索的时间复杂度为O(n^2)

GIN索引如果使用很长的关键词列表进行搜索,会导致性能显著下降。本文解释了为什么GIN索引关键词搜索的时间复杂度为O(n^2)

Here is the detail of why that query have O(N^2) inside GIN implementation.


Details

Inspect the index example_keys_idx

postgres=# select oid,* from pg_class where relname = 'example_keys_idx';
-[ RECORD 1 ]-------+-----------------
oid                 | 20699
relname             | example_keys_idx
relnamespace        | 20692
reltype             | 0
reloftype           | 0
relowner            | 10
relam               | 2742
relfilenode         | 20699
reltablespace       | 0
relpages            | 2051
reltuples           | 300000
relallvisible       | 0
reltoastrelid       | 0
relhasindex         | f
relisshared         | f
relpersistence      | p
relkind             | i
relnatts            | 1
relchecks           | 0
relhasoids          | f
relhasrules         | f
relhastriggers      | f
relhassubclass      | f
relrowsecurity      | f
relforcerowsecurity | f
relispopulated      | t
relreplident        | n
relispartition      | f
relrewrite          | 0
relfrozenxid        | 0
relminmxid          | 0
relacl              |
reloptions          | {fastupdate=off}
relpartbound        |

Find index information via index’s oid

postgres=# select * from pg_index where indexrelid = 20699;
-[ RECORD 1 ]--+------
indexrelid     | 20699
indrelid       | 20693
indnatts       | 1
indnkeyatts    | 1
indisunique    | f
indisprimary   | f
indisexclusion | f
indimmediate   | t
indisclustered | f
indisvalid     | t
indcheckxmin   | f
indisready     | t
indislive      | t
indisreplident | f
indkey         | 2
indcollation   | 0
indclass       | 10075
indoption      | 0
indexprs       |
indpred        |

Find corresponding operator class for that index via indclass

postgres=# select * from pg_opclass where oid = 10075;
-[ RECORD 1 ]+----------
opcmethod    | 2742
opcname      | array_ops
opcnamespace | 11
opcowner     | 10
opcfamily    | 2745
opcintype    | 2277
opcdefault   | t
opckeytype   | 2283

Find four operator corresponding to operator faimily array_ops

postgres=# select * from pg_amop where amopfamily =2745;
-[ RECORD 1 ]--+-----
amopfamily     | 2745
amoplefttype   | 2277
amoprighttype  | 2277
amopstrategy   | 1
amoppurpose    | s
amopopr        | 2750
amopmethod     | 2742
amopsortfamily | 0
-[ RECORD 2 ]--+-----
amopfamily     | 2745
amoplefttype   | 2277
amoprighttype  | 2277
amopstrategy   | 2
amoppurpose    | s
amopopr        | 2751
amopmethod     | 2742
amopsortfamily | 0
-[ RECORD 3 ]--+-----
amopfamily     | 2745
amoplefttype   | 2277
amoprighttype  | 2277
amopstrategy   | 3
amoppurpose    | s
amopopr        | 2752
amopmethod     | 2742
amopsortfamily | 0
-[ RECORD 4 ]--+-----
amopfamily     | 2745
amoplefttype   | 2277
amoprighttype  | 2277
amopstrategy   | 4
amoppurpose    | s
amopopr        | 1070
amopmethod     | 2742
amopsortfamily | 0

https://www.postgresql.org/docs/10/xindex.html

Table 37.6. GIN Array Strategies

Operation Strategy Number
overlap 1
contains 2
is contained by 3
equal 4

When we access that index with && operator, we are using stragety 1 overlap, which corresponding operator oid is 2750.

postgres=# select * from pg_operator where oid = 2750;
-[ RECORD 1 ]+-----------------
oprname      | &&
oprnamespace | 11
oprowner     | 10
oprkind      | b
oprcanmerge  | f
oprcanhash   | f
oprleft      | 2277
oprright     | 2277
oprresult    | 16
oprcom       | 2750
oprnegate    | 0
oprcode      | arrayoverlap
oprrest      | arraycontsel
oprjoin      | arraycontjoinsel

The underlying C function to judge arrayoverlap is arrayoverlap in here

Datum
arrayoverlap(PG_FUNCTION_ARGS)
{
	AnyArrayType *array1 = PG_GETARG_ANY_ARRAY_P(0);
	AnyArrayType *array2 = PG_GETARG_ANY_ARRAY_P(1);
	Oid			collation = PG_GET_COLLATION();
	bool		result;

	result = array_contain_compare(array1, array2, collation, false,
								   &fcinfo->flinfo->fn_extra);

	/* Avoid leaking memory when handed toasted input. */
	AARR_FREE_IF_COPY(array1, 0);
	AARR_FREE_IF_COPY(array2, 1);

	PG_RETURN_BOOL(result);
}

It actually use array_contain_compare to test whether two array are overlap

static bool
array_contain_compare(AnyArrayType *array1, AnyArrayType *array2, Oid collation,
					  bool matchall, void **fn_extra)

Line 4177, we see a nested loop to iterate two array, which makes it O(N^2)

	for (i = 0; i < nelems1; i++)
	{
		Datum		elt1;
		bool		isnull1;

		/* Get element, checking for NULL */
		elt1 = array_iter_next(&it1, &isnull1, i, typlen, typbyval, typalign);

		/*
		 * We assume that the comparison operator is strict, so a NULL can't
		 * match anything.  XXX this diverges from the "NULL=NULL" behavior of
		 * array_eq, should we act like that?
		 */
		if (isnull1)
		{
			if (matchall)
			{
				result = false;
				break;
			}
			continue;
		}

		for (j = 0; j < nelems2; j++)

GeoIP 地理逆查询优化

在应用开发中,一个‘很常见’的需求就是GeoIP转换。将请求的来源IP转换为相应的地理坐标,或者行政区划(国家-省-市-县-乡-镇)

IP归属地查询的高效实现

在应用开发中,一个‘很常见’的需求就是GeoIP转换。将请求的来源IP转换为相应的地理坐标,或者行政区划(国家-省-市-县-乡-镇)。这种功能有很多用途,譬如分析网站流量的地理来源,或者干一些坏事。使用PostgreSQL可以多快好省,优雅高效地实现这一需求。


0x01 思路方法

通常网上的IP地理数据库的形式都是:start_ip, stop_ip , longitude, latitude,再缀上一些国家代码,城市代码,邮编之类的属性字段。大概长这样:

Column Type
start_ip text
end_ip text
longitude text
latitude text
country_code text
…… text

说到底,其核心是从IP地址段地理坐标点的映射。

典型查询实际上是给出一个IP地址,返回该地址对应的地理范围。其逻辑用SQL来表示差不多长这样:

SELECT longitude, latitude FROM geoip 
WHERE start_ip <= target_ip AND target_ip <= stop_ip;

不过,想直接提供服务,还有几个问题需要解决:

  • 第一个问题:虽然IPv4实际上是一个uint32,但我们已经完全习惯了123.123.123.123这种文本表示形式。而这种文本表示形式是无法比较大小的。
  • 第二个问题:这里的IP范围是用两个IP边界字段表示的范围,那么这个范围是开区间还是闭区间呢?是不是还需要一个额外字段来表示?
  • 第三个问题:想要高效地查询,那么在两个字段上的索引又该如何建立?
  • 第四个问题:我们希望所有的IP段相互之间不会出现重叠,但简单的建立在(start_ip, stop_ip)上的唯一约束并无法保证这一点,那又如何是好?

令人高兴的是,对于PostgreSQL而言,这些都不是问题。上面四个问题,可以轻松使用PostgreSQL的特性解决。

  • 网络数据类型:高性能,紧凑,灵活的网络地址表示。
  • 范围类型:对区间的良好抽象,对区间查询与操作的良好支持。
  • GiST索引:既能作用于IP地址段,也可以用于地理位置点。
  • Exclude约束:泛化的高级UNIQUE约束,从根本上确保数据完整性。

0x01 网络地址类型

PostgreSQL提供用于存储 IPv4、IPv6 和 MAC 地址的数据类型。包括cidrinet以及macaddr,并且提供了很多常见的操作函数,不需要再在程序中去实现一些繁琐重复的功能。

最常见的网络地址就是IPv4地址,对应着PostgreSQL内建的inet类型,inet类型可以用来存储IPv4,IPv6地址,或者带上一个可选的子网。当然这些细节操作都可以参阅文档,在此不详细展开。

一个需要注意的点就是,虽然我们知道IPv4实质上是一个Unsigned Integer,但在数据库中实际存储成INTEGER其实是不行的,因为SQL标准并不支持Unsigned这种用法,所以有一半的IP地址的表示就会被解释为负数,在比大小的时候产生令人惊异的结果,真要这么存请使用BIGINT。此外,直接面对一堆长长的整数也是相当令人头大的问题,inet是最佳的选择。

如果需要将IP地址(inet类型)与对应的整数相互转换,只要与0.0.0.0做加减运算即可;当然也可以使用以下函数,并创建一个类型转换,然后就能直接在inetbigint之间来回转换:

-- inet to bigint
CREATE FUNCTION inet2int(inet) RETURNS bigint AS $$
SELECT $1 - inet '0.0.0.0';
$$ LANGUAGE SQL  IMMUTABLE RETURNS NULL ON NULL INPUT;

-- bigint to inet
CREATE FUNCTION int2inet(bigint) RETURNS inet AS $$
SELECT inet '0.0.0.0' + $1;
$$ LANGUAGE SQL  IMMUTABLE RETURNS NULL ON NULL INPUT;

-- create type conversion
CREATE CAST (inet AS bigint) WITH FUNCTION inet2int(inet);
CREATE CAST (bigint AS inet) WITH FUNCTION int2inet(bigint);

-- test
SELECT 123456::BIGINT::INET;
SELECT '1.2.3.4'::INET::BIGINT;

-- 生成随机的IP地址
SELECT (random() * 4294967295)::BIGINT::INET;

inet之间的大小比较也相当直接,直接使用大小比较运算符就可以了。实际比较的是底下的整数值。这就解决了第一个问题。


0x02 范围类型

PostgreSQL的Range类型是一种很实用的功能,它与数组类似,属于一种泛型。只要是能被B树索引(可以比大小)的数据类型,都可以作为范围类型的基础类型。它特别适合用来表示区间:整数区间,时间区间,IP地址段等等。而且对于开区间,闭区间,区间索引这类问题有比较细致的考虑。

PostgreSQL内置了预定义的int4range, int8range, numrange, tsrange, tstzrange, daterange,开箱即用。但没有提供网络地址对应的范围类型,好在自己造一个非常简单:

CREATE TYPE inetrange AS RANGE(SUBTYPE = inet)

当然为了高效地支持GiST索引查询,还需要实现一个距离度量,告诉索引两个inet之间的距离应该如何计算:

-- 定义基本类型间的距离度量
CREATE FUNCTION inet_diff(x INET, y INET) RETURNS FLOAT AS $$
  SELECT (x - y) :: FLOAT;
$$ LANGUAGE SQL IMMUTABLE STRICT;

-- 重新创建inetrange类型,使用新定义的距离度量。
CREATE TYPE inetrange AS RANGE(
  SUBTYPE = inet,
  SUBTYPE_DIFF = inet_diff
)

幸运的是,俩网络地址之间的距离定义天然就有一个很简单的计算方法,减一下就好了。

这个新定义的类型使用起来也很简单,构造函数会自动生成:

geo=# select misc.inetrange('64.60.116.156','64.60.116.161','[)');
inetrange | [64.60.116.156,64.60.116.161)

geo=# select '[64.60.116.156,64.60.116.161]'::inetrange;
inetrange | [64.60.116.156,64.60.116.161]

方括号和圆括号分别表示闭区间和开区间,与数学中的表示方法一致。

同时,检测一个IP地址是否落在给定的IP范围内也是很直接的:

geo=# select '[64.60.116.156,64.60.116.161]'::inetrange @> '64.60.116.160'::inet as res;
res | t

有了范围类型,就可以着手构建我们的数据表了。


0x03 范围索引

实际上,找一份IP地理对应数据花了我一个多小时,但完成这个需求只用了几分钟。

假设已经有了这样一份数据:

create table geoips
(
  ips          inetrange,
  geo          geometry(Point),
  country_code text,
  region_code  text,
  city_name    text,
  ad_code      text,
  postal_code  text
);

里面的数据大概长这样:

SELECT ips,ST_AsText(geo) as geo,country_code FROM geoips

 [64.60.116.156,64.60.116.161] | POINT(-117.853 33.7878) | US
 [64.60.116.139,64.60.116.154] | POINT(-117.853 33.7878) | US
 [64.60.116.138,64.60.116.138] | POINT(-117.76 33.7081)  | US

那么查询包含某个IP地址的记录就可以写作:

SELECT * FROM ip WHERE ips @> inet '67.185.41.77';

对于600万条记录,约600M的表,在笔者的机器上暴力扫表的平均用时是900ms,差不多单核QPS是1.1,48核生产机器也就差不多三四十的样子。肯定是没法用的。

CREATE INDEX ON geoips USING GiST(ips);

查询用时从1秒变为340微秒,差不多3000倍的提升。

-- pgbench
\set ip random(0,4294967295)
SELECT * FROM geoips WHERE ips @> :ip::BIGINT::INET;

-- result
latency average = 0.342 ms
tps = 2925.100036 (including connections establishing)
tps = 2926.151762 (excluding connections establishing)

折算成生产QPS差不多是十万QPS,啧啧啧,美滋滋。

如果需要把地理坐标转换为行政区划,可以参考上一篇文章:使用PostGIS高效解决行政区划归属地理编码问题。

一次地理编码也就是100微秒,从IP转换为省市区县整个的QPS,单机几万基本问题不大(全天满载相当于七八十亿次调用,根本用不满)。


0x04 EXCLUDE约束

问题至此已经基本解决了,不过还有一个问题。如何避免一个IP查出两条记录的尴尬情况?

数据完整性是极其重要的,但由应用保证的数据完整性并不总是那么靠谱:人会犯傻,程序会出错。如果能通过数据库约束来Enforce数据完整性,那是再好不过了。

然而,有一些约束是相当复杂的,例如确保表中的IP范围不发生重叠,类似的,确保地理区划表中各个城市的边界不会重叠。传统上要实现这种保证是相当困难的:譬如UNIQUE约束就无法表达这种语义,CHECK与存储过程或者触发器虽然可以实现这种检查,但也相当tricky。PostgreSQL提供的EXCLUDE约束可以优雅地解决这个问题。修改我们的geoips表:

create table geoips
(
  ips          inetrange,
  geo          geometry(Point),
  country_code text,
  region_code  text,
  city_name    text,
  ad_code      text,
  postal_code  text,
  EXCLUDE USING gist (ips WITH &&) DEFERRABLE INITIALLY DEFERRED 
);

这里EXCLUDE USING gist (ips WITH &&) 的意思就是ips字段上不允许出现范围重叠,即新插入的字段不能与任何现存范围重叠(&&为真)。而DEFERRABLE INITIALLY IMMEDIATE 表示在语句结束时再检查所有行上的约束。创建该约束会自动在ips字段上创建GIST索引,因此无需手工创建了。


0x05 小结

本文介绍了如何使用PostgreSQL特性高效而优雅地解决IP归属地查询的问题。性能表现优异,600w记录0.3ms定位;复杂度低到发指:只要一张表DDL,连索引都不用显式创建就解决了这一问题;数据完整性有充分的保证:百行代码才能解决的问题现在只要添加约束即可,从根本上保证数据完整性。

PostgreSQL这么棒棒,快快学起来用起来吧~。 什么?你问我数据哪里找?搜索MaxMind有真相,在隐秘的小角落能够找到不要钱的GeoIP数据。

PostgreSQL的触发器使用注意事项

详细了解PostgreSQL中触发器的管理与使用

概览

  • 触发器行为概述
  • 触发器的分类
  • 触发器的功能
  • 触发器的种类
  • 触发器的触发
  • 触发器的创建
  • 触发器的修改
  • 触发器的查询
  • 触发器的性能

触发器概述

触发器行为概述:英文中文

触发器分类

触发时机:BEFORE, AFTER, INSTEAD

触发事件:INSERT, UPDATE, DELETE,TRUNCATE

触发范围:语句级,行级

内部创建:用于约束的触发器,用户定义的触发器

触发模式:origin|local(O), replica(R),disable(D)

触发器操作

触发器的操作通过SQL DDL语句进行,包括CREATE|ALTER|DROP TRIGGER,以及ALTER TABLE ENABLE|DISABLE TRIGGER进行。注意PostgreSQL内部的约束是通过触发器实现的。

创建

CREATE TRIGGER 可以用于创建触发器。

CREATE [ CONSTRAINT ] TRIGGER name { BEFORE | AFTER | INSTEAD OF } { event [ OR ... ] }
    ON table_name
    [ FROM referenced_table_name ]
    [ NOT DEFERRABLE | [ DEFERRABLE ] [ INITIALLY IMMEDIATE | INITIALLY DEFERRED ] ]
    [ REFERENCING { { OLD | NEW } TABLE [ AS ] transition_relation_name } [ ... ] ]
    [ FOR [ EACH ] { ROW | STATEMENT } ]
    [ WHEN ( condition ) ]
    EXECUTE { FUNCTION | PROCEDURE } function_name ( arguments )

event包括
    INSERT
    UPDATE [ OF column_name [, ... ] ]
    DELETE
    TRUNCATE

删除

DROP TRIGGER 用于移除触发器。

DROP TRIGGER [ IF EXISTS ] name ON table_name [ CASCADE | RESTRICT ]

修改

ALTER TRIGGER 用于修改触发器定义,注意这里只能修改触发器名,以及其依赖的扩展。

ALTER TRIGGER name ON table_name RENAME TO new_name
ALTER TRIGGER name ON table_name DEPENDS ON EXTENSION extension_name

启用禁用触发器,修改触发模式是通过ALTER TABLE的子句实现的。

ALTER TABLE 包含了一系列触发器修改的子句:

ALTER TABLE tbl ENABLE TRIGGER tgname; -- 设置触发模式为O (本地连接写入触发,默认)
ALTER TABLE tbl ENABLE REPLICA TRIGGER tgname; -- 设置触发模式为R (复制连接写入触发)
ALTER TABLE tbl ENABLE ALWAYS TRIGGER tgname; -- 设置触发模式为A (总是触发)
ALTER TABLE tbl DISABLE TRIGGER tgname; -- 设置触发模式为D (禁用)

注意这里在ENABLEDISABLE触发器时,可以指定用USER替换具体的触发器名称,这样可以只禁用用户显式创建的触发器,不会把系统用于维持约束的触发器也禁用了。

ALTER TABLE tbl_name DISABLE TRIGGER USER; -- 禁用所有用户定义的触发器,系统触发器不变  
ALTER TABLE tbl_name DISABLE TRIGGER ALL;  -- 禁用所有触发器
ALTER TABLE tbl_name ENABLE TRIGGER USER;  -- 启用所有用户定义的触发器
ALTER TABLE tbl_name ENABLE TRIGGER ALL;   -- 启用所有触发器

查询

获取表上的触发器

最简单的方式当然是psql的\d+ tablename。但这种方式只会列出用户创建的触发器,不会列出与表上约束相关联的触发器。直接查询系统目录pg_trigger,并通过tgrelid用表名过滤

SELECT * FROM pg_trigger WHERE tgrelid = 'tbl_name'::RegClass;

获取触发器定义

pg_get_triggerdef(trigger_oid oid)函数可以给出触发器的定义。

该函数输入参数为触发器OID,返回创建触发器的SQL DDL语句。

SELECT pg_get_triggerdef(oid) FROM pg_trigger; -- WHERE xxx

触发器视图

pg_trigger (中文) 提供了系统中触发器的目录

名称 类型 引用 描述
oid oid 触发器对象标识,系统隐藏列
tgrelid oid pg_class.oid 触发器所在的表 oid
tgname name 触发器名,表级命名空间内不重名
tgfoid oid pg_proc.oid 触发器所调用的函数
tgtype int2 触发器类型,触发条件,详见注释
tgenabled char 触发模式,详见下。`O
tgisinternal bool 如果是内部用于约束的触发器则为真
tgconstrrelid oid pg_class.oid 参照完整性约束中被引用的表,无则为0
tgconstrindid oid pg_class.oid 支持约束的相关索引,没有则为0
tgconstraint oid pg_constraint.oid 与触发器相关的约束对象
tgdeferrable bool DEFERRED则为真
tginitdeferred bool INITIALLY DEFERRED则为真
tgnargs int2 传入触发器函数的字符串参数个数
tgattr int2vector pg_attribute.attnum 如果是列级更新触发器,这里存储列号,否则为空数组。
tgargs bytea 传递给触发器的参数字符串,C风格零结尾字符串
tgqual pg_node_tree 触发器WHEN条件的内部表示
tgoldtable name OLD TABLEREFERENCING列名称,无则为空
tgnewtable name NEW TABLEREFERENCING列名称,无则为空

触发器类型

触发器类型tgtype包含了触发器触发条件相关信息:BEFORE|AFTER|INSTEAD OF, INSERT|UPDATE|DELETE|TRUNCATE

TRIGGER_TYPE_ROW         (1 << 0)  // [0] 0:语句级 	1:行级
TRIGGER_TYPE_BEFORE      (1 << 1)  // [1] 0:AFTER 	1:BEFORE
TRIGGER_TYPE_INSERT      (1 << 2)  // [2] 1: INSERT
TRIGGER_TYPE_DELETE      (1 << 3)  // [3] 1: DELETE
TRIGGER_TYPE_UPDATE      (1 << 4)  // [4] 1: UPDATE
TRIGGER_TYPE_TRUNCATE    (1 << 5)  // [5] 1: TRUNCATE
TRIGGER_TYPE_INSTEAD     (1 << 6)  // [6] 1: INSTEAD OF 

触发器模式

触发器tgenabled字段控制触发器的工作模式,参数session_replication_role 可以用于配置触发器的触发模式。该参数可以在会话层级更改,可能的取值包括:origin(default),replica,local

(D)isable触发器永远不会被触发,(A)lways触发器在任何情况下触发, (O)rigin触发器会在origin|local模式触发(默认),而 (R)eplica触发器replica模式触发。R触发器主要用于逻辑复制,例如pglogical的复制连接就会将会话参数session_replication_role设置为replica,而R触发器只会在该连接进行的变更上触发。

ALTER TABLE tbl ENABLE TRIGGER tgname; -- 设置触发模式为O (本地连接写入触发,默认)
ALTER TABLE tbl ENABLE REPLICA TRIGGER tgname; -- 设置触发模式为R (复制连接写入触发)
ALTER TABLE tbl ENABLE ALWAYS TRIGGER tgname; -- 设置触发模式为A (始终触发)
ALTER TABLE tbl DISABLE TRIGGER tgname; -- 设置触发模式为D (禁用)

information_schema中还有两个触发器相关的视图:information_schema.triggers, information_schema.triggered_update_columns,表过不提。

触发器FAQ

触发器可以建在哪些类型的表上?

普通表(分区表主表,分区表分区表,继承表父表,继承表子表),视图,外部表。

触发器的类型限制

  • 视图上不允许建立BEFOREAFTER触发器(不论是行级还是语句级)
  • 视图上只能建立INSTEAD OF触发器,INSERTEAD OF触发器也只能建立在视图上,且只有行级,不存在语句级INSTEAD OF触发器。
  • INSTEAD OF` 触发器只能定义在视图上,并且只能使用行级触发器,不能使用语句级触发器。

触发器与锁

在表上创建触发器会先尝试获取表级的Share Row Exclusive Lock。这种锁会阻止底层表的数据变更,且自斥。因此创建触发器会阻塞对表的写入。

触发器与COPY的关系

COPY只是消除了数据解析打包的开销,实际写入表中时仍然会触发触发器,就像INSERT一样。

PostgreSQL开发规约(2018版)

微信公众号原文

0x00背景

没有规矩,不成方圆。

PostgreSQL的功能非常强大,但是要把PostgreSQL用好,需要后端、运维、DBA的协力配合。

本文针对PostgreSQL数据库原理与特性,整理了一份开发规范,希望可以减少大家在使用PostgreSQL数据库过程中遇到的困惑。你好我也好,大家都好。

0x01 命名规范

无名,万物之始,有名,万物之母。

【强制】 通用命名规则

  • 本规则适用于所有对象名,包括:库名、表名、表名、列名、函数名、视图名、序列号名、别名等。
  • 对象名务必只使用小写字母,下划线,数字,但首字母必须为小写字母,常规表禁止以_打头。
  • 对象名长度不超过63个字符,命名统一采用snake_case
  • 禁止使用SQL保留字,使用select pg_get_keywords(); 获取保留关键字列表。
  • 禁止出现美元符号,禁止使用中文,不要以pg开头。
  • 提高用词品味,做到信达雅;不要使用拼音,不要使用生僻冷词,不要使用小众缩写。

【强制】 库命名规则

  • 库名最好与应用或服务保持一致,必须为具有高区分度的英文单词。
  • 命名必须以<biz>-开头,<biz>为具体业务线名称,如果是分片库必须以-shard结尾。
  • 多个部分使用-连接。例如:<biz>-chat-shard<biz>-payment等,总共不超过三段。

【强制】 角色命名规范

  • 数据库su有且仅有一个:postgres,用于流复制的用户命名为replication
  • 生产用户命名使用<biz>-作为前缀,具体功能作为后缀。
  • 所有数据库默认有三个基础角色: <biz>-read<biz>-write<biz>-usage,分别拥有所有表的只读,只写,函数的执行权限。
  • 生产用户,ETL用户,个人用户通过继承相应的基础角色获取权限。
  • 更为精细的权限控制使用独立的角色与用户,依业务而异。

【强制】 模式命名规则

  • 业务统一使用<*>作为模式名,<*>为业务定义的名称,必须设置为search_path首位元素。
  • dbamonitortrash为保留模式名。
  • 分片模式命名规则采用:rel_<partition_total_num>_<partition_index>
  • 无特殊理由不应在其他模式中创建对象。

【推荐】 关系命名规则

  • 关系命名以表意清晰为第一要义,不要使用含混的缩写,也不应过分冗长,遵循通用命名规则。
  • 表名应当使用复数名词,与历史惯例保持一致,但应尽量避免带有不规则复数形式的单词。
  • 视图以v_作为命名前缀,物化视图使用mv_作为命名前缀,临时表以tmp_作为命名前缀。
  • 继承或分区表应当以父表表名作为前缀,并以子表特性(规则,分片范围等)作为后缀。

【推荐】 索引命名规则

  • 创建索引时如有条件应当指定索引名称,并与PostgreSQL默认命名规则保持一致,避免重复执行时建立重复索引。
  • 用于主键的索引以_pkey结尾,唯一索引以_key结尾,用于EXCLUDED约束的索引以_excl结尾,普通索引以_idx结尾。

【推荐】 函数命名规则

  • select,insert,delete,update,upsert打头,表示动作类型。
  • 重要参数可以通过_by_ids, _by_user_ids的后缀在函数名中体现。
  • 避免函数重载,同名函数尽量只保留一个。
  • 禁止通过BIGINT/INTEGER/SMALLINT等整型进行重载,调用时可能产生歧义。

【推荐】 字段命名规则

  • 不得使用系统列保留字段名:oid, xmin, xmax,cmin, cmax, ctid等。
  • 主键列通常命名为id,或以id作为后缀。
  • 创建时间通常命名为created_time,修改时间通常命名为updated_time
  • 布尔型字段建议使用is_has_等作为前缀。
  • 其余各字段名需与已有表命名惯例保持一致。

【推荐】 变量命名规则

  • 存储过程与函数中的变量使用命名参数,而非位置参数。
  • 如果参数名与对象名出现冲突,在参数后添加_,例如user_id_

【推荐】 注释规范

  • 尽量为对象提供注释(COMMENT),注释使用英文,言简意赅,一行为宜。
  • 对象的模式或内容语义发生变更时,务必一并更新注释,与实际情况保持同步。

0x02 设计规范

Suum cuique

【强制】 字符编码必须为UTF8

  • 禁止使用其他任何字符编码。

【强制】 容量规划

  • 单表记录过亿,或超过10GB的量级,可以考虑开始进行分表。
  • 单表容量超过1T,单库容量超过2T。需要考虑分片。

【强制】 不要滥用存储过程

  • 存储过程适用于封装事务,减少并发冲突,减少网络往返,减少返回数据量,执行少量自定义逻辑。
  • 存储过程不适合进行复杂计算,不适合进行平凡/频繁的类型转换与包装。

【强制】 存储计算分离

  • 移除数据库中不必要的计算密集型逻辑,例如在数据库中使用SQL进行WGS84到其他坐标系的换算。
  • 例外:与数据获取、筛选密切关联的计算逻辑允许在数据库中进行,如PostGIS中的几何关系判断。

【强制】 主键与身份列

  • 每个表都必须有身份列,原则上必须有主键,最低要求为拥有非空唯一约束
  • 身份列用于唯一标识表中的任一元组,逻辑复制与诸多三方工具有赖于此。

【强制】 外键

  • 不建议使用外键,建议在应用层解决。使用外键时,引用必须设置相应的动作:SET NULL, SET DEFAULT, CASCADE,慎用级联操作。

【强制】 慎用宽表

  • 字段数目超过15个的表视作宽表,宽表应当考虑进行纵向拆分,通过相同的主键与主表相互引用。
  • 因为MVCC机制,宽表的写放大现象比较明显,尽量减少对宽表的频繁更新。

【强制】 配置合适的默认值

  • 有默认值的列必须添加DEFAULT子句指定默认值。
  • 可以在默认值中使用函数,动态生成默认值(例如主键发号器)。

【强制】 合理应对空值

  • 字段语义上没有零值与空值区分的,不允许空值存在,须为列配置NOT NULL约束。

【强制】 唯一约束通过数据库强制

  • 唯一约束须由数据库保证,任何唯一列须有唯一约束。
  • EXCLUDE约束是泛化的唯一约束,可以在低频更新场景下用于保证数据完整性。

【强制】 注意整数溢出风险

  • 注意SQL标准不提供无符号整型,超过INTMAX但没超过UINTMAX的值需要升格存储。
  • 不要存储超过INT64MAX的值到BIGINT列中,会溢出为负数。

【强制】 统一时区

  • 使用TIMESTAMP存储时间,采用utc时区。
  • 统一使用ISO-8601格式输入输出时间类型:2006-01-02 15:04:05,避免DMY与MDY问题。
  • 使用TIMESTAMPTZ时,采用GMT/UTC时间,0时区标准时。

【强制】 及时清理过时函数

  • 不再使用的,被替换的函数应当及时下线,避免与未来的函数发生冲突。

【推荐】 主键类型

  • 主键通常使用整型,建议使用BIGINT,允许使用不超过64字节的字符串。
  • 主键允许使用Serial自动生成,建议使用Default next_id()发号器函数。

【推荐】 选择合适的类型

  • 能使用专有类型的,不使用字符串。(数值,枚举,网络地址,货币,JSON,UUID等)
  • 使用正确的数据类型,能显著提高数据存储,查询,索引,计算的效率,并提高可维护性。

【推荐】 使用枚举类型

  • 较稳定的,取值空间较小(十几个内)的字段应当使用枚举类型,不要使用整型与字符串表示。
  • 使用枚举类型有性能、存储、可维护性上的优势。

【推荐】 选择合适的文本类型

  • PostgreSQL的文本类型包括 char(n), varchar(n), text
  • 通常建议使用varchartext,带有(n)修饰符的类型会检查字符串长度,会导致微小的额外开销,对字符串长度有限制时应当使用varchar(n),避免插入过长的脏数据。
  • 避免使用char(n),为了与SQL标准兼容,该类型存在不合直觉的行为表现(补齐空格与截断),且并没有存储和性能优势。

【推荐】 选择合适的数值类型

  • 常规数值字段使用INTEGER。主键、容量拿不准的数值列使用BIGINT
  • 无特殊理由不要用SMALLINT,性能与存储提升很小,会有很多额外的问题。
  • REAL表示4字节浮点数,FLOAT表示8字节浮点数
  • 浮点数仅可用于末尾精度无所谓的场景,例如地理坐标,不要对浮点数使用等值判断。
  • 精确数值类型使用NUMERIC,注意精度和小数位数设置。
  • 货币数值类型使用MONEY

【推荐】 使用统一的函数创建语法

  • 签名单独占用一行(函数名与参数),返回值单启一行,语言为第一个标签。
  • 一定要标注函数易变性等级:IMMUTABLE, STABLE, VOLATILE
  • 添加确定的属性标签,如:RETURNS NULL ON NULL INPUT,PARALLEL SAFE,ROWS 1,注意版本兼容性。
CREATE OR REPLACE FUNCTION
  nspname.myfunc(arg1_ TEXT, arg2_ INTEGER)
  RETURNS VOID
LANGUAGE SQL
STABLE
PARALLEL SAFE
ROWS 1
RETURNS NULL ON NULL INPUT
AS $function$
SELECT 1;
$function$;

【推荐】 针对可演化性而设计

  • 在设计表时,应当充分考虑未来的扩展需求,可以在建表时适当添加1~3个保留字段。
  • 对于多变的非关键字段可以使用JSON类型。

【推荐】 选择合理的规范化等级

  • 允许适当降低规范化等级,减少多表连接以提高性能。

【推荐】 使用新版本

  • 新版本有无成本的性能提升,稳定性提升,有更多新功能。
  • 充分利用新特性,降低设计复杂度。

【推荐】 慎用触发器

  • 触发器会提高系统的复杂度与维护成本,不鼓励使用。

0x03 索引规范

Wer Ordnung hält, ist nur zu faul zum Suchen.

【强制】 在线查询必须有配套索引

  • 所有在线查询必须针对其访问模式设计相应索引,除极个别小表外不允许全表扫描。
  • 索引有代价,不允许创建不使用的索引。

【强制】 禁止在大字段上建立索引

  • 被索引字段大小无法超过2KB(1/3的页容量),原则上禁止超过64个字符。
  • 如有大字段索引需求,可以考虑对大字段取哈希,并建立函数索引。或使用其他类型的索引(GIN)。

【强制】 明确空值排序规则

  • 如在可空列上有排序需求,需要在查询与索引中明确指定NULLS FIRST还是NULLS LAST
  • 注意,DESC排序的默认规则是NULLS FIRST,即空值会出现在排序的最前面,通常这不是期望行为。
  • 索引的排序条件必须与查询匹配,如:create index on tbl (id desc nulls last);

【强制】 利用GiST索引应对近邻查询问题

  • 传统B树索引无法提供对KNN问题的良好支持,应当使用GiST索引。

【推荐】 利用函数索引

  • 任何可以由同一行其他字段推断得出的冗余字段,可以使用函数索引替代。
  • 对于经常使用表达式作为查询条件的语句,可以使用表达式或函数索引加速查询。
  • 典型场景:建立大字段上的哈希函数索引,为需要左模糊查询的文本列建立reverse函数索引。

【推荐】 利用部分索引

  • 查询中查询条件固定的部分,可以使用部分索引,减小索引大小并提升查询效率。
  • 查询中某待索引字段若只有有限几种取值,也可以建立几个相应的部分索引。

【推荐】 利用范围索引

  • 对于值与堆表的存储顺序线性相关的数据,如果通常的查询为范围查询,建议使用BRIN索引。
  • 最典型场景如仅追加写入的时序数据,BRIN索引更为高效。

【推荐】 关注联合索引的区分度

  • 区分度高的列放在前面

0x04 查询规范

The limits of my language mean the limits of my world.

—Ludwig Wittgenstein

【强制】 读写分离

  • 原则上写请求走主库,读请求走从库。
  • 例外:需要读己之写的一致性保证,且检测到显著的复制延迟。

【强制】 快慢分离

  • 生产中1毫秒以内的查询称为快查询,生产中超过1秒的查询称为慢查询。
  • 慢查询必须走离线从库,必须设置相应的超时。
  • 生产中的在线普通查询执行时长,原则上应当控制在1ms内。
  • 生产中的在线普通查询执行时长,超过10ms需修改技术方案,优化达标后再上线。
  • 在线查询应当配置10ms数量级或更快的超时,避免堆积造成雪崩。
  • Master与Slave角色不允许大批量拉取数据,数仓ETL程序应当从Offline从库拉取数据

【强制】 主动超时

  • 为所有的语句配置主动超时,超时后主动取消请求,避免雪崩。
  • 周期性执行的语句,必须配置小于执行周期的超时。

【强制】 关注复制延迟

  • 应用必须意识到主从之间的同步延迟,并妥善处理好复制延迟超出合理范围的情况
  • 平时在0.1ms的延迟,在极端情况下可能达到十几分钟甚至小时量级。应用可以选择从主库读取,稍后再度,或报错。

【强制】 使用连接池

  • 应用必须通过连接池访问数据库,连接6432端口的pgbouncer而不是5432的postgres。
  • 注意使用连接池与直连数据库的区别,一些功能可能无法使用(比如Notify/Listen),也可能存在连接污染的问题。

【强制】 禁止修改连接状态

  • 使用公共连接池时禁止修改连接状态,包括修改连接参数,修改搜索路径,更换角色,更换数据库。
  • 万不得已修改后必须彻底销毁连接,将状态变更后的连接放回连接池会导致污染扩散。

【强制】 重试失败的事务

  • 查询可能因为并发争用,管理员命令等原因被杀死,应用需要意识到这一点并在必要时重试。
  • 应用在数据库大量报错时可以触发断路器熔断,避免雪崩。但要注意区分错误的类型与性质。

【强制】 掉线重连

  • 连接可能因为各种原因被中止,应用必须有掉线重连机制。
  • 可以使用SELECT 1作为心跳包查询,检测连接的有消息,并定期保活。

【强制】 在线服务应用代码禁止执行DDL

  • 不要在应用代码里搞大新闻。

【强制】 显式指定列名

  • 避免使用SELECT *,或在RETURNING子句中使用*。请使用具体的字段列表,不要返回用不到的字段。当表结构发生变动时(例如,新值列),使用列通配符的查询很可能会发生列数不匹配的错误。
  • 例外:当存储过程返回具体的表行类型时,允许使用通配符。

【强制】 禁止在线查询全表扫描

  • 例外情况:常量极小表,极低频操作,表/返回结果集很小(百条记录/百KB内)。
  • 在首层过滤条件上使用诸如!=, <>的否定式操作符会导致全表扫描,必须避免。

【强制】 禁止在事务中长时间等待

  • 开启事务后必须尽快提交或回滚,超过10分钟的IDEL IN Transaction将被强制杀死。
  • 应用应当开启AutoCommit,避免BEGIN之后没有配对的ROLLBACKCOMMIT
  • 尽量使用标准库提供的事务基础设施,不到万不得已不要手动控制事务。

【强制】 使用游标后必须及时关闭

【强制】 科学计数

  • count(*)统计行数的标准语法,与空值无关。
  • count(col)统计的是col列中的非空记录数。该列中的NULL值不会被计入。
  • count(distinct col)col列除重计数,同样忽视空值,即只统计非空不同值的个数。
  • count((col1, col2))对多列计数,即使待计数的列全为空也会被计数,(NULL,NULL)有效。
  • a(distinct (col1, col2))对多列除重计数,即使待计数列全为空也会被计数,(NULL,NULL)有效。

【强制】 注意聚合函数的空值问题

  • 除了count之外的所有聚合函数都会忽略空值输入,因此当输入值全部为空时,结果是NULL。但count(col)在这种情况下会返回0,是一个例外。
  • 如果聚集函数返回空并不是期望的结果,使用coalesce来设置缺省值。

【强制】谨慎处理空值

  • 明确区分零值与空值,空值使用IS NULL进行等值判断,零值使用常规的=运算符进行等值判断。
  • 空值作为函数输入参数时应当带有类型修饰符,否则对于有重载的函数将无法识别使用何者。
  • 注意空值比较逻辑:任何涉及到空值比较运算结果都是unknown,需要注意unknown参与布尔运算的逻辑:
    • andTRUE or UNKNOWN会因为逻辑短路返回TRUE
    • orFALSE and UNKNOWN会因为逻辑短路返回FALSE
    • 其他情况只要运算对象出现UNKNOWN,结果都是UNKNOWN
  • 空值与任何值的逻辑判断,其结果都为空值,例如NULL=NULL返回结果是NULL而不是TRUE/FALSE
  • 涉及空值与非空值的等值比较,请使用``IS DISTINCT FROM 进行比较,保证比较结果非空。
  • 空值与聚合函数:聚合函数当输入值全部为NULL时,返回结果为NULL。

【强制】 注意序列号空缺

  • 当使用Serial类型时,INSERTUPSERT等操作都会消耗序列号,该消耗不会随事务失败而回滚。
  • 当使用整型作为主键,且表存在频繁插入冲突时,需要关注整型溢出的问题。

【推荐】 重复查询使用准备语句

  • 重复的查询应当使用准备语句(Prepared Statement),消除数据库硬解析的CPU开销。
  • 准备语句会修改连接状态,请注意连接池对于准备语句的影响。

【推荐】 选择合适的事务隔离等级

  • 默认隔离等级为读已提交,适合大多数简单读写事务,普通事务选择满足需求的最低隔离等级。
  • 需要事务级一致性快照的写事务,请使用可重复读隔离等级。
  • 对正确性有严格要求的写入事务请使用可序列化隔离等级。
  • 在RR与SR隔离等级出现并发冲突时,应当视错误类型进行积极的重试。

【推荐】 判断结果存在性不要使用count

  • 使用SELECT 1 FROM tbl WHERE xxx LIMIT 1判断是否存满足条件的列,要比Count快。
  • 可以使用select exists(select * FROM app.sjqq where xxx limit 1)将存在性结果转换为布尔值。

【推荐】 使用RETURNING子句

  • 如果用户需要在插入数据和,删除数据前,或者修改数据后马上拿到插入或被删除或修改后的数据,建议使用RETURNING子句,减少数据库交互次数。

【推荐】 使用UPSERT简化逻辑

  • 当业务出现插入-失败-更新的操作序列时,考虑使用UPSERT替代。

【推荐】 利用咨询锁应对热点并发

  • 针对单行记录的极高频并发写入(秒杀),应当使用咨询锁对记录ID进行锁定。
  • 如果能在应用层次解决高并发争用,就不要放在数据库层面进行。

【推荐】优化IN操作符

  • 使用EXISTS子句代替IN操作符,效果更佳。
  • 使用=ANY(ARRAY[1,2,3,4])代替IN (1,2,3,4),效果更佳。

【推荐】 不建议使用左模糊搜索

  • 左模糊搜索WHERE col LIKE '%xxx'无法充分利用B树索引,如有需要,可用reverse表达式函数索引。

【推荐】 使用数组代替临时表

  • 考虑使用数组替代临时表,例如在获取一系列ID的对应记录时。=ANY(ARRAY[1,2,3])要比临时表JOIN好。

0x05 发布规范

【强制】 发布形式

  • 目前以邮件形式提交发布,发送邮件至dba@p1.com 归档并安排提交。
  • 标题清晰:xx项目需在xx库执行xx动作。
  • 目标明确:每个步骤需要在哪些实例上执行哪些操作,结果如何校验。
  • 回滚方案:任何变更都需要提供回滚方案,新建也需要提供清理脚本。

【强制】发布评估

  • 线上数据库发布需要经过研发自测,主管审核,(可选QA审核),DBA审核几个评估阶段。
  • 自测阶段应当确保变更在开发、预发环境执行正确无误。
    • 如果是新建表,应当给出记录数量级,数据日增量预估值,读写量级预估。
    • 如果是新建函数,应当给出压测报告,至少需要给出平均执行时间。
    • 如果是模式迁移,必须梳理清楚所有上下游依赖。
  • Team Leader需要对变更进行评估与审核,对变更内容负责。
  • DBA对发布的形式与影响进行评估与审核。

【强制】 发布窗口

  • 19:00 后不允许数据库发布,紧急发布请TL做特殊说明,抄送CTO。
  • 16:00点后确认的需求将顺延至第二天执行。(以TL确认时间为准)

0x06 管理规范

【强制】 关注备份

  • 每日全量备份,段文件持续归档

【强制】 关注年龄

  • 关注数据库与表的年龄,避免事物ID回卷。

【强制】 关注老化与膨胀

  • 关注表与索引的膨胀率,避免性能劣化。

【强制】 关注复制延迟

  • 监控复制延迟,使用复制槽时更必须十分留意。

【强制】 遵循最小权限原则

【强制】并发地创建与删除索引

  • 对于生产表,必须使用CREATE INDEX CONCURRENTLY并发创建索引。

【强制】 新从库数据预热

  • 使用pg_prewarm,或逐渐接入流量。

【强制】 审慎地进行模式变更

  • 添加新列时必须使用不带默认值的语法,避免全表重写
  • 变更类型时,必要时应当重建所有依赖该类型的函数。

【推荐】 切分大批量操作

  • 大批量写入操作应当切分为小批量进行,避免一次产生大量WAL。

【推荐】 加速数据加载

  • 关闭autovacuum,使用COPY加载数据。
  • 事后建立约束与索引。
  • 调大maintenance_work_mem,增大max_wal_size
  • 完成后执行vacuum verbose analyze table

KNN极致优化:从RDS到PostGIS

KNN问题极致优化,从传统关系型设计到PostGIS

灵活应用数据库的功能,可以轻松实现 GIS 圈选场景下三万倍的性能提升。

Level 方法 性能/耗时(ms) 可维护性/可靠性 备注
1 暴力扫表 30,000 - 形式简单
2 经纬索引 35 复杂度/魔数问题 额外复杂度
3 联合索引 10 复杂度/魔数问题 额外复杂度
4 GIST 4 最简表达,完全精确 形式简单,距离更精确,PostgreSQL限定
5 btree_gist联合索引 1 最简表达,完全精确 形式简单,距离更精确,PostgreSQL限定

场景

互联网中的很多业务都涉及到地理相关的功能需求,最为普遍的需求莫过于最近邻查询了。

例如:

  • 为用户推荐附近的POI(餐厅、加油站、公交站)
  • 为用户推荐附近的用户(聊天匹配)
  • 找到距离用户所处的地址(地理逆编码)
  • 找到用户所处的商圈、省、市、区、县 (以点找面)

这些问题实质上都属于最近邻搜索或其变体。

有一些功能,它看上去和最近邻搜索无关,实际上剥了皮,也是最近邻搜索,典型的例如地理逆编码:

打车选择上车地点的时,点外卖选择送达位置时,都会将用户当前的经纬度坐标转换为文本地理位置,诸如:“某某小区几号楼”。实际上这也是最近邻搜索的问题:找到距离用户当前位置最近的一个坐标点。

最近邻(knn,k nearest neighiboor),顾名思义,就是找出距离某个中心点最近的K个对象。其问题满足这样一种形式:

找出满足某一条件的最近的K个对象(及其属性)。

最近邻搜索是如此常用的功能,优化的效益非常显著。

下面我们从一个具体问题出发,讲述这一功能实现方式的演化——如何实现超过三万倍的性能提升。


问题

我们选择推荐最近的餐厅,作为此类问题的代表。

问题很简单:给定包含中国所有POI点的表pois,及一个经纬度坐标点。在足够快的时间内找出距离该坐标点最近的10家餐馆。并返回这十家餐馆的名称和距离

细节说明:

  • pois表包括一亿条记录,其中类型为餐馆的POI约占一千万。

  • 给定的示例中心店:北京师范大学,116.3660 E, 39.9615 N。

  • 足够快意味着在1毫秒内完成

  • 距离意味着,以米计算的地球表面距离

  • pois表模式定义:

    CREATE TABLE pois (
      id        CHAR(10) PRIMARY KEY,
      name      VARCHAR(100),
      position  GEOMETRY, -- PostGIS ST_Point
      longitude FLOAT,    -- Float64
      latitude  FLOAT,    -- Float64
      category  INTEGER   -- type of POI
    );
    
  • 餐馆的特征是WHERE category BETWEEN 50000 AND 51000

同类问题

这个模式适用于许多的例子,例如对探探而言,其实就可以是:找出离用户所在位置最近的,且年龄位于某个范围,加上一些其他筛选条件的100个人。

对于美团点评而言,就是找出离用户最近的10个,类型为餐馆的POI。

对于逆地理编码而言,实质上就是找出离用户最近的POI(加上可选的类型限制,类型十字路口,地标建筑等)

题外话-坐标系:WGS84与GCJ02

这是另外一个很多人都会搞混的地方。

  • 滴滴打车的魔幻偏移。
  • 港澳台边界,碎屑多边形。

绝大多数互联网中与地理相关的功能,都涉及到最近邻查询的需求。

比如对于谈朋友的场景,把这里的 WHERE category BETWEEN 50000 AND 51000

换成 WHERE age BETWEEN 18 AND 27就好。

很多打ACM的同学,熟练使用各种数据结构与算法。可能已经跃跃欲试了,R树,就决定是你了。

不过在真实项目中,数据表就是数据结构,而索引与查询方式就是算法。

距离如何定义?

欲解此题,需明定义。距离的定义并没有看上去那样简单。

例如,对于导航软件而言,距离可能意味着路径长度而非直线距离。

在二维平面坐标系中,通常距离指的是欧氏距离:$d=\sqrt{(x_2-x_1)^2+(y_2-y_1)^2}$

但在GIS中,通常使用的坐标系是球面坐标系,即通过经纬度来标识一个点。

在球面上,两点之间的距离等于所在球面大圆上的弧长,也就是其球面角 x 半径。

这就引入了一个问题,每一纬度对应的距离是基本恒定的,差不多都是111公里。

然而,每一经度对应的距离,随着纬度不同而变化,在赤道上和一纬度差不多,也是111公里,然而随着纬度升高,到了北纬40°时,一经度对应的弧长只有85公里了,而到了北极点,一经度对应的弧长距离为0。

事实上,还会有其他更棘手的问题。例如,地球实际上是一个椭球体,而非正球体。

地球非球,乃不规则椭球。在最开始的时候,为了省事,我们可以设其为球计算距离。

CREATE OR REPLACE FUNCTION sphere_distance(lon_a FLOAT, lat_a FLOAT, lon_b FLOAT, lat_b FLOAT)
  RETURNS FLOAT AS $$
SELECT asin(
           sqrt(
               sin(0.5 * radians(lat_b - lat_a)) ^ 2 +
               sin(0.5 * radians(lon_b - lon_a)) ^ 2 * cos(radians(lat_a)) * cos(radians(lat_b))
           )
       ) * 127561999.961088 AS distance;
$$
LANGUAGE SQL IMMUTABLE COST 100;

将经纬度坐标当成平面坐标使用并不是不可以,但对于需要精准排序的场景,这样的近似可能会产生很大的问题:

每一经度对应的距离,随着纬度不同而变化,在赤道上一经度和一纬度代表的距离差不多都是111公里,然而随着纬度升高,到了北纬40°时,一经度对应的弧长只有85公里了,而到了极点,一经度对应的弧长距离为0。

因此,平面坐标系上的圆,在球面坐标系上可能只是一个瘦长的椭圆。计算距离时,纬度与经度方向上的距离权重不同会导致严重的正确性问题:一个正北100米处的商店可能比正东70m处的商店距离排序更靠前。对于高纬度地区,这一类问题会变得非常严重。

因此,暴力扫表之后,通常需要使用精确的距离计算公式再次计算并排序。

注意,这里的距离,量纲单位并不是米,而是°的平方,考虑到1经度和1纬度对应的实际距离在不同的地方存在巨大差异,这一结果并没有精确的实际意义。

经纬度是球面坐标系,而不是二维平面坐标系中的坐标。然而对于快速粗略圈选,这种方式是可以接受的。

对于需要精确排序的场景,必须使用地球表面球面距离的计算公式,而不是简单地求欧氏距离。

足够快又是多快?

天下武功,唯快不破,互联网强调的就是一个快,跑的也快,写的也快。

足够快又是多快呢?一毫秒,足够快了。这也是我们的优化目标

好了,开始进入干货环节。在PostGIS展现真正的实力之前,让我们来先看一看传统的关系型数据库,对解决这一问题,能走到多远。


0x02 方案

让我们从传统关系型数据库开始

LEVEL-1 暴力扫表

使用传统关系型数据库,此题有何解法?

暴力算法写起来是非常简单的,我们来看一下。

从POIS表中,首先找出所有的餐馆,拿出餐馆的名字,算出餐馆到我们这儿的距离,然后呢?再按距离排序,取距离最短的,也就是最近的10条记录。

新手拍拍脑袋,也可以很快写出这样Naive的SQL:

SELECT
  id,
  name,
  sphere_distance(longitude, latitude, 
                  116.3660 , 39.9615 ) AS d
FROM pois
WHERE category BETWEEN 50000 AND 51000
ORDER BY d
LIMIT 10;

为了简化问题,让我们暂时忽略经纬度其实是球面坐标,地球又是个椭球体的事实。

在这一前提下,这个SQL确实能正确完成工作。不过,谁要敢在生产环境这么用,DBA肯定得打死他。

让我们先考察其执行计划:

题外话:SQL内联

SQL内联有助于正确使用索引。

在真实环境执行,缓存充分预热,实际耗时30秒;开启PostgreSQL并行查询(2 worker)后实际执行时间16秒。

用时30秒,实际执行时间17秒。

用户对于响应时间是很敏感的,响应时间一上去,用户满意度立马就会掉下来。打王者荣耀的时候,100毫秒的延迟都已经很让人抓狂了。如果是一个实时性

对于几千条记录的表也许可以凑合工作,但对于1亿量级的表,暴力扫表不可取。

用户无法接受十几秒的等待时间,更罔论这样的设计能有任何扩展性可言。

存在的问题

开销离谱

这个查询每次都要计算目标点所有记录点之间的距离,然后再按距离排序取TOP。

对于几千条记录的表也许可以凑合工作,但对于1亿量级的表,暴力扫表不可取。用户无法接受十几秒的等待时间,更罔论这样的设计能有任何扩展性可言。

正确性堪忧

将经纬度坐标当成平面坐标使用并不是不可以,但对于需要精准排序的场景,这样的近似可能会产生很大的问题:

每一经度对应的距离,随着纬度不同而变化,在赤道上一经度和一纬度代表的距离差不多都是111公里,然而随着纬度升高,到了北纬40°时,一经度对应的弧长只有85公里了,而到了极点,一经度对应的弧长距离为0。

因此,平面坐标系上的圆,在球面坐标系上可能只是一个瘦长的椭圆。计算距离时,纬度与经度方向上的距离权重不同会导致严重的正确性问题:一个正北100米处的商店可能比正东70m处的商店距离排序更靠前。对于高纬度地区,这一类问题会变得非常严重。

因此,暴力扫表之后,通常需要使用精确的距离计算公式再次计算并排序。

题外话:错误的索引效果适得其反

有同学会说,这里POI类型字段,category出现在了查询的where条件中,可以通过索引来提高性能

这次他不直接扫表了,它先去扫描category上的索引,把属于餐厅的记录都过滤出来。

然后再按照索引,一个页面接一个页面地扫描。

结果顺序IO变成了随机IO。

那么索引的正确使用方式又是怎么样的呢?

LEVEL-2 经纬索引

索引是关系型数据库的吃饭家伙,既然顺序扫表不可取,我们自然会想到利用索引来加速查询。

朴素的思路是这样的,通过索引筛选出目标点周围一定范围内的候选点,再进一步计算距离并排序。

索引是关系型数据库的吃饭家伙,既然顺序扫表不可取,我们自然会想到利用索引来加速查询。

使用经纬度上的索引是基于这样一种思路:

北师在帝都繁华之地宇宙中心,如果我们用一个边长一公里的正方形(直径一公里的圆)

去地图上画个圈,那么别说十家餐厅了,一百家都有可能。

反过来说呢,既然最近的10家餐厅一定落在这么大的一个圆里,

这个表里的POI点包括了全中国的POI点,

筛选出目标点周围一定范围内的候选点,再进一步计算距离并排序。

CREATE INDEX ON pois1 USING btree(longitude);
CREATE INDEX ON pois1 USING btree(latitude);

同时,为了解决正确性的问题,假设我们已经有了一个从经纬度计算球面距离的SQL函数sphere_distance

CREATE FUNCTION sphere_distance(lon_a FLOAT, lat_a FLOAT, lon_b FLOAT, lat_b FLOAT) RETURNS FLOAT
IMMUTABLE LANGUAGE SQL COST 100 AS $$
SELECT asin(
           sqrt(
               sin(0.5 * radians(lat_b - lat_a)) ^ 2 +
               sin(0.5 * radians(lon_b - lon_a)) ^ 2 * cos(radians(lat_a)) *
               cos(radians(lat_b))
           )
       ) * 127561999.961088 AS distance;
$$;

$$ \Delta\sigma=\arccos\bigl(\sin\phi_1\cdot\sin\phi_2+\cos\phi_1\cdot\cos\phi_2\cdot\cos(\Delta\lambda)\bigr). $$

于是,如果使用以目标点为中心的边长为1公里的正方形来做初筛,这个查询可以写作:

SELECT 
  id, name, 
  sphere_distance(longitude, latitude, 116.365798, 39.966956) as d
FROM pois1
WHERE
  longitude BETWEEN 116.365798 - 0.5 / 85 AND 116.365798 + 0.5 / 85 AND
  latitude BETWEEN 39.966956 - 0.5 / 111 AND 39.966956 + 0.5 / 111  AND
  category = 60000
ORDER BY 3 LIMIT 10;

预热后,实际执行平均耗时35毫秒,相比暴力扫表有了近千倍的性能提高,一个巨大的进步。

对于比较简单粗糙的产品,这种方法已经达到了‘可用’的级别。但这一方法仍然存在许多问题。

存在的问题

这种方法最大的问题在于额外复杂度。它使用了一个(多个)魔数,来确定候选点的大致范围。

而这个魔数的选取,是有赖我们的先验知识的。我们清楚地知道,以繁华的宇宙中心五道口的商铺密度,一公里见方内,商铺个数绝对超过10个了。但对于极端的场景(实际可能很常见),比如在塔克拉玛干大沙漠或者羌塘无人区,最近的商铺,逻辑上是必定存在的,不过其距离可能超过几百公里。

这种方法的性能表现对魔数的选取极其敏感:距离选择的太大,性能会急剧恶化,距离选择的太小,对于乡下偏僻的地方又可能无法返回结果。让程序员头大的事情又多了一个。

用时35毫秒

千倍提升,不错哦,但不能高兴的太早

这么多奇怪的常数又是几个意思?

一千倍的性能提升,让我们来看一下查询执行计划,看看它是怎么做到的。

首先呢,经度上,走了一个索引扫描,生成了一个位图。

然后呢,纬度上,也走了一个索引扫描,又生成了一个位图。

接下来,两个位图做了一个位运算,生成了一个新位图,筛选出了满足经纬度条件的记录。

然后,才去扫描这些满足条件的候选点,计算距离,并排序。

我们这个边界值选的比较巧,所以实际参与距离计算和排序的记录,可能只有三十多条。

比起先前一千多万次的距离计算与排序,显然是要高明的多了。

题外话:超参数与额外复杂度

因为这个边界魔数凑的很好,所以性能比较理想。

这种方法最大的问题在于额外复杂度。它使用了一个(多个)魔数,来确定候选点的大致范围。

而这个魔数的选取,是有赖我们的先验知识的。我们清楚地知道,以繁华的宇宙中心五道口的商铺密度,一公里见方内,商铺个数绝对超过10个了。但对于极端的场景(实际可能很常见),比如在塔克拉玛干大沙漠或者羌塘无人区,最近的商铺,逻辑上是必定存在的,不过其距离可能超过几百公里。

这种方法的性能表现对魔数的选取极其敏感:距离选择的太大,性能会急剧恶化,距离选择的太小,对于乡下偏僻的地方又可能无法返回结果。让程序员头大的事情又多了一个。

让我们先忽略这恼人的问题,看看传统关系型数据库还能不能再压榨压榨。

Bad Case

因为这个边界魔数凑的很好,所以性能比较理想。

这种方法最大的问题在于额外复杂度。它使用了一个(多个)魔数,来确定候选点的大致范围。

而这个魔数的选取,是有赖我们的先验知识的。我们清楚地知道,以繁华的宇宙中心五道口的商铺密度,一公里见方内,商铺个数绝对超过10个了。但对于极端的场景(实际可能很常见),比如在塔克拉玛干大沙漠或者羌塘无人区,最近的商铺,逻辑上是必定存在的,不过其距离可能超过几百公里。

这种方法的性能表现对魔数的选取极其敏感:距离选择的太大,性能会急剧恶化,距离选择的太小,对于乡下偏僻的地方又可能无法返回结果。让程序员头大的事情又多了一个。

让我们先忽略这恼人的问题,看看传统关系型数据库还能不能再压榨压榨。

半径大了性能差 半径小了圈不着
mage-20180321221805
繁荣的五道口,一公里圈10家小意思。 300公里外才有一家,新疆人民哭晕在厕所

LEVEL-3 联合索引与聚簇

抛开魔数带来的烦恼,我们来研究传统关系型数据库能在解决这个问题上走得有多远。

通过多列索引替换每一列上独自的索引,并将表按该索引聚簇。

仍然是一模一样的查询语句

从30毫秒提升到10毫秒,三倍的性能提升

对于传统关系型数据库,这差不多就是极限了

有没有优雅、正确、快速的解决方案呢?

mage-20180321221928

CREATE INDEX ON pois4 USING btree(longitude, latitude, category);
CLUSTER pois4 USING pois4_longitude_latitude_category_idx;

相应的查询保持不变

SELECT id, name,
	sphere_distance(longitude, latitude, 116.365798, 39.966956) as d FROM pois4
WHERE
  longitude BETWEEN 116.365798 - 0.5 / 85  AND 116.365798 + 0.5 / 85  AND
  latitude  BETWEEN  39.966956 - 0.5 / 111 AND 39.966956  + 0.5 / 111 AND
  category = 60000
ORDER BY sphere_distance(longitude, latitude, 116.365798, 39.966956)
LIMIT 10;

联合索引查询的执行计划,实际执行时间可以压缩至7毫秒。

mage-20180321221945

这差不多就是传统关系数据模型的极限了,对于大部分业务,这都是一个可以接受水平了。

因为这个边界魔数凑的很好,所以性能比较理想。

扩展变体:GeoHash

GeoHash是此类方式的变体,通过将二维经纬度编码为一维字符串,可以使用传统的字符串前缀匹配操作来对地理位置进行过滤。然而固定的粒度使得其灵活度有显著下降,采用联合索引还是特殊编码的冗余字段需要针对具体场景进行分析。

仍然是一模一样的查询语句

从30毫秒提升到10毫秒,三倍的性能提升

对于传统关系型数据库,这差不多就是极限了

有没有优雅、正确、快速的解决方案呢?


LEVEL-4 GIST

有没有一种办法,能够优雅,高效,简洁的完成这项工作呢?

PostGIS提出了非常优秀的解决方案,改用Geometry类型,并创建GIST索引。

CREATE TABLE pois5(
  id       CHAR(10) PRIMARY KEY,
  name     VARCHAR(100),
  position GEOGRAPHY(Point), -- PostGIS ST_Point
  category INTEGER   -- type of POI
);

CREATE INDEX ON pois5 USING GIST(position);
SELECT id, name FROM pois6 WHERE category = 60000
ORDER BY position <-> ST_GeogFromText('SRID=4326;POINT(116.365798 39.961576)') LIMIT 10;

R树

R树的核心思想是,聚合距离相近的节点,并在树结构的上一层,将其表示为这些节点的最小外接矩形,这个最小外接矩形就成为上一层的一个节点。因为所有节点都在它们的最小外接矩形中,所以跟某个矩形不相交的查询就一定跟这个矩形中的所有节点都不相交。

mage-20180321220143

实际查询中,该查询能在1.6毫秒完成,这是相当惊人的一个结果了。但要注意,这里position的类型是GEOMETRY,意味着它使用的是二维平面坐标,正确的计算距离需要使用Geography类型。

SELECT
  id,
  name,
  position <-> 
  ST_Point(116.3660, 39.9615)::GEOGRAPHY AS d
FROM pois5
WHERE category BETWEEN 50000 AND 51000
ORDER BY d
LIMIT 10;

因为球面距离的计算开销比平面距离要大很多,使用Geography替换Geometry产开销,约4.5ms。

一倍的性能损失相当可观,因此日常应用中需要仔细权衡精确性与性能之间的关系。

通常拓扑类的查询、粗略的圈人都适合用Geometry类型,而精确的计算与判断则必须使用Geography类型。这里,按照距离排序需要精确的距离,因此使用Geography。

Geometry: 1.6 ms Geography: 3.4 ms
mage-20180321222024

现在,我们来看看PostGIS交出的答卷。

PostGIS,使用了不一样的数据类型、索引、与查询方法。

首先,这里数据类型不再是两个浮点数,而变成一个Geography字段。里面存就是一对经纬度坐标。

然后,我们使用的索引,也不再是常见的Btree索引,而是GIST索引。

Generalized Search Tree. 通用搜索树,平衡树结构。对于空间几何类型而言,实现通常使用的是R树。

通常拓扑类的查询、粗略的圈人都适合用Geometry类型,而精确的计算与判断则必须使用Geography类型。这里,按照距离排序需要精确的距离,因此使用Geography。

题外话:Geometry还是Geography?

因为球面距离的计算开销比平面距离要大很多,使用Geography替换Geometry产开销

拓扑关系,粗略估计使用Geometry,精确计算使用Geography

计算开销约为一倍,需要仔细权衡正确性/精确性与性能之间的关系。

现在,我们来看看PostGIS交出的答卷。

PostGIS,使用了不一样的数据类型、索引、与查询方法。

首先,这里数据类型不再是两个浮点数,而变成一个Geography字段。里面存就是一对经纬度坐标。

然后,我们使用的索引,也不再是常见的Btree索引,而是GIST索引。

Generalized Search Tree. 通用搜索树,平衡树结构。对于空间几何类型而言,实现通常使用的是R树。

通常拓扑类的查询、粗略的圈人都适合用Geometry类型,而精确的计算与判断则必须使用Geography类型。这里,按照距离排序需要精确的距离,因此使用Geography。


LEVEL-5 btree_gist

还能更进一步否?

观察Leve-4中的执行计划,我们发现category上的条件并没有用到索引。

可不可以像Level-3中的优化方式一样,创建一个 position 与 category 的联合索引呢?

不幸的是,B树与R树是两种完全不同的数据结构,甚至连使用方式都不一样

于是我们有这样一个想法,能不能把category当成 position的第三维坐标,让R树直接在三维空间里面进行索引呢?

这个思路是正确的, 但是完全不需要这么麻烦

GIST索引的一个问题在于,它的工作原理与B树不同,无法在不支持GIST索引方法的数据类型上创建GIST索引。

通常,几何类型,范围(range)类型支持GIST索引,但字符串,数值类型等都不支持GIST。这就导致了无法创建形如GIST(position, category)的多列索引。

PostgreSQL内置的btree_gist扩展解决了这一问题。

PostgreSQL内置的扩展 btree_gist,允许创建常规类型与几何类型的联合索引。

CREATE EXTENSION btree_gist;

CREATE INDEX ON pois6 USING GIST(position, category);

CLUSTER VERBOSE pois6 USING idx_pois6_position_category_gist;

同样的查询,可以简写为:

SELECT id, name, position <-> ST_Point(lon, lat) :: GEOGRAPHY AS distance
FROM pois6 WHERE category = 60000 ORDER BY 3 LIMIT 10;
Geometry: 0.85ms / Geography: 1.2ms
CREATE OR REPLACE FUNCTION get_random_nearby_store() RETURNS TEXT
AS $$
DECLARE
  lon FLOAT := 110 + (random() - 0.5) * 10;
  lat FLOAT := 30 + (random() - 0.5) * 10;
BEGIN
  RETURN (
    SELECT jsonb_pretty(jsonb_build_object('list', a.list, 'lon', lon, 'lat', lat)) :: TEXT
    FROM (
           SELECT json_agg(row_to_json(top10)) AS list
           FROM (
             SELECT id, name, position <-> ST_Point(lon, lat) :: GEOGRAPHY AS distance
             FROM pois6 WHERE category = 60000 ORDER BY 3 LIMIT 10 ) top10
         ) a);
END;
$$ LANGUAGE PlPgSQL;
import http, http.server, random, psycopg2

class GetHandler(http.server.BaseHTTPRequestHandler):
    conn = psycopg2.connect("postgres://localhost:5432/geo")
    def do_GET(self):
        self.send_response(http.HTTPStatus.OK)
        self.send_header('Content-type','application/json')
        with GetHandler.conn.cursor() as cursor:
            cursor.execute('SELECT get_random_nearby_store() as res;')
            res = cursor.fetchone()[0]
            self.wfile.write(res.encode('utf-8'))
        return

with http.server.HTTPServer(("localhost", 3001), GetHandler) as httpd: httpd.serve_forever()

案例小结

Level 方法 性能/耗时(ms) 可维护性/可靠性 备注
1 暴力扫表 30,000 - 形式简单
2 经纬索引 35 复杂度/魔数问题 额外复杂度
3 联合索引 10 复杂度/魔数问题 额外复杂度
4 GIST 4 最简表达,完全精确 形式简单,距离更精确,PostgreSQL限定
5 btree_gist联合索引 1 最简表达,完全精确 形式简单,距离更精确,PostgreSQL限定

那么好的,经过这么漫长的旅途,通过PostGIS与PostgreSQL,将原本需要3万毫秒的查询加速至1毫秒,三万倍的提升。相比传统关系型数据库,除了超过十倍以上的性能提升,还有很多优点:

SQL的形式非常简单,就是暴力扫表的SQL,不需要奇奇怪怪的额外复杂度。而且计算距离使用的是更精确的WGS84椭球球面距离。

那么从这个例子中我们可以得出什么结论呢? PostGIS的性能表现是非常优秀的,那么它在实际生产环境里的表现又如何呢?

我们把这里的position,从餐厅的位置换为用户的位置,把poi的种类范围,换成候选人的年龄范围。这就是探探匹配功能所面临的场景。

实际场景中的表现

性能很重要。天下武功,唯快不破。

目前数据库总共用了220台机器,业务QPS近10万。数据库TPS峰值的时候差不多接近250W。其中核心数据库是1主19从的配置。

我厂对于数据库的SLA是:99.99%的普通数据库请求需要在1毫秒内完成,而单个数据库节点的QPS峰值在3万上下。这两者之间其实有着紧密的联系,如果一个请求能在1毫秒内完成,那么对于单个线程而言,每秒钟就可以处理1000个请求。我们使用的数据库物理机CPU为24核48线程,不过超线程的机器CPU利用率在60%~70%左右。可以近似折算为30个可用核。那么,所有核能够承载的QPS量就是30*1000=30000。以极限水位80% CPU算,QPS上限在38k 左右,也与现实压测结果吻合。

整理自本人在2018象形中国北京PostGIS专场所做分享,转载请保留出处。

PostGIS高效解决行政区划归属查询

如何高效解决典型地理逆编码问题:根据用户的经纬度坐标,定位用户的行政区划。

微信公众号原文

在应用开发中,很多时候我们需要解决这样一个问题:根据用户的经纬度坐标,定位用户的行政区划。

我们收集到的是诸如28°00'00"N 100°00'00.000"E这样的经纬度坐标,但实际感兴趣的是这个点所属的行政区划:(中华人民共和国,云南省,迪庆藏族自治州,香格里拉市)。这种将地理坐标映射到某条记录的操作就称为地理编码(GeoEncode)。高效实现地理编码是一个很有趣的问题。

本文介绍了该问题的解决与优化方案:能在确保正确性的前提下,能用几兆的空间,110μs的执行时间完成一次地理编码。


0x01 正确至上

正确性是第一位的。我们不希望出现用户明明身处A地,却被划分到B地的尴尬情况。然而一个尴尬的现实是,很多地理编码服务的实现粗糙到令人无法直视,Vornoi方法就是一个典型的例子。

假设我们有一系列的坐标点,那么这些坐标点之间两两连线的中垂线就对整个坐标平面做了一个Vornoi划分。每一个细胞的中心点就是细胞核,而元胞内的任意一点到该细胞核的距离是最近的(与其他细胞核相比)。

当我们没有行政区划的边界数据,但有行政区划中心点的数据时,这也是一种能凑合管用办法。找到距离用户最近的某级行政区域中心,然后认为用户就位于该行政区域中心。这个功能实现起来非常简单。

不过,这种方法对于边界情况的处理很差:

最近邻搜索—Vornoi方法

vornoi

现实总是与理想情况相距甚远。也许对于国内而言,这种错误影响也许并不大。但涉及到国际主权边界时,这种粗糙的实现很可能会给自己带来不必要的麻烦:

还有一种思路,和编程中的“查表法”类似,预先计算好所有经纬度到行政区划的映射,使用时只要用经纬度坐标查表就好了。当然无论经度还是维度,都是一个连续的标量,理论上精度必然是有限的。

GeoHash就是这样一种方案:它将经度与维度交叉编码为单一字符串,字符串越长精度越高,每一个字符串都对应一个经纬度围成的“矩形”,只要精度足够,理论上是可以这么做的。当然,这种方案难以做到真正意义上的正确,存储开销也极为浪费。好处是实现很简单。只要有数据,一个KV服务就可以轻松搞定。

geohash

相比之下,基于地理边界多边形的解决方案在保证绝对正确的前提下,能在一毫秒内完成这种地理编码功能,而且可能只需要几兆的空间。唯一的难点可能在于如何获取数据上。


0x02 数据为王

地理编码属于典型的数据密集型应用,数据的质量直接决定了最终服务的效果。要想真正做好服务,优质数据必不可少。好在行政区划与地理边界数据也不算什么保密信息,有一些地方提供了公开获取的方式:

民政部信息查询平台与高德地图两者都提供了精确到县级区划的地理边界数据:

  • 高德地图行政区域查询API

    高德的数据更新更及时,形式简单,边界精度较高(点数多),但不够权威,有不少错漏之处

    geohash

  • 民政部全国行政区划信息查询平台

    民政部平台数据相对更加权威,而且采用的是拓扑编码,严格避免了边界重叠的问题,使用无偏的WGS84坐标,但边界精度较低(点数目较少)。

geohash

除了地理围栏数据之外,另一份重要的数据是行政区划代码数据。国家统计局使用的12位城乡统计用行政区划代码编制还是很科学的,具有层次包含关系,尤其适合作为行政区划的唯一标示。但问题是稍显过时,最新的版本是2016年8月发布的,2018年7月后可能会发布一份更新的数据。

笔者整理了一份连接国际统计局行政区划与高德区划边界的数据:https://github.com/Vonng/adcode

民政部的数据可以直接在该网站中打开浏览器的调试工具,从接口返回数据中直接获取。


0x03 牛刀小试

假设我们已经有一张表了,全国行政区划与地理围栏表:adcode_fences

create table adcode_fences
(
  code         bigint,
  parent       bigint,
  name         varchar(64),
  level        varchar(16),
  rank         integer,
  adcode       integer,
  post_code    varchar(8),
  area_code    varchar(4),
  ur_code      varchar(4),
  municipality boolean,
  virtual      boolean,
  dummy        boolean,
  longitude    double precision,
  latitude     double precision,
  center       geometry,
  province     varchar(64),
  city         varchar(64),
  county       varchar(64),
  town         varchar(64),
  village      varchar(64),
  fence        geometry
);

geohash

索引

为了高效执行空间查询,首先需要在表示地理边界的fence列上创建GIST索引。

中国县级行政区划的记录数据并不多(约3000条),但使用索引仍然能带来几十倍的性能提升。因为这个优化太基础太Trivial了,就不单独拎出来说了。(一百多毫秒到几毫秒)

CREATE INDEX ON adcode_fences USING GIST(fence);

查询

PostGIS提供了ST_ContainsST_Within两个函数,用于判断多边形与点之间的包含关系,例如以下SQL就会找出表中所有包含该点(116,40)的行政区划:

SELECT
  code,
  name
FROM adcode_fences
WHERE ST_Contains(fence, ST_Point(116, 40))
ORDER BY rank;

结果是:

100000000000	中华人民共和国
110000000000	北京市
110100000000	市辖区
110109000000	门头沟区

再比如(100,28)的坐标点:

SELECT json_object_agg(level,name) 
FROM adcode_fences WHERE ST_Contains(fence, ST_Point(100, 28));
{
  "country": "中华人民共和国",
  "city": "迪庆藏族自治州",
  "county": "香格里拉市",
  "province": "云南省"
}

相当不可思议,数据就位之后,借力于PostgreSQL与PostGIS,实现这一功能所需的代码少的惊人:一行SQL。

在笔者的笔记本上,该查询执行用时6毫秒。6ms的平均查询时间,换算为48核机器上的QPS差不多就是6400。在我们以前的生产环境代码中基本上就是这么做的,但因为还有其他国家的数据,以及单核主频没有我的机器高,因此一次查询的平均执行时间可能在12毫秒左右。

看上去几毫秒似乎已经很快了,但还是没有达到我们生产环境的性能要求(1毫秒)。对于真实世界的生产业务而言,性能很重要,十倍的性能提升意味着省十倍的机器。还能不能再给力点?实际上通过简单的优化就可以达到百倍的性能提升。


0x04 性能优化

针对数据特性优化

导致上述查询慢的一个重要原因是不必要的相交判断。行政区划是有层级关系的,如果一个用户位于县级行政区划中,那么他一定位于该县级区划所处的省级区划中。因此,知道了最低级的行政区划,其高级区划归属已经自然而然地确定了;那么与省界,国界做相交判断就是没有必要的。 实际上这可能是效果最明显的优化,单是中国地理边界与点做相交判断可能就需要几毫秒。

区域切分

R树索引的原理,能为我们带来优化的启发。R树是基于**AABB(Axis Aligned Bounding Box)**的索引。因此越是饱满的凸多边形,索引的效果就越好。而对于拥有遥远飞地的行政区划,效果则可能恶化的很厉害。因此,将区域切分为均匀饱满的小块,能有效提高查询的性能。

最基本的优化,就是将所有的`ST_MultiPolygon`拆分为`ST_Polygon`,并指向同一个行政区划。更进一步,可以将长得比较畸形的行政区划切分为形状饱满的小块(典型的比如甘肃这种)。当然,这样的代价就是让所有行政区划与地理围栏从一对一变成了一对多的关系。需要拆出一张单独的表。

实际操作中,如果已经有了县级行政区划的数据,通常只要将带有飞地的MultiPolygon拆为单独的几个Polygon,就已经能有很好的表现了。而县一级的行政区划通常边界也比较饱满,进一步拆分效果相当有限。

精确度

正确性是第一位的,然而有的时候我们宁愿牺牲一些准确性,换来性能的大幅提升。例如高德与民政部的数据对比,显然民政部要粗糙的多,但对于糙猛快的互联网场景,低精度的数据反而可能是更合适的。

高德 民政部
geohash geohash

高德的全国行政区划数据约100M左右,而民政部的数据约为10M(以原始拓扑数据表示则为4M)。但实际使用中效果差别不大,因此推荐使用民政部的数据。

主键设计

行政区划有内在的层次关系,国家包含省,省包含城市,城市包含区县,区县包含乡镇,乡镇包含村庄街道。我国的行政区划代码就很好的体现了这种层次关系,十二位的城乡区划代码包含了很丰富的信息:

  • 第1~2位,为省级代码;
  • 第3~4 位,为地级代码;
  • 第5~6位,为县级代码;
  • 第7~9位,为乡级代码;
  • 第10~12位,为村级代码。

因此这种12位的行政区划代码是很适合作为行政区划表的主键的。此外,当需要国际化支持时,这套区划代码体系还可以通过在前面添加国家代码来扩展(相应地中国行政区划对应地就是高位国家代码为0的特殊情况)。

另一方面,地理围栏表与行政区划表由一对一变为多对一,那么地理围栏表就不再适合用行政区划代码作为主键了。可能自增列是一个更合适的选择。

规范化与反规范化

数据模型设计的一个重要权衡就是规范化与反规范化。将地理围栏表从行政区划表中拆出来是一种规范化,而反规范化也可以用于优化:既然行政区划存在层次关系,那么在子行政区划中保留所有的祖先行政区划信息(或仅仅是代码与名称)是很合理的反规范化操作。这样,通过区划代码主键一次查询就可以取出所有的层次信息。

回溯支持

有时候我们想回溯到历史上某个特定时刻,查询该时刻的行政区划状态。

举个例子,行政区划变更并不会影响该区划内现有公民的身份证号码,只会影响新出生公民的身份证号。因此有时候用公民身份证号前6位去查现在的行政区划表可能一无所获,需要回溯到该公民出生的历史时间才能查询到正确的结果。可以参考PostgreSQL MVCC的实现方式,为行政区划表添加一对PostgreSQL提供的tstzrange类型字段,标识行政区划记录版本的有效时间段,并在查询时指明时间点作为筛选条件。PostgreSQL可以支持在范围类型与空间类型上建立联合GIST索引,提供高效查询支持。

不过,时序数据获取难度是很大的。而且一般这个需求也并不常见。所以这里就不展开了。


0x05 设计实现

既然已经将地理编码的功能从区划代码表拆分出来,本题对adcode中的结构就不甚关注了。我们只需要知道凭借code字段能从该表中快速查出我们感兴趣的东西,比如一连串的行政区划层次,行政区划的人口,面积,等级,行政中心等等。

create table adcode
(
  code         bigint PRIMARY KEY ,
  parent       bigint references adcode(code),
  name         text,
  rank         integer,
  path         text[],
        
  …… <other attrs>
);

相比之下,fences表才是我们需要关注的对象,因为这是性能损耗的关键路径。

CREATE TABLE fences (
  id    BIGSERIAL PRIMARY KEY,
  fence geometry(POLYGON),
  code  BIGINT
);

CREATE INDEX ON fences USING GiST(fence);
CREATE INDEX ON fences USING Btree(code);

CLUSTER TABLE fences USING fences_fence_idx;

不使用行政区划代码code作为主键,给予了我们更多的灵活性与优化空间。任何时候需要修正地理编码的逻辑时,只修改fences中的数据即可。你甚至可以添加冗余字段与条件索引,将不同来源的数据,不同等级的行政区划,相互重叠的地理围栏放在同一张表中,灵活地执行自定义的编码逻辑。

说句题外话:如果您能确保自己的数据不会重叠,则可以考虑使用PostgreSQL提供的Exclude约束确保数据完整性:

CREATE TABLE fences (
  id    BIGSERIAL PRIMARY KEY,
  fence geometry(POLYGON),
  code  BIGINT,
  EXCLUDE USING gist(fence WITH &&) 
     -- no need to create gist index for fence anymore
);

性能测试

那么优化完之后的性能表现又如何?让我们随机生成一些坐标点,检验一下性能。

\set	x	random(75,125)
\set	y	random(20,50)
SELECT code FROM fences2 WHERE ST_Contains(fence,ST_Point(:x,:y));

在笔者的机器上,现在一次查询只要0.1ms了,单进程9k TPS,折算为48核机器约为350kTPS

$ pgbench adcode -T 5 -f run.sql

number of clients: 1
number of threads: 1
duration: 5 s
number of transactions actually processed: 45710
latency average = 0.109 ms
tps = 9135.632484 (including connections establishing)
tps = 9143.947723 (excluding connections establishing)

当然拿到code之后还是需要去行政区划表里查一次,但一次索引扫描的开销是很小的。

总的来说,与优化之前的实现相比,性能提升了60倍。落实在生产环境中,可能就意味着省了百来万的成本。

Distinct On 去除重复数据

使用Distinct On扩展字句快速找出分组内具有最大最小值的记录

Distinct On是PostgreSQL提供的特有语法,可以高效解决一些典型查询问题,例如,快速找出分组内具有最大最小值的记录。

前言

找出分组内具有最大最小值的记录,这是一个非常常见的需求。用传统SQL当然有办法解决,但是都不够优雅,PostgreSQL的SQL扩展语法Distinct ON能一步到位解决这一类问题。

DISTINCT ON 语法

SELECT DISTINCT ON (expression [, expression ...]) select_list ...

Here expression is an arbitrary value expression that is evaluated for all rows. A set of rows for which all the expressions are equal are considered duplicates, and only the first row of the set is kept in the output. Note that the “first row” of a set is unpredictable unless the query is sorted on enough columns to guarantee a unique ordering of the rows arriving at the DISTINCT filter. (DISTINCT ON processing occurs after ORDER BY sorting.)

Distinct On应用案例

例如,找出每台机器的最新日志在日志表中,取出按照机器node_id分组,时间戳ts最大的的日志记录。

CREATE TABLE nodes(node_id INTEGER, ts TIMESTAMP);

INSERT INTO test_data
SELECT (random() * 10)::INTEGER as node_id, t
FROM generate_series('2019-01-01'::TIMESTAMP, '2019-05-01'::TIMESTAMP, '1h'::INTERVAL) AS t;

这里可以制造一些随机数据

5	2019-01-01 00:00:00.000000
0	2019-01-01 01:00:00.000000
9	2019-01-01 02:00:00.000000
1	2019-01-01 03:00:00.000000
7	2019-01-01 04:00:00.000000
2	2019-01-01 05:00:00.000000
8	2019-01-01 06:00:00.000000
3	2019-01-01 07:00:00.000000
1	2019-01-01 08:00:00.000000
4	2019-01-01 09:00:00.000000
9	2019-01-01 10:00:00.000000
0	2019-01-01 11:00:00.000000
3	2019-01-01 12:00:00.000000
6	2019-01-01 13:00:00.000000
9	2019-01-01 14:00:00.000000
1	2019-01-01 15:00:00.000000
7	2019-01-01 16:00:00.000000
8	2019-01-01 17:00:00.000000
9	2019-01-01 18:00:00.000000
10	2019-01-01 19:00:00.000000
5	2019-01-01 20:00:00.000000
4	2019-01-01 21:00:00.000000

现在使用DistinctON,这里Distinct On后面的括号里代表了记录需要按哪一个键进行除重,在括号内的表达式列表上有着相同取值的记录会只保留一条记录。(当然保留哪一条是随机的,因为分组内哪一条记录先返回是不确定的)

SELECT DISTINCT ON (node_id) * FROM test_data

0	2019-04-30 17:00:00.000000
1	2019-04-30 22:00:00.000000
2	2019-04-30 23:00:00.000000
3	2019-04-30 13:00:00.000000
4	2019-05-01 00:00:00.000000
5	2019-04-30 20:00:00.000000
6	2019-04-30 11:00:00.000000
7	2019-04-30 15:00:00.000000
8	2019-04-30 16:00:00.000000
9	2019-04-30 21:00:00.000000
10	2019-04-29 18:00:00.000000

DistinctON有一个配套的ORDER BY子句,用于指明分组内哪一条记录将被保留,排序第一条记录会留下,因此如果我们想要每台机器上的最新日志,可以这样写。

SELECT DISTINCT ON (node_id) * FROM test_data ORDER BY node_id, ts DESC NULLS LAST

0	2019-04-30 17:00:00.000000
1	2019-04-30 22:00:00.000000
2	2019-04-30 23:00:00.000000
3	2019-04-30 13:00:00.000000
4	2019-05-01 00:00:00.000000
5	2019-04-30 20:00:00.000000
6	2019-04-30 11:00:00.000000
7	2019-04-30 15:00:00.000000
8	2019-04-30 16:00:00.000000
9	2019-04-30 21:00:00.000000
10	2019-04-29 18:00:00.000000

使用索引加速Distinct On查询

Distinct On查询当然可以被索引加速,例如以下索引就可以让上面的查询用上索引

CREATE INDEX ON test_data USING btree(node_id, ts DESC NULLS LAST);

set enable_seqscan = off;
explain SELECT DISTINCT ON (node_id) * FROM test_data ORDER BY node_id, ts DESC NULLS LAST;
Unique  (cost=0.28..170.43 rows=11 width=12)
  ->  Index Only Scan using test_data_node_id_ts_idx on test_data  (cost=0.28..163.23 rows=2881 width=12)

注意,排序的时候一定要确保NULLS FIRST|LAST与查询时实际使用的规则匹配。否则可能用不上索引。

函数易变性等级分类

PgSQL中的函数默认有三种易变性等级,合理使用可以显著改善性能。

PgSQL中的函数默认有三种易变性等级,合理使用可以显著改善性能。

核心种差

  • VOLATILE : 有副作用,不可被优化。
  • STABLE: 执行了数据库查询。
  • IMMUTABLE : 纯函数,执行结果可能会在规划时被预求值并缓存。

什么时候用?

  • VOLATILE : 有任何写入,有任何副作用,需要看到外部命令所做的变更,或者调用了任何VOLATILE的函数
  • STABLE: 有数据库查询,但没有写入,或者函数的结果依赖于配置参数(例如时区)
  • IMMUTABLE : 纯函数。

具体解释

每个函数都带有一个易变性(Volatility) 等级。可能的取值包括 VOLATILESTABLE,以及IMMUTABLE。创建函数时如果没有指定易变性等级,则默认为 VOLATILE。易变性是函数对优化器的承诺:

  • VOLATILE函数可以做任何事情,包括修改数据库状态。在连续调用时即使使用相同的参数,也可能会返回不同的结果。优化器不会优化掉此类函数,每次调用都会重新求值。
  • STABLE函数不能修改数据库状态,且在单条语句中保证给定同样的参数一定能返回同样的结果,因而优化器可以将相同参数的多次调用优化成一次调用。在索引扫描条件中允许使用STABLE函数,但VOLATILE函数就不行。(一次索引扫描中只会对参与比较的值求值一次,而不是每行求值一次,因而在一个索引扫描条件中不能使用 VOLATILE函数)。
  • IMMUTABLE函数不能修改数据库状态,并且保证任何时候给定输入永远返回相同的结果。这种分类允许优化器在一个查询用常量参数调用该函数 时提前计算该函数。例如,一个 SELECT ... WHERE x = 2 + 2这样的查询可以被简化为SELECT ... WHERE x = 4,因为整数加法操作符底层的函数被 标记为IMMUTABLE

STABLE与IMMUTABLE的区别

调用次数优化

以下面这个函数为例,它只是简单的返回常数2

CREATE OR REPLACE FUNCTION return2() RETURNS INTEGER AS
$$
BEGIN
RAISE NOTICE 'INVOKED';
RETURN 2;
END;
$$ LANGUAGE PLPGSQL STABLE;

当使用STABLE标签时,它会真的调用10次,而当使用IMMUTABLE标签时,它会被优化为一次调用。

vonng=# select return2() from generate_series(1,10);
NOTICE:  INVOKED
NOTICE:  INVOKED
NOTICE:  INVOKED
NOTICE:  INVOKED
NOTICE:  INVOKED
NOTICE:  INVOKED
NOTICE:  INVOKED
NOTICE:  INVOKED
NOTICE:  INVOKED
NOTICE:  INVOKED
 return2
---------
       2
       2
       2
       2
       2
       2
       2
       2
       2
       2
(10 rows)

这里将函数的标签改为IMMUTABLE

CREATE OR REPLACE FUNCTION return2() RETURNS INTEGER AS
$$
BEGIN
RAISE NOTICE 'INVOKED';
RETURN 2;
END;
$$ LANGUAGE PLPGSQL IMMUTABLE;

再执行同样的查询,这次函数只被调用了一次

vonng=# select return2() from generate_series(1,10);
NOTICE:  INVOKED
 return2
---------
       2
       2
       2
       2
       2
       2
       2
       2
       2
       2
(10 rows)

执行计划缓存

第二个例子是有关索引条件中的函数调用,假设我们有这么一张表,包含从1到1000的整数:

create table demo as select * from generate_series(1,1000) as id;
create index idx_id on demo(id);

现在创建一个IMMUTABLE的函数mymax

CREATE OR REPLACE FUNCTION mymax(int, int)
RETURNS int
AS $$
BEGIN
     RETURN CASE WHEN $1 > $2 THEN $1 ELSE $2 END;
END;
$$ LANGUAGE 'plpgsql' IMMUTABLE;

我们会发现,当我们在索引条件中直接使用该函数时,执行计划中的索引条件被直接求值缓存并固化为了id=2

vonng=# EXPLAIN SELECT * FROM demo WHERE id = mymax(1,2);
                               QUERY PLAN
------------------------------------------------------------------------
 Index Only Scan using idx_id on demo  (cost=0.28..2.29 rows=1 width=4)
   Index Cond: (id = 2)
(2 rows)

而如果将其改为STABLE函数,则结果变为运行时求值:

vonng=# EXPLAIN SELECT * FROM demo WHERE id = mymax(1,2);
                               QUERY PLAN
------------------------------------------------------------------------
 Index Only Scan using idx_id on demo  (cost=0.53..2.54 rows=1 width=4)
   Index Cond: (id = mymax(1, 2))
(2 rows)

用 Exclude 实现互斥约束

Exclude约束是一个PostgreSQL扩展,它可以实现一些更高级,更巧妙的的数据库约束。

Exclude约束是一个PostgreSQL扩展,它可以实现一些更高级,更巧妙的的数据库约束。


前言

数据完整性是极其重要的,但由应用保证的数据完整性并不总是那么靠谱:人会犯傻,程序会出错。如果能通过数据库约束来强制数据完整性那是再好不过了:后端程序员不用再担心竞态条件导致的微妙错误,数据分析师也可以对数据质量充满信心,不需要验证与清洗。

关系型数据库通常会提供PRIMARY KEY, FOREIGN KEY, UNIQUE, CHECK约束,然而并不是所有的业务约束都可以用这几种约束表达。一些约束会稍微复杂一些,例如确保IP网段表中的IP范围不发生重叠,确保同一个会议室不会出现预定时间重叠,确保地理区划表中各个城市的边界不会重叠。传统上要实现这种保证是相当困难的:譬如UNIQUE约束就无法表达这种语义,CHECK与存储过程或者触发器虽然可以实现这种检查,但也相当tricky。PostgreSQL提供的EXCLUDE约束可以优雅地解决这一类问题。


Eclude约束的语法

 EXCLUDE [ USING index_method ] ( exclude_element WITH operator [, ... ] ) index_parameters [ WHERE ( predicate ) ] |
 
exclude_element in an EXCLUDE constraint is:
{ column_name | ( expression ) } [ opclass ] [ ASC | DESC ] [ NULLS { FIRST | LAST } ]

EXCLUDE子句定一个排除约束,它保证如果任意两行在指定列或表达式上使用指定操作符进行比较,不是所有的比较都将会返回TRUE。如果所有指定的操作符都测试相等,这就等价于一个UNIQUE约束,尽管一个普通的唯一约束将更快。不过,排除约束能够指定比简单相等更通用的约束。例如,你可以使用&&操作符指定一个约束,要求表中没有两行包含相互覆盖的圆(见 Section 8.8)。

排除约束使用一个索引实现,这样每一个指定的操作符必须与用于索引访问方法index_method的一个适当的操作符类(见Section 11.9)相关联。操作符被要求是交换的。每一个exclude_element可以选择性地指定一个操作符类或者顺序选项,这些在???中有完整描述。

访问方法必须支持amgettuple(见Chapter 61),目前这意味着GIN无法使用。尽管允许,但是在一个排除约束中使用 B-树或哈希索引没有意义,因为它无法做得比一个普通唯一索引更出色。因此在实践中访问方法将总是GiST或SP-GiST。

predicate允许你在该表的一个子集上指定一个排除约束。在内部这会创建一个部分索引。注意在为此周围的圆括号是必须的。


应用案例:会议室预定

假设我们想要设计一个会议室预定系统,并希望在数据库层面确保不会有冲突的会议室预定出现:即,对于同一个会议室,不允许同时存在两条预定时间范围上存在重叠的记录。那么数据库表可以这样设计:

-- PostgreSQL自带扩展,为普通类型添加GIST索引运算符支持
CREATE EXTENSION btree_gist;

-- 会议室预定表
CREATE TABLE meeting_room
(
    id      SERIAL PRIMARY KEY,
    user_id INTEGER,
    room_id INTEGER,
    range   tsrange,
    EXCLUDE USING GIST(room_id WITH = , range WITH &&)
);

这里EXCLUDE USING GIST(room_id WITH = , range WITH &&)指明了一个排它约束:不允许存在room_id相等,且range相互重叠的多条记录。

-- 用户1预定了101号房间,从早上10点到下午6点
INSERT INTO meeting_room(user_id, room_id, range) 
VALUES (1,101, tsrange('2019-01-01 10:00', '2019-01-01 18:00'));

-- 用户2也尝试预定101号房间,下午4点到下午6点
INSERT INTO meeting_room(user_id, room_id, range) 
VALUES (2,101, tsrange('2019-01-01 16:00', '2019-01-01 18:00'));

-- 用户2的预定报错,违背了排它约束
ERROR:  conflicting key value violates exclusion constraint "meeting_room_room_id_range_excl"
DETAIL:  Key (room_id, range)=(101, ["2019-01-01 16:00:00","2019-01-01 18:00:00")) conflicts with existing key (room_id, range)=(101, ["2019-01-01 10:00:00","2019-01-01 18:00:00")).

这里的EXCLUDE约束会自动创建一个相应的GIST索引:

"meeting_room_room_id_range_excl" EXCLUDE USING gist (room_id WITH =, range WITH &&)

应用案例:确保IP网段不重复

有一些约束是相当复杂的,例如确保表中的IP范围不发生重叠,类似的,确保地理区划表中各个城市的边界不会重叠。传统上要实现这种保证是相当困难的:譬如UNIQUE约束就无法表达这种语义,CHECK与存储过程或者触发器虽然可以实现这种检查,但也相当tricky。PostgreSQL提供的EXCLUDE约束可以优雅地解决这个问题。修改我们的geoips表:

create table geoips
(
  ips          inetrange,
  geo          geometry(Point),
  country_code text,
  region_code  text,
  city_name    text,
  ad_code      text,
  postal_code  text,
  EXCLUDE USING gist (ips WITH &&) DEFERRABLE INITIALLY DEFERRED 
);

​ 这里EXCLUDE USING gist (ips WITH &&) 的意思就是ips字段上不允许出现范围重叠,即新插入的字段不能与任何现存范围重叠(&&为真)。而DEFERRABLE INITIALLY IMMEDIATE 表示在语句结束时再检查所有行上的约束。创建该约束会自动在ips字段上创建GIST索引,因此无需手工创建了。

GO与PG实现缓存同步

巧妙运用Pg的Notify功能,可以方便地通知应用元数据变更,实现基于触发器的逻辑复制。

Parallel与Hierarchy是架构设计的两大法宝,缓存是Hierarchy在IO领域的体现。单线程场景下缓存机制的实现可以简单到不可思议,但很难想象成熟的应用会只有一个实例。在使用缓存的同时引入并发,就不得不考虑一个问题:如何保证每个实例的缓存与底层数据副本的数据一致性(和实时性)。

PostgreSQL在版本9引入了流式复制,在版本10引入了逻辑复制,但这些都是针对PostgreSQL数据库而言的。如果希望PostgreSQL中某张表的部分数据与应用内存中的状态保持一致,我们还是需要自己实现一种逻辑复制的机制。对于关键的少量元数据而言,使用触发器与Notify-Listen就是一个不错的选择。


传统方法

最简单粗暴的办法就是定时重新拉取,例如每个整点,所有应用一起去数据库拉取一次最新版本的数据。很多应用都是这么做的。当然问题也很多:拉的间隔长了,变更不能及时应用,用户体验差;拉的频繁了,IO压力大。而且实例数目和数据大小一旦膨胀起来,对于宝贵的IO资源是很大的浪费。

异步通知是一种更好的办法,尤其是在读请求远多于写请求的情况下。接受到写请求的实例,通过发送广播的方式通知其他实例。RedisPubSub就可以很好地实现这个功能。如果原本下层存储就是Redis自然是再方便不过,但如果下层存储是关系型数据库的话,为这样一个功能引入一个新的组件似乎有些得不偿失。况且考虑到后台管理程序或者其他应用如果在修改了数据库后也要去redis发布通知,实在太麻烦了。一种可行的办法是通过数据库中间件来监听RDS变动并广播通知,淘宝不少东西就是这么做的。但如果DB本身就能搞定的事情,为什么需要额外的组件呢?通过PostgreSQL的Notfiy-Listen机制,可以方便地实现这种功能。


目标

无论从任何渠道产生的数据库记录变更(增删改)都能被所有相关应用实时感知,用于维护自身缓存与数据库内容的一致性。


原理

PostgreSQL行级触发器 + Notify机制 + 自定义协议 + Smart Client

  • 行级触发器:通过为我们感兴趣的表建立一个行级别的写触发器,对数据表中的每一行记录的Update,Delete,Insert都会出发自定义函数的执行。
  • Notify:通过PostgreSQL内建的异步通知机制向指定的Channel发送通知
  • 自定义协议:协商消息格式,传递操作的类型与变更记录的标识
  • Smart Client:客户端监听消息变更,根据消息对缓存执行相应的操作。

实际上这样一套东西就是一个超简易的WAL(Write After Log)实现,从而使应用内部的缓存状态能与数据库保持实时一致(compare to poll)。


DDL

这里以一个最简单的表作为示例,一张以主键标识的users表。

-- 用户表
CREATE TABLE users (
  id   TEXT,
  name TEXT,
  PRIMARY KEY (id)
);

触发器

-- 通知触发器
CREATE OR REPLACE FUNCTION notify_change() RETURNS TRIGGER AS $$
BEGIN
  IF    (TG_OP = 'INSERT') THEN 
	PERFORM pg_notify(TG_RELNAME || '_chan', 'I' || NEW.id); RETURN NEW;
  ELSIF (TG_OP = 'UPDATE') THEN 
	PERFORM pg_notify(TG_RELNAME || '_chan', 'U' || NEW.id); RETURN NEW;
  ELSIF (TG_OP = 'DELETE') THEN 
	PERFORM pg_notify(TG_RELNAME || '_chan', 'D' || OLD.id); RETURN OLD;
  END IF;
END; $$ LANGUAGE plpgsql SECURITY DEFINER;

这里创建了一个触发器函数,通过内置变量TG_OP获取操作的名称,TG_RELNAME获取表名。每当触发器执行时,它会向名为<table_name>_chan的通道发送指定格式的消息:[I|U|D]<id>

题外话:通过行级触发器,还可以实现一些很实用的功能,例如In-DB Audit,自动更新字段值,统计信息,自定义备份策略与回滚逻辑等。

-- 为用户表创建行级触发器,监听INSERT UPDATE DELETE 操作。
CREATE TRIGGER t_user_notify AFTER INSERT OR UPDATE OR DELETE ON users
FOR EACH ROW EXECUTE PROCEDURE notify_change();

创建触发器也很简单,表级触发器对每次表变更执行一次,而行级触发器对每条记录都会执行一次。这样,数据库的里的工作就算全部完成了。


消息格式

通知需要传达出两个信息:变更的操作类型,变更的实体标记。

  • 变更的操作类型就是增删改:INSERT,DELETE,UPDATE。通过一个打头的字符’[I|U|D]‘就可以标识。
  • 变更的对象可以通过实体主键来标识。如果不是字符串类型,还需要确定一种无歧义的序列化方式。

这里为了省事直接使用字符串类型作为ID,那么插入一条id=1的记录,对应的消息就是I1,更新一条id=5的记录消息就是U5,删除id=3的记录消息就是D3

完全可以通过更复杂的消息协议实现更强大的功能。


智能客户端

数据库的机制需要客户端的配合才能生效,客户端需要监听数据库的变更通知,才能将变更实时应用到自己的缓存副本中。对于插入和更新,客户端需要根据ID重新拉取相应实体,对于删除,客户端需要删除自己缓存副本的相应实体。以Go语言为例,编写了一个简单的客户端模块。

本例中使用一个以User.ID作为键,User对象作为值的并发安全字典Users sync.Map作为缓存。

作为演示,启动了另一个goroutine对数据库写入了一些变更。

package main

import "sync"
import "strings"
import "github.com/go-pg/pg"
import . "github.com/Vonng/gopher/db/pg"
import log "github.com/Sirupsen/logrus"

type User struct {
	ID   string `sql:",pk"`
	Name string
}

var Users sync.Map // Users 内部数据缓存

func LoadAllUser() {
	var users []User
	Pg.Query(&users, `SELECT ID,name FROM users;`)
	for _, user := range users {
		Users.Store(user.ID, user)
	}
}

func LoadUser(id string) {
	user := User{ID: id}
	Pg.Select(&user)
	Users.Store(user.ID, user)
}

func PrintUsers() string {
	var buf []string
	Users.Range(func(key, value interface{}) bool {
		buf = append(buf, key.(string));
		return true
	})
	return strings.Join(buf, ",")
}

// ListenUserChange 会监听PostgreSQL users数据表中的变动通知
func ListenUserChange() {
	go func(c <-chan *pg.Notification) {
		for notify := range c {
			action, id := notify.Payload[0], notify.Payload[1:]
			switch action {
			case 'I':
				fallthrough
			case 'U':
				LoadUser(id);
			case 'D':
				Users.Delete(id)
			}
			log.Infof("[NOTIFY] Action:%c ID:%s Users: %s", action, id, PrintUsers())
		}
	}(Pg.Listen("users_chan").Channel())
}

// MakeSomeChange 会向数据库写入一些变更
func MakeSomeChange() {
	go func() {
		Pg.Insert(&User{"001", "张三"})
		Pg.Insert(&User{"002", "李四"})
		Pg.Insert(&User{"003", "王五"})  // 插入
		Pg.Update(&User{"003", "王麻子"}) // 改名
		Pg.Delete(&User{ID: "002"})    // 删除
	}()
}

func main() {
	Pg = NewPg("postgres://localhost:5432/postgres")
	Pg.Exec(`TRUNCATE TABLE users;`)
	LoadAllUser()
	ListenUserChange()
	MakeSomeChange()
	<-make(chan struct{})
}

运行结果如下:

[NOTIFY] Action:I ID:001 Users: 001          
[NOTIFY] Action:I ID:002 Users: 001,002      
[NOTIFY] Action:I ID:003 Users: 002,003,001  
[NOTIFY] Action:U ID:003 Users: 001,002,003  
[NOTIFY] Action:D ID:002 Users: 001,003      

可以看出,缓存确是与数据库保持了同样的状态。


应用场景

小数据量下这种做法是相当可靠的,大数据量下尚未进行充分的测试。

其实,对于上例中缓存同步的场景,完全不需要自定义消息格式,只要发送发生变更的记录ID,由应用直接拉取,然后覆盖或删除缓存中的记录即可。

用触发器审计数据变化

有时候,我们希望记录一些重要的元数据变更,以便事后审计之用。PostgreSQL的触发器就可以很方便地自动解决这一需求。

有时候,我们希望记录一些重要的元数据变更,以便事后审计之用。

PostgreSQL的触发器就可以很方便地自动解决这一需求。

-- 创建一个审计专用schema,并废除所有非superuser的权限。
DROP SCHEMA IF EXISTS audit CASCADE;
CREATE SCHEMA IF NOT EXISTS audit;
REVOKE CREATE ON SCHEMA audit FROM PUBLIC;

-- 审计表
CREATE TABLE audit.action_log (
  schema_name   TEXT                     NOT NULL,
  table_name    TEXT                     NOT NULL,
  user_name     TEXT,
  time          TIMESTAMP WITH TIME ZONE NOT NULL DEFAULT CURRENT_TIMESTAMP,
  action        TEXT                     NOT NULL CHECK (action IN ('I', 'D', 'U')),
  original_data TEXT,
  new_data      TEXT,
  query         TEXT
) WITH (FILLFACTOR = 100
);

-- 审计表权限
REVOKE ALL ON audit.action_log FROM PUBLIC;
GRANT SELECT ON audit.action_log TO PUBLIC;


-- 索引
CREATE INDEX logged_actions_schema_table_idx
  ON audit.action_log (((schema_name || '.' || table_name) :: TEXT));

CREATE INDEX logged_actions_time_idx
  ON audit.action_log (time);

CREATE INDEX logged_actions_action_idx
  ON audit.action_log (action);
---------------------------------------------------------------


---------------------------------------------------------------
-- 创建审计触发器函数
---------------------------------------------------------------
CREATE OR REPLACE FUNCTION audit.logger()
  RETURNS TRIGGER AS $body$
DECLARE
  v_old_data TEXT;
  v_new_data TEXT;
BEGIN
  IF (TG_OP = 'UPDATE')
  THEN
    v_old_data := ROW (OLD.*);
    v_new_data := ROW (NEW.*);
    INSERT INTO audit.action_log (schema_name, table_name, user_name, action, original_data, new_data, query)
    VALUES (TG_TABLE_SCHEMA :: TEXT, TG_TABLE_NAME :: TEXT, session_user :: TEXT, substring(TG_OP, 1, 1), v_old_data,
            v_new_data, current_query());
    RETURN NEW;
  ELSIF (TG_OP = 'DELETE')
    THEN
      v_old_data := ROW (OLD.*);
      INSERT INTO audit.action_log (schema_name, table_name, user_name, action, original_data, query)
      VALUES (TG_TABLE_SCHEMA :: TEXT, TG_TABLE_NAME :: TEXT, session_user :: TEXT, substring(TG_OP, 1, 1), v_old_data,
              current_query());
      RETURN OLD;
  ELSIF (TG_OP = 'INSERT')
    THEN
      v_new_data := ROW (NEW.*);
      INSERT INTO audit.action_log (schema_name, table_name, user_name, action, new_data, query)
      VALUES (TG_TABLE_SCHEMA :: TEXT, TG_TABLE_NAME :: TEXT, session_user :: TEXT, substring(TG_OP, 1, 1), v_new_data,
              current_query());
      RETURN NEW;
  ELSE
    RAISE WARNING '[AUDIT.IF_MODIFIED_FUNC] - Other action occurred: %, at %', TG_OP, now();
    RETURN NULL;
  END IF;

  EXCEPTION
  WHEN data_exception
    THEN
      RAISE WARNING '[AUDIT.IF_MODIFIED_FUNC] - UDF ERROR [DATA EXCEPTION] - SQLSTATE: %, SQLERRM: %', SQLSTATE, SQLERRM;
      RETURN NULL;
  WHEN unique_violation
    THEN
      RAISE WARNING '[AUDIT.IF_MODIFIED_FUNC] - UDF ERROR [UNIQUE] - SQLSTATE: %, SQLERRM: %', SQLSTATE, SQLERRM;
      RETURN NULL;
  WHEN OTHERS
    THEN
      RAISE WARNING '[AUDIT.IF_MODIFIED_FUNC] - UDF ERROR [OTHER] - SQLSTATE: %, SQLERRM: %', SQLSTATE, SQLERRM;
      RETURN NULL;
END;
$body$
LANGUAGE plpgsql
SECURITY DEFINER
SET search_path = pg_catalog, audit;

COMMENT ON FUNCTION audit.logger() IS '记录特定表上的插入、修改、删除行为';
---------------------------------------------------------------


---------------------------------------------------------------
-- 最后修改时间审计触发器函数
---------------------------------------------------------------
-- 当记录发生变更前,记录修改时间。
CREATE OR REPLACE FUNCTION audit.update_mtime()
  RETURNS TRIGGER AS $$
BEGIN
  NEW.mtime = now();
  RETURN NEW;
END;
$$ LANGUAGE 'plpgsql';

COMMENT ON FUNCTION audit.update_mtime() IS '更新记录mtime';
---------------------------------------------------------------


---------------------------------------------------------------
-- 元数据变动事件触发器函数
-- 向'change'信道发送数据变动的表名
---------------------------------------------------------------
CREATE OR REPLACE FUNCTION audit.notify_change()
  RETURNS TRIGGER AS $$
BEGIN
  PERFORM pg_notify('change', TG_RELNAME);
  RETURN NULL;
END;
$$ LANGUAGE 'plpgsql';

COMMENT ON FUNCTION audit.notify_change() IS '数据变动事件触发器函数,向`change`信道发送数据变动的表名';
---------------------------------------------------------------

SQL实现ItemCF推荐系统

用PostgreSQL 5分钟实现一个最简单ItemCF推荐系统

推荐系统大家都熟悉,猜你喜欢,淘宝个性化什么的,前年双十一搞了个大新闻,还拿了CEO特别贡献奖。

今天就来说说怎么用PostgreSQL 5分钟实现一个最简单ItemCF推荐系统,以推荐系统最喜闻乐见的movielens数据集为例。


原理

ItemCF的原理可以看项亮的《推荐系统实战》,不过还是稍微提一下吧,了解的直接跳过就好。

Item CF,全称Item Collaboration Filter,即基于物品的协同过滤,是目前业界应用最多的推荐算法。ItemCF不需要物品与用户的标签、属性,只要有用户对物品的行为日志就可以了,同时具有很好的可解释性。所以无论是亚马逊,Hulu,YouTube,balabala用的都是该算法。

ItemCF算法的核心思想是:给用户推荐那些和他们之前喜欢的物品相似的物品。

这里有两个要点:

  • 用户喜欢物品怎么表示?
  • 物品的相似度怎样表示?

用户评分表

可以通过用户评分表来判断用户对物品的喜爱程度,例如电影数据的5分制:5分表示非常喜欢,1分表示不喜欢。

用户评分表有三个核心字段:user_id, movie_id, rating,分别是用户ID,物品ID,用户对物品的评分。

怎样得到这个表呢?如果本来就是评论打分网站在做推荐系统,直接有用户对电影,音乐,小说的评分记录那是最好不过。其他的场景,比如电商,社交网络,则可以通过用户对物品的行为日志生成这张评分表。例如可以为“浏览”,“点击”,“收藏”,“购买”,点击“我不喜欢”按钮这些行为分别设一个喜好权重:0.1, 0.2, 0.3, 0.4, -100。将所有行为评分加权求和,最终得到这张用户对物品的评分表来,事就成了一半了。

物品相似度

还需要解决的一个问题是物品相似度的计算表示

假设一共有$N$个物品,则物品相似度数据可以表示为一个$N \times N$的矩阵,第$i$行$j$列的值表示物品$i$与物品$j$之间的相似度。这样相似度表示的问题就解决了。

第二个问题是物品相似度矩阵的计算。

但在计算前,首先必须定义,什么是物品的相似度?

两个物品之间的相似度有很多种定义与计算方式,如果我们有物品的各种属性数据(类型,大小,价格,风格,标签)的话,就可以在属性空间定义各式各样的“距离”,来定义相似度。但ItemCF的亮点就在于,不需要物品的属性标签数据也可以计算其相似度来。其核心思想是:如果一对物品被很多人同时喜欢,则认为这一对物品更为相似。

令$N(i)$为喜欢物品$i$的用户集合,$|N(i)|$为喜欢物品$i$的人数,$|N(i) \cap N(j)|$为同时喜欢物品$i,j$的人数,则物品$i,j$之间的相似度$_{ij}$可w以表示为:

$$ w_{ij} = \frac{|N(i) \cap N(j)|}{ \sqrt{ |N(i)| * |N(j)|}} $$

即:同时喜欢物品$i,j$的人数,除以喜爱物品$i$人数和喜爱物品$j$人数的几何平均数。

这样,就可以通过用户对物品的行为日志,导出一份物品之间的相似矩阵数据来。

推荐物品

现在有一个用户$u$,他对物品$j$的评分可以通过以下公式计算:

$$ \displaystyle p_{uj} = \sum_{i \in N(u) \cap S(i, K)} w_{ji}r_{ui} $$

其中,用户$i$对物品$i_1,i_2,\cdots,i_n$的评分分别为$r_1,r_2,…,r_n$,而物品$i_1,i_2,\cdots,i_n$与目标物品$j$的相似度分别为$w_1,w_2,\cdots,w_n$。以用户$u$评分过的物品集合作为纽带,按照评分以相似度加权求和,就可以得到用户$u$对物品$j$的评分了。

对这个预测评分$p$排序取TopN,就得到了用户$u$的推荐物品列表


实践

说了这么多废话,赶紧燥起来。

第一步:准备数据

下载Movielens数据集,开发测试的话选小规模的(100k)就可以。对于ItemCF来说,有用的数据就是用户行为日志,即文件ratings.csv地址

-- movielens 用户评分数据集
CREATE TABLE mls_ratings (
  user_id   INTEGER,
  movie_id  INTEGER,
  rating    TEXT,
  timestamp INTEGER,
  PRIMARY KEY (user_id, movie_id)
);

-- 从CSV导入数据,并将评分乘以2变为2~10的整数便于处理,将Unix时间戳转换为日期类型
COPY mls_ratings FROM '/Users/vonng/Dev/recsys/ml-latest-small/ratings.csv' DELIMITER ',' CSV HEADER;
ALTER TABLE mls_ratings
  ALTER COLUMN rating SET DATA TYPE INTEGER USING (rating :: DECIMAL * 2) :: INTEGER;
ALTER TABLE mls_ratings
  ALTER COLUMN timestamp SET DATA TYPE TIMESTAMPTZ USING to_timestamp(timestamp :: DOUBLE PRECISION);

得到的数据长这样:第一列用户ID列表,第二列电影ID列表,第三列是评分,最后是时间戳。一共十万条

movielens=# select * from mls_ratings limit 10;
 user_id | movie_id | rating |       timestamp
---------+----------+--------+------------------------
       1 |       31 |      5 | 2009-12-14 10:52:24+08
       1 |     1029 |      6 | 2009-12-14 10:52:59+08
       1 |     1061 |      6 | 2009-12-14 10:53:02+08
       1 |     1129 |      4 | 2009-12-14 10:53:05+08

第二步:计算物品相似度

物品相似度的DDL

-- 物品相似度表,这是把矩阵用<i,j,M_ij>的方式在数据库中表示。
CREATE TABLE mls_similarity (
  i INTEGER,
  j INTEGER,
  p FLOAT,
  PRIMARY KEY (i, j)
);

物品相似度是一个矩阵,虽说PostgreSQL里提供了数组,多维数组,自定义数据结构,不过这里为了方便起见还是使用了最传统的矩阵表示方法:坐标索引法$(i,j,m_{ij})$。其中前两个元素为矩阵下标,各自表示物品的ID。最后一个元素存储了这一对物品的相似度。

物品相似度的计算

计算物品相似度,要计算两个中间数据:

  • 每个物品被用户喜欢的次数:$|N(i)|$
  • 每对物品共同被同一个用户喜欢的次数 $|N(i) \cap N(j)|$

如果是用编程语言,那自然可以一趟(One-Pass)解决两个问题。不过SQL就要稍微麻烦点了,好处是不用操心撑爆内存的问题。

这里可以使用PostgreSQL的With子句功能,计算两个临时结果供后续使用,一条SQL就搞定相似矩阵计算:

-- 计算物品相似度矩阵: 3m 53s
WITH mls_occur AS ( -- 中间表:计算每个电影被用户看过的次数
    SELECT
      movie_id,     -- 电影ID: i
      count(*) AS n -- 看过电影i的人数: |N(i)|
    FROM mls_ratings
    GROUP BY movie_id
),
    mls_common AS ( -- 中间表:计算每对电影被用户同时看过的次数
      SELECT
        a.movie_id AS i, -- 电影ID: i
        b.movie_id AS j, -- 电影ID: j
        count(*)   AS n  -- 同时看过电影i和j的人数: |N(i) ∩ N(j)|
      FROM mls_ratings a INNER JOIN mls_ratings b ON a.user_id = b.user_id
      GROUP BY i, j
  )
INSERT INTO mls_similarity
  SELECT
    i,
    j,
    n / sqrt(n1 * n2) AS p  -- 距离公式
  FROM
    mls_common c,
    LATERAL (SELECT n AS n1 FROM mls_occur WHERE movie_id = i) n1,
    LATERAL (SELECT n AS n2 FROM mls_occur WHERE movie_id = j) n2;

物品相似度表大概长这样:

movielens=# SELECT * FROM mls_similarity LIMIT 10;
   i    | j |         p
--------+---+--------------------
 140267 | 1 |  0.110207753755597
   2707 | 1 |  0.180280682843137
 140174 | 1 |  0.113822078644894
   7482 | 1 | 0.0636284762975778

实际上还可以修剪修剪,比如计算时非常小的相似度干脆可以直接删掉。也可以用整个表中相似度的最大值作为单位1,进行归一化。这里都不弄了。


第三步:进行推荐!

现在假设我们为ID为10的用户推荐10部他没看过的电影,该怎么做呢?

WITH seed AS	-- 10号用户评分过的影片作为种子集合
  (SELECT movie_id,rating FROM mls_ratings WHERE user_id = 10)
SELECT
  j as movie_id,	-- 所有待预测评分的电影ID
  sum(seed.rating * p) AS score -- 预测加权分,按此字段降序排序取TopN
FROM
  seed LEFT JOIN mls_similarity s ON seed.movie_id = s.i 
  WHERE j not in (SELECT DISTINCT movie_id FROM seed) -- 去除已经看过的电影(可选)
GROUP BY j ORDER BY score DESC LIMIT 10; -- 聚合,排序,取TOP

推荐结果如下:

 movie_id |      score
----------+------------------
     1270 | 121.487735902517
     1214 | 116.146138947698
     1580 | 116.015331936539
     2797 | 115.144083402858
     1265 | 114.959033115913
      260 | 114.313571128143
     2716 | 113.087151014987
     1097 |  113.07771922959
     1387 | 112.869891345883
     2916 |  112.84326997566

可以进一步包装一下,把它变成一个存储过程get_recommendation

CREATE OR REPLACE FUNCTION get_recommendation(userid INTEGER)
  RETURNS JSONB AS $$ BEGIN
  RETURN (SELECT jsonb_agg(movie_id)
          FROM (WITH seed AS
          (SELECT movie_id,rating FROM mls_ratings WHERE user_id = userid)
                SELECT
                  j as movie_id,
                  sum(seed.rating * p) AS score
                FROM
                  seed LEFT JOIN mls_similarity s ON seed.movie_id = s.i
                WHERE j not in (SELECT DISTINCT movie_id FROM seed)
                GROUP BY j ORDER BY score DESC LIMIT 10) res);
END $$ LANGUAGE plpgsql STABLE;

这样用起来更方便啦,同时也可以在这里加入一些其他的处理逻辑:比如过滤掉禁片黄片,去除用户明确表示过不喜欢的电影,加入一些热门电影,引入一些随机惊喜,打点小广告之类的。

movielens=# SELECT get_recommendation(11) as res;
                                  res
-----------------------------------------------------------------------
 [80489, 96079, 79132, 59315, 91529, 69122, 58559, 59369, 1682, 71535]

最后写个应用把这个存储过程作为OpenAPI开放出去,事就这样成了。

关于这一步可以参考前一篇:当PostgreSQL遇上GraphQL:Postgraphql中的做法,直接由存储过程生成GraphQL API,啥都不用操心了。


What’s more

几行SQL一条龙执行下来,加上下载数据的时间,总共也就五分钟吧。一个简单的推荐系统就这样搭建起来了。

但一个真正的生产系统还需要考虑许许多多其他问题,例如,性能。

这里比如说计算相似度矩阵的时候,才100k条记录花了三四分钟,不太给力。而且这么多SQL写起来,管理起来也麻烦,有没有更好的方案?

这儿有个基于PostgreSQL源码魔改的推荐数据库:RecDB,直接用C实现了推荐系统相关的功能扩展,性能看起来杠杠地;同时还包装了SQL语法糖,一行SQL建立推荐系统!再一行SQL就开始使用啦。

-- 计算推荐所需的信息
CREATE RECOMMENDER MovieRec ON ml_ratings
USERS FROM userid
ITEMS FROM itemid
EVENTS FROM ratingval
USING ItemCosCF

-- 进行推荐!
SELECT * FROM ml_ratings R
RECOMMEND R.itemid TO R.userid ON R.ratingval USING ItemCosCF
WHERE R.userid = 1
ORDER BY R.ratingval
LIMIT 10

PostgreSQL能干的事情太多了,最先进的开源关系数据库确实不是吹的,其实真的可以试一试。

UUID性质原理与应用

UUID性质原理与应用,以及如何利用PostgreSQL的存储过程操作UUID。

最近一个项目需要生成业务流水号,需求如下:

  • ID必须是分布式生成的,不能依赖中心节点分配并保证全局唯一。
  • ID必须包含时间戳并尽量依时序递增。(方便阅读,提高索引效率)
  • ID尽量散列。(分片,与HBase日志存储需要)

在造轮子之前,首先要看一下有没有现成的解决方案。

Serial

传统实践上业务流水号经常通过数据库自增序列或者发码服务来实现。 MySQLAuto Increment,PostgresSerial,或者Redis+lua写个小发码服务都是方便快捷的解决方案。这种方案可以保证全局唯一,但会出现中心节点依赖:每个节点需要访问一次数据库才能拿到序列号。这就产生了可用性问题:如果能在本地生成流水号并直接返回响应,那为什么非要用一次网络访问拿ID呢?如果数据库挂了,节点也GG了。所以这并不是一个理想的方案。

SnowflakeID

然后就是twitter的SnowflakeID了,SnowflakeID是一个BIGINT,第一位不用,41bit的时间戳,10bit的节点ID,12bit的毫秒内序列号。时间戳,工作机器ID,序列号占用的位域长度是可以根据业务需求不同而变化的。

    0                   1                   2                   3
    0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |x|                    41-bit timestamp                         |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |       timestamp   |10-bit machine node|    12-bit serial      |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

SnowflakeID可以说基本满足了这四个需求,首先,通过不同的时间戳(精确到毫秒),节点ID(工作机器ID),以及毫秒内的序列号,某种意义上确实可以做到唯一。一个比较讨喜的特性是所有ID是依时序递增的,所以索引起来或者拉取数据会非常方便,长整形的索引和存储效率也很高,生成效率也没得说。

但我认为SnowflakeId存在两个致命问题:

  • 虽然ID生成不需要中心节点分配,但工作机器ID还是需要手工分配或者提供中心节点协调的,本质上是改善而不是解决问题。
  • 无法解决时间回溯的问题,一旦服务器时间发生调整,几乎一定会生成出重复ID。

UUID (Universally Unique IDentifier)

其实这种问题早就有经典的解决方案了,譬如:UUID by RFC 4122 。著名的IDFA就是一种UUID

UUID是一种格式,共有5个版本,最后我选择了v1作为最终方案。下面详细简单介绍一下UUID v1的性质。

  • 可以分布式本地生成。
  • 保证全局唯一,且可以应对时间回溯或网卡变化导致ID重复生成的问题。
  • 时间戳(60bit),精确至0.1微秒(1e-7 s)。蕴含在ID中。
  • 在一个连续的时间片段(2^32/1e7 s约7min)内,ID单调递增。
  • 连续生成的ID会被均匀散列,(所以分片起来不要太方便,放在HBase里也可以直接当Rowkey)
  • 有现成的标准,不需要任何事先配置与参数输入,各个语言均有实现,开箱即用。
  • 可以直接通过UUID字面值得知大概的业务时间戳。
  • PostgreSQL直接内建UUID支持(ver>9.0)。

综合考虑,这确实是我能找到的最完美的解决方案了。

UUID概览

# Shell中生成一个随机UUID的简单方式
$ python -c 'import uuid;print(uuid.uuid4())'
8d6d1986-5ab8-41eb-8e9f-3ae007836a71

我们通常见到的UUID如上所示,通常用'-'分隔的五组十六进制数字表示。但这个字符串只不过是UUID的字符串表示,即所谓的UUID Literal。实际上UUID是一个128bit的整数。也就是16个字节,两个长整形的宽度。

因为每个字节用2个hex字符表示,所以UUID通常可以表示为32个十六进制数字,按照8-4-4-4-12的形式进行分组。为什么采用这种分组形式?因为最原始版本的UUID v1采用了这种位域划分方式,后面其他版本的UUID虽然可能位域划分跟这个结构已经不同了,依然采用此种字面值表示方法。UUID1是最经典的UUID,所以我着重介绍UUID1。

下面是UUID版本1的位域划分:

    0                   1                   2                   3
    0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                          time_low                             |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |       time_mid                |         time_hi_and_version   |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |clk_seq_hi_res |  clk_seq_low  |         node (0-1)            |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                         node (2-5)                            |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   
 typedef struct {
    unsigned32  time_low;
    unsigned16  time_mid;
    unsigned16  time_hi_and_version;
    unsigned8   clock_seq_hi_and_reserved;
    unsigned8   clock_seq_low;
    byte        node[6];
} uuid_t;

但位域划分是按照C结构体的表示方便来划分的,从逻辑上UUID1包括五个部分:

  • 时间戳 :time_low(32), time_mid(16),time_high(12),共60bit。
  • UUID版本:version(4)
  • UUID类型: variant(2)
  • 时钟序列:clock_seq(14)
  • 节点: node(48),UUID1中为MAC地址。

这五个部分实际占用的位域如下图所示:

    0                   1                   2                   3
    0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                          time_low                             |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |       time_mid                |  ver  |      time_high        |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |var|       clock_seq           |         node (0-1)            |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                         node (2-5)                            |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

在UUID中:

  • version固定等于0b0001,即版本号固定为1

    反应在字面值上就是:一个合法的UUID v1第三个分组的第一个hex一定是1:

    • 6b54058a-a413-11e6-b501-a0999b048337

    当然,如果这个值是2,3,4,5,也代表着这就是一个版本2,3,4,5的UUID。

  • varient是用来和其他类型UUID(如GUID)进行区分的字段,指明了UUID的位域解释方法。这里固定为0b10

    反应在字面值上,一个合法的UUID v1第四个分组的第一个hex一定是8,9,A,B之一:

    • 6b54058a-a413-11e6-b501-a0999b048337
  • timestamp由系统时钟获得,形式为60bit的整数,内容是:Coordinated Universal Time (UTC) as a count of 100- nanosecond intervals since 00:00:00.00, 15 October 1582 (the date of Gregorian reform to the Christian calendar).

    即从1582/10/15 00:00:00至今经过的百纳秒数(100 ns= 1e-7 s)。这么蛋疼的设计是为了让产生良好的散列,让输出ID分布的熵最大化。

    unix timestamp换算为所需时间戳的公式为:ts * 10000000 + 122192928000000000

    time_low = (long long)timestamp [32:64) ,将时间戳的最低位的32bit按照同样的顺序填入UUID前32bit

    time_mid = (long long)timestamp [16:32) ,将时间戳中间的16bit按照同样的顺序填入UUID的time_mid

    time_high = (long long)timestamp [4:16) ,将时间戳的最高的12bit按照同样的顺序生成time_hi

    不过time_hiversion是共享一个short int的,所以其生成方法为:

    time_hi_and_version = (long long)timestamp[0:16) & 0x0111 | 0x1000

  • clock_seq是为了防止网卡变更与时间回溯导致的ID重复问题,当系统时间回溯或网卡状态变更时,clock_seq会自动重置,从而避免ID重复问题。其形式为14个bit,换算成整数即0~16383,一般的UUID库都会自动处理,不在乎的话也可以随机生成或者设为固定值提高性能。

  • node字段在UUID1中的涵义等同于机器网卡MAC。48bit正好与MAC地址等长。一般UUID库会自动获取,但因为MAC地址泄露出去可能会有一些安全隐患,所以也有一些库是按照IP地址生成的,或者因为拿不到MAC就用一些系统指纹来生成,总之也不用操心。

所以,其实UUIDv1的所有字段都可以自动获取,压根不用人操心。其实是很方便的。

阅读UUID v1时也有一些经验和技巧。

UUID的第一个分组位域宽度为32bit,以百纳秒表示时间的话,也就是(2 ^ 32 / 1e7 s = 429.5 s = 7.1 min)。即每7分钟,第一个分组经历一次重置循环。所以对于随机到达的请求,生成的ID哈希分布应该是很均匀的。

UUID的第二个分组位域宽度为16bit,也就是2^48 / 1e7 s = 326 Day,也就是说,第二个分组基本上每年循环一次。可以近似的看做年内的业务日期。

当然,最靠谱的方法还是用程序直接从UUID v1中提取出时间戳来。这也是非常方便的。

一些问题

前几天需要合并老的业务日志,老的系统里面日志压根没有流水号这个概念,这就让人蛋疼了。新老日志合并需要为老日志补充生成业务流水ID。

UUID v1生成起来是非常方便的,但要手工构造一个UUID去补数据就比较蛋疼了。我在中英文互联网,StackOverflow找了很久都没发现现成的python,Node,Go,pl/pgsql库或者函数能完成这个功能,这些包大抵就是提供一个uuid.v1()给外面用,压根没想到还会有回溯生成ID这种功能吧……

所以我自己写了一个pl/pgsql的存储过程,可以根据业务时间戳和当初工作机器的MAC重新生成UUID1。编写这个函数让我对UUID的实现细节与原理有了更深的了解,还是不错的。

根据时间戳,时钟序列(非必须),MAC生成UUID的存储过程,其他语言同理:

-- Build UUIDv1 via RFC 4122. 
-- clock_seq is a random 14bit unsigned int with range [0,16384)
CREATE OR REPLACE FUNCTION form_uuid_v1(ts TIMESTAMPTZ, clock_seq INTEGER, mac MACADDR)
  RETURNS UUID AS $$
DECLARE
  t       BIT(60) := (extract(EPOCH FROM ts) * 10000000 + 122192928000000000) :: BIGINT :: BIT(60);
  uuid_hi BIT(64) := substring(t FROM 29 FOR 32) || substring(t FROM 13 FOR 16) || b'0001' ||
                     substring(t FROM 1 FOR 12);
BEGIN
  RETURN lpad(to_hex(uuid_hi :: BIGINT) :: TEXT, 16, '0') ||
         (to_hex((b'10' || clock_seq :: BIT(14)) :: BIT(16) :: INTEGER)) :: TEXT ||
         replace(mac :: TEXT, ':', '');
END
$$ LANGUAGE plpgsql;

-- Usage: SELECT form_uuid_v1(time, 666, '44:88:99:36:57:32');

从UUID1中提取时间戳的存储过程

CREATE OR REPLACE FUNCTION uuid_v1_timestamp(_uuid UUID)
  RETURNS TIMESTAMP WITH TIME ZONE AS $$
SELECT to_timestamp(
    (
      ('x' || lpad(h, 16, '0')) :: BIT(64) :: BIGINT :: DOUBLE PRECISION -
      122192928000000000
    ) / 10000000
)
FROM (
       SELECT substring(u FROM 16 FOR 3) ||
              substring(u FROM 10 FOR 4) ||
              substring(u FROM 1 FOR 8) AS h
       FROM (VALUES (_uuid :: TEXT)) s (u)
     ) s;
$$ LANGUAGE SQL IMMUTABLE;