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) - 平衡二叉树

任何一个想实现专业Comet产品都避免不了去了解Bayeux, 它定义了一个协议，通过一系列 json 的事件来实现 pubsub 模型进而实现Comet各种业务。它也致力让自己成为Comet的标准。小型的Comet应用通常会在Streaming里面返回一些自定义的 JavaScript来实现各种业务功能，但是Bayeux实现了一个full stack的体系，包括客户端服务器的交互，Event, Transport协商, Authentication, Security等。

Bayeux一些术语和概念包括

• Pub/Sub,Bayeux的核心就是通过一个pub/sub模型来实现Comet各种业务。
• ClientID, 通过客户端handshake之后服务器分配。
• Channel,订阅的频道，可以理解成聊天的房间。
• Messages: 所有的包都封装成一个message，里面包含各种字段。
• data: message中的数据元素，应用可以根据业务再次定义细分的格式。

Bayeux的优势很明显，通过与Jetty配合可以几十行程序实现一个comet的聊天室demo

缺点

• PubSub模型，点对点支持不佳，除了多人聊天的场合之外，其实大部分comet应用更适合点对点的模式。如果用PubSub套上去也可以实现，问题是对服务器的压力更高，而且通常comet应用的访问量都比较大。
• 可靠性，一条信息publish了没法知道客户是否能收到了，也没法做进一步处理比如说保存或重发等业务逻辑。
• 顺序，publisher顺序和接收显示的顺序
• 多Tab浏览器打开同一个Comet应用，或者在IE里面Ctrl-N再次打开当前页面新窗口。

更详细的比较可参看 Battle of the Bayeux 系列

尽管Bayeux喜忧参半，但是对于希望实现一个专业Comet应用的开发者来说，Bayeux的诱惑是巨大的，它有开发者需要的完备的接口和成熟的体系架构。如果绕开它，不管是服务器还是客户端都需要一个漫长的摸索和自己定义规范的过程。如果看了这篇自己用C实现的comet http server,基于libevent以为就搞定Comet那可能就低估难度了。

Bayeux的例子可以通过下载Jetty6看到。

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)

最近看到一篇文章 Thoughts On Scalable XMPP Bots, 描述构建一个大型基于IM bot的一些思路。

• Client Bot

就是Client 自己按照IM协议作为一个普通的客户连接到服务器。普通用户添加这个bot账号之后可以进一步进行相关的业务交互。Client Bot在实现各种专有IM系统中比较常见，比如MSN bot, GTalk Bot等。

Client Bot最大的问题就是能够添加的好友列表的长度限制。因为bot是一个普通的客户端，所以普通客户端最多只能添加数百个好友的问题就成了最大的障碍。

另外由于bot通常流量过大，而且会给服务器造成额外压力，很容易被服务器当做发广告信息或垃圾信息或其他业务竞争方面的原因遭受屏蔽。

综上所述，基于client bot构建一个大型业务系统不是最佳的选择。

• Component Bot

这个只对XMPP系统而言，XMPP中Component使用专门的协议与服务器交互。实际上component有自己的domain, 如 rabbiter 使用 rabbiter@rabbiter.DOMAIN

在 ejabberd 上，component可以使用round robin负载均衡算法，将component请求分布到多个相同component name的服务上。以实现一个跨服务器的大型业务系统。

• S2S Bot

Bot有自己专门的域名，如 tim-bot.com, 它可以在 DNS 设置轮询使服务定向到多个具体的服务器上。但是由于此方法需要单独申请域名并配置配置独立的服务，这个做法显得有点过于复杂。

Component和S2S bot适合构建自己的基于bot的服务。比如文章开头连接中所说的Chesspark(一个实现下棋游戏的bot),以及以前介绍的Rabbiter一个开源的XMPP微博客实现。

一. Java 的不足
如何构建一个分布式可扩展的Java服务器？首先我们要非常了解Java构建网络应用的优点及不足之处。
Java网络架构的基础是RMI远程调用。RMI是一种成熟稳定方便的应用，它的不足主要有

1) 没有安全隔离机制，一段代码的不稳定会造成整个node failure

2) 没有接管及远程监控机制，失败不能由另外一个程序或另外一个节点接管

3) RMI是C/S结构，通常是一对一, Client无法选择多个Server，无法切换Server，无法转移Server，如下一个典型的 Java RMI Spring配置

<bean id="timDemoService" class="org.springframework.remoting.rmi.RmiProxyFactoryBean">
          <property name="serviceUrl" value="rmi://server:1199/fooService"/>
          <property name="serviceInterface" value="com.foo.TimDemoService"/>
</bean>

上面的 timDemoService在JVM系统启动时候就加载，client/server就已经固定。

4) RMI是单向的，只能 client 调用 server, Server 调用 Client需要另外配置一套(即Server变成另外一个场景的client)，不能共享同一个连接。

二. 传统的 RPC 都是错误的
因此最近有一种观点就说RPC都是错误的，下文中提到的RPC都可以理解成包含Java RMI

"but for normal languages, RPC creates more problems than it solves."
    -- Steve Vinoski

来源：(原文 中文版)
其主要论点就是说RPC最大的问题就是把远程调用做得象本地调用。但是，远程调用并不是本地调用，它的异常和错误及其他很多方面是截然不同的。传统的RPC调用忽略了local与remote的区别，因此在大型项目里面混淆了这两者调用区别的应用通常会造成性能问题。

三. Erlang的优势
跟传统的 RPC 相对比，Erlang 的主要优点包括

1) 2个process互为关联(link)，一个crash,另外一个自动接管。

2) RPC就是message send/receive(严格的讲Erlang里面没有RPC), 可以很方便增加error handling, 而且 error handling 可以放在远程，这样更适合网络架构，因为local error handling在本机发生故障时候毫无意义。

3) message receive可以增加timeout，不会阻塞在某个地方

4) 其他场景，如Node X调用Node Y, Node Y执行业务之后把结果返回给Node Z, 传统RPC无法处理

四. Java中一些替代思路
1) RMI 也可以设置 timeout，因为底层无非都是基于Socket

2) RMI也可以实现无单点故障及负载均衡，参看 Clustered Remoting For Spring Framework Cluster4Spring 支持一对多调用，动态发现服务(dynamic services discovering)及远程错误监控, The Server Side 上有更多深入的讨论

3) 分布式内存共享 Coherence Data Grid, Openfire Cluster 就用了这个模块，不过这个框架不是开源的。

4) 分布式内存共享 Terracotta，这是一个开源的，Scala会采用这个

5) JGroups 可靠的组播服务，集群通讯首选的工具库，在其他语言无类似替代产品。JGroups介绍可参看前文 JGroups 简介、适用场合、配置、程序例子Demo等完全使用指南

6) Concurrent, Erlang中有轻量级的process, Java7中会有Doug Lea主导的fork/join

不过 Erlang里面还有Java中暂时无法替代的优势, 如Immutable变量, 无共享内存，Process交换数据通过消息传递实现等，这些特性在多核CPU下具有先天优势，相关资料也很多，就不这里重复了。

继续改进部分基于用户好友关系的分布式PubSub系统。

本来的想法是把LocalSubList放到远端，好处是High availability即某个节点死了不会造成大面积故障，由另外一个节点可迅速接管。但是如果放在远端, 那更新的开销会非常大, 1个改变需要修改n份远程数据，比如拿在线好友列表说事，一个用户改变状态，所有在线好友的列表需要同时update，在设计上人为制造了一个瓶颈。

因此今天把思路调整下，由发送方广播1个通知, 接收方各自维护更新自己的列表。那HA怎么办，每2个节点分成一组互相替对方存一份。反正发送方会广播通知的，即使增加一个专用的节点来做备份listener也不是什么大问题。在可靠性面前，硬件成本微不足道。

自己做一个网络模块的优点是风险可控，时间可控，但是原理通过之后就只剩下枯燥的开放了。按照don't re-invent the wheel的思想，或许将来更好的做法是底层(语言和框架)来做这些事情。比如网络间的通讯，节点迁移，HA, 数据共享等。

这个模块有点抽象，尽管我觉得不复杂，但跟别人口述的时候对方也是听得一头雾水，从软件项目管理的角度来说设计要尽量简单，至少要项目小组里面一半以上的人一看就明白，因此这个设计还有很大的简化空间。

做软件设计不能做得象编程之美的题目那样高深。对于一个网络服务端程序，我觉得
1. 性能优先
2. 简单优先

需要一个pubsub的功能，用在基于各种好友关系的场合。

* publish list 可能成千上万、十万、百万。
* publish topic 生命周期可能极短，调用一次就结束；也可能很长
* publish 数据实时广播即可，无需保存等待consumer到来
* subscribe list 可能很长，大的数千，也可能很小，只有1个
* subscribe list 相对固定(在线好友列表 or follow list)
* subscribe list 需要跨节点的，即一个topic在多个节点有local subscribe list
* 对性能要求极高，性能为王
* 无事务要求，特殊状况下，如某节点发生故障，丢失小量数据可容忍。
* 分布式，无中心节点
* 节点可动态切换

目前还没找到适合我的现成产品。前几天提到的rabbitmq和erlang或许是一个思路。

Erlang太高深了，周末的时候想了一个适合各种小白语言的思路，试画了一个简单的。

最近听一个做类twitter系统的技术同行聊到 Rabbiter, 简单了解了一下，原理如下


1. Rabbiter 是一个xmpp bot，即 IM 机器人，基于 RabbitMQ 和 RabbitMQ XMPP Transport实现，即底层还是一个消息服务器

2. Rabbiter 采用 Erlang 开发，原理上具有良好的可扩展性，可支持非常大型的系统，通常跟 ejabberd 同时部署

3. Rabbiter 实现的原理上属于 XMPP PubSub

4. Rabbiter 实现的功能上目前主要是微博客(microblogging)的功能，支持的指令包括 follow, unfollow, following, followers 等。(微博客是twitter, 饭否之类系统)

5. Rabbiter 可以实现 MUC (多人聊天) 或群功能，比如用户A/B/C/D互相follow, 就成了一个多人群体

6. 所有 Client 订阅信息都是 PUSH 过去, 原理上可以避免 twitter 目前遇到的 API 负荷过大问题。

这个是我1年前关于 XMPP 与 Microblogging 不成熟的想法：Twitter中文版类似系统实现的技术构想。那现在 Rabbiter 则是可用的 XMPP/Microblogging 产品了。

Rabbiter的网站及下载地址为：http://github.com/tonyg/rabbiter/tree/master

前几个月曾经做个一次 比较Java中几种数据cache方式 的试验，最近看到 Openfire 中有一个非常小巧的本地 Cache实现， 在相同环境测试比流行的ehcache快大约5倍。简单介绍如下。

原理图

实现方法
* 用 HashMap 来存储和用来做 CacheKey 查找。
* 用一个LinkedList来存储访问顺序列表
* 用一个LinkedList来存储添加时间顺序列表，即过期时间。
* HashMap 中 Key 为 CacheKey, Value 包装成一个CacheObject
* CacheObject 包含：
1) object size
2) 指向 Access List 节点的指针
3) 指向 Age List 节点的指针

其中两个List的作用
1) AccessList
当添加新元素且 List 满时，删除列表最后的元素，即最长时间没有访问的元素。

2) AgeList
当调用 get cache 时候，判断 List 末尾有无过期元素，如有向前一直删除到最后一个没有过期的元素为止。

Performance 性能评测
写了个简单的测试，2线程写 Cache, 4 线程同时读Cache，每个Cache 100字节，平均速度大致为

写cache: 168,924 条/秒
读cache: 605,212 次/秒

结果在相同环境测试比流行的ehcache快大约5倍。

Resource资源下载
DefaultCache 源代码，稍修改去掉没用的引用即可独立使用。