12/20, 12/21 将会在上海参加 CN Erlounge III,
我主要关注的内容

• Erlang语言的动态
• Erlang在实现分布式系统中的实际情况及面临的问题
• 非Erlang系统中实现分布式及利用多核技术的思路
• 最重要的，是见识这些国内资深的Erlang开发人员。因为我对Erlang的掌握也不够深入，所以只能从架构的层面取感受大会所讨论的内容。

如果有机会，我会讲Jabber/XMPP与分布式方面内容。

• XMPP简介及优
• 常用的XMPP服务器实现思路
• 大型分布式XMPP Server面临的主要问题
• Web IM, Comet, XMPP Server 如何结合

因为组织者临时邀请我讲下Jabber方面话题，时间比较仓促，只能先完成一个提纲及简单准备下思路，会准备几个图用于讲解，不会特别多文字，具体内容根据现场的反馈进行适当延伸或缩减。文档做好之后会更新到这里。

另外这个大会注册通道早就关闭了，没有报名的朋友就不用去了解怎么参与了。

补充：演讲PPT在线预览

最近把新开发的登录服务器重构了一下，压力测试过程中发现用户增大之后就卡住。由于并发处理的服务器通常无法单步调试，在地毯式的添加log之后发现竟是一行很不起眼的 java.net.InetAddress.getHostName() 造成。

大批量用户登录 => 调用 getHostName() 阻塞 => 工作线程满 => 后续用户登录超时

简单示意代码如下：

java.net.InetAddress ia = InetAddress.getByName("192.168.100.100");
System.out.println(System.currentTimeMillis());
ia.getHostName(); // 很慢
System.out.println(System.currentTimeMillis());
ia.getHostAddress(); // 很快
System.out.println(System.currentTimeMillis());

从这个问题想到需要对于工作线程的状态需要增加一个监控机制，如果所有的 thread 都是 block 状态就需要引起足够重视。

另外很多网络服务器也有类似域名反向解析的做法，比如 mysql, ssh等。很多程序碰到在登录连接 mysql 时候很慢，在mysql配置去掉域名反向解析后就快了。

补充：最近刚看到 Gea-Suan Lin 也碰到了这个烦恼，见 Smokeping 啟動速度很慢的問題 :)

Presence and Data Structure - Part III

关于在线好友场景的说明参看前文：在线好友状态列表与数据结构(1)-list

我们再评估一下平衡二叉树在前文场景中的性能。平衡二叉树(Self-balancing binary search tree)是一种将树的深度自动保持最小化的一种数据结构。

1) 红黑树 Red Black Tree
Red-Black Tree是如图所示一种数据结构，它最深的叶子最多是最短的叶子深度的2倍，是通过红色和黑色的控制来达到目的。 它的Insert/Delete/lookup算法复杂度是O(Log n)
Red-Black的插入/删除有非常直观的Applet动画演示
http://gauss.ececs.uc.edu/RedBlack/redblack.html

2) AVL tree
AVL tree也 是一种自平衡的二叉树,和Red-Black Tree非常相似。原理上AVL insert/delete比Red Black tree慢，lookup更快，因此AVL Tree在查找密集型操作中表现更好。由于我们考察的案例是insert/delete密集操作且set比较小，所以就不对AVL tree做性能比较了。

性能比较
我们仍然比较Red-Black Tree同Hash table的性能区别。Red-Black Tree使用Java的TreeMap来实现；Hash Table使用HashMap来实现。

5千万数据, 每50个为一组，插入50个8位长的随机数，在达到30个之后再每次删除一个元素。

测试结果
HashMap 20秒
TreeMap 18秒

这和平时理解有点区别，因为一般的Java教材都是说不要直接使用TreeMap,当需要排序时候再用构建好的HashMap传递进去，但在上述测试中，对于数字的key，TreeMap的性能和HashMap大致是一样的,甚至性能更好。

简单小结
对于前文的场景，就是比较各种数据结构之后，还是HashMap领先。对于数字类型的账号，也可考虑使用Red-Black Tree, 即TreeMap

补充说明
Java Collection Framework 其实用来进行各种数据结构原理的性能比较，可能结果不一定100%反应该数据结构原理的优劣，因为Java集合类不是完全照搬按教科书来实现，而是做了很 多实用性及性能的优化。而且Java集合类的开发者是Java界最优秀的两位高手Joshua Bloch及Doug Lea

HashMap 的作者
* @author Doug Lea
* @author Josh Bloch

TreeMap 的作者
* @author Josh Bloch and Doug Lea

另外还有一个多线程下性能更好的 ConcurrentHashMap
* @since 1.5
* @author Doug Lea

尽管这样，我们通常关注是实际环境下使用基于数据结构原理的JDK集合类的性能，所以上述测试对实际生产环境是有借鉴意义的。

参看：
在线好友列表与数据结构(2) - Radix Tree
在线好友状态列表与数据结构(1)-list

Presence and Data Structure - Part II

1) Hash table
在讨论Radix Tree之前先看下 hash table, 它是目前大家都很熟悉使用非常广泛的一种数据结构。它的算法复杂度是O(1)

/** 
 * Roster item cache - table: key jabberid string; value roster item.
 */  
protected ConcurrentHashMap<String, RosterItem> rosterItems = 
     new ConcurrentHashMap<String, RosterItem>();

(Openfire class org.jivesoftware.openfire.roster.Roster)

2) Radix Tree

(图片来源：Wikipedia)

Radix Tree 是如图所示一种数据结构，对于小量范围有一定相似度的字符串具有较高的insert/delete/lookup性能。它的这几个操作算法复杂度是 O(k), k指key长度。与hash table相比，虽然O(k) > O(1)。但是 hash table的O(1)没有考虑计算hash所需时间及hash冲突的时间
。因此在某些情况下Radix Tree性能比hash table好也不足为奇。

性能比较

我们使用Google code中的 Radix Tree Java Library实现,
hash table使用Java Collection中的HashMap

1千万数据，每50个为一组，插入50个5位长的随机数，在达到30个之后再每次删除一个元素。考虑到实际应用中号码段可能会趋于集中，而且为了更好的测试Radix Tree，测试再在所有的号码前加上固定前缀1000。

执行时间：
HashMap 2秒
RadixTree 20秒

虽然构造的测试场景有利于Radix Tree, 但是测试结果是Radix Tree完全不适合此场景。而且还有不足的是上述Radix Tree库没有实现iterator()接口。

参看：
在线好友状态列表与数据结构(1)-list
在线好友列表与数据结构(3) - 平衡二叉树

Presence and Data Structure - Part I

在一个典型的IM Server上，每个登录的用户都需要维护一份自己在线用户列表，需要频繁进行以下操作

iterate
循环与遍历，很多操作需要调用iterator

insert/delete
由于在线的好友随时会产生上下线的变化，所以需要增加或删除列表的内容。

lookup
同时由于列表的元素需要保持唯一性，insert时候也需要查找已有的元素是否存在。

同时还具有以下一些特性

长度
在线的好友列表不会太长，通常都是几十个。

规律
假如系统使用的是基于号码的数字账号，这些数字通常有一定程度集中性，比如很多系统活跃用户集中在最新的号码段。


对于一个这样的需求，我尝试去了解一下需要知道在已有的数据结构中哪一种数据结构是最适合的。

在以下及后续的评估中，主要是考虑时间复杂度，即程序性能，对空间复杂度关注较少。

1) Array/List

对于这样一个列表，最简单的做法就是用数组或list实现。这就是往往现在大部分程序员不懂数据结构也能写出正常执行的程序。`

但是，Array/List都存在查找慢的问题，频繁的增删性能很慢。

2) Linked List
Linked List解决了增删性能问题，是一种最常采用的做法，如下代码片断。但仍然存在查找慢的问题。

/**
 * remove a jid from a list, returning the new list
 *
 * @param id the JabberID that should be removed
 * @param ids the list of JabberIDs
 * @return the new list
 */
static jid _mod_presence_whack(jid id, jid ids) {
       jid curr;

       if (id == NULL || ids == NULL)
       return NULL;

       /* check first */
       if (jid_cmp(id,ids) == 0)
       return ids->next;

       /* check through the list, stopping at the previous list entry to a matching one */
       for (curr = ids; curr != NULL; curr = curr->next) {
       if (jid_cmp(curr->next, id) == 0)
           break;
       }

       /* clip it out if found */
       if(curr != NULL)
           curr->next = curr->next->next;

       return ids;
}

(Jabberd 1.4 更新好友列表的代码, mod_presence.cc)

(待续: 在线好友列表与数据结构(2) - Radix Tree)

记得我刚开始从事软件开发工作的时候，当时的领导曾经给我推荐过一本很薄很经典的90年代的书，书名我已经记不起来了，讲的是微软开发小组里面的一些优秀的开发实践，如TRACE, ASSERT, bound check 的一些美妙之处，看后对我的编程风格有很深的影响，有些习惯可能一直延续至今。微软亚洲研究院的《编程之美》给我第一印象应该是这样一本书，然而看了几个小时之后，稍微觉得有点失望。一般程序员看后可能会对有些应试的用途，但对提升自身价值没有任何帮助。

也顺便说说我对开发人员能力如何衡量。

1. 90%以上公司需要的都是知识型人才，比重占70%,
拿Java来说
a) 基础知识类：如jdk, collection, thread, jdbc, jsp, servlet
b) 专业技术类，如Struts, Spring, Hibernate
2) 综合知识类，如TCP/IP, socket, linux, web service, xml, sql, ajax

2. 协作能力/EQ, 比重占20%
比如协作，沟通，态度，责任心，积极心等

3. IQ(智力题，数学题) 10%
这个很难衡量需要多少，按应用类型来说
a) 以功能为主的应用, 国内大部分是这种情况，开发就是怎样用程序来完成业务系统，这种类型知识面更重要
b) 以性能为主的应用, 如 nginx
c) 两者兼顾，如 mysql
b/c可能是对智力方面要求稍高，但我觉得任何一个数学能打80分以上的在1,2达到要求之后都可以胜任。

在大部分软件开发中，纯算法占的比例很少，甚至没有。一个有趣的现象就是《数据结构》（严蔚敏的那本经典教材不怎样）这本书大部分程序员只是在面试前阶段有机会看看，工作中根本没需要查阅。
比如Java中
常用数据结构：ArrayList, LinkList, Queue, Hashtable, HashSet
常用排序：SortedSet, SortedMap, TreeMap
数据结构中描述的那些东西基本上JDK都有了，对于Java程序员只要理解这些工具库的使用场合，能够使用恰当就非常合格了。

再讲个纯数学算法优化是否重要的问题，书中有例子，如2.10 寻找1个数组中最大值和最小值。这个题通常的解法的时间复杂度是2*N，实际上可以很容易优化到1.5*N。如果从一个产品的角度来考虑，如果一个程序员提交的代码复杂度是2*N, 我觉得这样就足够了。因为
1) 大部分应用的电脑CPU占用5%都不到
2) 这样纯算法的问题在目前大部分Web系统通常不会成为瓶颈，瓶颈通常在IO, 网络及架构设计及语言本身上。比如你用Ruby写，某个算法再优化可能也只有C语言效率的1/100
3) 产品负责人更关心代码质量，可维护性，可扩展性等方面。
4) 产品负责人更关心更关注知识型／经验型的层面，比如程序员原来用Java IO实现的，可能用Java NIO更合适。

可能上面这个例子是此书里面离开发最近的，大部分题目比这个离实际开发更远，比如“数独”问题等，用来做做头脑游戏可能更适合。如果一个程序员花了1天，写出了一个构造数独的程序，他的能力就得到了提高吗？

后记中其中一个现任职于微软研究院的作者提到，“作为一个曾经的求职者，当时自己能够做的，就是搜集和整理能够在网络上搜刮到的所有题目。算法题、智力题以及各种面经。把各种题目做到让自己条件反射为止……(原文)”。如果真是这样，我对微软亚洲研究院的这种“高考式”的面试方法表示担心。擅长做数学题和智力题跟能否够给软件企业和社会创造价值未必能划上等号。