In paper, they proposed lock-free version b+tree, especially optimized for cutting-edge flash storage.

They use “delta” to maintain the updating to the pages. Suppose the old page is P, and the updating D, and the page mapping is holding P. D has a link to P. They CAS page mapping to D (CAS(page mapping, P, D)). And it support multiple deltas form a chain, so we can continue to update this page without compact the pages and delta.

“Deltas” technique is also used in bw-tree structure modification, like split/merge.

Persistent

All the delta contains LSN, that allows updating BwTree before the WAL flush. Because even the system fails, they can recover and erase the deltas which LSN is larger than ESL(end of stable LSN).

They can consolidate the deltas for many reasons. But it must guarantee all the consolidated pages is not larger than RSSP (Redo scan start point).

This approach is an application of Deuteronomy. I think that paper is also worth to read.

周一的时候reading group 分享了这篇文章，我的slides。

主要是参考noria 作者给talk 的时候用的slides。这个最核心的思想是既然有缓存，那么不如把缓存放到数据库，这个思想是传统Materialized View。然后在工程上的创新是可以允许partially-state view 和动态改变view。

然后导师对这篇文章不是很喜欢是因为这个东西实际上有人做过很类似的了，而文章语气有点像拯救世界的样子。

在这里可以找到作者的slides：https://www.usenix.org/conference/osdi18/presentation/gjengset

翻译自 src/backend/storage/buffer/README

译者注：下文里面如果单独的用“缓存”这个词，那么原文中一般是是“buffer”。这时候指的是内存里面用来存放磁盘内容的最小单位。或者也可以用缓存页，缓存帧来表示。

对于共享缓存（shared disk buffer），这里有两种控制机制：引用计数(refernce counts, 或者说是pin counts) 和 buffer content locks。（实际上还有第三个层面的控制：一次访问必须要先得到一个表的锁才能合法的访问属于这个表的页面。表级别的锁（relation-level）不在这里的讨论范围内。）

Pins: 在访问一个缓存的内容之前，必须”pin这个缓存”（通过增加引用计数）。对于没有被pin的缓存，可能在任何时候被重新利用，存新的页到这个缓存里面。通常pin可以通过ReadBuffer得到（这里应该指ReadBuffer是一个函数），释放可以通过调用ReleaseBuffer。一个后端（backend，后文翻译时也会称作“进程”或者“任务”）可以pin一个页面多次，而且事实上也经常这样。而且持有pin很长一段时间也是可以的，比如说为了完成join操作，外层循环需要连续扫描（sequential scan）一个页面上面的全部tuple，这样就会花费很长时间。类似的，btree index scan也可能持有当前的索引页（index page）很长时间。这样不会有太大问题是因为通常的操作不需要等pin的数量减到0（如果真的有进程想要这样，那么最好是先获得一个表级别的锁。）然而在事务的边界处，是不应该持有pin的。

Buffer content locks: 这里有两种类型的缓存锁，共享（shared）的和排他的（exclusive）。和你想象的一样，多个任务可以持有共享锁锁，但是排他锁不允许其他任务持有任何类型的锁（所以有时候也叫做读锁和写锁）。这些锁设计上应该只被持有很端的一段时间，不应该长期持有。可以通过LockBuffer()来获得缓存锁。一个任务不能持有一个缓存锁多次！同时在获得锁之前，应该固定这个缓存。

缓存访问规则：

1. 为了扫描一个页面的tuples，必须pin缓存，而且获得共享锁或者排他锁。如果是为了检查缓存里面一个tuple的提交状态(commit status, XIDs 和 status bits)，也要固定缓存，而且获得共享锁或者排他锁。

2. 如果一旦决定对一个tuple 感兴趣（或可以被当前的事物看到），也许可以在持有pin的时候，扔掉内容锁。通常heap scans 时会这样做，这时tuple是通过heap_fetch返回一个指向缓存的数据来得到。 因此在持有pin的时候tuple 不可能消失（详见规则5）。它的状态可能会改变，但是一旦决定了是可以访问的就没啥关系了。（译者：不确定这里的heap scan是啥。看上去这里的意思是，反正只要先拿锁再拿pin，根据规则5，这个tuple就不能被删掉了。）

3. 增加一个tuple，或者修个一个现有tuple的xmin/xmax，必须持有包含这个tuple缓存的pin和排他锁。这保证了其他人在做可视性检查的时候，不会访问到tuple更新到一半的状态。

4. 即使只获得了共享锁和pin，有时候更新tuple的commit status （HEXAP_XMIN_COMMITED, HEAP_XMIN_INVALID, HEAP_XMAX_COMMITED 或者 HEAP_XMAX_INVALID 在 t_infomask 里面）也许是可以的。因为其他的其他正在查看tuple的后端会用OR来获得，所以这里可能只有一点或者没有风险；最多，这个导致了冲突只是意味着一个bit丢掉需要重新计算一遍。这四个bits只是提示（这些缓存了在pg_xactl中事物的结果），所以如果由于冲突导致以为变成0这没太大的危害。注意，然而如果一个tuple的HEAP_XMIN_INVALID和HEAP_XMIN_COMMITTED都被设置了，这个tuple是冻住的；这是一个critical update，对应的需要一个排他锁（也需要被WAL记录）。

5. 为了物理是删除一个tuple 或者压缩没有利用的空间，则必须持有pin 和排他锁，而且需要在持有排他锁以后，观察到引用计数为1（没有其他人物持有pin）。当这些条件都满足的时候，没有其他任务可以执行page scan 知道排它锁被释放掉，而且没有其他任务可以重新引用里面tuple。注意虽然在清理的时候其他进程可以持有pin，但是并不能使用page因为无法持有共享锁。

获得符合规则#5 的锁可以通过bufmgr的函数LockBufferForCleanup()或者ConditionalLockBufferForCleanup()。首先获得一个排他锁，并且检查当前的引用数量是不是1。如果不是，ConditionalLockBufferForCleanup()释放排他锁，然后返回false。而LockBufferForCleanup()释放排他锁但不释放调用者的pin，然后等其他任务的信号，当收到信号时候会再次尝试。这个信号当UnpinBuffer减小pin技术到1时候会出现。如上所说，这个操作可能会等很长时间来得到锁，但是这对并行的VACUUM操作并不是很大的问题。当前的实现只支持一个任务等待某一个buffer的pin-count-1信号。总之我们不支持多个VACUUMs 同时对一个库操作，这对于VACUUM已经够用了。除了VACUUM以外其他任务应该使用条件版本的函数（conditional）。

缓存管理器内部的锁 （Buffer Manger’s Internal Locking）

在PostgrSQL 8.1 之前，所有对缓存管理器的操作又一个系统级别的锁，BufMgrLock来保证，并不意外这是竞争的源头。新的锁机制避免了通常情况下获得系统级别的锁。它是这样工作的：

• 有一个系统级别的读写锁，BufMappingLock，这个锁保护了从buffer tags（page id）到缓存的映射。（实际上，可以认为这是在保护buf_table.c实现的hash表）。为了查询一个tag是否存在一个对应的缓存，从BufMappingLock获得一个共享锁已经足够了。注意如果想要pin这个缓存，必须要在释放锁共享锁之前就获得pin。如果想要改动一个缓存对应的具体的页面，则必须获得BufMappingLock的排它锁。这个锁必须在整个调整缓存的头和改变hash表整个期间持有。通常需要排它锁的操作是，读一个页面，发现这个页面不在缓存里面，这需要至少一次内核调用，而且通常需要等待IO操作，这本身就很慢了。

• 在PG 8.2中，BufMappingLock 被分成NUM_BUFFER_PARTITIONS个分别的锁，每个所负责保护一部分buffer tag 的范围。这样可以进一步减小在通常情况下代码里面的竞争。每一个buffer tag 属于的分区是由tag哈希值的low-order bits 来决定的。之前描述的规则适用于每一个单独的分区。如果需要同时锁上多个分区，那么必须按照分区编号的顺序来锁，来避免死锁的风险。

• 一个独立的系统范围的自旋锁，buffer_strategy_lock，为访问缓存的free list和“选择缓存以用来替换”的操作提供了互斥保障。这里用自旋锁而不是为了效率轻量的锁；而且当buffer_strategy_lock被持有的时候，不应持有其他任何类型的锁。这是多个后端同时出现缓存替换发生的时候，提供一定的并发的基本保障。

• 每个缓存头需要有一个自旋锁，而且所需要在修改缓存头内容的时候要锁上。这样可以让诸如ReleaseBuffer这样的操作改变一些自身的状态，而不需要获得一个系统级别的锁。我们用的是自旋锁，不是读写锁，因为这里没有特例需要持有锁去执行很多命令

注意缓存头的自旋锁不控制对于缓存里的内容的控制。每个缓存头也包含一个读写锁，“缓存内容锁”，这用来表示访问缓存里数据的权利。需要使用之前描述的规则。

每个缓存还有另一个读写锁，io_in_progress，被用作等待缓存IO的结束。在进程读和写的时候需要持有排他锁，而且进程在读写时需要先等待拿到共享锁（获得后之后立即释放掉）（这里面后面没太看懂）。在里面里面XXX 在系统里面是用来表示不一般的资源（nontrival resources）访问的读写锁，这么多读写锁有点烦人。也许我们可以每个后端放一个读写锁来代替这些（缓存头用一个字段表示那个后端在做IO操作）

正常的缓存替换策略（Normal Buffer Replacement）

有一个缓存”free list”，里面用来表示可以被用来替换的候选缓存。特别的，完全空的缓存（没有有效的页面）总是在这个列表里面。我们也可以把我们认为马上就不需要的缓存丢到这里面；然而，现在的算法还没有这样做。这个链表是用缓存头里面的一些变量来连接起来；我们在全局维护一个头指针和尾指针。（注意：尽管这些链表的链（next和last指针）在缓存头里面，但需要考虑用bufer_strategy_lock来保护起来，而不是缓存的自旋锁。）当free list是空的但要选择一个缓存提出的时候，我们使用一个很简单的clock-sweep 算法，它避免了通常操作下需要拿一个全局锁。它像这样工作：

每个缓存头包含一个使用计数，当缓存被pin的时候会增加（最多到一个有限的值）。（这只需要缓存头的自旋锁，那个锁在增加引用的时候也要增加，所以基本上没啥开销。）

“表的指针（clock hand）”是一个缓存页的索引，nextVictimBuffer，它周期性的在所有可用的缓存间移动。nextVictimBuffer由buffer_strategy_clock来保护。

1. 获得buffer_strategy_lock。

2. 如果free list不是空的，那么就删掉头部的缓存页。释放buffer_strategy_lock。如果缓存页被pin 或者使用计数不是0，它本来不该被使用；忽略掉他然后回到第一步。否则，pin这个缓存页，然后返回它。

3. 否则，free list是空的。选择nextVictimBuffer指向的缓存页，然后让nextVictimBuffer向后走一下以来用作下一次使用。释放buffer_strategy_lock。

4. 如果选择的缓存页被pin了，或者使用计数不为0，那么不能用这个缓存。减小缓存的使用计数（不是0的时候），获得buffer_strategy_lock，返回第三步继续判断下一个缓存。

5. pin选择的缓存页，返回。

（注意如果选择的缓存是脏的，我们必须在回收之前将它写回；如果这时有其他人在同一时间pin 了这个缓存页，我们必须放弃然后尝试其他的缓存页。作为一个只是用来“选择一个被提出缓存页算法”（select-a-victim-buff），这不是应该考虑的地方）

环状缓存替换策略（Buffer Ring Replacement Strategy）

当一个查询需要一次性访问许多缓存页的时候，比如VACUUM或者大规模的连续扫描，使用不同的策略。一个页面被这种操作用到看起来不像是很快需要再次用到，所以与其使用一个正常的clock-sweep 算法使得提出全部缓存，一个小的使用clock-sweep算法的环状的缓存页被分配来做整个扫描。这也意味着这个后端导致的巨大写流量只与自己有关，不需要影响其他进程。

对于连续扫描，使用一个256KB 的环。这小到可以填充进L2缓存，这使得从系统缓存（OS cache）到共享缓存（也就是PG自己管理的缓存）效率更高。即使环再小一点也没关系，但是至少要可以放下需要同时pin的缓存页。256KB 也已经留下足够的尾巴让其他后端加进来一起执行线性扫描。如果一个环状缓存是脏的，然后它的LSN（译者注：LSN是日志的Sequence Number，页的LSN应该是最后一个与这个页相关的最后一个LSN）被更新了，我们应该先执行写操作，并且刷新WAL（write-ahead log）之后再重新用这个缓存；这种清空下我们就放弃用环状缓存，而是用正常的clock-sweep算法。因此环状缓存最好是让只读的扫描来用（最多只能更新一下hint bits）。如果一个扫面更新了每一个页面，比如说大规模的UPDATE或者DELETE，环状的缓存总是会脏，然后缓存策略退化到正常的缓存策略。

VACUUM 像连续扫描一样使用256KB的环，但是脏页不从环里面删掉。而是，在需要的时候刷新WAL来重用缓存。在8.3引入环状缓存之前，VACUUM的环被放进了freelist里，相当于只有一个Buffer的环，但是需要大量的WAL刷新。允许VACUUM在刷新WAL的时候更新256KB可以更有效。

大量写的任务类似于VACUUM。目前只应用于COPY IN和CREATE TABLE AS SELECT。（也许让连续扫描的UPDATE和DELETE用这种大量写策略会很有趣？）对于大量写我们用16MB的环（但是不能超过shared_buffers的1/8）。已经发现更小的空间对于COPY经常需要阻塞来等待刷新WAL。虽然后台vacuum操作被刷新WAL阻塞问题不是很大， 我们更想让COPY不被这个限制住，所以我们让它用更大的缓存空间。

后台写进程的任务（Background Writer’s Processing）

后台写进程被设计用来写回那些看起来很快就要回收的页面，因此需要分离写工作和活跃的后端（backends）。为了达到这个目标，它从nextVictiBuffer 循环扫描（nextVictiBuffer不需要动），找到那些没有被pin或者没有使用引用计数的脏页。然后pin这个缓存页，写回，然后释放pin。

如果我们可以假设读nextVictimBuffer是原子操作，那么在找页面写回的时候，写进程甚至不需要获得buffer_startegy_lock；他只需要用自旋锁住缓存头来检查是不是脏的（检查dirtybit）。即使没有这个假设，也只需要在读nextVictimBuffer这个变量的时候来获得锁，在扫面的时候不需要。（译者：现在还有不是原子读的变量？即使是dirtybit？）（这相比PG 8.0，在避免竞争的花费方面提升了很多）。

后台写进程在写回的时候需要获得内容的共享锁（其他人做这件事情的时候也要这样干）。这保证了被写回磁盘的的页面是完整的。我们可能丢掉hint-bit的更新，但是根据在上面的缓存访问规则， 这不是个问题。

在8.4中，恢复模式中一些潜在的恢复被执行的时候，后台写进程也可能启动。它像正常处理提供服务，除了他写的checkpioints是理论上的restartpoints。

心血来潮花了200多刀，主要是看上这玩意有type-c，同时是触摸屏。但是没想到cpu很菜……

应用商店

可以安装安卓app，我就安装了tg试试，其实还不错，稍微卡一点点。但是因为系统输入法不支持双拼，不支持双拼！所以我放弃了，转身卸载掉了。

输入法

因为系统的不支持双拼，所以曲线救国在chrome 应用商店里面下载了输入法插件，体验还行。个别用js魔改输入框的页面不行。

Linux App

系统支持用kvm虚拟一个linux出来，这样就不用crouton了。甚至可以在里面跑x程序（不过还没测试）。

CPU/屏幕

CPU和屏幕都很菜，让我想起来我第一台电脑（屏幕意义上的）。

CPU是N3350，只有2MB的L2。一些操作有些卡卡的.

所以如果想要还行的体验，一定要买Google Pixelbook！钱少了只能买个体验很差的浏览器。

由于今天回家，加上Menci 告诉我说ios 上有wg 的客户端了，借我了一个美区账号，于是我就修了一下脚本，终于构建出来一个完全的overlay network了。

拓扑大概是：

1
2
3
4
5
6
7

           (10.56.100.1)
Mac --------- bj --------- hk  (10.56.100.2)
            /  \        /
           /    \      /
          /      dorm-router (10.56.100.3, 10.56.40.1)
     iPhone        |
                10.56.40.0/24 (宿舍内网)

大概是用wireguard 全部做p2p的隧道。然后在一些需要做路由的节点写上路由表，来把整个网络打通。

我为了让路由节点的ip和interface看起来整洁一点，我创建了一个network namespace，用veth创建一对端口，连接主机和ns，这样所有中间路由节点就有统一的ip，并且不影响自己外部的网络。

最终配置的脚本在这里。 里面的iPhone 和 Mac生成的脚本是一个占位符，目的的是为了建立的wg的端口。寝室里面处理内网的那段配置也没有在这里面体现出来，需要手动处理一下。

今天因为非常冷，然后打开米家的APP，woc，这怎么室内都有17度，昨天多少度来着？然后就想起来杰哥之前搭的grafana，于是干脆在路由器上面搭了一个。

首先建议到官网上根据官网教程安装grafana，influxdb，telegraf。其中grafana是一个显示的前端，influxdb是一个时间数据库，telegraf是抓数据喂到influxdb的工具。

这三个东西跑起来以后不需要啥设置，telegraf有一个默认配置是抓当前机器的cpu磁盘之类的信息上报，可以先玩一玩。

抓温度是用杰哥的脚本

miio是实现了小米物联网那一套的协议的一个工具，然后还可以用来控制设备，温度是从小米净化器那里抓的。miio有个坑是如果有好多子网，他就不知道在哪个子网下去发现设备了。所以建议直接在同一个子网下用另一台电脑miio discover一下，之后用miio tokens 来手动加设备。

经过测试得到结论关掉中厅门可以提高0.7度左右，也许是中厅漏风。

我同时加了一个用ifstat监控网速的监控，监控脚本在这

word.lcy.im

考虑到自己该背背单词准备托福（闲的发毛），于是就翻出来了之前在二手书店买的的托福词汇。之前想起来zrt做的一个背单词工具，但是他给下线了，就自己也做了一个。

因为自己发音不标准，于是主要是提示音标/意思/发音，然后输入拼写。前端用的bootstrap + jquery。后端自己输入单词列表，然后查询有道智云的API，给生成对应的翻译和发音。后端直接用flask撸了几个接口。代码并没有多少。

有道智云的API提供100元额度，但我发现乱搞用的并不慢，于是就把翻译等缓存下来了，发音直接用有道字典的接口嘿嘿。

1

https://dict.youdao.com/dictvoice?audio=abandon&type=2

word list是一个一个文件直接放到库里的，每次增加需要重新部署。于是刚刚折腾好了webhook自动部署，大概是用adnanh/webhook 这个程序，可以监听http请求调脚本。现在如果push代码服务器就会自动重新pull下来。服务端是跑在docker里面的。

因为还有api的key没有清理干净，暂时不开源。但有需要可以直接找我^^。

Stocastic Knapsack 应该是指的每个东西的价值或者大小服从某个概率分布而不是定值，当你决定选择这个物品以后其价值就确定了。需要做这个的原因是因为我博弈论的论文需要用到这个东西。

实际上解起来也特别简单，枚举一下自己的操作，假设价值大小是离散的。那么我们就可以简单的对每种价值计算一下贡献乘上概率即可。

如果是离散的话，可以给出一种fptas的做法，和普通背包的fptas一样，把价值大小除以 $\frac{\epsilon}{n}$。仔细计算一下误差不会很大就对了。

这个东西我之前听起来第一眼是觉得不可做，今天闲着想了一下发现非常裸。。。。。。还没去搜论文看，不知道会不会有更好的解。但是有fptas看起来很牛逼就对了。（再次后悔算设没好好学。

最近松鼠症，集了好多域名。

lcy.cat

lcy.im

ummm.io

.cat 域名是一个赞助类顶级域名。要求注册这个域名的必须放六个月的加泰罗尼亚语相关的网站。不过个人注册不放应该没啥问题吧🤔。

im域名还行吧。感觉还是想要io的，但是买不来了（天天：“加钱就能买来”

那个io域名是真的肉疼，一年200+。只是觉得ummm这个词很好就注册来了。

我把博客迁移到blog.lcy.im上来了，从blog.lcybox.com的访问会重定向过来。

把博客从wordpress 迁移到了 hexo。最主要的原因是为了静态化博客，这样部署起来稳一些（mysql 太占资源啦）。

为了兼容之前wordpress的链接，可以在_config.yml 里面，设置permalink: :year/:month/:day/:title/，并且在之前的文章头部加入之前在wordpress用的链接，比如permalink: 济南。这里我觉得是奇怪的历史遗留问题，因为文章的头部permalink只会替换掉:title部分。所以幸好之前wp是用日期/标题这种格式的，否则兼容链接也是个大问题。

部署脚本，大概就是ssh 到服务器上自动pull下来然后生成静态文件

1
2
3

#! /bin/bash

ssh louchenyao@blog.lcybox.com "cd /home/louchenyao/mmm-blog/; sudo chown -R louchenyao public; git pull; git submodule update; hexo g"