CRAK——Linux上的checkpoint/restart技术

浏览数：19 / 时间：2015年06月20日

我们都用过虚拟机，它能让保存一个正在运行系统的状态，这里用到的技术就是checkpoint，日后还可以restart，不过这是针对整个系统，有没有可能只checkpoint一个process，这个方向引来了研究热潮，CRAK就是其中做的比较不错的一个。

Checkpoint/restart技术应用场景：

1. 在分布式负载均衡方面，往往需要一个进程从一个host移到另一个host上

2. rollback：出错后可以回滚

3. 在系统关机前checkpoint，当系统重启后可以恢复程序执行

但是遗憾的是现在很多主流的商业和流行的操作系统，Unix，Linux等，都对fault-tolerance或分布式关注不够，并没有checkpoint/restart机制，这也给在其上加入这种机制带来很大的困难。虽然修改内核源码带来极大的困难，但有人想出了一个很聪明的办法：以内核可加载模块的形式引入checkpoint/restart机制。CRAK是这一理念的践行者，并可以作为模块应用在 linux kernel 2.6.25 版本（但 2.6.24, 2.6.27 和 2.6.32 并不支持 CRAK）。

先来看一下CRAK的设计理念：

1. 不是重写OS，利用通用OS，以模块加载的形式工作在OS上

2. 支持legacy applications

3. 低的overhead，所以不依赖stub process和home node

CRAK的工作流程（讲述 process migration）：

1. 加载模块到内核

2. 发出请求：checkpoint一个process

3. kernel收到请求后stop这个process，之后开始checkpoint它

4. kernel将它的state存到一个file中，然后这个process被kill掉了（因为它要开始迁移了）

5. 在要迁移到的host上创建一个新的process，将保存的state给它

CRAK提供的user interface是：

1. checkpoint：用户要做的是指明哪个process被checkpoint，创建的checkpointed imgage被存在哪里（硬盘或网络发送）。我们上面在checkpoint后kill掉了进程，用户还可以选择不kill

2. restart：当要恢复时，用户要使用那个image，让进程重生

这样，我们可以自己创建一个程序来监管你想要checkpoint的程序，定期自动去checkpoint。

Checkpoint：

当用户说要checkpoint某个进程时，都有哪些进程信息要save：

address space
register set
opened files/pipes/sockets
System V IPC structures
current working directory
signal handlers
timers
terminal settings
user identities(uid, gid, etc)
process identities(pid, pgrp, sid, etc)
rlimit
any other data that need to be saved

其中前两个是必不可少的。address space由几个section组成，一个section就是一个memory block，有开始地址和结束地址，以及访问标志（read，write，execute，private和shared）。checkpoint会遍历该进程所有的sections，将每个section的position和访问标志以及内容都存到image中。但我们知道一个简单的进程都会占据几MB的内存，更别说像apache这样的占据几十甚至上百MB的process。但CRAK很smart，这么多section中有code sections，它是read-only的，因此不必save它，直接从程序的二进制文件中获取即可。同样我们也不必save那些shared libraries，只需存那些会被修改的sections。

如果在checkpointing的过程中进程仍在running，所checkpoint的状态和进程最终的状态就会出现不一致性，因此在checkpoint前就要stop它：

// we don't checkpoint a currently running process.
  // stop it first.	
  if (p != current) {
    send_sig(SIGSTOP, p, 0);
    stop = 1;
  }
	
  if ((ret = do_checkpoint(fd, p, flags)) != 0)
    return ret;

其实虽然进程stop了，但并不表示进程就不会发生改变，此时它还可以接收signal，不过关于这个问题，CRAK给出了睿智的回答，但这并不是本文的重点，所以不做讨论了。

CRAK最聪明的一点就是以动态模块加载的方式工作，模块一加载，它就会成为内核空间的一部分，并以特权模式运行。实现这个理念是有难度的，module只可以和kernel协作，但不能随意更改它

Restart：

就像execve：

创建新进程
从image恢复address space
恢复register set
重新打开文件等

千言万语的价值不如几百行代码的价值，我想我们计算机人都应该信奉一条准则：

Don‘t talk, show me your code.

想法虽好，但要实现它，才是耗费心血的，下面来check一下CRAK的实现。

实现：

简单来说两个动作，一个文件，三个问题——

两个动作：checkpoint， restart

一个文件：存放process state的image file

三个问题：存哪些states？如何存？如何恢复这些states？

CRAK被加载后会将自己注册为一个device file：/dev/ckpt。这样用户程序就可以用标准文件的操作（open,close,write,read,ioctl）来跟这个kernel module交互了。CRAK提供ioctl这个接口来checkpoint和restart。

int checkpoint (int fd, int pid, int flags);

fd就是那个存process states的checkpoint image file，pid是要checkpoint的进程，flags标志有三种：

CKPT_KILL ：当checkpoint后进程马上被kill
CKPT_NO_BINARY_FILE：保留 code sections，是上面所说的减少要保存的内存空间的代码实现，这样就不必将code section也存入image中
CKPT_NO_SHARED_LIBRARIES ：保留 shared libraries

int restart (const char * filename, int pid, int flags);

filename是要加载的image file，从中恢复process。

pid：如果 flag 设为 RESTART_NOTIFY，当restart结束后kernel会发送一个SIGUSR1信号给进程pid

flags：

RESTART_NOTIFY ：如上，当restart完成后，由kernel通知pid进程
RESTART_STOP ：当restart完成后，立即结束这个restarted process

此外还有几个重要的函数：

get_kernel_address()

我们都知道内存地址有虚拟地址和物理地址，对于一个process，它的虚拟地址和物理地址是不同的，但对于kernel来说，虚拟地址就是物理地址。传给这个函数两个参数进程p和要访问的进程p的地址addr（虚拟地址），通过p的页目录和页表就可以计算出物理地址。

再来看一下register set，存寄存器状态并不是一个新鲜事物，在context swtich里，一个process要被替换，首先要保存它的寄存器状态。这里用的是同样的原理，在实现上的问题是它存在哪里了。一个process有自己的占据8K（2×PAGE_SIZE） frame的kernel stack，而进程的task_struct就在这里面，同样register set就在这个stack的顶部。例如，一个进程的 task_struct *p， register set的位置就是：

struct pt_regs *regs = ((struct pt_regs *)(2*PAGE_SIZE + (unsigned long)p)) - 1;

可惜的是CRAK的研究和开发已经年代久远，2001年，所用的实验环境是

Gateway PCs with Intel Celeron 433MHz CPUs and 128 MB RAM running Redhat 6.1 with Linux kernel 2.2.14.
All client machines were on a 100MB Fast Ethernet network.
The tests were done over NFS v3. The NFS server was a dual-processor Sun4u Sparc running Solaris 7 with 256 MB RAM.
The file system involved in the test was on a seagate 4.2GB SCSI disk (there were several other disks hosting other filesystems on the server).
The Linux client ran with NFS v3 UDP support.

作者自己都说在测试时会遇到unexpected results，如segfaults，所以CRAK只能算是原型开发，我们想要自己去完善它。

最后谈一下它的overhead。主要的overhead是将checkpoint image存起来，所以还是比较低的。它可以选择要存的内存sections，只存必要的，这也降低了overhead。下面是几个测试，第一行是使用了 CKPT_NO_BINARY_FILE和CKPT_NO_SHARED_LIBRARIES的优化（不存code和shared libraries所在的sections），可以节省80%-90%的时间和空间。

技术分享

如果要去研究它，最好选用 Virtualbox + Ubuntu 8.10，然后选择kernel 2.6.25 重新编译内核。或许你会碰到它运行出错的情况，这很有可能，毕竟这是个原型，而作者也说自己遇到了错误的结果，所以工作还是要靠我们自己来做。如果它运行异常，有可能是在dump内存是出错：

  for (i = 0, vm = p->mm->mmap; vm!=NULL; i++, vm = vm->vm_next) {
    unsigned char valid_mem;

    /* Dump the memory segment */
    valid_mem = valid_memory_segment(regs, p->mm, vm);

    /* Dump pages and shared libs if we are allowed to */

    if (!( ((no_binary && valid_mem) || (no_shrlib && !valid_mem)) &&
	   ( !(vm->vm_flags&VM_WRITE) || (vm->vm_flags&VM_MAYSHARE)) &&
	   vm->vm_file )) {
	    
      if (dump_vm_area(f, p, vm)) {
	ret = -EAGAIN;
	goto out;
      }
    }
  }

你可以先将这段注释掉，然后再进一步探究其root cause。Good luck!

这里附上它的源码和文档，以及继承它的一项研究Zap。

CRAK源码：

http://www.cs.fsu.edu/~baker/devices/projects/ale/crak-2.6.25.6.tar.gz

CRAK文档：

http://www.cs.columbia.edu/techreports/cucs-014-01.pdf

http://www.cs.fsu.edu/~baker/devices/projects/ale/

Zap论文：

http://systems.cs.columbia.edu/projects/zap/

http://dl.acm.org/citation.cfm?id=844162

作为checkpoint/restart的应用场景，可以看这篇论文Rex （Microsoft）：

http://research.microsoft.com/pubs/216938/ppaxos.pdf