DevOps
tokyocabinet（简称tc） 与 kyotocabinet（简称kc） 有如下主要区别：
1. tc是用c写的，kc使用c++写的
2. kc抛弃了fixedlength database, table database
3. tc只能在类unix系统中编译，kc也支持windows
Tokyo Tyrant（简称tt） 与 Kyoto Tycoon（简称kt）的区别：
1. tt是用c写的，kt使用c++写的
2. tt不支持自动过期，kt支持自动过期
3. kt有几乎tt的所有的优点
4. kt抛弃了fixedlength database, table database
参考文档： http://fallabs.com/kyotocabinet/kyotoproducts.pdf
首先，数据结构分为逻辑结构和存储结构，这里我们也要把树的逻辑结构和存储结构分开来讲。
树的最基本的定义：
树是n（n>=0）个结点的有限集合。当n==0时，称为空树；任意一棵非空树满足以下两个条件：
- 有且只有一个特定的称为根（root）的结点；
- 当n>1时，除根结点之外的其余结点被分成m(m>0)个互不相交的有限集合T1,T2,…,Tm，其中每个集合又是一棵树，并称为这个根结点的子树（Subtree）。
显然，树的定义是递归的。
其它所有的树都是在树的基本定义的基础上添加限制条件而得到的，他们都具有不同的特点，也因此有不同的用途；
树的表示形式：
树的几种基本存储方法：
二叉树：
二叉排序树：
它或者是一个空树，或者是具有如下性质的二叉树：
- 如果它的左子树不为空，则它的左子树的所有结点的值均小于其根结点的值
- 如果它的右子树不为空，则它的左子树的所有结点的值均大于其根结点的值
- 它的左右子树也分别为二叉排序树
用途： 二叉排序树的中序遍历是一个有序序列
二叉搜索树（也叫二叉查找树）：
很多地方把二叉搜索树与二叉排序树当成一个概念； 我觉得二叉搜索树应该是一个平衡二叉树，因为只有平衡才能保证搜索的最大时间复杂度为O(logn);
对于二叉排序树，在极端情况下（如斜树），查找的最坏的时间复杂度为O(n);
B-树：
B-树是一种平衡的多路查找树； 一棵m阶的B-树或为空树，或为满足下列特性的m叉树：
B+ 树：
B+树是B-树的变型，m阶的B+树和m阶的B-树的区别是：
键树：
键树（数字查找树）：是一棵度≥2的树，树中每个结点不是包含一个或几个关键字，而是只含有组成关键字的符号。如数值中的每一位，单词中的每个字母。
还需要了解的：
红黑树、AVL(平衡二叉树）、Treap、伸展树 等。
本次学习从百度百科、百度文库中学到不少东西。
参考资料：
http://baike.baidu.com/view/593144.htm
数据结构从某种角度（我也没想明白什么角度）可以分为：逻辑结构和存储结构。
逻辑结构基本分4类：
存储结构基本分为4类：
关于稠密索引与稀疏索引：
如果一组数据元素在索引表中只对应一个索引项，则该索引称为稀疏索引；
如果每个数据元素在索引表中都有一个索引项，则该索引称为稠密索引；
参考资料：
http://www.2cto.com/database/201301/184440.html
http://blog.csdn.net/xymyeah/article/details/6407118
如果有多个进程同时对一个mdb(其它的没看，不敢随便乱说)执行list操作，结果会怎样； 或许你会显得当然地认为相互没有太大关系，至少我开始时这么认为的，但是在看源码的时候，发现有些不太对劲儿，我们先看一下源码：
tcutil.c
说明：
1. 在操作mdb的时候，需要给这个mdb加锁，显然这个mdb是一个全局的对象，而不是当前线程私有的，如果另有一个list请求，显然还是用同一个mdb对象，list时使用到了mdb的iter属性；由此看来，多个list请求应该是相互干扰的。下面做一个测试
1. 初始化一个mdb，不需要太多记录，假设200条记录吧
2. 先启动一个list进程，每取出一条记录sleep 100ms；
3. 1s后启动另一个list进程（前一个进程还没有list完成）
4. 这时，我们会发现进程1又重新获取了已经获取的记录，但不是全部，因为有部分被进程2读取了
下面是第一个进程或取的部分key:value
a4:a
a13:a
a22:a
a31:a
a39:a
a40:a
a48:a
a57:a
a66:a
a75:a
a13:a
a31:a
a40:a
a57:a
a75:a
a93:a
a112:a
a129:a
a138:a
a156:a
我们发现a13读取了两次； 第二次没有读取到a22， 是被第二个进程读取走了，然后就直接读取到了a31
————————
还有一个问题，我写入的时候是挨个按照顺序写入的，为什么list的时候有漏洞呢？或许你还发现一点，至少在一段内是从小到大的。
说明：
写入的时候，是按照不同的hash值写入到了8个map中的，而list的时候，是通过for循环8个map来list的，明白了？哦，好吧，that’s over。
tt的遍历时获取的条目数的计数器会记录到cnt_get 上面的。
我使用tokyotyrant的方式如下：
/data1/tokyotyrant/bin/ttserver -host 10.10.10.111 -port 6789 -dmn -pid /data1/tokyotyrant_data/6789/6789.pid -le -uas -thnum 16 -log /data1/tokyotyrant_data/6789/6789.log -ulog /data1/tokyotyrant_data/6789/6789.ulog -sid 6789 -mhost 10.10.10.112 -mport 7890 -rts /data1/tokyotyrant_data/6789/6789.rts *
两项统计数据如下：
[root@localhost ~]# tcrmgr inform -port 6789 10.10.10.111
record number: 10470754
file size: 2014949218
[root@localhost ~]# tcrmgr inform -port 6789 -st 10.10.10.111 | grep rss
memrss 3826147328
[root@localhost ~]#
疑问：
存储的数据占用的内存大小file size为2G； 但是物理内存占用为3.8G； 我承认程序本身会占用一部分内存，100MB了不得了吧，那么其余的1.7G都做什么用了呢？
首先，通过看源码，得知，file size是通过存储的数据计算出来的，其中包括存储数据的数据结构占用的空间和key+value占用的空间。计算方式如下：
tcutil.c
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/* Get the total size of memory used in a map object. */
uint64_t tcmapmsiz(const TCMAP *map){
assert(map);
return map->msiz + map->rnum * (sizeof(*map->first) + sizeof(tcgeneric_t)) +
map->bnum * sizeof(void *);
}
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
所以，即使没有一条记录，filesize也不会是0的； 默认的bnum为65672； 如果你的机器是32位的，则，0条记录时的filesize为： 65672 * 4 = 262688； 所以，如果你执行了vanish，发现filesize不为0 ，就不用奇怪了。
什么？ 在源码中没有找到 65672 ？ 哦，这个数字是这么来的：
tcutil.c
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#define TCMDBMNUM 8 // number of internal maps
#define TCMDBDEFBNUM 65536 // default bucket number
…
/* Create an on-memory hash database object. */
TCMDB *tcmdbnew(void){
return tcmdbnew2(TCMDBDEFBNUM);
}
/* Create an on-memory hash database with specifying the number of the buckets. */
TCMDB *tcmdbnew2(uint32_t bnum){
TCMDB *mdb;
if(bnum < 1) bnum = TCMDBDEFBNUM;
bnum = bnum / TCMDBMNUM + 17;
TCMALLOC(mdb, sizeof(*mdb));
TCMALLOC(mdb->mmtxs, sizeof(pthread_rwlock_t) * TCMDBMNUM);
TCMALLOC(mdb->imtx, sizeof(pthread_mutex_t));
TCMALLOC(mdb->maps, sizeof(TCMAP *) * TCMDBMNUM);
if(pthread_mutex_init(mdb->imtx, NULL) != 0) tcmyfatal("mutex error");
for(int i = 0; i < TCMDBMNUM; i++){
if(pthread_rwlock_init((pthread_rwlock_t *)mdb->mmtxs + i, NULL) != 0)
tcmyfatal("rwlock error");
mdb->maps = tcmapnew2(bnum);
}
mdb->iter = -1;
return mdb;
}
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
说明:
(65536 / 8 + 17 ) * 8 = 65672
关于tcmdb的实现基本都是在 tcutil.c 中的，难道说tcmdb原来是作为一个cache工具来实现的？
其它tcbdb tchdb都是定义在单独的文件中的，而tcmdb则是定义在 tcutil.h中的，而且tcmdb也完全是通过map来实现的。
官方文档针对不同类型的存储一股脑地介绍了一大堆选项，至于哪个选项适用于哪种类型的存储并不清楚（可能是我没看清楚），下面只说一下影响memory db的参数选项：
参考源码：
tcadb.c :
说明：
有三个选项影响全内存型的hash存储：
bnum: 总的bucket的数量； 注意map有8个（固定的）；8个map中共有bnum个bucket
capnum： 最大允许的记录数；
capsize： 最大允许的key-value使用的存储的大小；
下面解释一下capnum与capsize的使用逻辑：
先看一下源代码吧：
tcadb.c :
说明：
1. 如果设置了capnum或者设置了capsiz， 则使用tcmdbput3()来写入，然后判断capnum或capsiz是否超过了设置；
2. 并不是记录数超过设置立即删除，也不是超过多少删除多少； 而是记录数为0x100（即：256）的倍数时才检查，如果超过则删除，而且是删除256条记录；
3. 如果内存使用（这里说内存使用不确切，而应是key-value字节数）超过了capsiz限制，则直接删除256条记录；
4. 这里面的tcmdbput3() 和 tcmdbput() 的差别在于：
如果插入的记录是存在的，对于tcmput3()来讲，将把该条记录移动到链表的尾部，视为热数据，删除总是从链表头开始的。但是作者没有在get的时候也做这样的调整，不知道是疏忽还是另有考虑。
或许你测试发现删除的并非恰好256条记录，原因是这样的，先看源码：
tcutil.c
说明：
因为存储是分了TCMDBMNUM（8）个map来存储的，不能只删除一个map中的num个，这样太不公平了。所以平均了一下，但是可能平均的不能分完，所以每个就多删除1个； 即使这样，其实还是有问题的，因为有的map重可能不够num条记录，或者根本就没有记录；
关于从map中删除记录tcmapcutfront的说明：
tcutil.c
说明：
因为每个map下面的记录通过pre、next指针形成一个链表结构； 删除记录的时候也就从链表的头部开始删除了； 而且这种删除也是不会考虑到数据的冷热的，删除完全是一种先进先出的策略；
对于memcache来讲，内存不够用时，也是从一头儿开始删除，但是因为memcache在读取的时候会将数据调整到链表的另一头，所以memcache删除的总是最冷的数据。
在tc的memory db的实现中，获取数据时，完全可以把获取的数据调整到链表的尾部（在非全内存的btree的map中是这么实现的，见tcutil.c:tcmapget3()），这样剔除的时候就不至于把热数据给删除掉了
————————-
说句废话：
xmsiz选项对mdb是没有关系的。
mdb – memory db
mdb是cabinet的一种数据组织方式，其他还有hdb(hash)、bdb(btree)等，详见"tokyo cabinet源码分析"。
由名字可知，mdb使用纯内存(不一定，见下面)，速度最快。它是后面其他较高级的数据组织方式的基础，hdb、bdb的read cache都是直接使用mdb实现。而且mdb的实现最简单，所以先从mdb分析。
先贴出mdb结构图片：
也有画做下图的：
个人觉得下图不如上图容易理解； 第一次看下图的时候，还以为hash冲突是用链表来解决的，仔细观察下图的第三对key、value，后面连接了两对key、value； 其实不是画错了，而是说明这里的结构是二叉搜索树，而非链表
Tokyocabinet的MAP存储的记录的存储结构体为：
typedef struct _TCMAPREC { /* type of structure for an element of a map */
int32_t ksiz; /* size of the region of the key */
int32_t vsiz; /* size of the region of the value */
struct _TCMAPREC *left; /* pointer to the left child */
struct _TCMAPREC *right; /* pointer to the right child */
struct _TCMAPREC *prev; /* pointer to the previous element */
struct _TCMAPREC *next; /* pointer to the next element */
} TCMAPREC;
该结构体有些特殊，一般我们看到的存储的结构体是有数据指针的，但是这里只有上下左右节点的指针和key、value的大小，却没有数据指针，作何解释呢？
原来是这样的：
大概是为了少malloc一次内存，于是在添加一条记录的时候，直接把存储结构体的内存和key、value的内存一并申请了： TCREALLOC(rec, rec, sizeof(*rec) + ksiz + psiz + vsiz + 1);
这样data的起始地址其实就是 rec + sizeof(*rec) 了。
参考资料：
http://topic.xhttp.cn/view/100/
http://hi.baidu.com/sing520/blog/item/60a29bcbaac3b0f352664ffa.html
http://hi.baidu.com/sing520/blog/item/60453c9787a5296355fb96b6.html
http://gavin.iteye.com/blog/553948
使用sed做目录替换：
echo "/data1/apache1/file1" | sed "s#/data1/apache1/#/data1/apache2#"
使用 #做定界符，就不需要转义了，当然你也可以使用 | 做定界符
如果输出的参数是写在执行命令的结尾的，则：
echo f1 f2 f3| xargs -n 1 ls
如果要将文件重命名，则：
echo f1 f2 f3| xargs -i -n 1 mv {} {}.bak
或者：
echo f1 f2 f3| xargs -ixx -n 1 mv xx xx.bak
-i 的默认值为 {} ; 所以如果不用默认值，必须挨着写，和i之间不能有空格， 即 -ixx 不能 -i xx
======================
在所有的php文件中找某字符串theString ：
find . -name "*.php" | xargs -n 1 -i grep theString {}
当系统swap空间所剩不多时，可通过在本地磁盘上创建普通文件作为swap，步骤如下：
$ dd if=/dev/zero of=./swapfile bs=1M count=1000
$ mkswap ./swapfile
$ swapon ./swapfile
即可为系统临时增加1G的swap。
使用完毕后执行：
$ swapoff ./swapfile
$ rm -f swapfile