作者
digoal
日期
2018-12-02
标签
PostgreSQL , uuid , 无序uuid , 索引分裂 , io , 性能诊断
背景
无序UUID会带来很多问题，例如索引分裂膨胀，离散IO，WAL膨胀等，详见以前的分析。
Regular random UUIDs are distributed uniformly over the whole range of possible values.
This results in poor locality when inserting data into indexes -
all index leaf pages are equally likely to be hit, forcing the whole index into memory.
With small indexes that's fine, but once the index size exceeds shared buffers (or RAM), the cache hit ratio quickly deteriorates.
《PostgreSQL 优化CASE - 无序UUID性能问题诊断》
《PostgreSQL sharding有序UUID最佳实践 - serial global uuid stored in 64bit int8》
https://blog.2ndquadrant.com/sequential-uuid-generators/
如何生成有序UUID呢？
以下是Instagram的做法
《PostgreSQL sharding有序UUID最佳实践 - serial global uuid stored in 64bit int8》
除此之外，还可以使用sequential-uuids这个插件：
https://github.com/tvondra/sequential-uuids
sequential-uuids插件例子
UUID为16字节类型，生成算法：在16字节的可枚举空间里随机生成，因此可以认为整个索引的所有页面都是热的，因为新生成的UUID值可能写入索引的任意位置。当UUID列的索引超出内存大小时，持续写入会不可避免的会引入较多的磁盘操作（FULL PAGE WRITE（由于可能写任意PAGE））。
而传统的序列方式的UUID，实际上是往一个方向递增会递减的。主要的问题：
1、对撞，由于取值范围降到了8字节（BIGINT的序列，或者时间戳（取决于精度））。所以对撞空间比UUID（16字节）小了，容易出现重复。
2、BTREE里面，往一个方向递增，如果一次性大量删除历史数据，会导致那些索引页全部废弃，导致膨胀。（当然，如果后续还有数据持续写入，那些完全删除了数据的索引页还可以被重复利用。）
为了解决这2个问题，提出了GUID的概念
https://en.wikipedia.org/wiki/Universally_unique_identifier
http://www.informit.com/articles/article.aspx?p=25862
GUID，实际上就是把数据拆成两部分，一部分自增，一部分随机。同样整个类型使用的是16字节。例如prefix部分使用自增（在有限空间内WRAP，重复使用），另一部分使用随机。同时解决了以上两个问题。
sequential-uuids插件就是这个思路实现的，
(block ID; random data)
提供了两种prefix算法：
1、prefix为自增序列，如果block ID使用2字节存储，一个索引BLOCK里面可以存储256条记录（假设8K的BLOCK，一条记录包括uuid VALUE(16字节)以及ctid(6字节)，所以一个索引页约存储363条记录(8000/(16+6))）
uuid_sequence_nextval(sequence regclass, block_size int default 65536, block_count int default 65536)
/*
* uuid_sequence_nextval
* generate sequential UUID using a sequence
*
* The sequence-based sequential UUID generator define the group size
* and group count based on number of UUIDs generated.
*
* The block_size (65546 by default) determines the number of UUIDs with
* the same prefix, and block_count (65536 by default) determines the
* number of blocks before wrapping around to 0. This means that with
* the default values, the generator wraps around every ~2B UUIDs.
*
* You may increase (or rather decrease) the parameters if needed, e.g,
* by lowering the block size to 256, in wich case the cycle interval
* is only 16M values.
*/
如下，假设block_size设置为256，则表示每256个连续值的prefix是一样的。
(nextval('seq') / 256) % 65536
意思是每256条记录，从0开始，prefix递增1，到65535后循环。
```
seq=1, prefix=0
seq=2, prefix=0
seq=256, prefix=1
...
```
2、prefix为时间戳。
uuid_time_nextval(interval_length int default 60, interval_count int default 65536) RETURNS uuid
/*
* uuid_time_nextval
* generate sequential UUID using current time
*
* The timestamp-based sequential UUID generator define the group size
* and group count based on data extracted from current timestamp.
*
* The interval_length (60 seconds by default) is defined as number of
* seconds where UUIDs share the same prefix). The prefix length is
* determined by the number of intervals (65536 by default, i.e. 2B).
* With these parameters the generator wraps around every ~45 days.
*/
默认每60秒内的数据prefix是一样的，prefix递增1，到65535后循环。
(timestamp / 60) % 65536
65535为prefix使用掉的字节数的取值空间，例如2字节，则为65536。
使用举例：
git clone https://github.com/tvondra/sequential-uuids
cd sequential-uuids/
USE_PGXS=1 make
USE_PGXS=1 make install
```
postgres=# create sequence seq;
CREATE SEQUENCE
postgres=# select uuid_sequence_nextval('seq'::regclass);
uuid_sequence_nextval
0000c98b-24e3-648d-d974-31a2a23e3f49
(1 row)
postgres=# select uuid_sequence_nextval('seq'::regclass,256);
uuid_sequence_nextval
0000a807-5878-05c1-7379-262e74e2d83e
(1 row)
postgres=# select uuid_sequence_nextval('seq'::regclass,256);
uuid_sequence_nextval
00005da3-473e-61d7-d2aa-ef3c0ad5ad3d
(1 row)
postgres=# select uuid_time_nextval();
uuid_time_nextval
97a52b75-fbc0-8758-eecf-be213e66f388
(1 row)
postgres=# select uuid_time_nextval(300);
uuid_time_nextval
84bab38b-87d5-17cd-07d3-93bd0c30d919
(1 row)
postgres=# select uuid_time_nextval(300);
uuid_time_nextval
84bacffe-69fb-7464-bbfb-bca9ca7bcb08
(1 row)
```
参考
https://github.com/tvondra/sequential-uuids
《PostgreSQL 优化CASE - 无序UUID性能问题诊断》
《PostgreSQL sharding有序UUID最佳实践 - serial global uuid stored in 64bit int8》
https://blog.2ndquadrant.com/sequential-uuid-generators/
https://github.com/tvondra/sequential-uuids/blob/master/sequential_uuids.c
PostgreSQL 许愿链接
您的愿望将传达给PG kernel hacker、数据库厂商等, 帮助提高数据库产品质量和功能, 说不定下一个PG版本就有您提出的功能点. 针对非常好的提议，奖励限量版PG文化衫、纪念品、贴纸、PG热门书籍等，奖品丰富，快来许愿。开不开森.
9.9元购买3个月阿里云RDS PostgreSQL实例
PostgreSQL 解决方案集合
德哥 / digoal's github - 公益是一辈子的事.
