软件开发: 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
有几台机器用SecureCRT登录上去以后，每隔大概5分钟左右就会断开连接，很麻烦。发现这个好像不能通过修改服务端的配置解决，只好配SecureCRT了，好在也很简单：
每隔60秒发一个“无操作”消息，服务端就不会断开连接了。
每隔60秒发一个“无操作”消息，服务端就不会断开连接了。
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) ，这样虽然麻烦，倒是可以通过编译器的类型检查提早发现上面的问题。
