仔细看了一下 Hadoop.MapReduce 的代码，发现了两个新类：MultipleInputs/MultipleOutpus，再仔细看它们的详细文档，的确实现了我想要的功能： 继续阅读 →

 

 

以前的这篇文章介绍了嵌入的变长数据结构（embeded）

 

本文介绍一个使用这种思想实现的通用strmap容器，相当于：

std::map<std::string, Mapped>。

 

实现上使用了我以前写的线索红黑树——相比标准map的实现，节省了一半的结点存储开销，而平均查找时间只付出很小的额外开销，并且没有代码膨胀问题。

 

使用

大多数情况下

trbstrmap<MappedType[, Compare]> // Compare是可选的，allocator 总在类范围，可以修改:

trbstrmap<MappedType[, Compare]>::s_vtab.alloc = ….;

 

为了节省空间，trbstrmap使用一个字节存储strkey_length，因此，strlen(strkey)不可超过255，允许长度为0的key。最大长度255基本上可以应对绝大多数情况。

把key作为变长字段，有一个原因很重要：key一旦插入，就不可改变！因此，整个结点的memblock也就不需要重新分配，可以修改的只有mapped_data。

作为一个比较：如果把key作为一个固定长度的结构，而mapped_data作为变长内嵌数据，当需要修改mapped_data时，就需要重新分配该结点，还需要修改该结点的父节点指向该结点的指针，并且，会破坏“node容器的iterator只有在删除该node以后才失效”的语义！

一旦用在多线程环境中，问题就会变得很复杂，因为修改了父节点。就不能仅lock需要修改数据的那个结点，而是需要lock整个tree，使用数据库的术语，就是一下子从记录锁变成了表锁，本来按key查找时，因为key没改变，就不需要加锁，而这样搞，查找时就需要对整个表加锁，严重影响并发性！

注意事项：

1.         trbstrmap::iterator::value_type 和trbstrmap::value_type都是 mapped_type/Value，*iter也是mapped_type；而不是std::map的pair<Key,Value>。

2.         trbstrmap::key(iter)获得iter对应的key

3.         trbstrmap::klen(iter)获得key_length，当然，strlen(trbstrmap::key(iter))也可以获得key_length，但需要一些时间开销；另外，当key_content中存在/0时，klen就是不可缺少的了（后面将详细介绍这种情况）

4.         再次强调，key_cstr_length最大长度不可超过255，但这个长度不包括末尾的 /0

 

示例代码：

         typedef febird::trbstrmap<int, &trb_compare_tev_inline_cstr_nocase> smap_t;

         smap_t smap, smap2;

 

         smap[“1”] = 0;

         smap[“2”] = 1;

         smap[“3”] = 1;

         smap[“4”] = 2;

         smap[“1”]++;

         smap[“4”] += 2;

         smap.insert(“5”, 5);

         assert(!smap.insert(“5”, 6).second);

         // str长度不可超过255

         smap[“aabbccddeeffgghhiijjkk=====================================”] = 10;

 

         for (typename SMT::iterator i = smap.begin(); i != smap.end(); ++i)

         {

                   printf(“smap[%s]=%d, klen=%d/n”, smap_t::key(i), *i, smap_t::klen(i));

         }

 

数据结构

Mapped Data 是模板参数，可以是任意struct/class，当然也可以内嵌指针，也可以是复杂对象，没有任何限制。

 

 

复杂情形：任意字符串，字符串中可以包含/0

trbstrmap允许加入内容中存在/0的字符串，这种应用比较罕见，但是仍然允许，只是必须遵循以下注意事项：

1.         在这种情况下，需要传入key_content_length参数：
trbstrmap.probe(key,key_content_length)
trbstrmap.insert(key,key_content_length, val)
key_content_length是整个key_content长度，包括末尾的/0——如果有的话

2.         或者，传入std::string ：
trbstrmap[std::string(…)] = val;
equal to: trbstrmap.probe(s.c_str(), s.size()+1) = val;

3.         trbstrmap.insert(key, klen, val)

4.         这种情况下，应用一般需要传入一个自定义的Compare

5.         trbstrmap::klen(iter)在任何情况下，返回的都是key_content_length – 1，
而不管末尾有没有/0

6.         自定义函数需要获取key_content_length时，应该如下：

int

trb_compare_custom ( const struct trb_vtab* TRB_restrict vtab,

                                          const struct trb_tree* TRB_restrict tree,

                                          const void* TRB_restrict x,

                                          const void* TRB_restrict y)

{

     size_t lx = ((unsigned char*)x)[-1] + 1;

     size_t ly = ((unsigned char*)y)[-1] + 1;

int ret = memcmp(x, y, lx<ly?lx:ly); // 仅示例，不一定非用memcmp

     return 0 == ret ? lx – ly : ret;

}

7.         当给trbstrmap::find/lower_bound/equal_range多传入一个key_content_length时，这些函数会将key和key_content_length打包（这些都在库内部完成），应用须知这会有稍微多一些的开销。

必须这么做，因为compare函数需要找到key_content_length，除此之外，别无他法。

8.         貌似很复杂，但始终坚持剃刀原理：在绝大多数情况下，也就是字符串是cstr，末尾包含/0时，函数的行为符合传统惯例并且高效；在罕见情况下也可用，只是效率有一点下降，使用难度也大一些。

9.         当情况复杂时，记住：只要你明确传入了长度，这个长度就是你真实数据的长度

本文假定读者已了解MapReduce。

先说 Map

Map阶段一般做三件事情：

继续阅读 →

符号、记法

其中{k,v}指一个Key,Value对，{..} 中第一个分量是Key，第二个是Value。

[e]指一个集合，其中的元素为e。 [{k,v}]就指一个{k,v}的集合。

继续阅读 →

mpool.h

 

 

mpool.c

 

  

memory pool

malloc可以分配任意大小的内存，因此，在malloc内部，保存了一些簿记信息（至少有一个包含内存块尺寸的信息）。调用free时，可以正确释放。

为了减少这些簿记开销，可以使用memory pool。

根据使用情境，可以分为两种：

1.         只分配固定大小的内存块，速度最快（normal path约10条机器指令）。

2.         可分配不同大小的内存块，速度稍慢，但比malloc快得多，也无簿记开销。

以下将分别说明

mpool

mpool可分配不同尺寸的内存。大多数时刻，都在内部分配。

销毁mpool时，会自动释放在mpool中未释放的内存。

mpool内部有一个包含多个不同尺寸fixed_mpool的array，根据请求分配的内存大小，直接索引到相应的fixed_mpool来分配一个单元（cell）。

通过定义宏FEBIRD_MPOOL_ALLOW_BIG_BLOCK，就允许大于max_cell_size的内存分配。在这种情况下，使用标准的malloc分配内存，分配出去的内存有额外簿记（用双向链表串起来），以便在销毁mpool时自动释放。 

 

 fixed_mpool

尺寸固定的内存池，一旦创建，该内存池只能分配固定尺寸的内存单元（cell）。这在很多情况下都适用，例如链表结点、树节点、图结点、自定义的结构、等等。

用于stl的map/set/list再适合不过了——但是不能用于vector/deque等需要分配可变尺寸的容器。

fixed_mpool内部的多个chunk使用数组，类似std::vector，iNextChunk相当于vector.size，nChunks相当于vector.capacity，每次空间不够时扩张一倍。使用数组，而不是链表，有以下好处：

1.         有助于对齐——如果chunk_allocator是对齐（对齐>=32时）分配的，而chunk使用链表组织，就会在chunk开始处预留一个chunk头部，这会导致不对齐。

2.         如果cell_size也刚好较大且整除chunk_size，使用链表就会浪费将近一个cell（cell_size – chunk_header_size）。

3.         如果不把连接信息保存在chunk header，就需要另外分配chunk结点，而分配chunk结点又需要其它内存分配函数。

空闲表使用单链表，因此，理论上每个cell最小必须能容纳一个指针，32位系统式4字节，64位系统式8字节，实现中使用8字节作为最小值。 

别说是JavaVM！

正确答案：x86vm

x86本身是一个硬件vm，它的指令系统是一个vm指令系统，通过翻译层后，才交给下面的risk内核。

 

一般的malloc实现，对一块已分配的内存，都有两个机器字的簿记，甚至更多。如果不需要排错，理论上讲，只需要一个字长的额外开销，用来记录这块内存的尺寸（放在intptr[-1]处是个好主意）。

为什么需要这个开销呢？因为free传入的只是个指针，它不知道要释放多大的内存，因此free内部必须通过某种方式来获得这块内存的尺寸。

可以想象，如果用 malloc/free 来作为一个关联数组（map）的分配器，要浪费不少内存。不过好在实际数据的尺寸往往比额外消耗要大很多，相比起来，浪费的比例不算很大，况且现在内存还很便宜。

其实，打造一个高效的分配器并不难，难的是它的适用范围（多线程？cell尺寸，chunk尺寸，对齐，排错…），如果可以忍受这些缺陷，或者说是限制，还是比较值得的。下一步就是它的灵活性——让它可以更加容易集成进其它系统。

对于C标准库，如果能增加一个/一族这样的分配器，还是很有价值的。从理论上讲，只要free时多传一个size参数，就可以完全去掉额外的开销。这样两个函数就可以做到：

这样做还有一个额外的好处，就是可以更好地对齐，假定程序需要按32字节对齐，malloc/free 就至少需要32字节做簿记，如果再加上内存越界检测，就需要64字节。salloc/sfree则只需要将分配的内存对齐到32字节边界即可。

 

但是这对程序的正确性要求很高，malloc/free中，内存越界检测可以很容易实现，而salloc/sfree就完全做不到（除非增加额外簿记）。一个好主意是可以在debug版中加入这些差错功能，而在release版中去掉。

 

更好（确切地讲应该是更灵活）的方案是，实现一个

 

而让 salloc/sfree简单地作为 mpool 的包装。

 

gcc的std::allocator基本上是按这样的方式实现的，只不过，它的size参数，大多数时刻是自动传递的（知道具体的class/struct，也就知道它的尺寸）。实现方式上，使用 size_aligned/align 作为索引去访问特定尺寸的mempool，一个 mempool 是多个链表串起来的大chunk，每个chunk内部是链表穿起来的cell。这也许是最好的实现方式了，除了节省的额外空间开销，时间开销上，如果不考虑加锁，一次alloc平均可以在10时钟周期内完成，dealloc用的时间更短。相比之下malloc/free耗的时间也要多得多。

固定长度的数据结构很简单，大家每天都在用。

可变长度数据结构，都可以通过内嵌对象的形式，转化成固定长度的数据结构，大家每天也都在用，例如：

 

每个 person 对象的长度是固定的，但是，其内嵌的 name 和 address 是变长的。从而，整个对象占据的总空间也是变长的。

 

但是，将这样的的对象平坦化，使之只占据一块连续空间，使用的人很少，因为在绝大多数情况下，很少有人思考这个问题，并且，大多数问题已经使用内嵌数据结构解决掉了。

 

然而，如果内存很紧张，或者需要处理得数据量非常大，这种方式浪费的内存就太多了。假定我们现在创建了一个 map<int, person> ，在gcc4.1 的 64位环境中，按8字节对齐，这个 map 总共会占用多少内存呢？

1. sizeof(map) = 48
2. sizeof(string) = 8
3. sizeof(person) = 24
4. sizeof(person_node) = alignto(24 + 32(rbtree node overhead), 8) = 56
5. sizeof(string_node) = 8*3(refcount, size_endptr, capacity_endptr)
6. memsizeof(string) = sizeof(string_node) + alignto(strlen + 1, 8)
7. memsizeof(person_node) = sizeof(person_node) + memsizeof(name) + memsizeof(address)

如果 avg(name) = 10, avg(address) = 20

实际占用的空间，大约还要再加上4：avg(name) = 14, avg(address) = 24

那么 memsizeof(person_node) = 56 + 24*2 + 14 + 24 = 142

那么该map 实际占用空间（gcc 的每个 map 还有一个虚结点:32个字节）：

48+32+n*142 = 80+n*142

 

如果使用一种理想的变长数据结构，再加上红黑树的优化(none virtual node, compressed color, no parentptr)，需要多少内存呢？

1. sizeof(map) = 16
2. memsizeof(person_node) = alignto(16(treenode) + 4(id) + 2*1(strlen) + 10(name) + 20(address) = 52, 8) = 56

memsizeof(map) = 16 + 56*n

 

内存一下节省了 60% 还多，也就是说，如果内存大小已经固定，可以装入 2.5 倍的数据。

1. 如果用来做集群缓存，可以节省50%的机器（系统也要占一些内存）。
2. 如果有5.6G的内存可用，就可以装入1亿条数据。
3. 并且，在节省了60%内存的同时，还有另外一种好处：提高cache命中率，如果3个字段访问的频率相同，cpu的 cache miss 会降低3倍。
4. 可以预见，因为cache miss降低，map.find 速度会大幅提高。

 

这个可变数据结构可以这样设计：

 

 

更复杂的情况：

1. 如果nName 和 nAddress 要大于 255 呢？——把 unsigned char 改成 unsigned short, 甚至 unsigned int
2. 如果person的字段很多，例如有20个字段：

 

这就不光是写代码的复杂了，运行时字段访问的性能也成问题！性能问题可以用另外一种方式——使用直接定位——来解决。

 

 

如果需要变长数据的数组，怎么办？简单，offset array + data byte array，具体实现方式与 person4 类似，只不过 offset array 元素需要使用更宽的整数。

 

 

一直在想：如何在 Hadoop.MapReduce 中，插入一个 C 写的 HashFunction，既要高效，又要接口简洁。通过命令行实现调用显然是不行的。刚刚终于想出了：使用管道！

一个非常简单的程序，从stdin读入，写到stdout。多简单！至于效率，管道嘛，本质上就是异步的，自然是buffered&asynchronous 模式。

 

hash 程序

 

 

框架可以一边不断往管道写key，一边从中读取结果，这两个工作完全可以是异步的。对hash程序来说，如果stdin/stdout是全缓冲的，就几乎没有io的开销，因为几百几千次 fgets/printf 才会导致一次系统调用。

对frame程序也是一样的。

 

在 hadoop.streaming 中，hash 函数目前还必须由 java 类指定，如果使用这种方式，那就更 unix 了。