CPU虚拟化

 

MySQL概览–系统架构和关键数据结构

      近期在研究HandlerSocket的相关源码，其命名也正是因为handler这一重要的数据结构，handlerSocket的简单点说就是越过mysql的SQL层，直接通过handler操作底层的存储引擎，由于减少了SQL Parse，Opentable等消耗，并且直接利用handler通过索引index进行查询和更新操作，因此有较高的性能，近期在公司组内做了一次关于handlerSocket调研的分享，主要包括handler协议解析，handlerSocket关键代码和原理，innoDB关键特性等主题内容，当然mysql的系统架构和关键数据结构也是该次分享的基础内容之一，也因为这次分享，本人很荣幸的拿到starbucks的消费券以资奖励.本文主要讲下理解HandlerSocket原理以及mysql的必须知晓的相关系统架构和关键数据结构。

 

MySQL关键模块和流程

上述步骤不多做详述，图片来源于《Understanding MySQL Internals》，详细的各模块功能和描述，请详细查看书籍，这里给出仅仅说明一下mysql大致的系统架构和流程.

 

Mysql关键数据结构

 

•THD 线程描述符(sql/sql_class.h)

MySQL Server层 和用户连接的线程对象，包含处理用户请求时需要的相关数据。

NET net; // 客户连接描述符
TABLE* open_tables  
Protocol *protocol; // 当前的协议
Protocol_text protocol_text; // 普通协议
Protocol_binary protocol_binary; // 二进制协议
HASH user_vars; //用户变量的hash值
String packet; // 网络IO时所用的缓存
String convert_buffer; // 字符集转换所用的缓存
struct sockaddr_in remote; //客户端socket地址 
THR_LOCK_INFO lock_info; // 当前线程的锁信息
pthread_mutex_t LOCK_thd_data; //thd的mutex锁，保护THD数据（thd->query, thd->query_length）不会被其余线程访问到。
Statement_map stmt_map; //prepared statements和stored routines 会被重复利用
LEX *lex; //语法树描述符

 

其中特别的注意到：

TABLE* open_tables  
被查询引用的非临时和非Handler Open表

TABLE* handler_tables
TABLE* temporary_tables
TABLE* derived_tables

 

•NET 网络连接描述（sql/mysql_com.h）

该类在HandlerSocket中没有用到
Vio *vio; //底层的网络I/O socket描述符
unsigned char *buff,*buff_end,*write_pos,*read_pos; //缓存相关
unsigned long remain_in_buf,length, buf_length, where_b;
unsigned long max_packet,max_packet_size; //当前值;最大值
unsigned int pkt_nr,compress_pkt_nr; //当前（未）压缩包的顺序值
my_bool compress; //是否压缩
unsigned int write_timeout, read_timeout, retry_count; //最大等待时间
unsigned int *return_status; //thd中的服务器状态
unsigned char reading_or_writing;/*1 代表读, 2 代表写, 0代表无状态 */
unsigned int last_errno; //返回给客户端的错误号
unsigned char error;
/*0：执行成功
1：在协议层有逻辑错误
2：系统调用或标准库出错
3：特例，表示缓存不能装下当前这么大的包
*/ 

•TABLE 数据库表描述符（sql/table.h）

/*每一个table的共享结构St_table_share*/
Field **field; /* 指向数据域的指针*/
KEY *key_info; /* 数据库中key的信息*/ 
TYPELIB  keynames;/*通过keyname查找keynum(OPENINDEX)*/
TYPELIB  fieldnames /*通过fieldname找fieldnumber*/

handler *file; //指向这张表在storage engine中的handler的指针
THD *in_use; /* 使用这张表的thread号 */
byte *record[2] ;
/*每次找到的记录会先写入record[0],如需要修改则将要修改的原记录在record[1]中，利用field.store()会默认将更新的field写入record[0]中，逐一修改,具体见handler分析*/

•Field 字段描述符（sql/field.h）

/*域描述符，是各种字段的抽象基类*/
uchar *ptr; // 记录中数据域的位置
uchar *null_ptr; // 记录 null_bit 位置的byte
TABLE *table; // 指向表的指针
TABLE *orig_table; // 指向原表的指针
const char **table_name, *field_name;

/* 数据域是下列key的一部分 */
key_map key_start, part_of_key, part_of_key_not_clustered;
key_map part_of_sortkey;
/*以下操作将要insert\Update的值先设置到field中，这些field会默认填充到table.record[0]中*/
int store(const char *from, uintlength, CHARSET_INFO *cs)
void store_time(TIME*ltime,timestamp_type t_type) 

•handler SQL层与Storage的接口

/*可通过table->file得到，innoDB等存储引擎将会实现handler的子类，以提供具体的write、update操作实现，但是handler中的ha_write_row等已经实现整体的逻辑，如先write_row,再binlog_log_row()*/
int  ha_open(const char *name, int mode, int test_if_locked)  /*tbname.frm文件*/
int  ha_index_init(uint idx)   
/*为下面的操作准备索引初始化,在find操作中使用了，但是在insert中没有使用*/
int ha_rnd_init(bool scan)  /*初始化为随机位置访问，scan决定是否全表扫描*/
int ha_write_row(uchar *buf);	
/*先write_row,再binlog_log_row(),binlog写入是在handler中完成的*/

该类也是实现自己的StorageEngine必须实现的,具体的StorageEngine的写法本文不深入研究，有兴趣请查看《Understanding.Mysql.Internals》 和《Expert MySQL》，下面简单列一下InnoDB需要实现的关键接口

virtual int write_row(byte * buf)			/*buf通常是table->record[0]*/
virtual int update_row
(const byte *old_data, byte * new_data)   /*record[1],record[0]*/
virtual int delete_row(const byte * buf）  /*record[0]*/
virtual int index_read(byte * buf, const
byte * key,uint key_len, enum ha_rkey_
function find_flag);					/*根据findflag找到第一匹配记录*/
virtual int index_prev(byte * buf);
/*根据当前索引的顺序，写入上一个record到buffer中*/
virtual int index_next(byte * buf);
/*根据当前索引的顺序，写入下一个record到buffer中*/
virtual int index_next_same
(byte *buf, const byte *key, uint keylen);/*从当前位置再找一个满足等于key的*/

本文只是有个粗略的介绍，分享下自己阅读代码和书籍的经验，只能对mysql的系统结构有个大致的描述，并且指出mysql源码研究必要的一些基础数据结构。如果读者想要深入研究mysql,请阅读上文中提到的两本书，并且务必请阅读源码。

Large-scale Incremental Processing Using Distributed Transactions and Notifications 译文

 

摘要

抓取文档的同时更新web的一个索引需要在新文档到达时不断地转换大规模的现有文档储存库。这个任务是通过小型的，独立的突变转换大规模数据存储任务类型中的一个例子。这些任务在已有架构的不同性能之间存在差异。数据库不符合这些任务对于存储和吞吐量的要求：谷歌的索引系统存储数十PB的数据，每天处理上千台机器的数十亿的更新。MapReduce和其他批处理系统无法独自处理轻量级的小更新因为他们靠大型的批处理来提高效率。

我们已经建立了一个用于递增地将更新处理成大规模数据集的系统Percolator（过滤器），并已部署它来创建谷歌网络搜索索引。通过将以批处理为基础的索引系统更换成以使用Percolator进行增量处理为基础的索引系统，我们每天在处理数量相同的文档的情况下，谷歌的搜索结果文档的所用平均时间减少了50%

1．简介

考虑建立一个能用来回应搜索查询的Web索引的任务。索引系统开始在网络上抓取每个页面并在处理它们的同时在索引上维护一个不变量的集合。例如，如果根据多个网址抓取到了相同的内容，只有最高PageRank [28]的网址出现在索引中。每一个链接也被转化这样来自每个传出连接的锚文本就被附加在链接指向的网页。链接倒排必须跨副本工作：指向一个页面副本的链接如果有必要应转交到最高的PageRank副本上。

这个批量处理任务，可表述为一系列MapReduce[13]操作：一个为了集群副本，一个为了链接倒排等。维护不变量很容易，因为MapReduce限制了计算的并行度；所有文档在一个处理步骤中完成，否则不进行下一个处理步骤。例如，当索引系统正在写倒推链接到当前最高PageRank的网址，我们不必担心同时改变其PageRank；一个以前的MapReduce步骤已经确定其PageRank。

现在，考虑如何在抓取web的一小部分后更新索引。仅仅在新网页上运行MapReduces是不够的，例如，在新网页和剩下的web之间存在链接。MapReduces必须再次在整个存储库上运行，也就是说，新的和旧的网页。如果有足够的计算资源，MapReduc的可扩展性使得这种方法可行，而事实上，谷歌的网页搜索索引就是以优先于这里所描述的工作的这种方式设计的。然而，预处理整个Web丢弃了之前运行的时候所做的工作，也使延迟与存储库的大小成正比，而不是一个更新的大小。

索引系统可以把存储库存储在DBMS并且在使用事务维护不变量时更新单个文档。但是，现有的DBMSs无法处理庞大的数据量：谷歌的索引系统存储跨越数千台机器[30]数十PB的数据。像Bigtable[9]的分布式存储系统可以扩展到我们的资源库的大小，但不能提供工具来帮助程序员面对并发更新时维护数据的变量规模。

一个理想的能维护网络搜索索引任务的数据处理系统，能被以增量处理为目的进行优化；也就是说，它使我们能够维持一个非常大的文档库并在每一个新的文档被抓取时有效地更新它。鉴于系统将同时处理许多小的更新，一个理想的系统也将提供维护不变量的机制，而不管并发更新以及跟踪哪些更新已被处理。

本文的其余部分描述了一个特定的增量处理系统：Percolator。Percolator提供用户随机的访问多PB级的储存库。随机访问使我们能够单独地处理文档，避免了MapReduce需要的资源库的全局扫描。为了达到高吞吐量，许多机器上许多线程需要同时转化储存库，所以Percolator提供ACIDcompliant事务，使程序员更容易对存储库的状态进行推理；我们目前完成了快照隔离语义[5]。

除了推理并发，一个增量系统程序员需要不断跟踪增量计算的状态。为了帮助他们完成这个任务，Percolator提供了observer：即一些代码段，只要用户指定的列更改就被系统调用。Percolator的应用程序作为一系列observer被结构化；每个observer完成一个任务并通过写表为“下游”的observer创造更多的工作。一个外部进程通过写初始数据到表中触发处于链中的第一个observer。

Percolator是专为增量处理建立的，而不是为了取代解决大多数数据处理任务的现有的解决方案。结果不能被分解成小的更新（例如，排序一个文件）的计算能更好的被MapReduce处理。此外，计算应具有较强的一致性要求；否则，BigTable就足够了。最后，计算应在某些方面非常大（总数据大小，转换所需的CPU资源等）；不合适MapReduce或Bigtable的较小的计算可以由传统的DBMSs处理。

在谷歌，Percolator的主要应用是准备将Web网页列入实时搜索索引。通过转换索引系统到一个增量系统，我们可以处理抓取的单独文档。这减少了100倍的文档平均处理延迟，在搜索结果中出现的一个文档的平均年龄下降了近百分之五十（搜索结果的年龄包括延迟而不是索引，如文档被改变和被抓取之间的时间）。该系统也被用来把页面渲染成图像；Percolator追踪网页和页面依赖的资源间的关系，因此当任何依赖资源变化时，页面可以被重新处理。

2．设计

Percolator对大规模数据的增量处理抽象为以下两个过程：对一个数据中心随机访问的ACID事务和组织增量计算的observers。

Percolator是由三个运行在每一个集群节点上的角色组成的，分别是Percolator worker、Bigtable tablet server以及GFS Chunkserver。所有的observer是连接到Percolator worker上的，它们负责对Bigtable中变化的列族进行扫描，而且可以对响应observers进行函数调用。观察者对事务的保证是通过向Bigtable tablet servers发送read/write RPC来实现的，而Bigtable tablet server反过来又向GFS Chunkserver 发送read/write RPC。整个系统是依赖于以下两个小服务的：timestamp oracle和轻量级锁服务。其中timestamp oracle提供严格的时间戳增量，这是正确操作集的隔离快照协议所必须的属性。而Percolator worker通过轻量级的锁服务使系统对更新通告的搜索更加高效。

从程序员的观点来看，Percolator数据中心是由少量表组成的。每一个表是由大量行列索引的数据单元组成的。每一个数据单元又包括一个值：一个无含义的字节数组。

由于需要在大规模系统上运行而且不需要对低延时的需求，我们设计了Percolator。不严格的延时需求让我们可以采用一种懒散的方法来清理因为事务在失败的机器上运行时遗留的锁。这种懒散而又执行过程简单的方法潜在地位事务提交时间延时数十秒。这种延时在运行于OLTP任务上的DBMS上是无法容忍的，但是在一个为处理web索引的增量系统上是可以的。Percolator在设计上是没有事务管理的中心结构的；而且它缺少一个全局的死锁检测器。这将增加冲突事务的延时，但是可以使系统可以扩展到数千台机器。

2.1 Bigtable概况

Percolator是建立在Bigtable分布式存储系统之上的。Bigtable提出了多维度的存储map：键是（行、列、时间戳）元组。Bingtable对每一行提供了查找和更新操作，而且Bigtable 的行事务可以确保单独的行之内的read-modify-write操作的原子性。Bigtable能够处理PB数量级的数据，在大量不可靠的机器上可靠地运行。

一个运行着的Bigtable是由一大堆tablet server所组成的，每一个tablet server负责为若干个tablet服务。一个master与tablet server通过指示他们装载或者卸载tablet来相互协作。每一个tablet作为一大堆只读文件的集合存储在Google SSTable中，而SSTable是存储在GFS上的，Bigtable对数据的保护是依赖于GFS的。Bigtable允许用户通过将一系列列族整合成一个locality group来控制表的性能特性。这些列族是存储在他们自己的SSTable上的，这样可以减小扫描开销。

Percolator是做在Bigtable之上的。Percolator维持了Bigtable的主要接口：数据是由Bigtable的行和列组成的，除此之外，Percolator元数据存储在特殊的列中（见图5）。Percolator的API和Bigtable非常类似：Percolator的库大部分是由Bigtable操作加上Percolator计算封装而成。Percolator的挑战就是Bigtable未能实现的：多行（multirow）事务和observer框架。

2.2 事务

Percolator提供具有ACID隔离快照语义特性的交叉行，交叉表事务。Percolator用户用一门语言（当前是C++）来写事务代码，而且用这些代码将对Percolar API的调用作混合处理。图2显示了一个简单的集群文档，它是利用对文档的内容作hash。在这个例子中，如果提交返回出错，那么事务将会发生冲突而且应该重新提交。Get()和Commit()的调用时阻塞的，并行性是由许多事务在一个线程池中同时运行来实现的。

对于增量数据处理而言，不需要任何强事务的优点，因此事务能够使用户更容易地处理系统的状态，并避免在生命力持久的数据中心中引入误差。举例来说，在一个基于web索引事务的系统中，程序员可以作以下假设：文档内容的hash值与表中的索引副本是具有一致性的。如果不采用事务，那么一个不合时宜的崩溃可能会导致永久的错误。事务也使构建索引表变得简单了，他们总是在更新而且要保持一致。请注意，这些例子都需要跨行的事务支持，而不是bigtable中已经提供的单行事务。

Percolator利用Bigtable 的时间戳对每一份数据保存有多个版本。对于提供隔离快照而言，多版本是有必要的，它能够在一些时间戳上从一个稳定的快照上读数据。而写则表现为不同的时间戳。隔离快照可以避免发生如下写写冲突：当事务A和事务B并发运行过程中，当写到同一个单元中去时，最多只能允许一个A和B中的其中一个提交。隔离快照不提供串行化，尤其是事务在隔离快照之下运行的时候，是服从写偏移（write skew）的。对于串行化策略来说，隔离快照的最大优势是使读更高效。因为任何时间戳表现为一个一致性的快照，对于一个数据单元的读取只需要对Bigtable实施一个给定时间戳的查找操作，也没有必要获取锁。图3描述了事务和隔离快照之间的关系。

Percolator是通过给客户提供一个库来访问Bigtable，而不是由自身访问存储来实现的，因此Percolator和传统的数据库管理系统相比，在实现分布式事务过程中，面临着一系列挑战。其他的并行数据库在管理磁盘访问时将锁机制整合到系统组件中：既然每一个节点已经可以通过协调来访问磁盘上的数据了，那么它可以授权访问请求的锁以及拒绝对违反访问请求的要求。

相比之下，Percolator的每一个结点都能够发出请求来直接修改Bigtable的状态：没有其他便捷的方法来拦截拥堵和指派锁。因此，Percolator必须明确地维持锁机制。在面对机器故障的时候锁必须是可用的；如果在两段任务提交的时候锁不可用了，那么系统将会错误地提交两个事务并因此可能发生冲突。由于上千台机器将会同时提出对锁服务的请求，因此锁服务必须提供高吞吐率的性能。除此之外，锁服务应该是低延时的；每一个Get()操作需要额外对锁的读取，我们希望将这个延时最小化。面对以上这些需求，锁服务需要作副本策略（可以免受因机器故障导致而导致的锁不可用）、分布式和负载均衡（为了处理高负载）、写到持久化的数据存储设备上。Bigtable本身满足以上所有的要求，因此Percolator将锁存储在和存放数据相同的Bigtable上特定的in-memory列中，当对数据进行访问的时候来读取或者修改bingtable行事务中相应的锁。

我们将来会对事务协议进行更为细致的考虑。图6描述的是Percolator事务的伪代码，图4描述的是在事务执行过程中Percolator数据和元数据的层次关系。这些系统中使用的元数据列在图5中有所描述。这些事务构造为start timestamp (line 6)请求一个 timestamp oracle，这将会决定由Get()操作可见的一致性快照。Set()调用是作为缓冲直到事务提交为止。对于缓冲区的写操作采用的基本方法是和客户端协同后两段提交。不同机器上的事务通过Bigtable tablet server上的行事务来实现交互。

两段提交的第一段提交操作是预写（prewrite），我们对所有正在写的单元进行加锁操作。（为了处理客户端失败，我们设计了一个最基本的锁primary lock，其机制将会在下面进行讨论）。事务通过读取元数据来检验每一个被写的单元的冲突操作。有以下两种类型的元数据冲突：1.如果事务在其开始时间戳之后发现了另一个写操作的记录，那将会终止（第32行）；这是由防止写冲突的隔离快照来保证的。2.如果事务在任何时间戳上发现另一个锁，那也将会终止（第34行）。也有以下这种可能，当事务已经提交之后，锁暂时还没有释放，但是我们可能认为这也是一种异常情况而终止。如果没有冲突，我们在开始时间戳对每一个单元写锁和数据（第36-38行）。

如果没有单元发生冲突，那么事务将会被提交转而进行第二段操作。在第二段操作的开始的时候，客户从timestamp orale中获取提交时间戳（line 48）。然后，每一个客户端释放锁，以写记录替换锁的方式来确保对每一个读者来说其所写的内容是可见的。对读者来说这一条写记录表明这个数据在单元中是存在的；这包括一个指向开始时间戳的指针，帮助读者能够找到实际数据。一旦写是可见的（line 58），事务必须提交。

Get()操作首先校验锁的时间戳范围[0, start_timestamp]，这个范围在事务的快照中是可见的（line 12）。如果一个锁被提出了，而另一个事务同时在写一个单元，那么读事务必须等到锁被释放才可以进行。如果没有发现冲突锁，Get()操作在时间戳范围中取最后更新的记录，然后返回这个记录。

客户端失败的情况发生（由于Bigtable确保了写锁的正确性，那么tablet server失败并不影响系统）将导致事务处理过程非常复杂。如果在事务正在提交的过程中一个客户端失败了，那么锁将会在遗漏在后面。Percolator必须清除这些锁，否则将会导致事务的失败。Percolator采取一种懒散的方法来清除这些锁：当一个事务A遇到了一个由事务B遗漏的冲突锁，A可能会认为B失败了，并清除该锁。

其实对于A来说，并不能明确地判定B发生了错误；因此我们必须避免A清除B的事务与一个事实上没有失败的B提交相同的事务之间的竞争。Percolator通过在每一个事务中为提交或者是清除操作指定一个单元作为同步点的方式来处理这种竞争。这个单元的锁就是前面提到的基本锁（primary lock）。A和B都是信任（agree on）基本锁的。无论是清除还是提交操作都需要修改基本锁；因为这个修改是基于Bigtable row而完成的，那么在清除和提交操作中只能二选一。特别地：当B提交之后，它必须校验它仍然占据着这个基本锁，而且用写记录来替换它。当A清除了B的锁后，A必须校验这个基本锁来确保B还没有提交；如果基本锁仍然存在，那就可以安全地清除它了。

当一个客户端在执行第二段提交时崩溃了，事务将会越过这个提交点，但是仍将表现出杰出的锁机制。我们必须对这些事务进行前滚（roll-forward）。对于一个事务而言，它能够通过检查基本锁来找出两种情况下的区别：如果基本锁被一条写记录取代了，那么写锁的事务一定已经提交了而且锁已经前滚了；否则它应该回滚（rolled back）（既然我们总是首先提交基本锁，那么我们能够保证如果基本锁还没提交时进行回滚是安全的）。对于前滚（roll forward）而言，事务用清除的方法来取代搁浅的锁。

既然清除操作在基本锁上是同步的，那么对于清除被客户端占有的锁也是安全的。但是，这也引发了性能上的下降，因为回滚会迫使事务终止。所以事务只有在怀疑一个锁是被死亡或者阻塞的worker占有时才会进行清理。Percolator使用简单的机制来判定另一个事务是否还活着。Running worker写一个令牌到Chubby 锁服务器中，来表明他们属于这个系统。其他workers能使用已经存在的令牌作为一个表明他们还活着的标志（当处理过程退出时，这些令牌会自动删除）。为了处理一个worker是活着的而不是正在工作的，我们在锁中额外写了经过时间（wall time）；当锁所包含的经过时间太久之后，即使worker的令牌是有效的，也将会被清除。为了处理长时间的提交操作，workers在提交时定期地更新这个经过时间

2.3 时间戳

Timestamp oracle 是一个能够按照严格递增次序分派时间戳的服务器。由于每一个事务需要和timestamp oracle交互两次，这个服务必须能够稳定的承担。Oracle服务器通过写入最高的已经分派给稳定存储的时间戳去阶段性的生成一系列时间戳集合；通过这个时间戳集合，the oracle能够严格满足未来来自内存的请求。如果这个oracle重启，这些时间戳将会向前直接跳到最大已分派的时间戳（而不会往回）。为了节省RPC的开销（增加的事务延迟），每一个Percolator Worker会通过维持一个pending的RPC来批量事务处理这些请求。当oracle的负载变得越来越大，批处理自然会达到更好的效果。批处理在不会影响时间戳保证的情况下增长了oracle的可扩展性。我们的oracle每台单独的机器能够提供大概每秒两百万个时间戳。

事务协议采用严格递增的时间戳来保证Get()操作返回所有在事务开始时间戳之前已经提交的写入结果。为了说明它是如何提供这种保证的，我们考虑一个事务R在时间戳T_R进行读操作，一个事务W在时间戳T_W<T_R时刻提交。我们将显示R能够看到W的写入。由于T_W<T_R，我们知道timestamp oracle分发T_W在T_R的之前或者同一批量处理中；因此，W请求得到T_W会在R接受到T_R之前. 我们知道R在得到它的时间戳T_R之前是不能执行读操作的，而W写锁在请求他的提交时间戳T_W之前。因此上面的处理保证了W必须在R做任何读操作之前已经写了所有的锁;R的读操作将会看到已经完全提交的写操作或者是锁限制，这里W将会阻塞知道锁被释放，或者W已经提交的写操作对R的Get()操作可见.

2.4 通告机制

事务让用户在维护不变量的同时需要对数据表做变更，但是用户也需要一种方法去引发和运行这些事务。在Percolator中，用户写code(“observers”)使得被数据表的更新所trigger,同时我们将所有的observers连接到一个同时运行在系统中每个tablet server的二进制程序上.每一个observer与Percalator注册一个函数和一个列的集合，同时Percolator在数据被写入这些列的任一行时调用这些函数。

Percolator应用被组织为一系列observers;每一个observer完成一个任务并通过写入一个table来创建更多的任务给后面流处理的observer. 在我们的索引系统中，a MapReduce通过运行loader事务将已经爬取的文档加载进入Percolator,这一过程中将引发文档process事务去给这些文档做索引(parse\抽取链接等等).文档process事务进而引发更多的事务，比如分类聚簇(clustering)等等.分类聚簇事务进而引发事务去导出更新的文档聚簇到服务的系统中(这里应该指接受搜索查询的系统)。

我们的通知机制和数据库的trigger机制以及在active database中的event机制比较类似，但是它不像数据库的trigger机制，他们不能被用来维持数据库的不变量.特别的，已经被引发的observer运行在一个和trigger write相独立的事务中，这使得trigger write和已经被引发的observer的写不是原子的。通知机制意图帮助构建一个增量的计算而不是去帮助维护数据的完整性。

语义和目的的不同让observer行为比起层叠trigger的复杂语义更加容易理解。Percalotor应用由几个oberser组成——Google的索引系统有大约10个observer。每一个observer在可执行的worker的main()中被明确的建立，所以哪一个observer可用的是很清楚的。有可能是的几个observer同时监控相同的列，但是我们避免了这个情况以至于当指定的列被写的时候observer将会运行什么。用户确实需要小心无限循环的的通知，但是Percolator不能对此有什么防止措施；用户需要组织一系列的observers去阻止无限的循环。

我们提供了一个保证：一个observer对每一个被监控的列的更新最多只有一个事务提交。这个说法是不对的，考虑对同一个列的多个写入或许只会引发相应的observer只被调用一次。我们将这个功能叫做Message Collapsing(消息压缩),由于他通过减少对许多消息回应的开销达到了减少计算的效果。比如，对于http://google.com阶段性的重新处理是足够的，而不需要每次我们发现有一个新的连接指向他时都去重新处理。

为了为通知提供这些语义，每一个被监控的列都有一个伴随的”acknowlegement”确认列与每一个observer对应， 它的内容包括observer最近开始运行的时间戳。当被监控的列被更新的时候，Percolator开始了一个事务去处理通知。这个事务去读被监控列和它相应的acknowledge确认列。如果被监控列是在最近一次确认之后写入更新的，则我们运行这个observer，并且同时设置这个确认列为我们这时开始的时间戳.否则，说明observer已经开始运行了，于是我们不需要再运行它。即如果Percolator偶然同时启动两个事务，他们将都会看见发生更新的通知，然后运行observer. 但是一个将会取消，因为他们将会在确认列时发生冲突。因此我们保证了至多只有一个observer将会为每一个通知提交。

为了实现通知机制，Percolator 需要有效的找到变更单元以便observer被其引发运行.这个搜索是复杂的，因为通知机制是极少的：我们的表有上万亿的单元，但是，如果跟上负载的情况下，只会有百万级别的通知。除此之外，监控代码是运行在大量分布在各个机器上的进程上，这意味着这个搜索工作必须是分布式的。

为了识别这些变更单元，Percolator维持了一个特殊的Bigtable 通知列，包括对于每一个变更单元的入口。当一个事务写了被监控的单元，他也将同时设置相应的通知单元。那些workers在上述通知列上执行一个分布式的搜索去找到变更的单元。在observer被引发并且事务被提交之后，我们在通知列上删除这个通知单元。由于这个通知列仅仅是一个Bigtable 列，而不是一个Percolator 列，因此他没有事务特性，仅仅只是起到一个提示的作用，它提示搜索程序去检查acknowledge列以便确认observer是否应该运行。

为了让搜索更加有效，Percolator 将这些通知列放在分离的Bigtable 位置组中，以至于让搜索程序仅仅需要读取几百万的改变单元而不是上亿万条的所有数据。每一个Percolator Workder 启动几个线程去搜索。对于每一个线程，这个worker为其分派 table的一部分，workder通过事先随机选择一个Bigtable tablet，然后随机选择一个key, 最后从这个key的位置开始搜索这个table. 由于每一个worker都在随机搜索这个table的一部分，我们担心两个workers在相同的row同时运行了observer。虽然这个行为并不会导致正确性问题，因为通知具有其事务特性，但是它是低效的。为了防止这个问题，每一个worker需要在搜索这个row之前从轻量级的所服务中获得一个锁。由于这仅是一个忠告，这个锁服务器不需要持续的状态,因此也具有很好的可扩展性.

这个随机的搜索方法需要一个特别的难点处理：当它开始部署的时候，我们发现搜索线程将会趋向于凑到该table的几个区域，从而减少了搜索的并行度。这个现象也发生在很常见的公共运输系统中，即”platooning”或者”bus clumping”（车辆扎堆）,他在公汽是很慢的时候通常发生（因为交通或者很慢的载货载人）。因此每一个站点上旅客的数量随着时间而增长，加载延时将会变得更坏，并且更加减慢车辆的速度.同时，在那个慢车辆之后的任一个车辆将会加速，因为它在每一次停靠的时候将会加载更少的旅客。这样的结果就是经常一堆车辆同时到达一个停车点。我们的搜索线程和这是极其相似的，一个线程在运行observer后减速，然后在其后面的线程，快速的跳过这些rows，以至于和领头的线程相互扎堆,并且不能超越领头的线程，因为线程堆使得tablet 服务器过载了.为了解决这个问题，我们用一种公共交通系统所不能的方法修改我们的系统：当一个搜索线程发现他正在和另一个线程搜索同一个row，则他将在table中选择一个新的随机位置区搜索.进一步和交通系统类比，这些车辆（搜索线程）在我们的城市中为了避免扎堆在他们和前面的车隔得太近的时候，他们将随机传送到一个随机的站点(table中的位置).

最后，通知的经验让我们引入一种更加轻量级但是语义更弱的通知机制。我们发现当重复的相同页面需要同时处理时，每一个事务将会在试图引发同一个重复的cluster重新处理的时候遇到冲突。这让我们设计了一个没有事务冲突可能的方法去通知一个单元。我们通过写BigTable的notify列实现这个弱的通知机制。为了维持Percolator剩余部分这个事务的语义，我们严格限制这些弱的通知到一个特殊类型的列，它是不能被其他人写的，而只能被系统通知的。这个更弱的语义也意味着多个observer将会由于这个单一的语义在运行并且提交（虽然系统试图最小化这情况发生）.这也成为了一个重要的管理冲突的功能；如果一个observer频繁在一个热点上冲突，可以将他分为两个在热点上被非事务通知连接的两个observer。

2.5讨论

Percolator 和基于MapReduce的系统比较起来，一个最低效的地方是每个工作单元RPC的数据量。当MapReduce做一个单一的大块读取到GFS系统，获取所有的数据需要10到100秒的时间，Percolator执行大约50个单一Bigtable操作去处理单一的文档。

额外的RPC发生的一个来源是在提交的过程中，当写一个锁，我们必须做一个read-modify-write操作需要两次Bigtable RPC:一个是读是否有冲突锁或者写入，另一个是写入新的锁。为了减少这个开销，我们修改了Bigtable 的API依靠添加条件突变使得读修改些操作只需要单一的RPC。许多条件突变的目的点是同一个tablet服务器，他们能够被在一起被批量处理成为一个单一的RPC，从而进一步减少了RPC总数量。我们通过延迟锁操作几秒钟来搜集他们到一个批处理中。因为锁是被并行获得的，这仅仅给每个事务增加了几秒的延迟。批处理也增加了冲突发生的时间窗口，但是在我们的低竞争环境下，这并不是一个问题。

当从一个表中读取数据的时候我们也执行相同的批处理:每一个读操作被延迟，使得他有机会能够和其他的作用于同一tablet服务器的操作一起形成一个批处理.在每一个读的时候都延迟一下，潜在的增加了事务的延时。一个最后的优化减轻了这个效果，即预读取。预读取利用的原理是，读在同一个row中两个或者更多的值和读取一个值几乎相同的代价。Bigtable必须从文件系统中读取整个SSTable，然后压缩它。Percolator试图预测，每一次一个列被读取，同一行中哪些列将会在后续事务中被读取。这个预测是基于过去行为的。预读取，和已经读取的缓存结合，几乎减少了10倍的系统读取Bigtable的数量

在Percolator的早期实现中，我们决定让所有的API调用阻塞，并且依靠在每个机器上运行成千上万的线程来提供足够的并行度，去维持一个好的CPU利用率。我们选择thread per request 模式主要在于让应用代码比在事件驱动模式下更加简单的编写。强制用户在每次读取数据的时候捆绑状态将会使得应用开发非常困难。thread per request 模式的经验就是，总体来说积极地方面：应用代码是简单的，我们在多核机器上获得了好的利用率，并且通过有意义和完整的堆栈跟踪crash调试是非常简单。在应用代码中我们几乎没有遇到比我们想象更坏的紊乱条件。这个方法最大的弱点是和linux内核可扩展性以及google基础架构相关的高线程数目。我们的内部内核开发小组能够部署补丁去解决这些内核问题。

《片上多处理器体系结构》浏览收获

1. CPU功耗与频率f与电压平方的乘积，频率减半的双核和单核性能相当，但是总体能耗减少为1/4。
   当然功能很难降到这个水平，因为还存在静态功耗和漏电流
2. 传统的处理器侧重开发与利用指令集并行的传统处理器系统，运行说这种应用时的处理器利用率极低。对于指令级并行度很低的因公，使用传统的处理器不可能产生任何提升效果，而且这种复杂乱序的传统高级处理器，简单的处理器具有更低的功耗，因此实际中，CMP的架构通常采用的简单的顺序执行处理器。
3. 流水级少、结构简单的的流水线往往比目前流水技术多、结果复杂的流水线在功耗方面更有优势。但是这个结论的错误之处在于警惕管状态切换所造成的攻台功能只是处理器整体功耗的一部分，维持晶体管状态还会产生所谓的漏电流功耗（静态功耗部分）。当静态功耗足够大时，处理器流水线功耗的最优方案是一个中等级数的流水线结构，而不是无流水线结构
4. 多数服务器应用具有多线程并行度高、指令集并行度低，且缓存命中率低的特点。由于缓存命中率不高，且缺乏指令级并行性，因此运行这些应用时，大部分现代处理器多数时间处于闲置状态。选通时钟（clock gating）技术可以大幅度降低闲置状态下系统的动态能耗，但静态功耗和时钟分布功耗依然存在。
5. 为了解决4中问题，硬件多线程技术可降低片上资源的闲置率，只增加少量功耗就能答复提升系统性能，并显著改善性能功耗比。研究表明，为一个单线程处理器增加一个硬件现成只需要增加4%-7%的额外芯片面积。
6. 吞吐率：多线程、最大化单芯片上的处理器内核数量、提供足够的缓存和贮存访问带宽
7. 预取帮手，伪线程
8. 线程级猜测，实现自动并行
   两个线程并行执行时发生的硬件必须处理的关键情况
   1.在并行线程间传递数据
   2.在读操作提前时发现先写后读冲突
   3.在冲突发生后，安全的抛弃猜测状态
   4.按正确的顺序完成猜测式写操作
   5.提供内存重命名机制已完成先读后写冲突
9. 通常循环和子函数调用，对于循环，可以通过在多核处理器上并行的执行多个循环迭代来获得并行。只要循环迭代间的相关性很少，再多核并行的执行循环就能获得提速。
   对于子函数调用，则使用一个新的线程来运行子函数调用返回之后的代码，而使用原来的线程继续运行子函数的执行代码，以这种方式来获得细粒度的任务级别的并行，只要子函数的返回值是可猜测的（通常在没有返回值的时候）并且任何子函数造成的边际效应不会被立即调用到，那么这两个线程就可以并行的执行。相对循环来说，对子函数猜测并行化更具挑战性。

     本书主要致力于改善吞吐率和延迟的技术，关于TLS和程序手工并行化的内容也有所提到，将在后期阅读中进行深入学习。

XenMon工作机制

一、 背景：

XenMon是一个支持资源分配和功能配置部件，它可以精确地监视和展现分析结果的基础部件，它报告在不同VMs资源利用率，而且还提供一个对Xen的共享内部资源接口和资源安排。

以下为XenMon的架构图：

Xenbaked 是一个高度可配置的模块，它能让用户配置多久记录一帧，保存多久的历史记录。

Xenmon frontend 是作为前段应用，它是基于xentrace事件产生器的数据收集收集到的数据进行展示。

Xentrace是事件触发器，其机制在之后会介绍。

二、 xentrace机制：

Xentrace 是以共享内存的方式来进行操作的，内核部分对Xen中的一些系统调用函数都会对这片共享内存进行写入。在用户区，用户通过一些方法得到共享内存内的数据，并对其进行解析并显示，以下是xentrace工作机制的流程图：

三、 t_buf结构：

在xentrace的代码中会经常发现t_buf这个结构体：

Struct t_buf{

unsigned long cons;

unsigned long prod;

};

这个结构提记录的生产者和消费者的位置指针，而且它还是一个环状结构的共享内存，在代码中不难发现生产者和消费者的地址不是无限增大的，它是有一定大小的限制。

此处讨论的t_buf只是单纯的结构体，而环形缓存的结构大小是由t_buf结构体占用的空间和t_buf中消费者和生产者指针指向的地址data区所占用空间的总和。

四、 t_rec结构：

struct t_rec {

uint32_t event:28; //事件的宏定义，在处理的时候根据宏定义来处理响应的函数

uint32_t extra_u32:3; /* # entries in trailing extra_u32[] array */

uint32_t cycles_included:1; /* u.cycles or u.no_cycles?是否是cycles方式 */

union {

struct {

uint32_t cycles_lo, cycles_hi; /* cycle counter timestamp */

uint32_t extra_u32[7]; /* event data items */

} cycles;

struct {

uint32_t extra_u32[7]; /* event data items */

} nocycles;

} u;
}

t_rec结构是t_buf映射到用户区的内存空间，同样也是一个环状结构的缓存。从t_rec的结构上，可以得到事件类型等信息，然后在对这些事件进行处理。

Xenoprof 安装和使用

          关于Xenoprof的功能简介这里不详细介绍，可以查看这里，而其前身Oprofile的安装和使用可以看这里。
          本文主要记录本人关于Xenoprof的安装和使用，以及在其中可能曾经遇到的问题。

Xenoprof的安装
         前文已经介绍了Xen的源码编译和安装，如果在之前Xen的安装中没有考虑Oprofile的安装配置，则这里需要进行如下配置并做轻量级编译。

1. 软件包下载
   Oprofile是一个用户级别的工具，Xenoprof已经被包括在Xen中，仅仅需要对在Oprofile的网站(http://Oprofile.sourceforge.net/)上下载的Oprofile源代码包，并且在Xenoprof的网站上(http://xenoprof.sourceforge.net/)下载对应的Patch。
2. 打Patch,安装Oprofile 
   打Patch的命令，网上可以找到很多，从这里可以得到比较实践性的理解。
   执行patch -p1 < ../../oprofile-0.9.3-xen-r2.patch  注意p1和p0可以自行选择使用.
   执行./configure –with-kernel-support命令进行编译前的配置(可能提示没有libertylibrary，需要yum installbinutils-devel，同时需要gcc-c++编译器)； 配置好以后，按照Oprofile的README文件中执行make |  make install即可完成OProfile的安装。
3. 配置Xen，重新编译
   如果你的Xen已经编译安装过啦，那么这时你就需要更改配置文件进行轻量级编译安装。
   在编译前，需要修改一下配置文件，进入Xen源代码目录使用命令makelinux-2.6-xen-config CONFIGMODE=menuconfig，进入图形界面后需要将instrumentationsupport中的OProfile选中(一共两个选项，选择第一个选项以及第一个选项下的子选项即可)，保存并退出，然后进行Xen的轻量级安装，具体的过程可以查看Xen的ReadMe文件：
   # make linux-2.6-xen-build
   # make linux-2.6-xen-instal

Xenopof的使用

        Xen编译安装好后，重新启动进入新编好的内核，其详细用法可以详细参考Oprofile的使用例子http://oprofile.sourceforge.net/examples/
这里从虚拟机的测试来说明他的用法，它的相关资料可以在http://www.xen.org/files/summit_3/xenoprof_tutorial.pdf找到.
虚拟化下oprofile的测试分为两种，一种是主动模式，一种是被动模式，对于半虚拟化建议使用主动模式方式，而被动模式仅在镜像无法自定义修改的情况下使用，并且实验证明主动模式对于测试xen或者内核的开发的测试所获得的信息比被动模式要多.Xenoprof会建立一个profile的session，在这个session里可以有选择性地对多个虚拟机进行profile，以获取内核或应用程序的性能信息。启动这个会话的过程尤为重要，执行顺序特别要按照tutorial中来。其实这两种方式在tutoria中其实已经写得非常清楚了，这里不浪费资源重复写。这里特别说一下执行顺序和相关问题:

1. 环境检查。opcontrol –reset做安装检查，在dom0中一般都可以通过，domu中无法通过，则需要检查一下你的半虚拟化镜像的制作是否是在oprofile安装好之后。
2. opcontrol –help 可以查看相关的帮助,
3. 开始要分别在各个dom0和domu中做opcontrol –reset的操作
4. start-daemon的配置。
      dom0> opcontrol –start-daemon –event=GLOBAL_POWER_EVENTS:1000000
   –xen=/boot/xen-syms-3.0-unstable –vmlinux=/boot/vmlinux-syms-2.6.16.13-xen0
   –active-domains=1,3
   如上所示，可以用opcontrol –help|more来查看一些需要配置的信息。最主要的是以下几个：
   -e/event:监测的事件。比如我想去监测CPU不空闲的时候的比率。用CPU_CLK_UNHALTED(这个对不同的CPU是不一定相同的，还有硬件不支持的，只能用时钟中断的方式来监测,注意CPUHalted的理解：
             无论什么时候，只要操作系统调用HALT指令，CPU就会进入一种称之为HALT（译注：处于停机指令周期状态，又称C1状态，下同）的状态。具体来讲，当CPU进入HALT状态时，它的时钟信号就会被切断关闭一段时间。就在时钟信号关闭期间，CPU芯片逻辑单元也会相应地停止工作，这样就达到了节能目的。与此同时，系统性能也会受到较大影响。不过，HALT指令通常在系统繁忙期间并不会被调用，所以，HALT的性能损失并不大。（http://bbs.ocer.net/thread-271444-2-1.html）
   –xen  指向xen的为压缩的镜像
   –vmlinux/–no-vmlinux:指定未压缩的内核文件，这个我在之前的文章《Xen源码编译安装总结》中提到过,在Xen编译过程中，同时还会生成一个未压缩的vmlinux文件在/lib/modules/2.6.18.8-xen/build，直接将其拷出来引用即可.
   –active-domains  则是指定将要评测的dom的ID，这个可用通过xm list命令查看得到.
5. 在会话start-daemon启动之后，先启动domu的 start，再启动dom0的start,会话结束时，却是先直接用dom0的stop关掉，然后再一次shutdown，这里频繁切换dom,可能觉得不方便，可以使用ssh/rsh执行远程命令的方式进行，可以尽可能的减少反应时间引起的误差.
6. Opreport的使用
   在测试结束后，需要用opreport进行分析，opreport的选项可以参考Oprofile的使用例子http://oprofile.sourceforge.net/examples/
   opreport –help可以参看详细的用法和选项。通常我们在opreport中加入如下选项
   opreport -a -g –symbols –image-path=/lib/modules/2.6.18.8-xen/kernel >result
   其中-a指accumulate，即累加的，他可以方便的看到这段时间内某个事件的总时间,以CPU_CLK_UNHALTED为例，测试中，我们采用计算密集型程序进行测试，理论团队CPU应该几乎没有HLATED的时间，总的抽样数和CPU总的CLK数几乎吻合。
   -g，则表示会细化到某个模块源代码的某一行
   -l/—symobols  只相关符号，如函数等
   -p/—image-path表示相关模块的查找位置，通常我们选用/lib/modules文件夹下所用内核对应的模块，当然不同的需求可以按需指定。
   其余的命令不一一介绍，需要的话直接opreport –help就知道.

Xen 源码编译安装总结

          关于Xen的源码编译安装文章网上也比较多，我主要从我的实验经历对其进行总结。

1. 下载xen和hg源码包。
   先从http://xen.org   上下载两个源码包，xen源码和linux的hg文件,本文讨论xen3.3和xen3.4的情况，下面以xen3.tar.gz和linux-2.6.18-xen3.hg为例说明，必要时再做区分
2. 依赖包安装 
   tar xvf xen3.tar.gz 解压下载的文件，并仔细阅读目录下的README文件，打开README文件可以查看安装Xen前必须安装的软件包
   * GCC v3.4 or later
   * GNU Make
   * GNU Binutils
   * Development install of zlib (e.g., zlib -dev)
   * Development install of Python v2.3 or later (e.g., python-dev)
   * Development install of curses (e.g., libncurses -dev)
   * Development install of openssl (e.g., openssl -dev)
   * Development install of x11 (e.g. xorg-x11-dev)
   * bridge-utils package (/sbin/brctl )
   * iproute package (/sbin/ip )
   * hotplug or udev
   进入xen3.3.1/tools/check目录，运行./chk build命令，可查看目前这些必需的软件包的安装状态。
   对于这些安装包的补充安装，方法有很多，Linux的发行版本可以大体分为两类，一类是商业公司维护的发行版本，一类是社区组织维护的发行版本，前者以著名的Redhat（RHEL）为代表，后者以Debian为代表。两者方法总结如下:

   RHEL的包安装
   对于RHEL的用户，可直接采用光盘镜像做源的方法，光盘中包括所有需要包，其他用户则可以利用yum在网上下载.yum的配置比较简单，在google中搜索“RHEL yum 源”即可找到网络软件仓库、以及光盘镜像做源的方法。做源的好处在于以后缺什么包或软件可以直接用yum来安装。当然如果不想配置yum源，你可以直接将ISO mount 上linux，进入光盘中的Server文件，在该文件下，可以用 rpm –a|grep openssl 进行相关包的查询,再用rpm –ivh xxx.rpm 对相关的包进行安装，其中特别注意x11包的名字是以libX11开头的。

   Debian的包安装
   对于debian用户而言，配置apt-get的方法，在网上也可以找到响应版本最新的源，根据自己的网络条件进行选择。用ISO做源的方法网上也可以查到。
   除此之外，虽然我们以及手动下载了hg文件，但是由于在makefile文件中会调用hg命令做些其他的下载和检查工作，因此还必须安装mercurial,如果上面的yum和apt-get配置好了，则可以直接进行安装即可，若没有配置好源，则可以下载mercurial的源码包自己参照其中的README进行源码安装.最后./chk build全部OK后才能进入下一步安装。

3. 上面的准备工作弄好后，关键的步骤就是hg文件的放置位置和相关文件的配置方法
   对于xen3.3的版本，直接将hg文件加压到xen3.3的统计目录即可，但是该方法对于xen3.4无效，需要执行如下修
   vim buildconfigs/src.hg-clone
   去掉hg同步linux内核源码的步骤，如下：
   —————————————————————-
   # Mercurial
   HG ?= hg
   LINUX_SRCDIR ?= linux-$(LINUX_VER)-xen.hg
   # Repository to clone.
   XEN_LINUX_HGREPO ?= $$(sh buildconfigs/select-repository $(LINUX_SRCDIR) $(LINUX_SRC_PATH))
   # Set XEN_LINUX_HGREV to update to a particlar revision.
   XEN_LINUX_HGREV  ?= tip
   $(LINUX_SRCDIR)/.valid-src: $(__XEN_LINUX_UPDATE)
   set -e ; \
   touch $@
   —————————————————————-
   然后将hg的文件夹拷贝到xen代码的根目录中即可。
   
4. 对编译进行相关配置
   make linux-2.6-xen-config CONFIGMODE=menuconfig，这个依据你对xen编译实验的要求进行相关配置，编入内核或是编程模块，比如有些研究xenprof的需要在对oprofile执行./configure命令后在xen的配置中加入内核oprofile选项，相关配置和使用文章我将在后期文章中加上。
   
5. 开始编译模块 
   特别的，对于stubdom的相关设置，网络条件好则不用担心，但是不好则要预先做些设置和下载。
   如果不需要研究stubdom，则直接修改xen目录下的Makefile文件，删掉stubdom相关内容，不影响xen的使用.
   在18行（.PHONY: install的下一行反正）把install-stubdom删掉
   在40行（.PHONY: dist的下两行，恩）把dist-stubdom删掉
   而对于需要stubdom做研究的同志，则需要事先从网站上准备以下软件包：
   fuse-2.8.3.tar.gz  ||   grub-0.97.tar.gz  || lwip-1.3.0.tar.gz || newlib-1.16.0.tar.gz || pciutils-2.2.9.tar.bz2 || zlib-1.2.3.tar.gz
   将这些软件包放到studom文件下，但是特别注意不要执行make world,因为它会执行clean操作使得刚刚拷贝的包删除。推荐使用make dist开始编译，编译时间依机器不同而不同，通常可以使用make dist -j8进行多线程编译，这里8是线程数可以自己设定，有些会在complier.h找不到等错误，或是文档安装需要额外的包，但是不会这些都是不会影响Xen的正常编译和使用。
   
6. make install进行模块安装，生成vmlinz
   这一步比较快，会在boot目录下生成一个gzip压缩并包含启动ELF头的vmlinz文件,同时还会生成一个未压缩的vmlinux文件在/lib/modules/2.6.18.8-xen/build，即内核文件，其中未压缩的vmlinux文件在以后的oprofile的测试中–vmlinux选项中可以使用，这里要略微提一下网上关于用gzip解压vmlinz生成vmlinux的做法是不必要且不对的，经比较原生的vmlinux比经解压缩的要大，至于损失哪些信息我还没有做深入的研究。也许你会问，到这一步不是已经编译成功了吗？这里补充说明一下vmlinz和initrd的关系。vmlinuz自然就是内核了，initrd.img是一个小的映象，包含一个最小的linux系统。通常的步骤是先启动内核，然后内核挂载 initrd.img，并执行里面的脚本来进一步挂载各种各样的模块，然后发现真正的root分区，挂载并执行/sbin/init… …。
   initrd.img当然是可选的了，如果没有initrd.img,内核就试图直接挂载root分区。
   之所以要有initrd，那是为了启动的时候有更大的灵活性。比如，你把ext3支持编译成模块了。偏偏你的root分区又是ext3的。这下就麻烦了。因为内核需要挂载root分区之后才能加载ext3支持。但是没有ext3支持就没法挂载root分区。initrd就是用来解决这个问题的。
   类似的用这个东西还可以做其他的事情，比如从usb盘启动linux也会面临上面类似的问题。用initrd就能搞定了。
   甚至，我想在有些嵌入式设备里面都不需要真正的root分区，用initrd就足够搞定一切了。主要是为了解决vmlinuz太大的问题，用initrd可以解决这个问题。否则的话在2.6的内核中启动会失败的
   
7. initrd映像制作,安装xen README文件的说法，经测试主要包括以下两种情
   对于RHEL等商业公司维护的发行版本来说，多采用如下方式进行
   Depending on your config, you may need to use ‘mkinitrd’ to create
   an initial ram disk, just like a native system e.g.
   # depmod 2.6.18-xen
   # mkinitrd -v -f –with=aacraid –with=sd_mod –with=scsi_mod initrd-2.6.18-xen.img 2.6.18-xen
   而对于debian平台的用户来说，如ubuntu则一般采用如下方式进行
   Other systems may requires the use of ‘mkinitramfs’ to create the
   ram disk.
   # depmod 2.6.18-xen
   # mkinitramfs -o initrd-2.6.18-xen.img 2.6.18-xen
   这一步中通常依据机器不同，出现不同的出错，对于缺失的模块可以加上—allow-missing 选项，而对于其他错误这里不一一列举，则用户最好在网上搜一下，一般都会有合适的解决方案
8. Grub启动项的制作
   特别的，如下面的形式，通常只有kernel和initrid的两项，在xen的启动中,xen.gz作为内核会先启动，随后才是原来的vmlinuz和initrd皆以模块形式加载，如下为grub 2以前的启动方式，在/boot/menu.lst(或者grub.conf)中加上
   title Xen 3.4 / XenLinux 2.6
          kernel /boot/xen-3.4.gz console=vga
          module /boot/vmlinuz-2.6-xen root=<root-dev> ro console=tty0
          module /boot/initrd-2.6-xen.img
   而对于当前新的grub 2方式，我们会发现，这些命令失效了，在grub2中，会修改/boot/grub/grub.cfg文件，便将其中的原来一项linux启动项复制，并将原来的linux 和initrd命令，替换为
   multiboot /boot/xen-3.4.gz console=vga
   module /boot/vmlinuz-2.6-xen root=<root-dev> ro console=tty0
   module /boot/initrd-2.6-xen.img
   

   至此，整个xen源码编译的过程就结束了，你可以进行重启了，通常如果上述过程中没有出现错误，则会正常启动，如出现mount找不到文件等等，一般是grub中的路径写错了，而如果是kernel panic 错误，则可以先尝试在第7步中用一下其他的配置选项，如果还不行，建议重新检查本文之前的步骤是否有错误未处理，特别是编译的过程。

海盗分金块问题

       在加入联创团队的通宵笔试过程中,曾经就遇到这个题,当时就是太相信自己的直觉,而放弃了冷静而周密的逻辑推导,导致当时整个题目出错,通宵笔试后,我回到寝室,就找到了这篇文章,一直没有机会好好把他精心剪辑出来,利用最近学校考试的一点复习时调节的空余时间.我转载了这篇文章,另外,也想到了一些其它的类似的题目供读者玩味!
数学的逻辑有时会导致看来十分怪异的结论。一般的规则是，如果逻辑推理没有漏洞，那么结论就必定站得住脚，即使它与你的直觉矛盾。 1998年9月，加利福尼亚州帕洛阿尔托的Stephen M. Omohundro寄给我一道难题，它恰好就属于这一类。这难题已经流传了至少十年，但是Omohundro对它作了改动，使它的逻辑问题变得分外复杂了。
先来看看此难题原先的形状。10名海盗抢得了窖藏的100块金子，并打算瓜分这些战利品。这是一些讲民主的海盗（当然是他们自己特有的民主），他们的习惯是按下面的方式进行分配：最厉害的一名海盗提出分配方案，然后所有的海盗（包括提出方案者本人）就此方案进行表决。如果50%或更多的海盗赞同此方案，此方案就获得通过并据此分配战利品。否则提出方案的海盗将被扔到海里，然后下提名最厉害的海盗又重复上述过程。
        所有的海盗都乐于看到他们的一位同伙被扔进海里，不过，如果让他们选择的话，他们还是宁可得一笔现金。他们当然也不愿意自己被扔到海里。所有的海盗都是有理性的，而且知道其他的海盗也是有理性的。此外，没有两名海盗是同等厉害的——这些海盗按照完全由上到下的等级排好了座次，并且每个人都清楚自己和其他所有人的等级。这些金块不能再分，也不允许几名海盗共有金块，因为任何海盗都不相信他的同伙会遵守关于共享金块的安排。这是一伙每人都只为自己打算的海盗。
最凶的一名海盗应当提出什么样的分配方案才能使他获得最多的金子呢？
为方便起见，我们按照这些海盗的怯懦程度来给他们编号。最怯懦的海盗为1号海盗，次怯懦的海盗为2号海盗，如此类推。这样最厉害的海盗就应当得到最大的编号，而方案的提出就将倒过来从上至下地进行。
       分析所有这类策略游戏的奥妙就在于应当从结尾出发倒推回去。游戏结束时，你容易知道何种决策有利而何种决策不利。确定了这一点后，你就可以把它用到倒数第2 次决策上，如此类推。如果从游戏的开头出发进行分析，那是走不了多远的。其原因在于，所有的战略决策都是要确定：“如果我这样做，那么下一个人会怎样做？”
因此在你以下海盗所做的决定对你来说是重要的，而在你之前的海盗所做的决定并不重要，因为你反正对这些决定也无能为力了。
记住了这一点，就可以知道我们的出发点应当是游戏进行到只剩两名海盗——即1号和2号——的时候。这时最厉害的海盗是2号，而他的最佳分配方案是一目了然的：100块金子全归他一人所有，1号海盗什么也得不到。由于他自己肯定为这个方案投赞成票，这样就占了总数的50%，因此方案获得通过。
        现在加上3号海盗。1号海盗知道，如果3号的方案被否决，那么最后将只剩2个海盗，而1号将肯定一无所获——此外，3号也明白1号了解这一形势。因此，只要 3号的分配方案给1号一点甜头使他不至于空手而归，那么不论3号提出什么样的分配方案，1号都将投赞成票。因此3号需要分出尽可能少的一点金子来贿赂1号海盗，这样就有了下面的分配方案： 3号海盗分得99块金子，2号海盗一无所获，1号海盗得1块金子。
4号海盗的策略也差不多。他需要有 50%的支持票，因此同3号一样也需再找一人做同党。他可以给同党的最低贿赂是1块金子，而他可以用这块金子来收买2号海盗。因为如果4号被否决而3号得以通过，则2号将一文不名。因此，4号的分配方案应是：99块金子归自己，3号一块也得不到，2号得1块金子，1号也是一块也得不到。
       5号海盗的策略稍有不同。他需要收买另两名海盗，因此至少得用2块金子来贿赂，才能使自己的方案得到采纳。他的分配方案应该是：98块金子归自己，1块金子给3号，1块金子给1号。
这一分析过程可以照着上述思路继续进行下去。每个分配方案都是唯一确定的，它可以使提出该方案的海盗获得尽可能多的金子，同时又保证该方案肯定能通过。照这一模式进行下去，10号海盗提出的方案将是96块金子归他所有，其他编号为偶数的海盗各得1块金子，而编号为奇数的海盗则什么也得不到。这就解决了10名海盗的分配难题。
        Omohundro的贡献是他把这一问题扩大到有500名海盗的情形，即500名海盗瓜分100块金子。显然，类似的规律依然成立——至少是在一定范围内成立。事实上，前面所述的规律直到第200号海盗都成立。 200号海盗的方案将是：从1到199号的所有奇数号的海盗都将一无所获，而从2到198号的所有偶数号海盗将各得1块金子，剩下的1块金子归200号海盗自己所有。
乍看起来，这一论证方法到200号之后将不再适用了，因为201号拿不出更多的金子来收买其他海盗。但是即使分不到金子，201号至少还希望自己不会被扔进海里，因此他可以这样分配：给1到199号的所有奇数号海盗每人1块金子，自己一块也不要。
202号海盗同样别无选择，只能一块金子都不要了——他必须把这100块金子全部用来收买100名海盗，而且这100名海盗还必须是那些按照201号方案将一无所获的人。由于这样的海盗有101名，因此202号的方案将不再是唯一的——贿赂方案有101种。
203 号海盗必须获得102张赞成票，但他显然没有足够的金子去收买101名同伙。因此，无论提出什么样的分配方案，他都注定会被扔到海里去喂鱼。不过，尽管 203号命中注定死路一条，但并不是说他在游戏进程中不起任何作用。相反，204号现在知道，203号为了能保住性命，就必须避免由他自己来提出分配方案这么一种局面，所以无论204号海盗提出什么样的方案，203号都一定会投赞成票。这样204号海盗总算侥幸拣到一条命：他可以得到他自己的1票、203 号的1票、以及另外100名收买的海盗的赞成票，刚好达到保命所需的50%。获得金子的海盗，必属于根据202号方案肯定将一无所获的那101名海盗之列。
        205号海盗的命运又如何呢？他可没有这样走运了。他不能指望203号和204号支持他的方案，因为如果他们投票反对205号方案，就可以幸灾乐祸地看到205号被扔到海里去喂鱼，而他们自己的性命却仍然能够保全。这样，无论205号海盗提出什么方案都必死无疑。206号海盗也是如此—— 他肯定可以得到205号的支持，但这不足以救他一命。类似地，207号海盗需要104张赞成票——除了他收买的100张赞成票以及他自己的1张赞成票之外，他还需3张赞成票才能免于一死。他可以获得205号和206号的支持，但还差一张票却是无论如何也弄不到了，因此207号海盗的命运也是下海喂鱼。
         208 号又时来运转了。他需要104张赞成票，而205、206、207号都会支持他，加上他自己一票及收买的100票，他得以过关保命。获得他贿赂的必属于那些根据204号方案肯定将一无所获的人（候选人包括2到200号中所有偶数号的海盗、以及201、203、204号）。
现在可以看出一条新的、此后将一直有效的规律：那些方案能过关的海盗（他们的分配方案全都是把金子用来收买100名同伙而自己一点都得不到）相隔的距离越来越远，而在他们之间的海盗则无论提什么样的方案都会被扔进海里——因此为了保命，他们必会
投票支持比他们厉害的海盗提出的任何分配方案。得以避免葬身鱼腹的海盗包括201、202、204、208、216、232、264、328、456号，即其号码等于200加2的某一方幂的海盗。
       现在我们来看看哪些海盗是获得贿赂的幸运儿。分配贿赂的方法是不唯一的，其中一种方法是让201号海盗把贿赂分给1到199号的所有奇数编号的海盗，让 202号分给2到200号的所有偶数编号的海盗，然后是让204号贿赂奇数编号的海盗，208号贿赂偶数编号的海盗，如此类推，也就是轮流贿赂奇数编号和偶数编号的海盗。
结论是：当500名海盗运用最优策略来瓜分金子时，头44名海盗必死无疑，而456号海盗则给从1到199号中所有奇数编号的海盗每人分1块金子，问题就解决了。由于这些海盗所实行的那种民主制度，他们的事情就搞成了最厉害的一批海盗多半都是下海喂鱼，不过有时他们也会觉得自己很幸运——虽然分不到抢来的金子，但总可以免于一死。只有最怯懦的200名海盗有可能分得一份脏物，而他们之中又只有一半的人能真正得到一块金子，的确是怯懦者继承财富。
类似比较有意思的智力题,可以查看一下链接:
http://zhidao.baidu.com/question/6954588.html?si=2
http://zhidao.baidu.com/question/17550593.html?si=4