原文档见：http://gitlab.alibaba-inc.com/middleware/coding4fun-3rd/blob/master/observer.hany/design.md
- 淘宝中间件第三期编程比赛，题意概述：读入一个文件，统计其中最常出现的前 10 个单词。
系统设计
- 按照题意，可设计如下简单拓扑图。
- 图中
方块表示计算节点，箭头表示数据流动。
注意： Counter 和 Selector 之间需要设置一道栅栏 ，所有单词统计完毕后才能开始筛选单词。
优化1：同步 OR 异步
-
Reader 是 IO 集中型操作，其他计算节点都是 CPU 集中型操作。
如果先读完文件再操作，读文件的这段时间 CPU 就白白空闲着浪费掉了。 -
简单的优化就是异步读文件。
增加一个后台 Task 线程，Reader 每读取一小块文件数据(Chunk)，
就交给 Task 线程处理，Reader 继续读下一个 Chunk 的时候，Task 已经跑起来了，
一个占用 IO，一个占用 CPU，充分利用计算机资源。
- 通过异步读文件，Reader 和 Task 能够并发处理数据，提高性能。
实现细节
-
ChunkedTextReader 实现按 Chunk 分块读文件。
为了避免 Chunk 边界意外将一个单词拆成两半，
除最后一个 Chunk 外，每个 Chunk 都将末尾的最后一个单词切开，
拼接到下一个 Chunk 的前面，让下一个 Chunk 处理。 - Reader 和 Task 之间通过 BlockingQueue 传输数据，
这是一个线程安全的 "生产者-消费者" 队列。 - 经测试，Chunk 分块太小队列操作过于频繁，性能下降。
分块太大读文件阻塞太久，达不到异步读的目的，
因此默认限制 Chunk 最小 1MB，最大 8MB。
优化2：并发 OR 并发
- 读文件的速度比处理文件的速度快的多，一个线程 CPU 跑到 100% 也是远远处理不过来。
测试机有 16 个核，可创建多个并发的 Task 线程，将每个核都利用起来。
由于 Task 是高度 CPU 密集型操作，默认取 Task 线程数等于 CPU 核数。
- 栅栏控制所有数据处理完成才能开始按词频选择单词。
实现细节
-
ConcurrentBlockingQueueExecutor 管理所有 Task 线程，
executor 在每个线程上等待线程结束，实现栅栏同步。 - ConcurrentBlockingQueueTask 实现 Task 线程处理流程。
- Reader 读完文件后在 executor 上设置 done 标识位，
Task 发现 queue 为空且 executor 设置了 done 标志位，
则说明文件已经读完并处理完，task 结束。 - ConcurrentTrieNode 实现了线程安全的 Trie 树。
语言细节
- 在 Java 实现中，
ConcurrentBlockingQueueTask 和
ConcurrentBlockingQueueExecutor 互相依赖，
但 C++ 不能处理互相依赖，
所以将 task 对 executor 的依赖剥离到
ConcurrentBlockingQueueExecutorSupport 中，
避免互相依赖的问题。
C++程序员通常使用前置声明、分离实现等办法解决互相依赖问题。 - 程序先用 Java 设计开发完成，再逐个类翻译成 C++。
编码尽量遵守 Java 约定，
每个类放到独立的文件，方法实现直接写在头文件的类声明中，".cpp" 文件基本都是空的。
排除 ".cpp" 文件，文件数量就少一半了，嘿嘿~~
简单场景还能用 C++ 模拟一下Java，复杂场景就只能用 Java 了。
优化3：双保险模式避免加锁
- DANGEROUS双保险模式已经被证明是不可靠的，禁止在生产代码中使用。
- UPDATE@齐楠 @宏江 指出, jdk 1.5 之后加上 volatile 关键字双保险模式是可用的。早期版本不行。
ConcurrentTrieNode* getChild(char c) {
int const index = c - 'a';
if (children[index] == NULL) {
synchronized: {
Locker locker(childrenLock);
if (children[index] == NULL) {
children[index] = (ConcurrentTrieNode*) calloc(1, sizeof(ConcurrentTrieNode));
}
}
}
return children[index];
}
语言细节
-
ConcurrentTrieNode 是一个简单 struct， 不包含虚函数和复杂对象字段，
其构造函数只是简单地将所有字段(包括Lock)初始化为 0。
使用calloc(1, sizeof(ConcurrentTrieNode))直接分配一块 0 初始化的内存，
calloc 返回内存地址时，已经得到一个合法初始化的 ConcurrentTrieNode 对象，
而不必调用构造函数。
优化4: 原子操作避免加锁
- 并发统计 count 时，将 count 字段声明为 volatile()，
/** * Word 出现的次数. */ volatile int count;
- 使用原子操作实现线程安全并避免加锁()，提高性能。
// atomic_inc
__asm__ __volatile__(
"lock ; " "incl %0"
:"=m" (node->count)
:"m" (node->count));
优化5：统计单词结束后再过滤排除单词
- 程序要求排除一些单词，在统计前排除，每个分词都要判断一次。
统计结束再排除，相同单词已经合并，减少判断，性能更高。
总结
-
优化过程中曾想过各种方案，
比如并发 merge sort 排序再处理，每线程一个 Map 最后再合并等，
结果发现使用 ConcurrentHashMap 不但编程复杂度明显简单，性能还更加理想。
再一次证明， 最简单的方案往往就是最好的方案 ，
不仅从开发维护的角度来看，有时从性能角度来看也是这样。
Java 的 ConcurrentHashMap 性能相当赞，并发环境首选啊。 -
程序开始是用 Java ConcurrentHashMap 实现的。
为了提升性能翻译成 C++，过程可谓大费周折，相当痛苦，我会告诉你我大半夜还在调segmental fault吗？
C++ 没有 ConcurrentHashMap，实现 ConcurrentTrie 相对简单，所以选择了 Trie。
很多同学采用 Java 实现性能也非常好，相当赞！