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的同步策略有点别扭，读采用广播，怎么保证读的效率呢？当然，也许人家有高招。
数据划分
按分布式系统常用的哈希算法切分数据，分放在不同的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方法预先分配好内存，免得在使用中动态增长。
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
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....
小钢炮： 你们！
haodong： 是刮胡刀，而且是三刀片的
夏辉： 为什么用三刀片的？
haodong： 因为....只有最man的男人才用三刀片的
小钢炮： 什么叫man？
第二天
董昊： 程xx是新来的吗？
夏辉： 是的，算法组的
董昊： 男的女的？
夏辉： 男的，而且是很man的那种
董昊： 哼，有小钢炮man吗？
夏辉： 应该还是没有小钢炮man....
小钢炮： 你们！
有几台机器用SecureCRT登录上去以后，每隔大概5分钟左右就会断开连接，很麻烦。发现这个好像不能通过修改服务端的配置解决，只好配SecureCRT了，好在也很简单：
每隔60秒发一个“无操作”消息，服务端就不会断开连接了。
每隔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) ，这样虽然麻烦，倒是可以通过编译器的类型检查提早发现上面的问题。
{
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) ，这样虽然麻烦，倒是可以通过编译器的类型检查提早发现上面的问题。
