B+ 树 (2): snapshot, copy-on-write

ou 1 Comment

很多时候我们修改一个重要的文件时都会先把文件复制一份作为备份，然后才对原文件进行修改，这样既可以防止修改错误无法恢复到原来正确的状态，也防止计算机突然断电造成数据不一致。当我们确定修改没有问题时会把原来的备份删掉（当然也可以保留下来），然后把修改后的文件再复制一份作为备份，再在当前的基础上进行修改，修改完成后再删掉原来的备份……如果文件较小，一般的版本控制工具都可胜任，但是如果数据很大（几百 G 到上 T，例如虚拟机镜像，数据库文件等），每次修改都要复制一遍或者比较和上一版本的差异以便增量保存，这样的做法无论是时间还是空间上都是难以忍受的。

快照（snapshot）

快照（snapshot） 就像上面提到的备份功能，即把某一时刻的状态保存起来，像照相机照相一样把当时的情景记录下来，虽然照相之后环境有变化，但是照片的内容不会随着环境变化而改变，这样的快照就是只读快照。另外还有支持修改的可写快照。经常使用的虚拟机软件如 vmware，virtualbox 等都提供快照的功能。有时我们需要尝试新软件或观察病毒的行为，但是又不想让它们修改真实的计算机，就可以先对虚拟机做一个快照，然后再做测试，测试完后恢复到快照的状态就可以了，既安全又快捷。

一般来说快照功能都是虚拟机软件或数据库自己实现的，对文件系统的使用只限于基本的读写新增删除操作，不只是因为 POSIX 标准只提供最基本的文件系统功能的接口，也因为没有几个文件系统具有文件快照的功能，文件系统的快照功能一般都由卷管理器实现。新出现的一些“现代文件系统”（参考资料 [1]）如 zfs，btrfs，除了文件系统的基本功能外还有快照和卷管理功能，抢了逻辑卷管理器如 lvm 等的饭碗。

快照在读多写少的情况下可以避免读写锁的竞争。对于实时性要求不高的应用来说，可以先对某一时刻的状态做一个快照，然后让读进程对快照进行访问（只读进程不需要加锁），而其它写进程则在另一个版本上进行更新，一段时间后再修改指针让其指向新的版本，等所有的读进程都完成旧快照的读取后就可以把旧快照删除。

写时复制（copy-on-write）

写时复制（copy-on-write） 的意思是多个用户共享一块相同的数据时，如果其中某个用户要对数据进行修改，系统会把这块数据复制一份然后进行修改，修改完成后让该用户的记录指向新修改的数据，这样其它用户看到的还是原来的数据而该用户看到的是已经修改过的数据。如果数据没有被修改则不会被复制，这样可以节省存储空间，像共享链接库，一个程序的多个进程实例等都用到了这个技术。

对于快照来说写时复制几乎是一个必需的功能。像上面所说的虚拟机文件来说，保存了快照之后要基于快照之上进行修改，但是由于虚拟机文件很大，而且修改的只是文件的一部分，不同状态的多个虚拟机文件可以共享大部分相同的数据块。

实现方法

比较容易想到的简单方法是使用线性表来实现，即为每个历史记录创建一个索引，这个索引指向该快照所有的数据块。elephant 文件系统（参考资料 [2]）就使用了这种方法。

参考资料 [3] 中使用了一种类似于内存地址转换的方法，即为每个数据块分配一个逻辑地址，另外还有一个逻辑地址到实际地址的映射表，访问数据块内容的时候要从映射表中找到实际的地址。这样建立快照的时候只需修改映射表就行了，坏处是映射表难以维护，地址转换也降低了性能。

还有一种方法就是下面要说的 B+ 树实现。

B+ 树的自顶向下操作

在看具体实现之前，先说说 B+ 树的自顶向下操作方法。上一篇笔记 说的是自底向上的方法，即分裂是从叶节点到根节点进行的。而自顶向下的方法是指，在查找叶节点的过程中对有可能会造成分裂/合并的节点预先进行分裂/合并，这样当最后对叶节点操作时不需要重新检查从该叶节点到根节点路径上的节点。这些预先分裂/合并操作并不会改变 B+ 树的性质。…

阅读全文…

pthread 学习笔记 (3)

ou Leave a comment

读者-写者问题

一个缓冲区，有些进程只读取里面的内容，另外有的进程会修改里面的内容。为了保持数据的一致性，如果没有进程修改内容时，任意个读进程可以同时访问缓冲区，但是同一时间只能有一个写进程可以访问缓冲区，其它写进程和读进程都不能对缓冲区进行操作。

读者-写者问题和生产者-消费者问题不同的是，后者的每个线程都要修改缓冲区的内容，所以不得不使用互斥锁来保证数据一致性，而前者有些线程是只读的，多个只读线程同时访问并不会出现数据不一致的情况，所以在实现上不必为每个线程都加一个互斥锁，而是让多个读线程可以同时访问，只有写进程的访问是互斥的。

使用互斥锁实现

下面是利用 pthread_mutex 系列函数的实现。

#include <stdio.h>
#include <pthread.h>

struct pool {
   int nr_reader;
   unsigned long long value;
   pthread_mutex_t may_write, rd_count_mutex;
};

static void* writer(void* arg)
{
   struct pool* p = arg;

   while (1) {
      pthread_mutex_lock(&p->may_write);
      ++p->value;
      printf("writer:
…

阅读全文…

linux 内核编译脚本

ou Leave a comment

上一次编译内核已经是三年前倒腾 LFS 的事了。这两天心血来潮编译了最新的内核，写个脚本备份一下。这个脚本在 debian 6.0 下成功编译 3.2.0-rc5 并配置好 grub，在别的系统上可能不好使，所以这里更多的是一个过程记录。注释掉的部分是 grub 相关的，因为经实验发现这个工作 update-grub 已经做了。

#!/bin/bash

function display_usage()
{
   echo "Usage: $0 [install src | uninstall version]" >&2
}

if [ $# -ne 2 ]; then
   display_usage
   exit 1
fi

if [
…

阅读全文…

debian 安装和配置 oracle 数据库

ou Leave a comment

这里记录一下在 debian 6.0 上安装和配置 oracle 数据库 11gR2 的一些注意事项。

准备工作

先设置一下环境变量（加入 ~/.bashrc）：

export ORACLE_BASE=<oracle base>
export ORACLE_HOME=<install home>
export ORACLE_SID=<orcl> # default is orcl
export PATH=$PATH:$ORACLE_HOME/bin

注意环境变量的目录末尾不能带有“/”，否则会有奇奇怪怪的问题。然后读入设置：

. ~/.bashrc

安装一些包：

aptitude install gawk libaio1 libaio-dev libstdc++5
ln -s /usr/bin/gawk /bin/awk
ln
…

阅读全文…

使用 rdesktop 连接 windows

ou Leave a comment

kvm 的性能比较好，但是显示的时候不能根据窗口的大小自动调整分辨率，而且 win7 就那么几个固定的分辨率，每当我想调整一下 kvm 窗口大小时 windows 界面立刻填充整个窗口分辨率变得模糊不清，最后找到一个很好的工具 rdesktop 总算是解决了问题。

rdesktop 是 linux 下一个远程桌面连接的工具，tsclient 和 grdesktop 是它的两个图形前端。rdesktop 拥有众多选项，与 kvm 配合使用相当不错，下面总结一下好用的选项。

本文中 rdesktop 的版本是 1.9。在旧版本可能有些选项不支持。按惯例先放出完整命令：

rdesktop localhost -x l -g workarea -P -z -r clipboard:CLIPBOARD -r disk:tmp=/tmp

关于 kvm 的设置可以参考 这里…

阅读全文…

pthread 学习笔记 (2)

ou Leave a comment

互斥和同步

互斥（mutual exclusion，缩写mutex）是指一段区域在同一时间内只能有一个线程对其进行操作，否则会造成不一致的情况，这段区域叫做临界区。互斥只要求同一时间内只能有一个线程进行访问，但是线程之间的访问顺序可以是任意的；同步要求线程之间的访问有一定的顺序，并且一般都要求线程之间互斥访问(如果不修改临界区的值的话可以允许多个只读线程同时访问)。

生产者-消费者问题

同步和互斥的一个经典例子是生产者-消费者问题。假设一个缓冲区的大小为 N，如果缓冲区还没满，生产者每次可以往缓冲区里放入一个物品；如果缓冲区非空，消费者每次可以从缓冲区里取出一个物品。缓冲区是生产者和消费者共用的，同一时间内只能有一个线程可以对缓冲区进行修改，否则可能会出现错误。为了保证对缓冲区修改的原子性（即访问过程中不能被别的线程打断），可以对缓冲区加一个互斥锁（mutex lock）。当线程要访问缓冲区时需要先检查锁是否被其它线程占用，如果是的话就必须等待正在访问的线程释放；然后它占用互斥锁，防止别的线程在自己修改的过程中访问缓冲区；访问完毕后释放锁，让其它线程可以进行访问。

只有一个生产者和一个消费者

#include <stdio.h>
#include <pthread.h>

struct pool {
   pthread_mutex_t mutex;
#define MAX_NUM 5
   int num;
};

/* mutex should be held by the caller when one of the following four inline functions is
…

阅读全文…

B+ 树 (1): 定义与基本操作

ou 6 Comments

1972 年 R. Bayer 和 E. McCreight 提出了 B- 树（参考 这里）。1979 年 Douglas Comer 在 The Ubiquitous B-Tree 提出了 B- 树的一个变形——B+ 树。由于多路平衡树减少了磁盘读写次数，并且仍然保持 O(logN) 的插入/删除/查找的效率，被广泛应用于数据库和文件系统中。

定义（参考资料 [1, 3]）

模仿 B- 树的定义（参考资料 [3]），一棵 m 阶的 B+ 树可以这样定义：

  • 每个节点最多可以有 m 个元素；
  • 除了根节点外，每个节点最少有
…

阅读全文…

programming in lua (5)

ou Leave a comment

第 8 章。

虽然我们说 lua 是一种解释语言，但是 lua 在执行前会被预编译为一种中间代码。解释执行语言的特殊之处不在于它们不需要编译执行，而是编译器是语言运行时（runtime）本身的一部分，也就是说可以执行在运行过程中动态产生的代码。

例如函数 loadstring() 接收一个字符串，返回一个可被执行的语句块（chunk）：

f = loadstring("i = i + 1")

i = 10
f()
print(i) -- 11

又或者是省略赋值操作直接使用 loadstring() 的返回值：

i = 10
loadstring("i = i + 1")()
print(i) -- 11

但是直接使用的话如果出错了出错信息会比较模糊。可以使用 …

阅读全文…

programming in lua (4)

ou Leave a comment

第 7 章。这一章看得不是很明白。

迭代器可以遍历一个集合中的所有元素。在 lua 中，迭代器一般都是函数，每次调用这个函数都会返回集合中的“下一个”元素，前面提到的闭包函数就是实现迭代器的很好选择：

function values (t)
   local i = 0
   return function ()
      i = i + 1
      return t[i]
   end
end

arr = {"one", "two", "three"}

iter = values(arr)
while true do
   local e = iter()
…

阅读全文…

使用 libpcap 分析网络报文 (2)

ou Leave a comment

这里打算写写报文分析接口的设计。 一般来说，以太网的报文格式为：

+------------+-------------------+-----+
| eth header | ip/arp/... header | ... |
+------------+-------------------+-----+

例如手机上的一次网页请求的报文格式可能像下面这样：

+-----+----+-----+-----+----+-----+--------------+
| eth | ip | udp | gtp | ip | tcp | http request |
+-----+----+-----+-----+----+-----+--------------+

不同的应用对于不同协议的内容可能会有不同的需求。比方说，一个应用希望抓取 gtp 报头中的 pdp context，以此建立起某个手机号在某段时间内使用的是哪个 ip 的映射，它不关心上层应用的内容；另一个应用希望抓取内层 ip …

阅读全文…