# note: Enabling Efficient OS Paging for Main-Memory OLTP Databases

In this paper, they found the OS page replacement policy is not good for DBMS workload according to experiments. So they proposed to identify cold/hot data through sampling the access log, then re-organize the data to corresponding memory area. It divide the mmapped area to two parts, first part is Hot Area, second is for Cold data, the Hot Area be mlock-ed into memory.

They implement it on VoltDB. In VoltDB, each object (e.g. partition data table or index) has a continuous VM address space. The re-organization is done in userspace. The memory allocator (in userspace) has two free-list, one holds the free memory blocks on Hot area and one on Cold. To move one tuple, they just deallocate it and reallocate in another area (in userspace). The abstract data-structure will not be affected, it’s relative easy to implement such strategy.

And the experiments shows the performance is almost same to pure in-memory implementation even the data size is 50x physical memory, when the working set can fit into memory.

I have a question is that how calculate working set size for TPCC benchmark?

And this method also gets out the by production, the hot data is more compact now! It reduces the CPU cache miss rate.

# note: What’s Really New with NewSQL?

I occasionally found this paper from Andy (LOL) and decide to read it. Reading it is like reading a story book or novel. It introduces the history about disk-oriented DMBS and “New” DBMS w/ distributed architecture. In paper, Andy divided the NewSQL to three categories: DBMS having new architecture (especially distributed architecture), middleware, and cloud database.

In my option, cloud databases are traditionally database but optimized for cloud environment (Amazon Aurora); The middleware is like a coordinator in distributed DMBS context. And the distributed DBMS (especially for short-lived OLTP workload), is the most appealing to me. I don’t like the idea of replication for traditionally DBMS, because it still need to address consistency problem. And I don’t like that Andy uses “2PL” as the example for consensus rather than “Paxos”.

And there are some details I’m curios about distributed DBMS. It’s not about this paper, it’s for general distributed DBMS.

1. How do they guarantee that for different query go through to different nodes, the results or view are same if some modifications not yet propagate to these nodes. Locking? Even w/ locking, some nodes can be unlock before others.

2. How MVCC+2PL works in distributed context.

By the way, they mention VoltDB is based on OS virtual memory to support large than memory dataset. A question is whether the mmap(2) is good for in-memory DBMS?

# note: RUMA has it: Rewired User-space Memory Access is Possible!

They use mmap(2) with MAP_FIXED parameter, to map the file backed on ramdisk to user namespace. They use this approach to maintain the map between virtual memory address and physical pages. Based on this approach, it enables growing or shrinking the vector size, partition the data (for hash-join or something) without histogram pass, and userspace COW (snapshotting). Or for any application which needs shuffle the memory page can gain the improvement though this approach.

The experiments show it is at least as good as chucks directory (a[i] is represented as dir[i/chunkSize][i%chunkSize]).

They threat allocation of memory through mmap with Anonymous and Private parameters as the baseline. I’m not sure what’s huge page for mmap Anonymous Private memory. And the most performance penalty for Anonymous Private memory is populating the pages, because the OS copy/clean the page by default. The Rewiring Memory is already materialized and don’t have to populate the pages in general. I think it is not fair. They argue this is a feature or benefit of Rewiring Memory.

They also suffer mmmap(2) syscall performance problem when they need to call it many times. Increasing the page size is a workaround, and they argue it’s enough.

# note: Bw-Tree: A B-tree for New Hardware Platforms

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.

# 【翻译】关于PostgreSQL 的共享缓存访问控制的规则（Notes About Shared Buffer Access Rules）

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因为无法持有共享锁。

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

• 有一个系统级别的读写锁，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这样的操作改变一些自身的状态，而不需要获得一个系统级别的锁。我们用的是自旋锁，不是读写锁，因为这里没有特例需要持有锁去执行很多命令

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

“表的指针（clock hand）”是一个缓存页的索引，nextVictimBuffer，它周期性的在所有可用的缓存间移动。nextVictimBufferbuffer_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 像连续扫描一样使用256KB的环，但是脏页不从环里面删掉。而是，在需要的时候刷新WAL来重用缓存。在8.3引入环状缓存之前，VACUUM的环被放进了freelist里，相当于只有一个Buffer的环，但是需要大量的WAL刷新。允许VACUUM在刷新WAL的时候更新256KB可以更有效。

# Chromebook 体验

## CPU/屏幕

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

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

# 搭建grafana

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

word.lcy.im