Yahoo PNUTS 阅读笔记

下周的技术交流准备讨论下yahoo的分布式kv系统PNUTS，所以上周也温习了下paper，阅读中遇到了一些问题，有些在paper中有解释，有些可能就没有说的很清楚，所以本文根据自己对paper的理解对阅读过程中产生的几个疑问尝试进行解释，文中肯定有众多理解不到位的地方，欢迎大家一起讨论研究。本文可以被任意转载，但请注明出处。

Yahoo PNUTS是一个分布式的kv系统，设计支持1000台机器*1000个子表的容量，使用单点单层结构管理存储结点，使用消息队列实现副本之间的数据同步，提供被称为timeline一致性的一致性方案，提供单行的更新事务，并提供强或弱一致的读取接口。如paper所述并据了解，目前PNUTS已经比较稳定的用在Yahoo用户数据存储(id/password/profile等数据)和yahoo社交网站(pulse.yahoo.com)的全局数据存储。

关于架构和功能不再赘述，请阅读paper或参考网友的介绍

http://blog.csdn.net/wh62592855/archive/2011/04/14/6323791.aspx

下面开始7个问题的讨论

1 PNUTS的timeline一致性协议与dynamo的最终一致性协议有什么区别

       Pnuts中的数据更新要通过一个单点的master来处理，可以保证master中的数据是最新且是无冲突的，其他的副本只是通过消息队列同步master的中的数据因此会有延迟，但是slave在回放日志过程中任何一个状态都是master曾经的历史状态，读取任何副本用户都只可能读到master历史状态的数据，而不会读取到脏数据，因此不会出现paper中提到的实例那种对同一个行的两次顺序更新被乱序读取到的情况。相对而言dynamo与pnuts最大的不同是dynamo的任何副本都提供写入服务，因此可能出现两个对同一行的更新操作只在一个副本上有所有的历史记录，读取时必须保证R>=W才不会读到脏数据。虽然后可以做到一致性读取，但是dynamo的代价更大。

2 PNUTS中为什么使用router而不是客户端缓存

       Pnuts提供HTTP的数据存取方式，用户不需要安装任何客户端，可以直接通过HTTP协议访问集群，因此也就不需要客户端缓存，router中缓存了元数据的位置信息，用户访问router的请求将被重定向到数据对应的StoreUnit，而router由于是一个无状态的服务端，因此可以根据集群的负载情况部署多台机器，也可以与StoreUnit(SU)共用机器。在缓存过期的情况下StoreUnit将通知对应的router更新位置缓存。

3 写操作中如何保证写master和写消息队列的事务性

       在pnuts中数据都将首先被推送到Tablet或Record的master结点，然后由master决定是否可以执单行的事务操作，master执行成功后将操作日志发送到消息队列，订阅这个Topic的slave结点将收到这个操作日志并回放。因此需要保证更新master与发送到消息队列的事务性，即要保证数据在master和slave的最终一致性。可以通过让master在启动时也订阅自己的Topic来解决这个问题，master在本地预提交行事务，成功后将日志写入消息队列，写成功后再实际更新本地数据，然后更新操作日志时间戳，最后向客户端返回。如果在实际写本地数据之前master宕机，maste重启后通过回放上面提到的时间戳之后的日志来恢复数据。

4 切换master record/tablet的流程是什么样的

       pnuts在非本地读写请求变多的情况下，可以动态切换Tablet和Record的master结点，以保证最低的读写延迟，因此在master中会为每条record(处理update和delete时)和每个tablet(处理insert时)记录最近3次访问源的机房ID。切换的动作将由master发起，它首先停止接收来自可户端的数据更新，然后向消息队列写入一条SwitchMaster(指定一个slave副本变成master)的日志，然后将自己的状态修改slave，被指定的slave播放到这条日志时将自己的状态修改为master，可以开始接受来自客户端的数据更新，其他slave则修改本地更新master位置信息。在上一个master切换为slave和新的master产生之间的这段时间，对这个Tablet/Record的更新和read latest version请求将被hold住直到超时或确认到新的master。

5 如果处理master record/tablet宕机的情况

       StoreUnit的上线和下线都由TabletController(TC)通过心跳和lease来控制，在发现有SU下线的时候，TC将向这台机器存储的tablet相关的消息队列各发送一条日志，包括了下线机器的IP。

TableMaster宕机切换过程：当副本回放到这条机器下线的日志时先判断下线的机器如果不是master则什么都不处理，如果是master则发送一条ElectMaster日志到消息队列指定自己成为master，并将自己的状态修改为waiting，播放到这条日志的副本将一条确认消息写入消息队列，并修改自己保存的master的位置信息，当waiting状态的副本收到所有在线副本的确认消息后将自己的状态修改为master，开始接受数据更新请求。在这期间的insert请求将被hold。

       RecordMaster宕机切换过程：使用一种比较lazy的方式，当副本回放到这条机器下线的日志时直接记入本地，在下次Record更新或read latest version时如果自己不是master，并且判断master已下线时，则发送一条ElectMaster日志到消息队列指定自己成为master，后续流程与上述TabletMaster宕机切换一致。在切换期间的update和delete请求将被hold。

       RecordMaster宕机切换之所以使用lazy方式，主要是考虑到不可能针对每个record都立即执行一次master选举，所以改为由需要读写master的操作来触发。而TabletMaster的切换则需要在master下线后立即执行选择，以避免对后续insert操作带来的延迟

6 处理tablet分裂的流程是什么样的，为什么不能使用消息队列而使用了2PC

       Tablet的分裂由master发起两阶段提交执行，新分裂的tablet将会产生新的Topic。

       Paper中说根据tablet的复制协议，要保证副本间tablet范围的一致性，但是既然由master统一控制副本更新，将分裂命令写入消息队列好像也没有问题，对此我的理解是副本各自根据消息队列上的日志执行分裂可能增加controller管理的复杂性(这个问题在目前正在开发的淘宝海量数据库系统中也有遇到)，因此由master发起执行两阶段的分裂应该是个很简单可依赖的方案。

7 tablet拷贝副本的流程是什么样的，为什么需要写入checkpoint message

       Paper中讲述的过程是：第一，TC向源tablet发出拷贝消息；第二，源tablet向消息队列写入一条checkpointer日志；第三，向目标地址拷贝tablet。

       我没有很明白paper所讲述的，下面只能先讨论一下我考虑的tablet拷贝方案:

       如果源tablet是slave的话，在tablet中记录当前回放到的日志时间戳，只需要暂停同步消息队列中的数据然后将当前的tablet拷贝到目标地址，拷贝成功后继续从记录的时间戳开始回放消息队列上的日志即可。

       而如果源tablet是master的话，由于StoreUnit可能并不支持快照和检查点功能，因此开始拷贝前需要消息队列写入一条check pointer日志，得到这条日志时间戳后记入本地，在此之后的数据修改将只发布到消息队列而不执行到tablet(开一个新的临时tablet存储)，在拷贝完成后开始回放check pointer日志之后的日志，回放完成之后恢复正常流程(回放速度当然要快于外部的写入速度)。

http://research.yahoo.com/files/pnuts.pdf

一个简单Lrucache的设计思路

今天跟同事聊了下lrucache相关的东西，正好整理一下之前写过的一个lrucache的设计思路。

本文讨论在我们的系统中使用过的一种用于缓存磁盘或网络中静态数据的lrucache模块的设计方案。需求与常见的lrucache基本相同，要求提供get/put功能，内存管理，lru淘汰，支持多线程大量并发访问。

采用常见方案，使用一个key-value映射表加上一个lru-list实现，其中key-value映射表使用hashmap，lru-list则使用一个单链表就可以搞定。

但是这样一来我们需要面对多线程并发访问的情况下的挑战，对kv-map和lru-list的访问使用mutex加一把大锁保证原子性，在key为字符串的情况下对kv-map的查询变成了比较耗时的操作，而这个操作是在互斥锁中执行的，多线程的情况下大量时间被锁冲突浪费。

因此可以修改方案，对cache使用两层结构的设计，上层是index层，下层是memblock层。index层仍然是一个kv-map，但是这次value不是被缓存的数据而只是一个uint64_t的handle；下层是一个kv-map和一个lru-list，其中kv-map的key是uint64_t的handle，value则是一个定长内存块。对index层的访问使用无锁或小粒度的锁保证线程安全，对memblock层使用一个mutex保护kv-map和lru-list。

在这个方案中数据淘汰的粒度并不以一个key-value执行，而是以存储在一个定长内存块中的多条key-value为单位，memblock层负责管理多个这样的内存块的申请，访问和淘汰。每次访问cache先查询index层，获取用于访问底层的handle，通过这个uint64_t的handle访问memblock层获取实际存储的数据地址。Memblock层在执行淘汰的时候无需通知index层，当使用handle访问memblock层失败的时候自然可以知道内存已被淘汰。

Memblock层使用引用计数以确保正在被访问的内存块不会淘汰，因此我们也可以将index层的key同样存储在这个内存块中，用户访问index的hashmap时，通过hash值找到对应的桶，就可以通过这个桶内每个item的handle先增加对应内存块的引用计数，然后就可以安全访问对应的key了。

[zt] mallinfo malloc-hook mtrace

一：获得即时内存状态：

void getMemStatus()
{
    struct mallinfo info = mallinfo ();
    printf("arena = %d\n", info.arena);
    printf("ordblks = %d\n", info.ordblks);
    printf("smblks = %d\n", info.smblks);
    printf("hblks = %d\n", info.hblks);
    printf("hblkhd = %d\n", info.hblkhd);
    printf("usmblks = %d\n", info.usmblks);
    printf("fsmblks = %d\n", info.fsmblks);
    printf("uordblks = %d\n", info.uordblks);
    printf("fordblks = %d\n", info.fordblks);
    printf("keepcost = %d\n", info.keepcost);
}

Usage：

#include <malloc.h>
 
struct mallinfo [Data Type]
This structure type is used to return information about the dynamic memory allocator.
It contains the following members:
int arena 
    This is the total size of memory allocated with sbrk by malloc, in bytes.
int ordblks
    This is the number of chunks not in use. (The memory allocator internally gets chunks of memory from the operating system, and then carves them up to satisfy individual malloc requests; see Section 3.2.2.6 [EciencyConsiderations for malloc], page 36.)
int smblks
    This field is unused.
int hblks 
    This is the total number of chunks allocated with mmap.
int hblkhd
    This is the total size of memory allocated with mmap, in bytes.
int usmblks
    This field is unused.
int fsmblks
    This field is unused.
int uordblks
    This is the total size of memory occupied by chunks handed out by malloc.
int fordblks
    This is the total size of memory occupied by free (not in use) chunks.
int keepcost
    This is the size of the top-most releasable chunk that normally borders the end of the heap (i.e., the high end of the virtual address space''s data segment).
struct mallinfo mallinfo (void) [Function]
    This function returns information about the current dynamic memory usage in a structure of type struct mallinfo.

二：打印堆栈：

     #include <execinfo.h>

     #include <stdio.h>

     #include <stdlib.h>

     /* Obtain a backtrace and print it to stdout. */

     void print_trace (void)

     {

       void *array[10];

       size_t size;

       size_t i;

       size = backtrace (array, 10);

       printf ("Obtained %zd stack frames.\n", size);

       for (i = 0; i < size; i++)

          printf ("%ff">p \n",  array [i]);

     }

     /* A dummy function to make the backtrace more interesting. */

     void dummy_function (void)

     {

       print_trace ();

     }

     int main (void)

     {

       dummy_function ();

       return 0;

     }

三：malloc钩子函数

static void* (* old_malloc_hook) (size_t,const void *);
static void (* old_free_hook)(void *,const void *);
static void my_init_hook(void);
static void* my_malloc_hook(size_t,const void*);
static void  my_free_hook(void*,const void *);

static void my_init_hook(void)
{
    old_malloc_hook = __malloc_hook;
    old_free_hook = __free_hook;
    __malloc_hook = my_malloc_hook;
    __free_hook = my_free_hook;
}


static void* my_malloc_hook(size_t size,const void *caller)
{
    void *result;
//    print_trace();
    __malloc_hook = old_malloc_hook;
    result = malloc(size);
    old_malloc_hook = __malloc_hook;
    PHONE_DEBUG_PRINT("\n@@@ %p + %p 0x%x\n",caller,result,(unsigned long int)size);
    __malloc_hook = my_malloc_hook;

    return result;
}

static void my_free_hook(void *ptr,const void *caller)
{
    __free_hook = old_free_hook;
    free(ptr);
    old_free_hook = __free_hook;
    PHONE_DEBUG_PRINT("\n@@@ %p - %p\n",caller,ptr);
    __free_hook = my_free_hook;
}

just need call my_init_hook() at the check point.

四：check memory leak

想要跟踪的时候用mtrace。
 
停止跟踪可以使用muntrace.
 
内存泄漏检查方法(for Linux) ：

如果你更想读原始文档, 请参考glibc info的"Allocation Debugging" 
一章 (执行info libc);
glibc提供了一个检查内存泄漏的方法, 前提是你的程序使用glibc的标准函数 
分配内存(如malloc, alloc...): 

1. 在需要内存泄漏检查的代码的开始调用void mtrace(void) (在mcheck.h中 
? 有声明). mtrace为malloc等函数安装hook, 用于记录内存分配信息. 
在需要内存泄漏检查的代码的结束调用void muntrace(void). 
注意: 一般情况下不要调用muntrace, 而让程序自然结束. 因为可能有些 
释放内存代码要到muntrace之后才运行. 

2. 用debug模式编译被检查代码(-g或-ggdb) 

3. 设置环境变量MALLOC_TRACE为一文件名, 这一文件将存有内存分配信息. 

4. 运行被检查程序, 直至结束或muntrace被调用. 

5. 用mtrace命令解析内存分配Log文件($MALLOC_TRACE) 
(mtrace foo $MALLOC_TRACE, where foo is the executible name) 
如果有内存泄漏, mtrace会输出分配泄漏 
内存的代码位置,以及分配数量. 


其他东西 

1. 可以将mtrace, muntrace放入信号处理函数(USR1, USR2), 以动态地进行 
内存泄漏检查控制. 

2. mtrace是个perl代码, 如果你对符号地址与代码文本的转换感兴趣, 可以 
读一下. 

3. again, 尽量不要用muntrace()


 

$gcc -g a.c #记得编译带-g调试选项 

$export MALLOC_TRACE=a.log 
$./a.out 
$unset MALLOC_TRACE #记得执行完后unset变量,否则可能运行其他命令可能覆盖log 
$mtrace a.out a.log 
Memory not freed:
-----------------
   Address     Size     Caller
0x09b08378      0xa  at /XXX/a.c:6
0x09b08388     0x10  at /XXX/a.c:7

可以看到,会显示未释放动态空间的代码具体位置.

DFS中关于存储优化的讨论

名词解释：

1 记录：DFS不同于传统的文件系统，它要求用户存储半结构化的数据，即将要存储的数据组成多条DFS规定的记录(record)格式，以record为读写DFS的最小单位。

2 重复记录：在DFS设计的一致性协议中，由重试机制带来的一份数据可能被写入多次的情况，在读取的时候也可能读到，这就是重复记录问题，后面会有专门的文章分析一致性协议

3 chunk：DFS内部的数据存储单位，通常为256M，一个写入DFS的大文件将被拆分为多个chunk分别存储到不同的chunkserver上，多个DFS文件不会共享一个chunk

4 数据压缩：仅指BigTable写入数据前进行的压缩，因为DFS并不了解存入里面的数据特点，无法选择最优的压缩算法，因此压缩的任务干脆交给使用者

本文主要讨论分布式文件系统中的数据节点(chunkserver)在数据存储方面的优化设计。

首先分析使用模式，考虑分布式文件系统将主要用于MapReduce计算框架的输入输出和BigTable系统的底层存储。对MapReduce计算框架来说，它的应用模式比较简单，在绝大部分情况下对输入的数据都是顺序扫描读取，对输出的结果文件也是批量的顺序写入。对BigTable来说，它的应用模式稍显复杂，包括批量顺序写入(写sstable文件)，大量小记录顺序写入(写commitlog文件)，随机读取(读sstable文件)，顺序扫描(读commitlog文件)。从上面的需求分析来看，对GFS论文中提到的overwrite功能没有需求，因此可以将DFS设计为只提供追加写入(append)和按offset读取功能(pread)。而无论对于大块记录还是小块记录则都需要提供支持和优化。

下面从几个方面分别讨论可以在chunkserver实施的优化设计：

第一，记录级别的索引，前面我们提到在DFS中数据读写的最小单位是record，这意味着我们要在record级别上保证读写的原子性，即在pread的时候要么读取到至少一条完整的record，要么什么都读取不到。而在实际操作磁盘的时候对大于一个block的操作是无法保证原子性的，因此我们需要为每个chunk文件维护一个record索引，在确认完整record写磁盘成功后更新这个索引，而读取操作需要来查询这个索引，判断offset所在位置是否有写成功的record。

但是使用索引同样存在索引本身无法保证写磁盘的原子性，对此可以使用两个简单的方案来处理，第一，在chunk文件的元数据中保存索引的checksum，保证这个小于一个磁盘block的元数据能够原子的刷新到磁盘即可；第二，对于写坏的索引数据可以从数据日志中恢复，在下面提到的”数据日志”中会详细讨论。

索引要为每条record记录一个在文件内的offset，需要一个int32_t来对应一个record，record的数量因此受到限制，考虑到DFS上层的两种应用MapReduce和BigTable，MapReduce往往都以MB级别大小的record写入DFS，在绝大多数情况下可以避免小记录的写入，而BigTable在写commitlog的时候虽然也进行了批量处理，但是数据使得一次MB级别的日志变成了几百KB或几十KB。考虑极端情况下，每次只写入8K的数据，那么在256MB的容量内可以保存32K条record数据，需要32K*4B=128KB的索引空间，代价可以接受，而一旦用户写入的record数量超过32K条，那么可以视为chunk写满。

第二，chunk文件的复用，对DFS中文件的删除操作最终都将反映为chunkserver端对chunk文件的删除操作，线上应用无论是MapReduce还是BigTable每天都将有大量的文件被创建和删除，因此对大量chunk文件的删除操作将成为chunkserver端一个严重的IO瓶颈，但是仅仅通过控制删除chunk文件的速度可能又会造成磁盘空间不足的问题，因此可以对要删除的chunk文件不立即删除，而是改名到一个目录(trash)中，在需要创建新chunk的时候优先从这个目录中改名一个文件出来，使用覆盖写的方式打开这个文件。而为了能够回收磁盘空间，在chunkserver空闲的时候仍然可以慢慢的删除掉trash目录中的文件。

第三，多次磁盘的有效管理，DFS在chunkserver机器上配置了多块大容量的廉价sata硬盘，在线上大压力使用的情况下每个小时都会报出新的磁盘损坏，而修好的磁盘又会不定期的重新挂载到机器上，在linux系统已经支持磁盘热插拔的基础上，也就产生了对chunkserver不停机热插拔磁盘的需求。因此在磁盘管理模块中需要解决如下几个问题，动态加载新的磁盘，发现读写磁盘错误后卸载损坏的磁盘，宕机重启后不加载已经标记损坏的磁盘。

使用文件系统软连接可以比较容易的解决多磁盘管理的问题，在一个目录中建立软连接指向要使用磁盘的挂载点，chunkserver启动是扫描并加载这个目录中软连接指向的磁盘，并在定期扫描新加入的软连接。当读写磁盘出现错误的时候，关闭在这个磁盘上打开的文件，并将软连接改名，保证在启动和定期扫描的时候不会再次加载这个磁盘，在修好之后由人工或其他自动脚本将软连接改回为原来的名字，等待chunkserver重新加载。

第四，读写缓存和异步IO，首先再总结一下上层应用对DFS的读写模式：不区分大小的记录追加，批量的顺序扫描，随机的小记录读取。操作系统的page cache对这种简单应用模式下的IO密集型系统已经难以发挥硬件的全部性能，甚至会因为过多的内存拷贝，无意义的预读和缓存而降低系统的性能，并且无法把握的write back时机也让IO操作的响应时间无法被工程师精确控制。

因此DirectIO几乎成为必然的选择，而工程师也必须面对由此带来的内存管理，数据对齐和读写并发的复杂问题。而顺便需要解决的定长数据块校验的问题也是在使用廉价存储设备时必须面对的问题。

考虑一种简单但确实可依赖的设计思路，使用512K(或其他大小都可以)的定长内存块管理内存，每个磁盘中的chunk文件(前面提到过最大为256M)就会被映射到512个内存块中，当然是要在需要读写对应的数据时才去分配实际的物理内存；使用64K作为一个数据校验单位，这也意味着每次读写磁盘的最小单位是64K，每个1M的内存块维护8个64K数据块的状态，比如缓存，未缓存，半缓存。所有读写操作的都使用这些内存块，无论网络IO还是和磁盘IO都直接使用，避免多余的内存拷贝，因此内存淘汰和读写并发是这里面的实现难点，同时也是一个很锻炼工程师的机会。

缓存和预读，同样从需求出发，MapReduce基本上是一次扫描输入文件，不需要缓存数据，而BigTable会根据用户schema来优化的进行缓存管理，只是可能存在写成功的数据立即读取的情况，因此DFS使用上面提到512K的块管理读写所需要的内存即可。而对于MapRedue顺序扫描文件的需求，预读就成为一个行之有效的优化方法，同样可以使用一个简单的办法判断读取操作是否是MapReduce的顺序扫描，当pread发送来的size按照record的实际大小对齐的时候，可以认为是BigTable根据索引读取的请求，否则认为是MapReduce框架在不知道record大小情况的下的顺序扫描。在判断为顺序扫描的情况下，可以生成异步任务继续读取后面的数据到内存中。

异步IO，为了使有限的线程数量服务更多的读写请求，对网络和磁盘IO的异步化是一个重要的优化方向，我会在后面专门写一篇博文介绍网络和磁盘IO。而glibc的异步IO使用线程模拟，效率十分地下几乎无法使用，因此推荐一个高效的磁盘异步IO库：libaio，它使用类似epoll的事件触发接口，调用linux内核提供的异步调用，限制是必须使用directIO。

在处理读写请求时，使用上面提到的512K内存块配合异步IO使用，并进行简单的IO聚合，例如：处理写请求时，直接使用内存块接收网络数据，收到一个块后提交异步IO，等所有网络数据都传输完成后，集中等待所有的内存块的IO操作完成；处理读请求时同样以一个内存块为单位提交异步IO，聚合一个内存块的多个请求后，发起一次IO操作。

第五，数据日志，上一节提到的由于数据校验和读写都以64K为最小单位，那么由于用户每次写入的数据大小几乎都不按照64K对齐，因此基本每次写入都会产生没有按照64K对齐的数据，对于这样的数据不能立即写入磁盘和计算校验和(原因：可以考虑这种情况，多个线程共同操作一个64K内存的不同区域，那么计算的校验和不确定的)，因此对于这种不能立即写入磁盘的数据与同一个磁盘内其他chunk的数据聚合在一起写入数据日志，在意外宕机情况下回放这个日志可以恢复数据。而正常情况下，关闭chunk文件时可以保证没有其他线程在写这个chunk，可以将不对齐的数据写入磁盘。

Chunk元数据的操作，每次写操作都需要更新一次chunk的size，和前面提到的索引信息，那么每次都回写这个元数据的代价还是很大，索引对chunk元数据的更新操作同样可以记入数据日志中，chunk在正常关闭之前吧元数据刷入磁盘，否则可以在意外宕机情况下回放日志。

因此我们在以写方式打开chunk的时候需要在chunk头部回写一个dirty标志，当chunkserver启动扫描时，判断如果dirty标识被置，那么认为在回放日志时将这个chunk相关的信息回放到chunk文件中。

第六，减小bug带来的影响，在此谈两点经验，首先，任何系统操作尤其是涉及到io的操作都有可能被阻塞住不返回，因此尽量将涉及io的操作异步化可以尽量减小对模块的影响，例如rename这样的操作可以考虑由单独的线程池来处理。其次，死锁的自我监控，多线程系统中一个编码错误或系统调用阻塞都可能导致所有线程陷入等锁的状态而无法服务，虽然主线程还在不断的接受连接，而这些连接的最终的下场都是超时，影响整个系统的可用性还是比较严重的，如果能够在主线程监控工作线程池的状态，在没有线程服务的情况下拒绝连接或者主动离开分布式集群，那么在分布式系统中由此带来的对可用性的影响是相对较小的。

DFS中关于chunk一致性的讨论

在分布式文件系统中的一个设计难点就是数据写入和一致性的维护，而我们只考虑append操作而不考虑over write，在一致性语义方面采用Google在论文中提到的语义，即append成功的数据在各个副本上是确定并且严格一致的，写失败的数据在各个副本上是确定但是不严格一致（在这里我们理解“确定”的意义是保证单次写入数据的原子性，即要么读到完整的一次追加数据，要么读不到，不会读到一半的数据）。因此在这样语义的情况下不可避免的要面对重复记录的问题，即追加一次的数据可能在顺序扫描读取的时候被到多次，在一次追加失败（有的副本成功有的副本失败）的情况下，对同一份数据重试追加就会出现这样的情况，因此需要在用户层做数据的去重处理。

         使用master为每个文件记录当前的size可能会是一个避免重复记录的办法，但是由此带来的对单点master的压力将成为分布式系统聚合带宽的一个严重瓶颈。因此在这样的分布式文件系统中如何减少对单点master的依赖和压力都将成为影响系统设计的重要因素。我们的append lease机制也是基于这样的考虑而设计的。

         Lease是DFS中master对chunkserver在一段时间内针对一个chunk的授权，在这段时间内对这个chunk的修改master都不参与而是由chunkserver在多个副本之间来维护一致性。为了实现简单，在一次lease有效期内由master选择一个chunkserver作为primary，其他副本被称为secondary，primary负责lease期间副本一致性的维护。同样出于减小对master压力的考虑，一次lease的总超时时间可以设置的比较长使得API不至于因为lease过期而频繁的向master请求新lease；而为了更快的检测异常则可以使用较短的lease续订超时时间(使用较短的心跳超时虽然也可以更快的检测异常，但是可能带来较多的假下线的情况)，在lease续订成功的情况下，API仍然可以使用缓存的lease来进行追加，因为机群内同时存在的lease数有限，并且多个副本都通过primary来续订一次lease，续订lease对master压力不会很大。

         Chunk版本号由master和chunkserver为每个chunk维护，用于保证多个副本的一致和无效chunk的检查。考虑到上面提到的一致性语义，意味着一旦lease分配成功，在lease有效期内多个副本的一致已经可以保证，因此chunk version的作用就是处理副本下线上线可能带来的不一致的情况(考虑这种情况：一个副本下线后另外两个副本又写了一些数据，那么这个副本再上线后就是一个过期副本，需要能被检测出来；而如果在它下线期间另外两个副本没有写新的数据，那么它再上线时还是有效副本，不能被删除掉)。

         因此chunk version由两部分组成：一个自增长的versionID，在lease分配成功的情况下升级；一个时间戳timestamp，在lease分配成功的情况下由master更新为当前时间。

         在master端，为每个chunk保存了versionID和timestamp；在chunkserver端，记录一个全局的chunkserver启动(汇报完所有chunk)时间戳，并为每个chunk保存了versionID。

         分配的lease 时候，master将本地versionID加1后的值连同timestamp一起发送给chunkserver。Chunkserver收到后与本地versionID进行比较，如果本地versionID+1大于或等于master发来的versionID，并且启动时间小于master发来的timestamp，则接受lease，并将本地versionID加1，否则向master汇报。Master在收到所有副本接受lease的应答后，将本地versionID加1，并更新timestamp为当前时间。

         Chunkserver在接受读请求的时候，判断如果本地versionID大于或等于api带来的versionID，则接受读请求，否则拒绝并向master汇报。

         Master在接到chunkserver汇报的versionID和启动时间时，判断如果本地versionID小于或等于chunkserver汇报的versionID，并且timestamp大于chunkserver汇报的启动时间，则表示chunkserver汇报的chunk副本有效，否则要删除这个副本。

==========

修正关于timestamp的描述，上面描述的关于timestamp的协议，虽然可以避免下线又重新上线的过期副本接入机群的问题，但是凡下线过的副本再上线都会变成无效，这样的问题无法被接受。因此协议修改如下：

仍然使用timestamp配合versionID作为维护一致性的方法，在chunkserver端也要为每个chunk维护一个timestamp，在接受lease成功的情况下更新为系统当前时间，并跟随lease应答消息返回给master，master在三个副本的返回的timestamp中选择一个最小值T，将本地timestamp更新为T。

合法性检查，1，chunkserver上的versionID要大于或等于master上的versionID；2，chunkserver上的timestamp要大于或等于master上的timestamp。由于不同机器时钟存在误差，因此要求master对同一个chunk两次分配lease的间隔要大于时钟最大误差(最慢和最快之差)。

对于下线又上线的副本，通过与master对比timestamp可以确认下线这个chunk是否有成功分配lease，对于chunkserver上timestamp大于或等于master的情况，表示下线期间并没有lease分配成功，因此当前副本有限；否则表示副本数据可能已经过期需要删除。

==========

再次修正一点，master向chunkserver分发lease的时候，timestamp不是由chunkserver生成，而是由master生成当前时间发送给chunkserver，这样避免了不同机器之间时钟的误差导致的潜在风险

多参数模板偏特化

[zt] 记录一个老的面试题 百层高楼扔棋子

原帖地址 http://zgd1st.blogbus.com/logs/6143417.html

http://www.cnblogs.com/clive/archive/2009/09/14/a_question_solution_in_google_interview.html

这是一道Google的面试试题，具体来源不得而知，网上有无数解法，讽刺的是，Google自己搜到的大部分解法都是错的。3月份的《程序员》杂志刊登了这到题目，但我分析了一下，对杂志上给出的答案（起始测试层）也有疑问。这并不是什么了不得的难题吧（////），网上的答案集中在19次，18次，16次和15次，我现在找到的策略是14次。我敢说超过15次的策略一定不是最优的，那么14一 是不是最优的呢？呵呵，我们来分析一下。
    假设你从50层开始扔第一枚棋子。如果第一枚棋子碎了，你就要从第1层开始逐层试探，最坏的情况是临界层在第49层，这样你总共测试了49+1=50次；如果第一枚棋子没碎，你可以把它拿到——比如说——75层，再试，如果这次碎了，另一枚棋子就要从51层试验到74层，这样总共试验了2+（74-51+1）=26次……以此类推，总之，最坏的情况，你要试验50次。
    现在假设你从10层开始扔第一枚棋子，假如第一枚棋子没有碎，则之后每10层扔一次。跟上面相同的道理，假如临界层在第87层，总共经历了9+（87-81+1）=16次试验；最坏的情况当然是临界层在第99层，你要试验10+（99-91+1）=19次。
    显而易见，如何把大楼“分段”成为解决问题的关键。“段”分得合理，就可以让试验次数减少。那么，是让每段包含的层数均匀分布好一些，还是让投掷次数分布均匀好一些呢？如果是前者，平均分段后那么19次就是最优策略了。如果是后者，首先的解决方案是：尝试逐渐减少分段所包含的层数（否则随着第一枚棋子测试层数的累加，最坏的情况下总的投掷次数也有所增加），我们假设第一次扔棋子的层数为n，之后逐层递减，可以考虑这样一个不等式：
    n+(n-1)+(n-2)+...+2+1<=100
    也就是：
    n(n+1)/2<=100
    n^2+n<=200
    可以得到（取整数）
    n<14
    于是就有了我们的方案：从第14层开扔第一枚棋子，如果它没有破碎，则从第14+13=27层开始扔，还是没有破碎就从14+13+12=39层开始扔，以此类推；如果第一枚棋子39层破碎了，则以第二枚棋子从第28层试验到第38层，总共试验次数为3+（38-28+1）=14次。
    按照这个策略，可测试到第14+13+12+...+4=99层。假如第99层还没有破碎，那么临界层就是第100层，总共测试了11次。如果99破碎了，那么分别在第96，97，98层用第二枚棋子进行第12，13，14次投掷（第10次投掷第一枚棋子在95层），最坏的情况是98层破碎，总共试验次数也是14次。

twitter推出新版搜索引擎

Twitter搜索引擎的一大缺点在于，随着时间的推移，越来越难寻找过去的信息。截至9月中旬，用户最多还只能搜索前四天的Twitter信息。而在周三的文章中，Twitter表示，该公司的搜索引擎目前已经将这一时限延长了两倍。对此进行过测试的业内人士表示，现在的确可以搜索到7天前的Twitter信息。但是如果要查找更早的信息，则必须要借助谷歌和Topsy等搜索引擎来实现。

除此之外，Twitter还在博客文章中透露了以下重要数据：

- 每秒发送的Twitter信息达1000条；

- 每秒进行的Twitter查询达到1.2万次；

- 每天进行的Twitter查询超过10亿次(每天1,036,800,000次)。

按照上述数据计算，Twitter每月的查询达到310亿次。

值得注意的是，Twitter在对数据进行描述时，使用的是“查询”(query)而非“搜索”(search)。这是因为谷歌、雅虎和必应等常规搜索引擎的“搜索”基本都是人工进行的，而Twitter的很多“搜索”则是由客户端自动展开的，所以用“查询”更为恰当。

但业内人士认为，如果Twitter能够公布“搜索”次数，就可以更好地与主流搜索引擎进行对比。

以下为Twitter最近公布的几次月查询量数据：

- 2010年4月14日，月查询量达190亿次；

- 2010年7月6日，月查询量达240亿次；

- 2010年10月6日，月查询量达310亿次。

按照上述数据计算，Twitter查询量6个月内增长了63%。

按照comScore公布的2009年12月各大主要搜索引擎的全球搜索请求数据计算，Twitter仅次于谷歌，位列第二。具体数据如下：

- 谷歌：每月880亿次

- Twitter：每月310亿次

- 雅虎：每月94亿次

- 必应：每月41亿次

需要注意的是，谷歌、雅虎和必应都是2009年12月的搜索数据(comScore尚未公布最新数据)，而Twitter是最新的查询数据，因此并不具备完全的可比性，只能作为参考。而且谷歌有很多通过API(应用编程接口)开展的搜索，尽管Twitter也有类似的数据，但如果进行加总，谷歌的实际数据还将进一步领先Twitter。

另外，Facebook此前曾经公布，用户通过其服务发送的状态更新数量达到每秒700条，落后于Twitter每秒1000条的最新数据。但Facebook此后没有公布最新数据，因此无法对二者的现状进行对比

[扫盲] ACID

ACID，指数据 库事务正确执行的四个基本要素的缩写.包含:原子性(Atomicity）、一致性（Consistency）、隔离性（Isolation）、持久性（Durability）。一个支持事务（Transaction）的数据库系统，必需要具有这四种特性，否则在事务过程（Transaction processing）当中无法保证数据的正确性,交易过程极可能达不到交易方的要求.

原子性 整个事务中的所有操作，要么全部完成，要么全部不完成，不可能停滞在中间某个环节。事务在执行过程中发生错误，会被回滚（Rollback）到事务开始前的状态，就像这个事务从来没有执行过一样。

一致性 在事务开始之前和事务结束以后，数据库的完整性约束没有被破坏。

隔离性 两个事务的执行是互不干扰的，一个事务不可能看到其他事务运行时，中间某一时刻的数据。

持久性 在事务完成以后，该事务所对数据库所作的更改便持久的保存在数据库之中，并不会被回滚。

C++的NRV研究

1. 默认构造函数、拷贝操作符对NRV的出现没有影响

析构函数 拷贝构造函数只要定义一个就会使编译器触发NRV

2.

A foo()

{

  A xx;

  // ...

  return xx;

}

A xx = foo();

在没有NRV优化的情况下会调用一次A的default constructor，和一次bitwise的copy constructor，只产生两个对象，并不产生传说中的临时对象，这就是《深入探索C++对象模型》中描述的“返回值初始化”，需要注意是这并不是编译优化行为

3. 在直接return A()这样的情况下，不论是否定义析构函数或拷贝构造函数，都会使编译器产生类似NRV后的代码，即只有一个对象产生，这个在《深入探索C++对象模型》中被称为使用者层面的优化，但是作者也表示出了忧虑，程序员为了实现这个优化可能会将原被应该在外部执行的计算移动到构造函数中执行

4. 在侯捷翻译的《深入探索C++对象模型》的P67提到，在没有显式定义copy constructor的情况下NRV不会被触发，事实证明确实如此，原因不明确，有网友解释如下：

自己定义了copy   constructor，一般同时也重载了assignment   operator，这意味着在类本身需要深拷贝。 
也就是说，copy   constructor，和assginment   operator可能是一个相当耗费时间的操作（和简单复制相比）。 

这时候优化的效果是明显的。

如果没有定义copy   constructor，很多时候，简单的bitwise就可以进行复制工作，这个负担是很轻的。基于安全原则，调用default   copy   constructor是合理的。因为NRV优化存在着一些风险(书上提到了几种情况)。

5. 总之对于NRV要小心，对于有side-effect的对象和多线程的情况，最好通过参数传入传出，返回值用来标识错误码

CSDN上的几个讨论贴：

http://bbs.chinaunix.net/viewthread.php?tid=1076374

http://topic.csdn.net/t/20020620/22/819545.html

http://topic.csdn.net/t/20020313/17/573849.html