DongHao: 10 2008存档

      看了介绍Dynamo的论文，虽然英文不济，理解可能有误，但还是交流一下学习心得。Dynamo是亚马逊的key-value模式的存储平台，可用性和扩展性都很好，性能也不错：读写访问中99.9%的响应时间都在300ms内。

数据划分
      按分布式系统常用的哈希算法切分数据，分放在不同的node上。Read操作时，也是根 据key的哈希值寻找对应的node。Dynamo使用了Consistent Hashing算法【参考 http://tech.idv2.com/2008/07/24/memcached-004/】，node对应的不再是一个确定的hash值，而是一 个hash值范围，key的hash值落在这个范围内，则顺时针沿ring找，碰到的第一个node即为所需。
      Dynamo对Consistent Hashing算法的改进在于：它放在环上作为一个node的是一组机器（而不是memcached把一台机器作为node），这一组机器是通过同步机制保证数据一致的。
以上图为例，node1其实包含了多台机器，在一个node里宕了一台机或增加一台机，并不影响整个Dynamo对key的寻找。
      如果一个ring内的访问量大了，则可以在两个node间加入一个新node以缓解压力，这时会影响到其后继node的hash范围，需要调整数据。假设一 个ring中原本只有node2、node3、node4，在加入新的node1之后，原先从node2查询的部分key将改为从node1查 询，node1和node2中的数据就需要调整，主要是node1从node2中提取出属于它的数据，这样做需要选取性能压力不高的时候。（至于具体的调 整方法，从论文中没找到 -_-b）

数据同步
      Dynamo的一个node中的同步是由client端来“解决”的，使用所谓的（N, R, W）模型，其中，N表示node中机器的总数，R表示一个读请求需要的机器参与总数，W代表一个写请求需要的机器参与总数，这些值由client端配置。
      例如，一个node有5台机器（N=5），client发出写请求——广播到5台机，如果收到3个“写完成”的返回消息，即认为写成功 （W=3）；client发出读请求——还是广播到5台机，如果收到2个“读完成”的返回消息，即认为读成功（R=2）。对于数据十分重要的应用（如金融），配置可以为(5, 5, 5)，即要求node中所有机器的写都成功；而对于数据读写访问量极高的应用，配置可以为（5, 1, 1）。
      通常W不等于N，于是，在某些情况下一个node内的机器上的数据可能会有不一致，这时Dynamo是通过将多个Read的返回结果“合并”来得出最终结果 的，使用了所谓Object Version和Vector clock的技术，即跟踪一个Object在不同机器上的版本变化，以确保当多个Read请求结果返回不一致时，能够更具其版本信息得出正确的结果。 Dynamo的这种做法是一种折衷，即为了同时保证读和写的效率，写操作不要求绝对同步，而把不同步可能产生的后果推给了读操作。

数据恢复
      Dynamo的一个node中一台机器建有一个Merkle Tree，当两台机器不一致时（如一台机器宕机一段时间），通过这个tree结构，可以快速定位不一致的Object来恢复数据。Merkle Tree又叫Hash Tree，它把key分成几个range，每个range算出一个hash值，作为叶子，再一层层合并计算上去，这样，从root开始比较hash值，就可以快速找到哪几段range中的hash值变化了。

      个人感觉Dynamo的同步策略有点别扭，读采用广播，怎么保证读的效率呢？当然，也许人家有高招。

      程序出现了coredump，用gdb发现了出错的地方。

vector<size_t> seq_offset;
......
if(seq_id < seq_offset.size())
{
    seq_offset[seq_id];        //此处coredump
}

      没有超过vector的大小，访问是不应该有问题的，而且这一现象是偶然出现，所以怀疑是多线程的原因。果然在另一个线程里发现对seq_offset有 insert操作，insert本身不会影响访问，但是当vector大小不够的时候，insert会引发内存重新分配。STL代码(linux gcc-3.4.3 /usr/include/c++/3.4.3/bits)里，vector的insert会调用_M_fill_insert，而当空间不够时 _M_fill_insert会重新分配空间，并将相关数据结构指向新空间。

文件 vector.tcc
324        std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish);        //销毁vector里的元素，即调用各元素的析构函数
325         _M_deallocate(this->_M_impl._M_start,                                           //收回存放各元素的空间，即free
326               this->_M_impl._M_end_of_storage - this->_M_impl._M_start);       
327         this->_M_impl._M_start = __new_start.base();                                //数据结构指向新的空间
328         this->_M_impl._M_finish = __new_finish.base();             
329         this->_M_impl._M_end_of_storage = __new_start.base() + __len;

      麻烦就在于当326行结束后，_M_start指向的是一块已经释放了的空间，这时候再有vector的访问操作（如 seq_offset[seq_id]）当然就会coredump。其实STL完全可以先把_M_start赋给一个临时变量，然后_M_start指向 新空间，最后再释放临时变量指向的空间，这样可以保证在多线程下顺利运行。不过STL文档说了——它不支持多线程——所以这样做也没错。
      加锁也可以解决这个问题，不过那样太低效了，不予考虑。最后的解决方案是，用vector的reserve方法预先分配好内存，免得在使用中动态增长。

      十一在花市看到有一小株一小株的珍珠菠萝（这是姑公告诉我的名字，今天才知道应该叫珍珠芦荟，不过姑且这么叫吧）卖，跟当年姑公送给我的那盆简直一模一 样，看着十分亲切，忍不住买了一小株。上周五家里又寄来了三小株吊兰，想想以前在老家还觉得这东西太普通都没在意过，而现在那一点嫩绿在这北方苦寒之地都 显得那么难得。阳台都快成花园了。我不是在种植物，我是在寻味飘散的回忆。
      古希腊哲人说每颗树都是一个神明，确实，看着哪怕是一颗拳头大小的榕树，也让我觉得平静、觉得高兴，如果不是神，又怎会如此？

      看到代码里有
      printf("%.*s", msgLen, msg)
      觉得奇怪，还以为是笔误，查了查资料，才知道有 %.*s 这种用法：即在字符串指针前再跟上想打印的长度参数。
      const char* msg="hello,world";
      printf("%.*s", 3, msg);                   //输出： hel
      printf("%.*s", 6, msg);                   //输出： hello,


      启动程序的时候发现一个日志都不输出，什么都不执行，但ps可以看到进程，strace跟一下才发现程序在open一个有名管道（fifo）的时候停住了。原来有名管道如果没有读的一方，open是阻塞的，详细规则如下：
      “如果同时用读写方式(O_RDWR)方式打开，则不会引起阻塞。
      如果用只读方式(O_RDONLY)方式打开，则open()会阻塞一直到有写方打开管道， 除非你指定了O_NONBLOCK，来保证打开成功。
      同样以写方式(O_WRONLY)打开也会阻塞到有读方打开的管道，不同的是如果O_NONBLOCK被指定open()会以失败告终。 ”


      程序一直运行正常，突然不转了，再重启也不行，十分怪异：如果是程序有问题，为何先前能运行？如果程序没问题，为什么现在又不能启动了？后来才发现是日志写到2G大小了，重启也写不进日志。linux下2G的文件大小限制，可以在编译时加参数来解决：
      gcc -D_FILE_OFFSET_BITS=64

夏辉： 小钢炮收到个包裹咧，是什么？

haodong： 是刮胡刀，而且是三刀片的

夏辉： 为什么用三刀片的？

haodong： 因为....只有最man的男人才用三刀片的

小钢炮： 什么叫man？


第二天


董昊： 程xx是新来的吗？

夏辉： 是的，算法组的

董昊： 男的女的？

夏辉： 男的，而且是很man的那种

董昊： 哼，有小钢炮man吗？

夏辉： 应该还是没有小钢炮man....

小钢炮： 你们！

      有几台机器用SecureCRT登录上去以后，每隔大概5分钟左右就会断开连接，很麻烦。发现这个好像不能通过修改服务端的配置解决，只好配SecureCRT了，好在也很简单：

      每隔60秒发一个“无操作”消息，服务端就不会断开连接了。

      十一期间看了倪金刚写的《CFM56方程》，还有点意思。
      法国人在战后建立了独立的航空工业，包括达索飞机制造公司（产品：“超军旗”战斗机、“幻影”系列）和斯奈克玛航空发动机公司，毫无疑问，所有的军用发动 机都由斯奈克玛这家“国企”生产。上世纪70年代初，斯奈克玛开始图谋民用发动机市场，在被普.惠公司拒绝后，和通用电气公司（GE）开始了合作。先是按 照GE提供的图纸生产，后来在法美两国总统的帮助下，斯奈克玛和GE开始合作研发F101发动机（用于美国B1轰炸机），不过，核心机（高压压气机、高压 涡轮等）技术还是在GE手里，斯奈克玛只是负责风扇、低压压气机、低压涡轮、附件机匣等，不过跟超级大国合作，能从军用发动机研发中分一杯羹，已经非常不 容易了。由于以上合作都较为愉快，斯奈克玛和GE合资建立了CFM国际公司（因为GE发动机的编号是字母“CF”开头，而斯奈克玛的是“M”开头，所以合 起来），两家各占一半股份，70年代中期，著名的民用航空发动机CFM56终于问世。30年过去了，全部新型波音737和空客A340、60%的A320 都装配的是CFM56。
      书里的故事讲得确实有趣，但对专业知识涉及较少，航空爱好者可以借来看看（别买，与内容相比，感觉太贵），书中本来是想以这两家公司为范例，讲讲商业合作 和谈判的技巧，但我看完书还是不知道斯奈克玛和GE的合作妙在哪里，觉得它们的合作也没啥稀奇，两家对自己的技术都是高度保密的，无法从对方那里学到高级 技术，说白了就是“强强拼合”，而不是“强强融合”。生产的时候你负责你的、我负责我的，最后按接口规范把组件拼在一块儿，一个产品就完成了。最终造成CFM56成功的是两家的“硬实力”，而不是什么商业技巧。话说远一点，那么多讲MBA、讲商战案例的书，读完了你也不会觉得有什么启发，感觉学成一样的 模式容易，做到一样的成功就难了。书本和现实之间还是隔很远的。

      struct ThreadParam
      {
        bool  *exit;
        ......
      };
     
      ......

      ThreadParam my;
      my.exit = false;

      pthread_create(thread, NULL, threadProc, &my);

      ......

      void threadProc(void* p)
      {
        ThreadParam *param = (ThreadParam*)p;
        if(param->exit)
        {
        ......

      昨天的一段程序，却发现param->exit的判断总是成功，心想怪了：我赋值为false了啊，难道my析构了？调了半天才发现是 if 判断的问题，应该判断bool的指 *(param->exit) ，判断 param->exit 就成了判断指针是否为空了（当然不为空了）！
      以前听过有人建议所有对bool量的判断应该用 if(param->exit == true) ，这样虽然麻烦，倒是可以通过编译器的类型检查提早发现上面的问题。