6行代码实现一个 id 发号器

id 发号器的问题,@一乐 的这篇文章说的很透彻了:http://weibo.com/p/1001603800404851831206 但参考实现就显得有些复杂。最近在雪球工作中正好需要用到发号器,于是用 Lua 在 Redis 上实现了一个最简单的:


-- usage: redis-cli -h 10.10.201.100 -p 10401 EVAL "$(cat getID.lua)" 1 XID:01:02
local arg = KEYS[1]
-- project id must has 2 digits, 01 - 15
local pid = tonumber(string.sub(arg, 5, 6))
-- instance id must has 2 digits, 01 - 15
local iid = tonumber(string.sub(arg, 8, 9))
local idnum = redis.call("INCR", "ID_IDX") % 65536
local sec = redis.call("TIME")[1] - 1420041600
return sec*16777216 + pid*1048576 + iid*65536 + idnum

解释:

  • id 总长度 52bit,为了兼容 js,php,flex 等语言 long 类型最长只能 52 bit
  • 最高 28 bit 为秒级时间戳,因为位数限制,不能从 1970.1.1 开始,-1420041600 表示从 2015.1.1 开始,大约可以使用10年(3106天)
  • 接下来4个bit为 project id,客户端传入,区分业务
  • 再接下来4个bit为 instance id,HA 用的,支持最多16个instance。如果业务只需要“秒级粗略有序”,比如发微博或发评论,则可以多个 instance 同时使用,不需要做任何特殊处理;如果业务需要“因果有序”,比如某个user短期内快速做的多个操作必须有因果顺序(程序化交易,必须先卖再买,几个毫秒内完成),那么就需要做一些特殊处理,要么用 uid 做一致性hash,或者像我们这样偷懒:一段时间内固定使用一个 instance
  • 最低16个bit是 sequence id,每个 instance 支持每秒 65535 个 id。bit数再大,redis 该成为瓶颈了。
  • twitter和微博都是把 instance id 写死到 server 端,这样 server端就变成有状态的了:16个instance,每个 instance 都与其它的配置不一样。在雪球我们不希望 server 端有状态,于是设计成 instance id 由客户端传入,server 端退化成一个普通的 redis cache server (不需要 rdb,不需要 aof,宕机重启即可)
  • 几个注意点:宕机不能自动立即重启,必须间隔1秒以上,避免 sequence id 重复导致 id 重复;迁移时必须先 kill 老的 instance,再启动新的,也是为了避免 sequence id 重复。

id 发号器说简单也确实挺简单。任何一个技术点,只要理解了本质,大约都是这么简单罢。

转:缓存算法

没有人能说清哪种缓存算法是源于其他的缓存算法。

Least Frequently Used(LFU)

大家好,我是 LFU,我会计算为每个缓存对象计算他们被使用的频率。我会把最不常用的缓存对象踢走。

Least Recently User(LRU)

我是LRU缓存算法,我把最近最少使用的缓存对象给踢走。

我总是需要去了解在什么时候,用了哪个缓存对象。如果有人想要了解我为什么总能把最近最少使用的对象踢掉,是非常困难的。

浏览器就是使用了我(LRU)作为缓存算法。新的对象会被放在缓存的顶部,当缓存达到了容量极限,我会把底部的对象踢走,而技巧就是:我会把最新被访问的缓存对象,放到缓存池的顶部。

所以,经常被读取的缓存对象就会一直呆在缓存池中。有两种方法可以实现我,array 或者是 linked list。

我的速度很快,我也可以被数据访问模式适配。我有一个大家庭,他们都可以完善我,甚至做的比我更好(我确实有时会嫉妒,但是没关系)。我家庭的一些成员包括LRU2 和 2Q,他们就是为了完善 LRU 而存在的。

Least Recently Used 2(LRU2):

我是 Least Recently Used 2,有人叫我最近最少使用twice,我更喜欢这个叫法。我会把被两次访问过的对象放入缓存池,当缓存池满了之后,我会把有两次最少使用的缓存对象踢走。 因为需要跟踪对象2次,访问负载就会随着缓存池的增加而增加。如果把我用在大容量的缓存池中,就会有问题。另外,我还需要跟踪那么不在缓存的对象,因为他 们还没有被第二次读取。我比LRU好,而且是 adoptive to access 模式 。

Two Queues(2Q):

我是 Two Queues;我把被访问的数据放到LRU的缓存中,如果这个对象再一次被访问,我就把他转移到第二个、更大的LRU缓存。

我踢走缓存对象是为了保持第一个缓存池是第二个缓存池的1/3。当缓存的访问负载是固定的时候,把 LRU 换成 LRU2,就比增加缓存的容量更好。这种机制使得我比 LRU2 更好,我也是 LRU 家族中的一员,而且是 adoptive to access 模式 。

Adaptive Replacement Cache(ARC)

我是 ARC,有人说我是介于 LRU 和 LFU 之间,为了提高效果,我是由2个 LRU 组成,第一个,也就是 L1,包含的条目是最近只被使用过一次的,而第二个 LRU,也就是 L2,包含的是最近被使用过两次的条目。因此, L1 放的是新的对象,而 L2 放的是常用的对象。所以,别人才会认为我是介于 LRU 和 LFU 之间的,不过没关系,我不介意。

我被认为是性能最好的缓存算法之一,能够自调,并且是低负载的。我也保存着历史对象,这样,我就可以记住那些被移除的对象,同时,也让我可以看到被移除的对象是否可以留下,取而代之的是踢走别的对象。我的记忆力很差,但是我很快,适用性也强。

Most Recently Used(MRU)

我是 MRU,和 LRU 是对应的。我会移除最近最多被使用的对象,你一定会问我为什么。好吧,让我告诉你,当一次访问过来的时候,有些事情是无法预测的,并且在缓存系统中找出最少最近使用的对象是一项时间复杂度非常高的运算,这就是为什么我是最好的选择。

我是数据库内存缓存中是多么的常见!每当一次缓存记录的使用,我会把它放到栈的顶端。当栈满了的时候,你猜怎么着?我会把栈顶的对象给换成新进来的对象!

First in First out(FIFO)

我是先进先出,我是一个低负载的算法,并且对缓存对象的管理要求不高。我通过一个队列去跟踪所有的缓存对象,最近最常用的缓存对象放在后面,而更早的缓存对象放在前面,当缓存容量满时,排在前面的缓存对象会被踢走,然后把新的缓存对象加进去。我很快,但是我并不适用。

Second Chance

大家好,我是 second chance,我是通过FIFO修改而来的,被大家叫做 second chance 缓存算法,我比 FIFO 好的地方是我改善了 FIFO 的成本。我是 FIFO 一样也是在观察队列的前端,但是很FIFO的立刻踢出不同,我会检查即将要被踢出的对象有没有之前被使用过的标志(1一个bit表示),没有没有被使用 过,我就把他踢出;否则,我会把这个标志位清除,然后把这个缓存对象当做新增缓存对象加入队列。你可以想象就这就像一个环队列。当我再一次在队头碰到这个 对象时,由于他已经没有这个标志位了,所以我立刻就把他踢开了。我在速度上比FIFO快。

CLock

我是Clock,一个更好的FIFO,也比 second chance更好。因为我不会像second chance那样把有标志的缓存对象放到队列的尾部,但是也可以达到second chance的效果。

我持有一个装有缓存对象的环形列表,头指针指向列表中最老的缓存对象。当缓存miss发生并且没有新的缓存空间时,我会问问指针指向的缓存对象的标 志位去决定我应该怎么做。如果标志是0,我会直接用新的缓存对象替代这个缓存对象;如果标志位是1,我会把头指针递增,然后重复这个过程,知道新的缓存对 象能够被放入。我比second chance更快。

Simple time-based

我是 simple time-based 缓存算法,我通过绝对的时间周期去失效那些缓存对象。对于新增的对象,我会保存特定的时间。我很快,但是我并不适用。

Extended time-based expiration

我是 extended time-based expiration 缓存算法,我是通过相对时间去失效缓存对象的;对于新增的缓存对象,我会保存特定的时间,比如是每5分钟,每天的12点。

Sliding time-based expiration

我是 sliding time-based expiration,与前面不同的是,被我管理的缓存对象的生命起点是在这个缓存的最后被访问时间算起的。我很快,但是我也不太适用。

好了!听了那么多缓存算法的自我介绍,其他的缓存算法还考虑到了下面几点:

成本。如果缓存对象有不同的成本,应该把那些难以获得的对象保存下来。
容量。如果缓存对象有不同的大小,应该把那些大的缓存对象清除,这样就可以让更多的小缓存对象进来了。
时间。一些缓存还保存着缓存的过期时间。电脑会失效他们,因为他们已经过期了。
根据缓存对象的大小而不管其他的缓存算法可能是有必要的。

Random Cache

我是随机缓存,我随意的替换缓存实体,没人敢抱怨。你可以说那个被替换的实体很倒霉。通过这些行为,我随意的去处缓存实体。我比FIFO机制好,在某些情况下,我甚至比 LRU 好,但是,通常LRU都会比我好。

(示例代码略)

http://www.zavakid.com/27
http://www.jtraining.com/component/content/article/35-jtraining-blog/137.html

关于 Jetty Continuation

领导说,我们不能绑定在某个产品,某个框架,某个技术实现上。所以当我们希望使用 jetty 的 continuation 技术的时候,我们必须对它进行一个包装,以保证将来如果需要,我们可以用其它的技术或框架进行替换。

一个简单的包装:

TaskManager 类:

       /**
	 * submit a task async
	 * 
	 * @param request
	 * @param response
	 * @param task
	 * @return result true for first submit task, false for expire or exception
	 */
	public static boolean submitTask(final HttpServletRequest request,
			final HttpServletResponse response,
			final AbstractContinuation task) {
		final Continuation continuation = ContinuationSupport
				.getContinuation(request);

		if (continuation.isExpired()) {
			@SuppressWarnings("unchecked")
			final FutureTask ftask = (FutureTask) request
					.getAttribute(TASK_FUTURE);
			if (ftask != null) {
				// not Interrupt if it is still running
				ftask.cancel(false);
			}
			task.onExpire(request, response);
			return false;
		}

		// first call of this request
		continuation.setTimeout(ContinuationConfig.timeout);
		continuation.suspend(response);

		try {
			final FutureTask ftask = new FutureTask(task) {
				@Override
				protected void done() {
					// cancelled, just return
					if (isCancelled()) {
						return;
					}
					// expired, just return
					if (continuation.isExpired()) {
						return;
					}

					// complete, so *NO* attribute will take effects
					// request.setAttribute(TASK_RESULTS, get());
					try {
						final Object result = get();
						task.onResult(request, response, result);
					} catch (final Exception e) {
						task.onException(request, response, e);
					}
					continuation.complete();
				}
			};
			exec.submit(ftask);
			request.setAttribute(TASK_FUTURE, ftask);
			return true;
		} catch (final TooManyWaitingTaskException e) {
			task.onException(request, response, e);
			return false;
		}

	}

	/**
	 * submit a task sync, with *NO* expire support
	 * 
	 * @param request
	 * @param response
	 * @param task
	 * @return result true for first submit task, false for expire or exception
	 */
	public static boolean submitTask2(final HttpServletRequest request,
			final HttpServletResponse response,
			final AbstractContinuation task) {
		try {
			final Object result = task.call();
			task.onResult(request, response, result);
			return true;
		} catch (final TooManyWaitingTaskException e) {
			task.onException(request, response, e);
			return false;
		} catch (final Exception e) {
			task.onException(request, response, e);
			return false;
		}

	}

servlet 里面可以这样调用:(注意,当前不支持 jsp )

        @Override
	protected void doGet(final HttpServletRequest request,
			final HttpServletResponse response) throws ServletException,
			IOException {

		// create an asynchronous task
		final AbstractContinuation task = new AbstractContinuation() {
			@Override
			public Object call() throws Exception {
				// do the job
			}

			@Override
			public void onResult(final HttpServletRequest request,
					final HttpServletResponse response, final Object result) {
				// has result, so ignore all exception
                                // do output
			}

			@Override
			public void onExpire(final HttpServletRequest request,
					final HttpServletResponse response) {
				try {
					response.sendError(504, "continuation job expired");
					log.warn("on expire:" + request);
				} catch (final IOException e) {
					log.warn("exception on expire: " + request + e.getMessage());
				}
				return;
			}

			@Override
			public void onException(final HttpServletRequest request,
					final HttpServletResponse response, final Exception e) {
				try {
					response.sendError(503, "some exception occured ");
					log.warn("on exception:" + request, e);
				} catch (final IOException ioe) {
					log.warn("exception on exception: " + request
							+ e.getMessage() + ioe.getMessage());
				}
				return;
			}
		};

		if (TaskManager.submitTask(request, response, task)) {
			// first submit
			// do nothing here
		} else {
			// expire, or exception
			// just ignore here, because we have dealed with it other place
		}

		return;
	}

分享我的 jetty 配置

最近接手做一个类似 bit.ly 的短链服务,把原来 php 实现的一个模块独立出来,以服务的形式提供。

新的实现基于 java,嵌入式的 jetty。先贴一下 jetty Server 的配置文件。一些细节和感悟稍后添加。

<?xml version="1.0"?> 
<!DOCTYPE Configure PUBLIC "-//Jetty//Configure//EN" "http://www.eclipse.org/jetty/configure.dtd"> 
 
<Configure id="Server" class="org.eclipse.jetty.server.Server">

    <!-- =========================================================== -->
    <!-- Server Thread Pool                                          -->
    <!-- =========================================================== -->
    <Set name="ThreadPool">
      <!-- Default queued blocking threadpool -->
      <New class="org.eclipse.jetty.util.thread.QueuedThreadPool">
        <Set name="minThreads">200</Set>
        <Set name="maxThreads">500</Set>
      </New>
    </Set>

    <!-- =========================================================== -->
    <!-- Set connectors                                              -->
    <!-- =========================================================== -->

    <Call name="addConnector">
      <Arg>
          <New class="org.eclipse.jetty.server.nio.SelectChannelConnector">
            <Set name="host"><Property name="jetty.host" /></Set>
            <Set name="port"><Property name="jetty.port" default="8080"/></Set>
            <Set name="maxIdleTime">300000</Set>
            <Set name="Acceptors">2</Set>
            <Set name="statsOn">false</Set>
            <Set name="confidentialPort">8443</Set>
            <Set name="lowResourcesConnections">20000</Set>
            <Set name="lowResourcesMaxIdleTime">5000</Set>
          </New>
      </Arg>
    </Call>

    <!-- =========================================================== -->
    <!-- Set Servlets handler                                        --> 
    <!-- =========================================================== -->
    <Set name="handler">
      <New id="Handlers" class="org.eclipse.jetty.server.handler.HandlerCollection">
        <Set name="handlers">
         <Array type="org.eclipse.jetty.server.Handler">
           <Item>
             <New id="Servlets" class="org.eclipse.jetty.servlet.ServletContextHandler">
                <Call name="setContextPath"><Arg>/</Arg></Call>
             
                <!-- general short2long and long2short -->
                <Call name="addServlet">
                  <Arg>org.fulin.servlets.Long2Short</Arg>
                  <Arg>/short.xml,/short.json,/secure/short.xml,/secure/short.json</Arg> 
                </Call>
                <Call name="addServlet">
                  <Arg>org.fulin.servlets.Short2Long</Arg>
                  <Arg>/long.xml,/long.json,/secure/long.xml,/secure/long.json</Arg>
                </Call>

                <!-- secure mark safe and unsafe, call back -->
                <Call name="addServlet">
                  <Arg>org.fulin.servlets.UpdateStatus</Arg>
                  <Arg>/secure/safe.xml,/secure/safe.json,/secure/unsafe.xml,/secure/unsafe.json</Arg>
                </Call>
                
                <!-- update ext, call back -->
                <Call name="addServlet">
                  <Arg>org.fulin.servlets.UpdateExt</Arg>
                  <Arg>/secure/update.xml,/secure/update.json</Arg>
                </Call>
                
                <!-- monitor for varnish or something else -->
                <Call name="addServlet">
                  <Arg>org.fulin.servlets.Monitor</Arg>
                  <Arg>/monitor</Arg>
                </Call>
              </New>
           </Item>
           
           <!-- Configure Request Log -->
           <Item>
               <New id="RequestLog" class="org.eclipse.jetty.server.handler.RequestLogHandler">
                <Set name="requestLog">
                  <New id="RequestLogImpl" class="org.eclipse.jetty.server.NCSARequestLog">
                    <Set name="filename"><Property name="jetty.logs" default="./logs"/>/yyyy_mm_dd.request.log</Set>
                    <Set name="filenameDateFormat">yyyy_MM_dd</Set>
                    <Set name="retainDays">90</Set>
                    <Set name="append">true</Set>
                    <Set name="extended">false</Set>
                    <Set name="logCookies">false</Set>
                    <Set name="LogTimeZone">GMT</Set>
                  </New>
                </Set>
              </New>
          </Item>
          
           
         </Array>
        </Set>
      </New>
    </Set>

    <!-- =========================================================== -->
    <!-- extra options                                               -->
    <!-- =========================================================== -->
    <Set name="stopAtShutdown">true</Set>
    <Set name="sendServerVersion">false</Set>
    <Set name="sendDateHeader">true</Set>
    <Set name="gracefulShutdown">1000</Set>
    
    <!-- =========================================================== -->
    <!-- add stat handler wrapper                                    -->
    <!-- =========================================================== 
    
    <Get id="oldhandler" name="handler"/>
    <Set name="handler">
     <New id="StatsHandler" class="org.eclipse.jetty.server.handler.StatisticsHandler">
      <Set name="handler"><Ref id="oldhandler"/></Set>
     </New>
    </Set>
    -->
    
    <!-- =========================================================== -->
    <!-- add debug handler wrapper                                   -->
    <!-- =========================================================== 
    
    <Get id="oldhandler" name="handler"/>
    <Set name="handler">
      <New id="DebugHandler" class="org.eclipse.jetty.server.handler.DebugHandler">
        <Set name="handler"><Ref id="oldhandler"/></Set>
        <Set name="outputStream">
          <New class="org.eclipse.jetty.util.RolloverFileOutputStream">
            <Arg type="String"><Property name="jetty.logs" default="./logs"/>/yyyy_mm_dd.debug.log</Arg>
            <Arg type="boolean">true</Arg> 
            <Arg type="int">90</Arg> 
          </New>
        </Set>
      </New>
    </Set>
    -->
    
    <!-- =========================================================== -->
    <!-- add access control wrapper                            -->
    <!-- ===========================================================   >
    
    <Get id="oldhandler" name="handler"/>

    <Set name="handler">
     <New id="IPAccessHandler" class="org.eclipse.jetty.server.handler.IPAccessHandler">
      <Set name="handler"><Ref id="oldhandler"/></Set>
      <Set name="white">
        <Array type="String">
          <Item>127.0.0.1</Item>
          <Item>127.0.0.2/*.html</Item>
        </Array>
      </Set>
      <Set name="black">
        <Array type="String">
          <Item>127.0.0.1/blacklisted</Item>
          <Item>127.0.0.2/black.html</Item>
        </Array>
      </Set>
     </New>
    </Set>
    -->
    
</Configure>

翻译:Facebook的新实时信息系统

您可能已经在某个地方了解到 Facebook 已经推出了新的整合了电子邮件,即时通讯,手机短信,Facebook 站内信的 社会收件箱 的消息。所有的这一切加起来,他们每个月需要存储超过1350亿条消息。 他们用什么存储这些消息呢?Facebook的Kannan Muthukkaruppan给出了一个让人惊讶的回答: 消息系统的底层技术HBase HBase 击败了MySQL,Cassandra,和其他几种备选方案。

为什么惊讶? Facebook 开发了 Cassandra,最初的目的就是用来搭建类似收件箱的应用,但他们发现 Cassandra 的最终一致性模型与新的实时消息系统的要求不相匹配。 Facebook也拥有广泛的 MySQL基础设施,但他们发现当数据集和索引快速增长时,mysql 的性能会受到很大的影响。 他们也可以选择建立自己开发一套系统,但他们没有那么做,而是选择了 HBase。

HBase的是一种 在大数据量下仍支持快速的行级别的更新的可扩展表存储。这正是消息系统所需要的。HBase 是建立在 BigTable的 模型上的,基于列的 key-value 存储。 它擅长于根据 key 获取一行或多行数据,或者扫描数据区间,以及过滤操作。 这也是消息系统需要的 HBase 不支持复杂的查询。 复杂的查询通常由分析工具来完成,比如 Hive,Hive 也是 Facebook 开发的,用来分析他们 PB 级别的数据仓库。Hbase 和 Hive 一样,都使用 Hadoop的文件系统,HDFS。

Facebook 选择 Hbase,是因为他们 分析了消息系统的使用情况,并找出了系统真正需要的特性 他们需要的是一个可以处理两种模式类型的数据的系统:

  1. 一个经常被访问的,不稳定的,小的临时数据集
  2. 一个不断增长的,很少访问的,大的数据集

就这样。 你读过了当前收件箱中的消息,然后很少,如果有的话,会再去看它。这两种模式差别很大,所以人们可能需要两个不同的系统。恰巧的是, HBase 能很好的支持两者。 目前尚不清楚他们是如何处理通用搜索功能的,这是 HBase 的弱点,尽管它能够整合 多种搜索系统

他们的系统的一些关键点:

  • HBase:
    • 比Cassandra简单一致性模型。
    • 对于他们的数据模式来说,HBase 具有很好的扩展性和性能。
    • 功能丰富:自动负载平衡和故障转移,支持压缩,每个服务器上可部署多个分片等
    • HDFS,HBase 使用的文件系统,支持复制,端到端的校验,和自动平衡。
    • Facebook 的运维小组有很多使用HDFS的经验,因为 Facebook 是 Hadoop 的大用户,而 Hadoop 也使用分布式文件系统 HDFS。
  • 使用 Haystack 存储附件。
  • 全新开发的自定义应用服务器,以服务来自不同源的大量消息流入。
  • 基于 ZooKeeper 的用户自动发现服务
  • 提供基础服务:电子邮件帐户验证,朋友关系,个性定义,和交付路由(消息通过聊天还是通过短信发送?)。
  • 保持他们小团队做大事情的传统,目前 15个工程师一年发布20个基础服务
  • Facebook 不会在单一的数据库平台上做标准化,他们使用不同的平台承担不同的任务。

我很惊喜的看到,Facebook 选择 HBase,是因为他们有很多使用 HDFS/ Hadoop/ Hive 的经验。 借着作为另一个很流行的产品的好搭档的方式,来加入它的生态系统,这是任何一个产品都有的梦想 这是 HBase 已经取得的成就。 鉴于 HBase 在持久存储方面涵盖的特性: 实时,分布,线性可扩展,健壮,BigData,开放源码,键值存储,面向列存储, 它将会变得越来越受欢迎,特别是在 Facebook 宣布了他们的选择以后。

原文见:http://highscalability.com/blog/2010/11/16/facebooks-new-real-time-messaging-system-hbase-to-store-135.html

转:图形数据库、NOSQL和Neo4j

简介

众多不同的数据模型里,关系数据模型自80年代就处于统治地位,而且有不少实现,如OracleMySQLMSSQL,它们也被称为关系数据库管理系统(RDBMS)。然而,最近随着关系数据库使用案例的不断增加,一些问题也暴露了出来,这主要是因为两个原因:数据建模中的一些缺陷和问题,以及在大数据量和多服务器之上进行水平伸缩的限制。两个趋势让这些问题引起了全球软件社区的重视:

  1. 在应对这些趋势时,关系数据库产生了更多的问题。这导致大量解决这些问题某些特定方面的不同技术的出现,它们可以与现有RDBMS相互配合或代替它们 – 亦被称为混合持久化(Polyglot Persistence)。数据库替代品并不是新鲜事物,它们已经以对象数据库(OODBMS)、层次数据库(如LDAP)等形式存在很长时间了。但是,过去几年间,出现了大量新项目,它们被统称为NOSQL数据库(NOSQL-databases)用户、系统和传感器产生的数据量呈指数增长,其增长速度因大部分数据量集中在象Amazon、Google和其他云服务这样的分布式系统上而进一步加快。
  2. 数据内部依赖和复杂度的增加,这一问题因互联网、Web2.0、社交网络,以及对大量不同系统的数据源开放和标准化的访问而加剧。

本文旨在介绍图形数据库(Graph Database)在NOSQL运动里的地位,第二部分则是对Neo4j(一种基于Java的图形数据库)的简介。

NOSQL环境

NOSQL(Not Only SQL,不限于SQL)是一类范围非常广泛的持久化解决方案,它们不遵循关系数据库模型,也不使用SQL作为查询语言。

简单地讲,NOSQL数据库可以按照它们的数据模型分成4类:

  1. 键-值存储库(Key-Value-stores)
  2. BigTable实现(BigTable-implementations)
  3. 文档库(Document-stores)
  4. 图形数据库(Graph Database)

VoldemortTokyo Cabinet这类键/值系统而言,最小的建模单元是键-值对。对BigTable的克隆品来讲,最小建模单元则是包含不同个数属性的元组,至于象CouchDBMongoDB这样的文档库,最小单元是文档。图形数据库则干脆把整个数据集建模成一个大型稠密的网络结构。

在此,让我们深入检阅NOSQL数据库的两个有意思的方面:伸缩性和复杂度。

1. 伸缩性

CAP: ACID vs. BASE

为了保证数据完整性,大多数经典数据库系统都是以事务为基础的。这全方位保证了数据管理中数据的一致性。这些事务特性也被称为ACIDA代表原子性、C表示一致性、I是隔离性、D则为持久性)。然而,ACID兼容系统的向外扩展已经表现为一个问题。在分布式系统中,高可用性不同方面之间产生的冲突没有完全得到解决 – 亦称CAP法则:

  • 一致性(C):所有客户端看到的数据是同一个版本,即使是数据集发生了更新 – 如利用两阶段提交协议(XA事务),和ACID,
  • 可用性(A):所有客户端总能找到所请求数据的至少一个版本,即使集群中某些机器已经宕机,
  • 分区容忍性(P):整个系统保持自己的特征,即使是被部署到不同服务器上的时候,这对客户端来讲是透明的。

CAP法则假定向外扩展的3个不同方面中只有两个可以同时完全实现。

为了能处理大型分布式系统,让我们深入了解所采用的不同CAP特征。

很多NOSQL数据库首先已经放宽了对于一致性(C)的要求,以期得到更好的可用性(A)分区容忍性(P)。这产生了被称为BASE基本(B)可用性(A)软状态(S)最终一致性(E))的系统。它们没有经典意义上的事务,并且在数据模型上引入了约束,以支持更好的分区模式(如Dynamo系统等)。关于CAP、ACID和BASE的更深入讨论可以在这篇介绍里找到。

2. 复杂度

蛋白质同源网络(Protein Homology Network),感谢Alex Adai:细胞和分子生物学院 – 德州大学

数据和系统的互联性增加产生了一种无法用简单明了或领域无关(domain-independent)方式进行伸缩和自动分区的稠密数据集,甚至连Todd Hoff也提到了这一问题。关于大型复杂数据集的可视化内容可以访问可视化复杂度(Visual Complexity)

关系模型

在把关系数据模型扔进故纸堆之前,我们不应该忘记关系数据库系统成功的一个原因是遵照E.F. Codd的想法,关系数据模型通过规范化的手段原则上能够建模任何数据结构且没有信息冗余和丢失。建模完成之后,就可以使用SQL以一种非常强大的方式插入、修改和查询数据。甚至有些数据库,为了插入速度或针对不同使用情况(如OLTP、OLAP、Web应用或报表)的多维查询(星形模式),对模式实现了优化。

这只是理论。然而在实践中,RDBM遇到了前面提到的CAP问题的限制,以及由高性能查询实现而产生的问题:联结大量表、深度嵌套的SQL查询。其他问题包括伸缩性、随时间的模式演变,树形结构的建模,半结构化数据,层级和网络等。

关系模型也很难适应当前软件开发的方法,如面向对象和动态语言,这被称为对象-关系阻抗失配。由此,象Java的Hibernate这样的ORM层被开发了出来,而且被应用到这种混合环境里。它们固然简化了把对象模型映射到关系数据模型的任务,但是没有优化查询的性能。尤其是半结构化数据往往被建模成具有许多列的大型表,其中很多行的许多列是空的(稀疏表),这导致了拙劣的性能。甚至作为替代方法,把这些结构建模成大量的联结表,也有问题。因为RDBMS中的联结是一种非常昂贵的集合操作。

图形是关系规范化的一种替代技术

看看领域模型在数据结构上的方案,有两个主流学派 – RDBMS采用的关系方法和图 – 即网络结构,如语义网用到的。

尽管图结构在理论上甚至可以用RDBMS规范化,但由于关系数据库的实现特点,对于象文件树这样的递归结构和象社交图这样的网络结构有严重的查询性能影响。网络关系上的每次操作都会导致RDBMS上的一次”联结”操作,以两个表的主键集合间的集合操作来实现 ,这种操作不仅缓慢并且无法随着这些表中元组数量的增加而伸缩。

属性图形(Property Graph)的基本术语

在图的领域,并没有一套被广泛接受的术语,存在着很多不同类型的图模型。但是,有人致力于创建一种属性图形模型(Property Graph Model),以期统一大多数不同的图实现。按照该模型,属性图里信息的建模使用3种构造单元:

  • 节点(即顶点)
  • 关系(即边) – 具有方向和类型(标记和标向)
  • 节点和关系上面的属性(即特性)

更特殊的是,这个模型是一个被标记和标向的属性多重图(multigraph)。被标记的图每条边都有一个标签,它被用来作为那条边的类型。有向图允许边有一个固定的方向,从末或源节点到首或目标节点。属性图允许每个节点和边有一组可变的属性列表,其中的属性是关联某个名字的值,简化了图形结构。多重图允许两个节点之间存在多条边。这意味着两个节点可以由不同边连接多次,即使两条边有相同的尾、头和标记。

下图显示了一个被标记的小型属性图。

TinkerPop有关的小型人员图

图论的巨大用途被得到了认可,它跟不同领域的很多问题都有关联。最常用的图论算法包括各种类型的最短路径计算测地线(Geodesic Path)、集中度测量(如PageRank、特征向量集中度、亲密度、关系度、HITS等)。然而,在很多情况下,这些算法的应用仅限制于研究,因为实际中没有任何可用于产品环境下的高性能图形数据库实现。幸运的是,近些年情况有所改观。有几个项目已经被开发出来,而且目标直指24/7的产品环境:

下图展示了在复杂度和伸缩性方面背景下的主要NOSQL分类的位置。

关于“规模扩展和复杂度扩展的比较”的更多内容,请阅读Emil Eifrem的博文

Neo4j – 基于Java的图形数据库

Neo4j是一个用Java实现、完全兼容ACID的图形数据库。数据以一种针对图形网络进行过优化的格式保存在磁盘上。Neo4j的内核是一种极快的图形引擎,具有数据库产品期望的所有特性,如恢复、两阶段提交、符合XA等。自2003年起,Neo4j就已经被作为24/7的产品使用。该项目刚刚发布了1.0版 – 关于伸缩性和社区测试的一个主要里程碑。通过联机备份实现的高可用性和主从复制目前处于测试阶段,预计在下一版本中发布。Neo4j既可作为无需任何管理开销的内嵌数据库使用;也可以作为单独的服务器使用,在这种使用场景下,它提供了广泛使用的REST接口,能够方便地集成到基于PHP、.NET和JavaScript的环境里。但本文的重点主要在于讨论Neo4j的直接使用。

开发者可以通过Java-API直接与图形模型交互,这个API暴露了非常灵活的数据结构。至于象JRuby/RubyScalaPythonClojure等其他语言,社区也贡献了优秀的绑定库。Neo4j的典型数据特征:

甚至“传统”RDBMS应用往往也会包含一些具有挑战性、非常适合用图来处理的数据集,如文件夹结构、产品配置、产品组装和分类、媒体元数据、金融领域的语义交易和欺诈检测等。

围绕内核,Neo4j提供了一组可选的组件。其中有支持通过元模型构造图形结构、SAIL – 一种SparQL兼容的RDF TripleStore实现或一组公共图形算法的实现。

要是你想将Neo4j作为单独的服务器运行,还可以找到REST包装器。这非常适合使用LAMP软件搭建的架构。通过memcached、e-tag和基于Apache的缓存和Web层,REST甚至简化了大规模读负荷的伸缩。

高性能?

要给出确切的性能基准数据很难,因为它们跟底层的硬件、使用的数据集和其他因素关联很大。自适应规模的Neo4j无需任何额外的工作便可以处理包含数十亿节点、关系和属性的图。它的读性能可以很轻松地实现每毫秒(大约每秒1-2百万遍历步骤)遍历2000关系,这完全是事务性的,每个线程都有热缓存。使用最短路径计算,Neo4j在处理包含数千个节点的小型图时,甚至比MySQL快1000倍,随着图规模的增加,差距也越来越大。

这其中的原因在于,在Neo4j里,图遍历执行的速度是常数,跟图的规模大小无关。不象在RDBMS里常见的联结操作那样,这里不涉及降低性能的集合操作。Neo4j以一种延迟风格遍历图 – 节点和关系只有在结果迭代器需要访问它们的时候才会被遍历并返回,对于大规模深度遍历而言,这极大地提高了性能。

写速度跟文件系统的查找时间和硬件有很大关系。Ext3文件系统和SSD磁盘是不错的组合,这会导致每秒大约100,000写事务操作。

示例 – 黑客帝国

前面已经说过,社交网络只是代表了图形数据库应用的冰山一角,但用它们来作为例子可以让人很容易理解。为了阐述Neo4j的基本功能,下面这个小型图来自黑客帝国这部电影。该图是用Neo4j的Neoclipse产生的,该插件基于Eclipse RCP

这个图链接到一个已知的引用节点(id=0),这是为了方便的从一个已知起点找到条路进入这个网络。这个节点不是必须的,但实践证明它非常有用。

Java的实现看上去大概是这个样子:

在“target/neo”目录创建一个新的图形数据库

EmbeddedGraphDatabase graphdb = new EmbeddedGraphDatabase("target/neo");

关系类型可以动态创建:

RelationshipType KNOWS = DynamicRelationshipType.withName("KNOWS");

或通过类型安全的Java Enum:

enum Relationships implements RelationshipType { KNOWS, INLOVE, HAS_CODED, MATRIX }

现在,创建2个节点,给每个节点加上“name”属性。接着,把两个节点用一个“KNOWS”关系联系起来:

Node neo = graphdb.createNode();
node.setProperty("name", "Neo");
Node morpheus = graphdb.createNode();
morpheus.setProperty("name", "Morpheus");
neo.createRelationshipTo(morpheus, KNOWS);

任何修改图或需要数据隔离级别的操作要包在事务中,这样可以利用内置的回滚和恢复功能:

Transaction tx = graphdb.beginTx();
try {
	Node neo = graphdb.createNode();
	...
	tx.success();
} catch (Exception e) {
	tx.failure();
} finally {
	tx.finish();
}

创建“黑客帝国”图的完整代码:

graphdb = new EmbeddedGraphDatabase("target/neo4j");
index = new LuceneIndexService(graphdb);
Transaction tx = graphdb.beginTx();
try {
	Node root = graphdb.getReferenceNode();
	// we connect Neo with the root node, to gain an entry point to the graph
	// not neccessary but practical.
	neo = createAndConnectNode("Neo", root, MATRIX);
	Node morpheus = createAndConnectNode("Morpheus", neo, KNOWS);
	Node cypher = createAndConnectNode("Cypher", morpheus, KNOWS);
	Node trinity = createAndConnectNode("Trinity", morpheus, KNOWS);
	Node agentSmith = createAndConnectNode("Agent Smith", cypher, KNOWS);
	architect = createAndConnectNode("The Architect", agentSmith, HAS_CODED);
	// Trinity loves Neo. But he doesn't know.
	trinity.createRelationshipTo(neo, LOVES);
	tx.success();
} catch (Exception e) {
	tx.failure();
} finally {
	tx.finish();
}

以及创建节点和关系的成员函数

private Node createAndConnectNode(String name, Node otherNode,
RelationshipType relationshipType) {
    Node node = graphdb.createNode();
    node.setProperty("name", name);
    node.createRelationshipTo(otherNode, relationshipType);
    index.index(node, "name", name);
    return node;
}

谁是Neo的朋友?

Neo4j的API有一组面向Java集合的方法可轻易地完成查询。这里,只消看看“Neo”节点的关系便足以找出他的朋友:

for (Relationship rel : neo.getRelationships(KNOWS)) {
    Node friend = rel.getOtherNode(neo);
    System.out.println(friend.getProperty("name"));
}
returns "Morpheus" as the only friend.

但是,Neo4j的真正威力源自Traverser-API的使用,它可以完成非常复杂的遍历描述和过滤器。它由Traverser和ReturnableEvaluator组成,前者计算StopEvaluator来获知何时停止,后者则用于在结果中包含哪些节点。此外,你还可以指定要遍历关系的类型和方向。Traverser实现了Java的Iterator接口,负责延迟加载和遍历整个图,在节点被首次要求访问(如for{…}循环)时进行。它还内置了一些常用的Evaluator和缺省值:

Traverser friends = neo.traverse(Order.BREADTH_FIRST,
StopEvaluator.DEPTH_ONE,
ReturnableEvaluator.ALL_BUT_START_NODE, KNOWS, Direction.BOTH);
for (Node friend : friends) {
    System.out.println(friend.getProperty("name"));
}

我们在继续访问更深一级的节点之前首先从起点访问处于同一深度的所有节点(Order.BREADTH_FIRST),在深度为1的一次遍历后停止(StopEvaluator.DEPTH_ONE),然后返回除了起点(”Neo”)之外的所有节点(ReturnableEvaluator.ALL_BUT_START_NODE)。我们在两个方向只遍历类型为KNOWS的关系。这个遍历器再次返回Morpheus是Neo仅有的直接朋友。

朋友的朋友?

为了调查谁是Neo朋友的朋友,KNOWS网络需要再进行深度为2的步骤,由Neo开始,返回Trinity和Cypher。实际编程中,这可以通过调整我们的Traverser的StopEvaluator,限制遍历深度为2来实现:

StopEvaluator twoSteps = new StopEvaluator() {
    @Override
    public boolean isStopNode(TraversalPosition position) {
        return position.depth() == 2;
    }
};

还要定制ReturnableEvaluator,只返回在深度2找到的节点:

ReturnableEvaluator nodesAtDepthTwo = new ReturnableEvaluator() {
    @Override
    public boolean isReturnableNode(TraversalPosition position) {
        return position.depth() == 2;
    }
};

现在“朋友的朋友”遍历器就成了:

Traverser friendsOfFriends = neo.traverse(Order.BREADTH_FIRST,

    twoSteps, nodesAtDepthTwo, KNOWS, Direction.BOTH);
for (Node friend : friendsOfFriends) {
    System.out.println(friend.getProperty("name"));
}

它的结果是Cypher和Trinity。

谁在恋爱?

另一个有趣的问题是,这个图上是否有人正在热恋,比方说从架构师(Architect)开始。

这次,整个图需要沿着由架构师(假定他的节点ID是已知的,但要到很晚才知道)开始的任何关系开始检查,返回拥有向外LOVE关系的节点。一个定制的ReturnableEvaluator可以完成这件事:

ReturnableEvaluator findLove = new ReturnableEvaluator() {
@Override
    public boolean isReturnableNode(TraversalPosition position) {
        return position.currentNode().hasRelationship(LOVES, Direction.OUTGOING);
    }
};

为了遍历所有关系,需要知道整个图的所有关系类型:

List<Object> types = new ArrayList<Object>();
// we have to consider all relationship types of the whole graph
// (in both directions)
for(RelationshipType type : graphdb.getRelationshipTypes()) {
    types.add(type);
    types.add(Direction.BOTH);
}
//let's go!
Traverser inLove = architect.traverse(Order.BREADTH_FIRST,
StopEvaluator.END_OF_GRAPH, findLove, types.toArray());
for (Node lover : inLove) {
    System.out.println(lover.getProperty("name"));
}

上述代码的返回结果只有一个节点:Trinity,因为我们只返回拥有向外LOVE关系的节点。

给图建立索引

尽管沿着所有关系的遍历操作是Neo4j的亮点之一,但也需要在整个图之上进行面向集合的操作。所有节点属性的全文检索就是一个典型的例子。为了不重新发明轮子,Neo4j在这里使用了外部索引系统。针对常见的基于文本的搜索,Neo4j已经跟LuceneSolr进行了深度集成,在Lucene/Solr里增加了给具有事务语义的任意节点属性创建索引的功能。

在黑客帝国的例子里,如给“name”属性创建索引:

GraphDatabaseService graphDb = // a GraphDatabaseService instance

IndexService index = new LuceneIndexService( graphDb );

//create a new node and index the "name" property
Node neo = graphDb.createNode();
neo.setProperty( "name", "Neo" );
index.index( neo, "name", neo.getProperty( "name" ) );

//search for the first node with "name=Neo"
Node node = index.getSingleNode( "name", "Neo" );

Lucene是图的外部索引的一个例子。但是,作为一个快速图形引擎,有大量的策略来构建图本身内部的索引结构,针对特殊数据集和领域缩短遍历模式。例如,有针对一维数据的timeline和B树,给二维数据(在空间和GIS社区非常普遍)建立索引的RTrees和QuadTrees等。另一个常见的有用模式是将重要的子图直接连接到根节点,以创建重要开始节点的快捷路径。

Java太麻烦了。拜托,有没有简短点的?

Neo4j甚至还提供了一组优秀的语言绑定来简化图结构操作。这个例子使用了优秀的Neo4j-JRuby-绑定,它极大地减少了整个代码量:

先安装neo4j gem

>gem install neo4j

这时,整个黑客帝国的图和前面提到的查询,用JRuby代码编写就成了这个样子:

require "rubygems"

require "neo4j"

class Person
  include Neo4j::NodeMixin

  #the properties on the nodes
  property :name

  #the relationship types
  has_n :friends

  # Lucene index for some properties
  index :name
end

#the players

neo       = Person.new :name => 'Neo'
morpheus  = Person.new :name => 'Morpheus'
trinity   = Person.new :name => 'Trinity'
cypher    = Person.new :name => 'Cypher'
smith     = Person.new :name => 'Agent Smith'
architect = Person.new :name => 'Architect'

#the connections

cypher.friends << morpheus
cypher.friends << smith
neo.friends << morpheus
morpheus.friends << trinity
trinity.rels.outgoing(:loves) << neo

architect.rels.outgoing(:has_coded) << smith

#Neos friends

neo.friends.each { |n| puts n }

#Neos friends-of-friends

neo.friends.depth(2).each { |n| puts n }

#Who is in love?
architect.traverse.both(:friends, :has_coded, :loves).depth(:all).filter do
  outgoing(:loves).to_a.size > 0
end.each do |n|
 puts 'In love: ' + n.name
end

图编程语言 – Gremlin

直到最近,还没有任何查询语言涉及大型的图领域和图相关项目。在语义网/RDF领域,有SPARQL,受SQL启发的查询语言,专注于描述用来匹配元组集合的样本图。但是,大量的图并不兼容RDF,而且采用不同或更侧重于更实用的方式进行数据建模,象本文中的黑客帝国例子,以及其他领域特定的数据集。其他查询语言都是面向JSON的,如MQL,一种用于Freebase的查询语言。这些语言只工作于它们自己定义的数据模型,完全不支持或只非常有限地支持深度图算法和启发式分析方法,而这又是当今大型图里不可或缺的内容。

至于针对各种图数据模型(如RDF)的更复杂有趣的查询,Gremlin – 一种面向XPath,图灵完备的图形编程语言 – 正由TinkerPop团队开发,主要由Marko A. Rodriguez推动。借助引入属性图模型,它创造了一个针对现有大多数模型的超集,以及最小的公共操作集合。此外,它允许连接其他图形框架(如Gremlin使用JUNG),同时支持在不同的图实现上都能表达图的遍历。已支持的一组实现包括,从简单的如内存中的TinkerGraph,到其他通过针对AllegroGraphSesameThinkerPop LinkedData SAIL(最开始由Josh ShinavierRipple编程语言开发)的RDF-SAIL适配器,一直到Neo4j。

Gremlin的语法建立在XPath基础之上,这是为了可以简单地表达整个图的深度路径描述。很多简单的例子几乎就像普通的XPath。

安装Gremlin在线试用之后,黑客帝国例子里的图的Gremlin会话大致是:

peterneubauer$ ~/code/gremlin/gremlin.sh

         ,,,/
         (o o)
-----oOOo-(_)-oOOo-----
gremlin> #open a new neo4j graph as the default graph ($_g)
gremlin> $_g := neo4j:open('tmp/matrix')
==>neo4jgraph[tmp/matrix]
gremlin> #the vertices
gremlin> $neo := g:add-v(g:map('name','Neo'))
==>v[1]
gremlin> $morpheus := g:add-v(g:map('name','Morpheus'))
==>v[2]
gremlin> $trinity := g:add-v(g:map('name','Trinity'))
==>v[3]
gremlin> $cypher := g:add-v(g:map('name','Cypher'))
==>v[4]
gremlin> $smith := g:add-v(g:map('name','Agent Smith'))
==>v[5]
gremlin> $architect := g:add-v(g:map('name','The Architect'))
==>v[6]
gremlin> #the edges
gremlin> g:list($cypher,$neo,$trinity)[g:add-e($morpheus,'KNOWS',.)]
==>v[4]
==>v[1]
==>v[3]
gremlin> g:add-e($cypher,'KNOWS',$smith)
==>e[3][4-KNOWS->5]
gremlin> g:add-e($trinity,'LOVES',$neo)
==>e[4][3-LOVES->1]
gremlin> g:add-e($architect,'HAS_CODED',$smith)
==>e[5][6-HAS_CODED->5]
gremlin> #go to Neo as the current root ($_) via a full-text index search
gremlin> $_ := g:key('name','Neo')
==>v[1]
gremlin> #is this Neo?
gremlin> ./@name
==>Neo
gremlin> #what links to here and from here?
gremlin> ./bothE
==>e[0][1-KNOWS->2]
==>e[4][3-LOVES->1]
gremlin> #only take the KNOWS-edges
gremlin> ./bothE[@label='KNOWS']
==>e[0][1-KNOWS->2]
gremlin> #Neo's friend's names
gremlin> ./bothE[@label='KNOWS']/inV/@name
==>Morpheus
gremlin>

gremlin> #Neo's Friends of friends, 2 steps
gremlin> repeat 2
               $_ := ./outE[@label='KNOWS']/inV
           end
==>v[4]
==>v[3]
gremlin> #What are their names?
gremlin> ./@name
==>Cypher
==>Trinity
gremlin> #every node in the whole graph with an outgoing LOVES edge
gremlin> $_g/V/outE[@label='LOVES']/../@name
==>Trinity

深度图算法 – 关系的价值

鉴于Gremlin的能力,黑客帝国的例子显得相当幼稚。更有趣的是开发和测试大型图上的算法。象特征向量集中度和Dijkstra这类穷举算法并不会扩展到这些图上,因为它们需要了解网络里的每个顶点。对于针对这些问题的如基于语法的随机访问器扩散激活Marko Rodriguez这里有更深入的解释)这类概念,启发式方法更合适。Google PageRank算法就是启发式的,而且可以用Gremlin建模,代码如下(Greatful Dead的歌曲、演唱会和相册图的一个例子,图从这里装入,2500个循环,每次重复能量损失15%):

$_g := tg:open()

g:load('data/graph-example-2.xml')

$m := g:map()

$_ := g:key('type', 'song')[g:rand-nat()]

repeat 2500

  $_ := ./outE[@label='followed_by'][g:rand-nat()]/inV

  if count($_) > 0

    g:op-value('+',$m,$_[1]/@name, 1.0)

  end

  if g:rand-real() > 0.85 or count($_) = 0

    $_ := g:key('type', 'song')[g:rand-nat()]

  end

end

g:sort($m,'value',true())

它返回如下的歌曲权重列表:

==>DRUMS=44.0
==>PLAYING IN THE BAND=38.0
==>ME AND MY UNCLE=32.0
==>TRUCKING=31.0
==>CUMBERLAND BLUES=29.0
==>PROMISED LAND=29.0
==>THE MUSIC NEVER STOPPED=29.0
==>CASSIDY=26.0
==>DARK STAR=26.0
==>NOT FADE AWAY=26.0
==>CHINA CAT SUNFLOWER=25.0
==>JACK STRAW=25.0
==>TOUCH OF GREY=24.0
==>BEAT IT ON DOWN THE LINE=23.0
==>BERTHA=23.0

其底层图的另一个有趣的例子是LinkedData图,在互联网上可在线了解:LinkedData和DBPedia的音乐推荐算法

总结

就像RDBMS和其他持久化解决方案一样,图不是解决所有问题的银弹。数据才是最重要的东西,它是关键,然后是查询类型、要处理的操作结构,以及什么需求要考虑伸缩性和CAP。

将采用NOSQL数据库的高伸缩性方面作为使用非关系解决方案的唯一考量往往是不必要的,而且也不符合预期。使用Neo4j和当今的硬件,大多数情况下,完全可以在单实例里容纳整个领域模型和查询数十亿领域对象。

如果那还不够,总是有办法引入针对领域优化过的数据分区概念,无需引入文档或键/值系统的硬数据建模限制。最终导致的结果是一个文档模型、或领域特定的“对象数据库”还是其他模型则取决于领域上下文和应用场景。

本文的代码可以从这里下载。

我要感谢Michael HungerMarko Rodriguez给我提供了优秀的反馈和有帮助的建议。

作者简介

Peter Neubauer是Neo Technology的COO,他同时还是几个基于Java和图开源项目的合伙创办人,如Neo4jGremlinLinkedProcessOPS4JQi4j。你可以通过peter@neotechnology.com.联系到Peter。

转:免费电子书列表

原帖的地址在stackoverflow.com

List of Free Programming books (compiled):

Graphics Programming

Language Agnostic

ASP.NET MVC:

Assembly Language

Bash

C/C++

C#

  • See .NET below

Django

Forth

Git

Haskell

Java

JavaScript

Linux

Lisp

Lua

Maven

Mercurial

.NET (C#)

NoSQL

Objective-C

Parrot / Perl 6

Perl

PHP

PowerShell

Prolog

PostgreSQL

Python

Ruby

Scala

Scheme

SmallTalk

Subversion

*SQL (Implementation agnostic) *

Vim

学习:一个并发的Cache

public class Memoizer implements Computable {
    private final ConcurrentMap<A, Future> cache
        = new ConcurrentHashMap<A, Future>();
    private final Computable c;

    public Memoizer(Computable c) { this.c = c; }

    public V compute(final A arg) throws InterruptedException {
        while (true) {
            Future f = cache.get(arg);
            if (f == null) {
                Callable eval = new Callable() {
                    public V call() throws InterruptedException {
                        return c.compute(arg);
                    }
                };
                FutureTask ft = new FutureTask(eval);
                f = cache.putIfAbsent(arg, ft); //先把FutureTask放进去再说
                if (f == null) { f = ft; ft.run(); } //开始计算
            }
            try {
                return f.get();
            } catch (CancellationException e) {
                cache.remove(arg, f);
            } catch (ExecutionException e) {
                throw launderThrowable(e.getCause());
            }
        }
    }
}

继续阅读“学习:一个并发的Cache”

转:netty 中文手册

原文地址:http://docs.jboss.org/netty/3.1/guide/html_single/

The Netty Project 3.1 User Guide
The Proven Approach to Rapid Network Application Development

3.1.5.GA, r1772

序言
1. 问题
2. 方案 

第一章. 开始
1.1. 开始之前
1.2. 抛弃协议服务
1.3. 查看接收到的数据
1.4. 响应协议服务
1.5. 时间协议服务
1.6. 时间协议服务客户端 
1.7. 流数据的传输处理   
1.7.1. Socket Buffer的缺陷  
1.7.2. 第一种方案 
1.7.3. 第二种方案
1.8. 使用POJO代替ChannelBuffer
1.9. 关闭你的应用
1.10. 总述 

第二章. 架构总览
2.1. 丰富的缓冲实现 
2.2. 统一的异步 I/O API 
2.3. 基于拦截链模式的事件模型 
2.4. 适用快速开发的高级组件
2.4.1. Codec框架
2.4.2. SSL / TLS 支持 
2.4.3. HTTP实现
2.4.4. Google Protocol Buffer 整合 
2.5. 总述 

序言
本指南对Netty 进行了介绍并指出其意义所在。

1. 问题
现在,我们使用适合一般用途的应用或组件来和彼此通信。例如,我们常常使用一个HTTP客户端从远程服务器获取信息或者通过web services进行远程方法的调用。

然而,一个适合普通目的的协议或其实现并不具备其规模上的扩展性。例如,我们无法使用一个普通的HTTP服务器进行大型文件,电邮信息的交互,或者处理金 融信息和多人游戏数据那种要求准实时消息传递的应用场景。因此,这些都要求使用一个适用于特殊目的并经过高度优化的协议实现。例如,你可能想要实现一个对 基于AJAX的聊天应用,媒体流或大文件传输进行过特殊优化的HTTP服务器。你甚至可能想去设计和实现一个全新的,特定于你的需求的通信协议。

另一种无法避免的场景是你可能不得不使用一种专有的协议和原有系统交互。在这种情况下,你需要考虑的是如何能够快速的开发出这个协议的实现并且同时还没有牺牲最终应用的性能和稳定性。

2. 方案
Netty 是一个异步的,事件驱动的网络编程框架和工具,使用Netty 可以快速开发出可维护的,高性能、高扩展能力的协议服务及其客户端应用。

也就是说,Netty 是一个基于NIO的客户,服务器端编程框架,使用Netty 可以确保你快速和简单的开发出一个网络应用,例如实现了某种协议的客户,服务端应用。Netty相当简化和流线化了网络应用的编程开发过程,例如,TCP和UDP的socket服务开发。

“快速”和“简单”并不意味着会让你的最终应用产生维护性或性能上的问题。Netty 是一个吸收了多种协议的实现经验,这些协议包括FTP,SMPT,HTTP,各种二进制,文本协议,并经过相当精心设计的项目,最终,Netty 成功的找到了一种方式,在保证易于开发的同时还保证了其应用的性能,稳定性和伸缩性。

一些用户可能找到了某些同样声称具有这些特性的编程框架,因此你们可能想问Netty 又有什么不一样的地方。这个问题的答案是Netty 项目的设计哲学。从创立之初,无论是在API还是在其实现上Netty 都致力于为你提供最为舒适的使用体验。虽然这并不是显而易见的,但你终将会认识到这种设计哲学将令你在阅读本指南和使用Netty 时变得更加得轻松和容易。

继续阅读“转:netty 中文手册”

转:Cassandra – 一个分散的非结构化存储系统

本文翻译自Facebook员工在LADIS大会上发布的论文.Cassandra – A Decentralized Structured Storage System
这篇论文中,两位作者详细介绍了Cassandra的系统架构,它的设计初衷,设计应用时使用到的相关技术,以及设计/实现/使用过 程中得到的经验教训.

Cassandra – 一个分散的非结构化存储系统
By Avinash Lakshman Facebook ,Prashant Malik Facebook; Translated By Jametong

概要

Cassandra是一个分布式的存储系统,可用来管理分布在大量廉价服务器上的巨量结构化数据,并同时提供没有单点故障的高 可用服务.Cassandra的设计目的是运行在由几百个节点(可能分布在多个不同的数据中心)组成的基础设施(infrastructure) 上.当节点达到这个规模时,大大小小的组件出现故障就可能经常发生了.Cassandra在管理持久状态时面临这些故障,这 种情况也驱动软件系统的可靠性(reliability)与可伸缩性(scalability)会依赖于Cassandra的服务. 虽然大部分情况,Cassandra看上去像一个数据库系统, 也与数据库系统共享大量的设计与实现手段,但是Cassandra并 不支持完整的关系数据模型;相反,它提供了一个简单数据模型的客户端,支持对数据布局与数据格式的动态控制.我们设计 Cassandra的初衷是,可以运行在廉价硬件上,并能在不牺牲读效率的情况下实现高的写吞吐量.

1. 导论

Facebook维护着世界上最大的社交网络平台,利用分布在世界各地的大量数据中心的成千上万台服务器,为上亿的用户提供服 务.Facebook平台有严格的业务要求,包含性能、可靠性、效率以及高度的可伸缩性以支持平台的持续增长.在一个包含 成千上万的组件的基础设施上处理故障是我们的标准运作模式;在任何时候,随时都可能出现相当数量的服务器或网络组件故障.这样,软 件系统在构建时就需要将故障当作一种常态而不是异常来处理.为了满足上面描述的这些可靠性与可伸缩性,Facebook开发了 Cassandra系统.
为了实现可伸缩性与可靠性,Cassandra组合了多项众所周知的技术.我们设计Cassandra的最初目的是解决收件箱搜索的 存储需要.在Facebook,这意味着这个系统需要能够处理非常大的写吞吐量,每天几十亿的写请求,随着用户数的规模而 增长.由于我们是通过在地理上分布的数据中心对用户进行服务的,因此支持跨越多个数据中心的数据复制对于降低搜索延时就非常关键了. 当我们在2008年6月发布收件箱搜索项目时,我们有1亿的用户,现在我们差不多有2.5亿的用户,Cassandra一直保持了其 对业务的承诺.目前,Facebook内部已经有多个服务部署了Cassandra作为其后端存储系统.
本文的结构如下.第2节讨论相关研究,其中的部分研究对我们的设计有很大影响.第3节介绍详细的数据模型.第4节简要介绍客户端 API.第5节介绍系统设计以及Cassandra中应用到的分布式算法.第6节介绍我们如何使用Cassandra部署 Facebook平台的一个应用.

2. 相关研究

对于为了性能、可用性与数据持久性对数据进行分布,文件系统与数据库社区已经进行了广泛的研究.与仅支持扁平命名空间 (namespace)的点对点(P2P)存储系统相比,分布式文件系统通常支持层次化(hierarchical)的命名空间.与 Ficus[14]与Coda[16]类似的系统都是通过牺牲一致性来复制文件以实现高可用(high availability).通常使用特别的冲突解决(conflict resolution)程序来管理更新冲突(update conflict). Farsite[2]是一个没有使用任何中心服务器的分布式文件系统. Farsite使用复制来实现高可用性与可伸缩性.Google文件系统(GFS)[9]是另一个分布式文件系统,用来存储 Google内部应用的各种状态数据.GFS设计比较简单,用一台主服务器存储所有的元数据(metadata),数据拆分成块 (chunk)存储在多个块服务器(chunk server)上.不过,目前Google已经使用Chubby[3]抽 象层为GFS的主服务器做了容错处理(fault tolerant).Bayou[18]是一个分布式的关系数据库系统,它支持断开操作(个 人理解为网络断开以后的操作)并提供最终的数据一致性(eventual data consistency).在这些系统中,Bayou、Coda 与Ficus允许断开操作,并且在遇到类似与网络断开与停机时能够做到自动复原.这些系统在冲突解决程序上存在差异.例如,Coda 与Ficus执行系统级别的冲突解决,而Bayou允许应用级别的冲突解决.但所有这些都保证最终一致性(eventual consistency).与这些系统类似,即使在网络段开的时候,Dynamo[6]也允许进行读写操作,并使用不同的冲突解决机 制(部分客户端驱动)来解决更新冲突.传统的基于复制的关系数据库系统重点在保证复制数据的强一致性(strong consistency).虽然强一致性为应用写程序提供了一个方便的编程模型,但是,这些系统在伸缩性与可用性方面却受到了限制.因 为这些系统提供强一致性的保证,所以在网络分开时,它们就无法进行处理.
Dynamo[6]是一个Amazon开发的存储系统,Amazon用它来存储检索用户的购物车.Dynamo利用基于Gossip 的会员算法来维护每个节点上所有其他节点的信息.可以认为Dynamo是一个只支持一跳路由请求(one-hop request routing)的结构化覆盖层(structured overlay).Dynamo使用一个向量时钟(vector lock)概要来发现更新冲突,但偏爱客户端的冲突解决机制.为了管理向量时间戳(vector timestamp),Dynamo 中的写操作同时也需要执行一次读操作.在一个需要处理非常大的写吞吐量的系统中,这可能会成为瓶颈. Bigtable[4]既提供了结构化也支持数据的分布式,不过它依赖于一个分布式的文件系统来保证数据的持久化.

3. 数据模型

Cassandra中的表是一个按照主键索引的分布式多维图.它的值是一个高度结构化的对象.表中的记录键是一个没有大小限制 的字符串,虽然它通常都只有16-36个字节的长度.无论需要读写多少列,单一记录键的每个副本的每次操作都是一个原子操作.多 个列可以组合在一起形成一个称为column family的列的集合,这一点与Bigtable[4]系统非常相似.Cassandra提供 两种类型的column family,简单的column family与超级的column family.可以将超级column family想象成column family里面嵌入column family.进一步,应用还可以指定超级column family或者简单column family里面的列的排序顺序.系统允许按时间或者名称对列进行排序.按照时间对列进行排序可 以被类似于收件箱搜索这样的应用使用,因为它们的结果始终需要按照时间顺序进行展示.column family中的每个列都需要通过规范column family : column来进行访问,每个超级column family中的列都通过规范column family : super column : column来进行访问.小节6.1给出了一个 展示超级column family抽象能力的非常好的例子.通常,应用都会使用一个独占的Cassandra集群,并将它们当作服 务的一部分进行管理.虽然,Cassandra系统支持多表的概念,在部署时每个概要中都只能有一个表.

4. API

Cassandra的API由下面三种方法组成.

  • insert(table, key, rowMutation)
  • get(table, key, columnName)
  • delete(table, key, columnName) 列名可以是column family里面的一个特定列,或column family,或超级column family,或超级列里面的一个列

5. 系统架构
一个需要在生产环境运转的存储系统的架构是很复杂的.除了真实的数据持久化组件外,这个系统还需要包含以下特性;可伸缩性与强大负载 均衡解决方案、会员与故障检测、故障恢复、副本同步、超负荷处理、状态转移、并发与任务调度、请求编组、请求路由、系统监控与报警以 及配置管理.详细描述这里的每一个解决方案超出了本论文的范围,我们将集中介绍Cassandra使用的核心的分布式系统技术:分 区、复制、会员、故障处理以及伸缩性.处理读写请求需要所有这些模块的协同处理.通常,一个键的请求可能被路由到Cassandra 集群的任何一个节点去处理.这个节点会确定这个特定的键的副本.对于写操作来讲,系统会将请求路由到副本上,并且等待仲裁 数量的副本以确认写操作完成.对于读操作来讲,基于客户端要求的一致性保证,系统要么将请求路由到最近的副本,要么将请求路由到所有 的副本并等待达到仲裁数量的响应.

继续阅读“转:Cassandra – 一个分散的非结构化存储系统”