Java性能优化全攻略

来自:慧都控件网

链接:https://www.evget.com/article/2016/5/17/24105.html

原文:http://www.oracle.com/technetwork/java/javaseproducts/mission-control/java-mission-control-wp-2008279.pdf

让Java应用程序运行是一回事,但让他们跑得快就是另外一回事了。在面对对象的环境中,性能问题就像来势凶猛的野兽。但JVM的复杂性将性能调整的复杂程度增加了一个级别。这里Refcard涵盖了JVM internals、class loading(Java8中更新以映射最新的元空间)、垃圾回收、故障诊断、检测、并发性,等等。

介绍

Java是目前软件开发领域中使用最广泛的编程语言之一。Java应用程序在许多垂直领域(银行、电信、医疗保健等)中都有广泛使用。Refcard的目的是,帮助开发者通过专注于JVM内部,性能调整原则和最佳实践,以及利用现有监测和故障诊断工具,来提升应用程序在商业环境中的性能。

它能以不同的方式定义“optimal performance(最佳性能)”,但基本要素是:Java程序在业务响应时间要求内执行计算任务的能力,程序在高容量下执行业务功能的能力,并具有可靠性高和延迟低的特点。有时,数字本身变得模式化:对于一些大型网站,优秀的页面响应时间应该在500ms以下。在适当的时候,Refcard包括目标数字。但在大多数情况下,您需要根据业务需求和现有的性能基准自己决定这些。

JVM Internals

基础知识

代码编译和JIT

编译Java字节码显然没有直接从主机执行本机代码那么快。为了提高性能,Hotspot JVM找出最繁忙的字节码区域,然后将其编译成更高效地原生、机器代码(自适应优化)。然后这种本地代码就会存储在非堆内存中的代码缓存中。

注意:多数的JVM是通过禁用JIT编译器实现的(Djava.compiler=NONE)。您只需要考虑禁用的关键性优化,比如JVM崩溃。

下图说明了Java源代码,即时编译流程和生命周期。

内存空间

HotSpot Java Virtual Machine是由以下的存储空间组成。

类加载

Java的另一个重要特点是,在JVM启动之后,它能够加载编译的Java类(字节码)。根据程序的大小,在刚刚重启之后,程序在类加载过程中性能会显著降低。这种现象是因为内部JIT编译器在重启之后需要重新开始优化。

自JDK 1.7版本之后,有一些改进值得大家重视。例如默认的JDK class loader具有更好的装在类并发能力。

热点


故障诊断和监视

垃圾回收

Java垃圾回收流程对于程序性能是至关重要的。为了提供有效的垃圾回收,Heap(堆)本质上是划分在子区域中。

堆区域


GC Collectors

选择正确的collector或GC policy可以将程序的性能、可扩展性和可靠性优化到最佳状态。许多应用程序对于响应时间延迟都很敏感,因此大多需要使用并发的回收器,例如HotSpot CMS或IBM GC policy balanced。

我们强烈建议您通过适当的性能和负载测试确定最合适的GC策略。应该在生产环境中执行全面监控策略,以跟踪整体的JVM性能,并确定在之后需要改进的领域。



Garbage First (G1) Collector

HotSpot G1 collector是专为是专为满足用户定义的垃圾回收(GC)高概率暂停时间设计的,同时实现高吞吐量。

最新的HotSpot collector将heap基本划分到一组大小相等的堆区域,虚拟内存的每个区域连续范围。它将回收压缩的活动集中在heap区域,那里充满了可回收的对象(garbage first)。换句话说就是,这个区域有最低限度的“live”对象。

Oracle建议在以下例子和情况下使用G1 collector,尤其是对于目前正在使用CMS或parallel collectors的:

  • 专为large heaps(>= 6 GB),并限制GC延迟(暂停时间<= 0.5秒)的应用程序设计。
  • 超过50%的Java heap被实时数据占用(对象不能被GC回收)。
  • 对象分析率和促进作用显著变化。
  • 不期望过长的垃圾回收或压缩停顿(超过0.5至1秒)。

Java Heap尺寸

你一定要知道没有GC策略可以挽救Java Heap尺寸不足的现象。这些演习涉及到为不同的存储空间(包括新旧不同的版本)配置最大和最小的容量,包括元数据和本地内存容量。这里有一些建议准则:

  • 在32-bit或64-bit JVM之间进行明智的选择。如果程序运行需要超过2GB内存,并且JVM暂停时间在可接受范围内,可以考虑使用64-bit JVM。
  • 永远将应用程序放在第一考虑。确保将其配置好,并根据程序的内存占用量调整heap尺寸。建议通过性能和负载测试来衡量实时数据占有量。
  • larger heap并不总是表现得更好、更快,因此不需要过度调整Java heap。并行中的JVM性能调优,找准机会减少或“spread”程序的内存占有量,以保证JVM的平均响应时间<1%。
  • 对于32-bit JVM,为了从元数据和本地heap中留出一些内存,考虑2GB的最大heap尺寸。
  • 对于64-bit JVM,我们要想办法在垂直和水平层面进行扩展,而不是试图将Java heap尺寸增加到15GB以上。这种做法往往提供更好的吞吐量,更好地利用硬件,提高应用程序的故障切换功能。
  • 不许重复开发:充分利用开源以及商业故障排除的优势和监控工具,使这些变成可能。APM(应用性能管理)产品在过去十年里发展迅猛。

JDK 1.8 Metaspace指南

Hot Spots

故障诊断和监视



Java并发性

Java并发性可以定义为程序同时执行多个任务的能力。对于大型的Java EE系统,这意味着执行多个用户的业务功能的同时,实现最佳的吞吐量和性能的能力。

无论是硬件能力还是JVM稳定状况,Java并发性问题可能引起程序的瘫痪,严重影响程序的整体性能和可用性。

Thread Lock Contention

当您评估Java应用程序的并发线程的稳定状况时,你会经常遇到Thread lock contention的问题,这是目前最常见的Java并发问题。

例如:Thread lock contention会触发non-stop,它会尝试将一个缺少Java类(ClassNotFoundException的)加载到默认的JDK 1.7 ClassLoader。

如果您在成熟的技术环境中遇见像Thread Dump analysis这样的问题,我们强烈建议您积极面对它。这个问题的根源通常不同于之前的Java synchronization to legitimate IO blocking或者其他的non-thread safe calls。Lock contention问题往往是另一个问题的“症状”。

Java-level Deadlocks

真正的Java-level deadlocks是不太常见的,它同样可以极大程度地影响应用程序的性能和稳定性。当遇到两个或多个线程永远阻塞的时候,就会触发这样的问题。这种情况不同于其他常见的那种“day-to-day”线程问题,例如 lock contention、threads waiting on blocking IO calls等等。真正的lock-ordering deadlock问题可以被看做如下:

Oracle HotSpot 和IBM JVM为大多数的deadlock detectors情况提供了解决方案,帮助您快速找出造成这种状况的罪魁祸首的线程。遇到类似lock contention troubleshooting的问题,建议从诸如线程转储分析为出发点来解决该问题。

一旦找到造成问题的代码根源,解决方案涉及lock-ordering条件寻址和来自JDK其他可用的并发编程技术,如java.util.concurrent.locks.ReentrantLock,提供了诸如tryLock()的方法。这种方法给予开发人员更大的灵活性,也为防止deadlock和thread lock “starvation”提供了更多方式。

Clock Time和CPU Burn

在进行JVM调优的同时,也有必要检查应用程序的行为,更确切地说是最高clock time和CPU burn的贡献者。

当Java垃圾回收和线程并发不再是压力点,深入到你的应用程序代码的执行模式,并专注于顶级响应时间贡献者(也叫作clock time)是很重要的。检查应用程序代码的消CPU耗和Java 线程(CPU burn)也同样至关重要。CPU使用率较高(>75%)是不正常的(良好的物理资源的利用率)。因为这往往意味着效率低下和容量问题。对于大型的Java EE企业应用,保持安全的CPU缓冲区是必要的,以应对突发的负载冲击情况。

摒弃那些传统的跟踪方法,如在代码中加入响应时间“日志”。Java剖析工具和APM解决方案恰恰可以帮助您分析这类型的问题。这种方式更加高效、可靠。对于Java生产环境缺乏一个强大的APM解决方案。您仍然可以依赖诸如Java VisualVM的工具,通过多个快照进行thread dump分析,并使用OS CPU分析每个线程。

最后的建议是,不要妄图同时解决所有的问题。列出排在最前面的5个clock time和CPU burn问题,然后寻找解决方案。

Application预算

其他关于Java应用程序性能的重要方面是稳定性和可靠性。在有着99.9%典型可用目标的SLA umbrella下,稳定和可靠对于程序的操作尤为重要。这些系统应该具有高容错级别,并对应用和资源进行严格的预算,以防止发生多米诺效应。用这种方法可以防止一些这样的情况,例如,一个业务流程使用所有可用的物理,中间件或JVM资源。

Hot Spots

超时管理

Java application与外部系统之间缺乏合理的超时时间,由于中间件和JVM线程消耗(blocking IO calls),可能导致严重的性能下降和中断。合理的超时时间可以避免在遇到外部服务提供商速度缓慢的时候,Java线程等待太久。

工具



详解Java定时任务

来自:博客园

作者: chenssy 

链接: http://www.cnblogs.com/chenssy/p/3788407.html

在我们编程过程中如果需要执行一些简单的定时任务,无须做复杂的控制,我们可以考虑使用JDK中的Timer定时任务来实现。下面LZ就其原理、实例以及Timer缺陷三个方面来解析Java Timer定时器。

一、简介

在Java中一个完整定时任务需要由Timer、TimerTask两个类来配合完成。 API中是这样定义他们的,Timer:一种工具,线程用其安排以后在后台线程中执行的任务。可安排任务执行一次,或者定期重复执行。由TimerTask:Timer 安排为一次执行或重复执行的任务。我们可以这样理解Timer是一种定时器工具,用来在一个后台线程计划执行指定任务,而TimerTask一个抽象类,它的子类代表一个可以被Timer计划的任务。

Timer类

在工具类Timer中,提供了四个构造方法,每个构造方法都启动了计时器线程,同时Timer类可以保证多个线程可以共享单个Timer对象而无需进行外部同步,所以Timer类是线程安全的。但是由于每一个Timer对象对应的是单个后台线程,用于顺序执行所有的计时器任务,一般情况下我们的线程任务执行所消耗的时间应该非常短,但是由于特殊情况导致某个定时器任务执行的时间太长,那么他就会“独占”计时器的任务执行线程,其后的所有线程都必须等待它执行完,这就会延迟后续任务的执行,使这些任务堆积在一起,具体情况我们后面分析。

当程序初始化完成Timer后,定时任务就会按照我们设定的时间去执行,Timer提供了schedule方法,该方法有多中重载方式来适应不同的情况,如下:

schedule(TimerTask task, Date time):安排在指定的时间执行指定的任务。

schedule(TimerTask task, Date firstTime, long period) :安排指定的任务在指定的时间开始进行重复的固定延迟执行。

schedule(TimerTask task, long delay) :安排在指定延迟后执行指定的任务。

schedule(TimerTask task, long delay, long period) :安排指定的任务从指定的延迟后开始进行重复的固定延迟执行。

同时也重载了scheduleAtFixedRate方法,scheduleAtFixedRate方法与schedule相同,只不过他们的侧重点不同,区别后面分析。

scheduleAtFixedRate(TimerTask task, Date firstTime, long period):安排指定的任务在指定的时间开始进行重复的固定速率执行。

scheduleAtFixedRate(TimerTask task, long delay, long period):安排指定的任务在指定的延迟后开始进行重复的固定速率执行。

TimerTask

TimerTask类是一个抽象类,由Timer 安排为一次执行或重复执行的任务。它有一个抽象方法run()方法,该方法用于执行相应计时器任务要执行的操作。因此每一个具体的任务类都必须继承TimerTask,然后重写run()方法。

另外它还有两个非抽象的方法:

boolean cancel():取消此计时器任务。

long scheduledExecutionTime():返回此任务最近实际执行的安排执行时间。

二、实例

2.1、指定延迟时间执行定时任务

public class TimerTest01 {

Timer timer;

public TimerTest01(int time){

timer = new Timer();

timer.schedule(new TimerTaskTest01(), time * 1000);

}

public static void main(String[] args) {

System.out.println(“timer begin….”);

new TimerTest01(3);

}

}

public class TimerTaskTest01 extends TimerTask{

public void run() {

System.out.println(“Time’s up!!!!”);

}

}

运行结果:

首先打印:timer begin….3秒后打印:Time’s up!!!!

2.2、在指定时间执行定时任务

public class TimerTest02 {

Timer timer;

public TimerTest02(){

Date time = getTime();

System.out.println(“指定时间time=” + time);

timer = new Timer();

timer.schedule(new TimerTaskTest02(), time);

}

public Date getTime(){

Calendar calendar = Calendar.getInstance();

calendar.set(Calendar.HOUR_OF_DAY, 11);

calendar.set(Calendar.MINUTE, 39);

calendar.set(Calendar.SECOND, 00);

Date time = calendar.getTime();

return time;

}

public static void main(String[] args) {

new TimerTest02();

}

}

public class TimerTaskTest02 extends TimerTask{

@Override

public void run() {

System.out.println(“指定时间执行线程任务…”);

}

}

当时间到达11:39:00时就会执行该线程任务,当然大于该时间也会执行!!执行结果为:

指定时间time=Tue Jun 10 11:39:00 CST 2014指定时间执行线程任务…

2.3、在延迟指定时间后以指定的间隔时间循环执行定时任务

public class TimerTest03 {

Timer timer;

public TimerTest03(){

timer = new Timer();

timer.schedule(new TimerTaskTest03(), 1000, 2000);

}

public static void main(String[] args) {

new TimerTest03();

}

}

public class TimerTaskTest03 extends TimerTask{

@Override

public void run() {

Date date = new Date(this.scheduledExecutionTime());

System.out.println(“本次执行该线程的时间为:” + date);

}

}

运行结果:

本次执行该线程的时间为:Tue Jun 10 21:19:47 CST 2014本次执行该线程的时间为:Tue Jun 10 21:19:49 CST 2014本次执行该线程的时间为:Tue Jun 10 21:19:51 CST 2014本次执行该线程的时间为:Tue Jun 10 21:19:53 CST 2014本次执行该线程的时间为:Tue Jun 10 21:19:55 CST 2014本次执行该线程的时间为:Tue Jun 10 21:19:57 CST 2014……………..

对于这个线程任务,如果我们不将该任务停止,他会一直运行下去。

对于上面三个实例,LZ只是简单的演示了一下,同时也没有讲解scheduleAtFixedRate方法的例子,其实该方法与schedule方法一样!

2.4、分析schedule和scheduleAtFixedRate

1、schedule(TimerTask task, Date time)、schedule(TimerTask task, long delay)

对于这两个方法而言,如果指定的计划执行时间scheduledExecutionTime<= systemCurrentTime,则task会被立即执行。scheduledExecutionTime不会因为某一个task的过度执行而改变。 2、schedule(TimerTask task, Date firstTime, long period)、schedule(TimerTask task, long delay, long period) 这两个方法与上面两个就有点儿不同的,前面提过Timer的计时器任务会因为前一个任务执行时间较长而延时。在这两个方法中,每一次执行的task的计划时间会随着前一个task的实际时间而发生改变,也就是scheduledExecutionTime(n+1)=realExecutionTime(n)+periodTime。也就是说如果第n个task由于某种情况导致这次的执行时间过程,最后导致systemCurrentTime>= scheduledExecutionTime(n+1),这是第n+1个task并不会因为到时了而执行,他会等待第n个task执行完之后再执行,那么这样势必会导致n+2个的执行实现scheduledExecutionTime放生改变即scheduledExecutionTime(n+2) = realExecutionTime(n+1)+periodTime。所以这两个方法更加注重保存间隔时间的稳定。

3、scheduleAtFixedRate(TimerTask task, Date firstTime, long period)、scheduleAtFixedRate(TimerTask task, long delay, long period)

在前面也提过scheduleAtFixedRate与schedule方法的侧重点不同,schedule方法侧重保存间隔时间的稳定,而scheduleAtFixedRate方法更加侧重于保持执行频率的稳定。为什么这么说,原因如下。在schedule方法中会因为前一个任务的延迟而导致其后面的定时任务延时,而scheduleAtFixedRate方法则不会,如果第n个task执行时间过长导致systemCurrentTime>= scheduledExecutionTime(n+1),则不会做任何等待他会立即执行第n+1个task,所以scheduleAtFixedRate方法执行时间的计算方法不同于schedule,而是scheduledExecutionTime(n)=firstExecuteTime +n*periodTime,该计算方法永远保持不变。所以scheduleAtFixedRate更加侧重于保持执行频率的稳定。

三、Timer的缺陷

3.1、Timer的缺陷

Timer计时器可以定时(指定时间执行任务)、延迟(延迟5秒执行任务)、周期性地执行任务(每隔个1秒执行任务),但是,Timer存在一些缺陷。首先Timer对调度的支持是基于绝对时间的,而不是相对时间,所以它对系统时间的改变非常敏感。其次Timer线程是不会捕获异常的,如果TimerTask抛出的了未检查异常则会导致Timer线程终止,同时Timer也不会重新恢复线程的执行,他会错误的���为整个Timer线程都会取消。同时,已经被安排单尚未执行的TimerTask也不会再执行了,新的任务也不能被调度。故如果TimerTask抛出未检查的异常,Timer将会产生无法预料的行为。

1、Timer管理时间延迟缺陷

前面Timer在执行定时任务时只会创建一个线程任务,如果存在多个线程,若其中某个线程因为某种原因而导致线程任务执行时间过长,超过了两个任务的间隔时间,会发生一些缺陷:

public class TimerTest04 {

private Timer timer;

public long start;

public TimerTest04(){

this.timer = new Timer();

start = System.currentTimeMillis();

}

public void timerOne(){

timer.schedule(new TimerTask() {

public void run() {

System.out.println(“timerOne invoked ,the time:” + (System.currentTimeMillis() – start));

try {

Thread.sleep(4000);

//线程休眠3000

}

catch (InterruptedException e) {

e.printStackTrace();

}

}

}, 1000);

}

public void timerTwo(){

timer.schedule(new TimerTask() {

public void run() {

System.out.println(“timerOne invoked ,the time:” + (System.currentTimeMillis() – start));

}

}, 3000);

}

public static void main(String[] args) throws Exception {

TimerTest04 test = new TimerTest04();

test.timerOne();

test.timerTwo();

}

}

按照我们正常思路,timerTwo应该是在3s后执行,其结果应该是:

timerOne invoked ,the time:1001timerOne invoked ,the time:3001

但是事与愿违,timerOne由于sleep(4000),休眠了4S,同时Timer内部是一个线程,导致timeOne所需的时间超过了间隔时间,结果:

timerOne invoked ,the time:1000timerOne invoked ,the time:5000

2、Timer抛出异常缺陷

如果TimerTask抛出RuntimeException,Timer会终止所有任务的运行。如下:

public class TimerTest04 {

private Timer timer;

public TimerTest04(){

this.timer = new Timer();

}

public void timerOne(){

timer.schedule(new TimerTask() {

public void run() {

throw new RuntimeException();

}

}, 1000);

}

public void timerTwo(){

timer.schedule(new TimerTask() {

public void run() {

System.out.println(“我会不会执行呢??”);

}

}, 1000);

}

public static void main(String[] args) {

TimerTest04 test = new TimerTest04();

test.timerOne();

test.timerTwo();

}

}

运行结果:timerOne抛出异常,导致timerTwo任务终止。

Exception in thread “Timer-0” java.lang.RuntimeException    at com.chenssy.timer.TimerTest04$1.run(TimerTest04.java:25)    at java.util.TimerThread.mainLoop(Timer.java:555)    at java.util.TimerThread.run(Timer.java:505)

对于Timer的缺陷,我们可以考虑 ScheduledThreadPoolExecutor 来替代。Timer是基于绝对时间的,对系统时间比较敏感,而ScheduledThreadPoolExecutor 则是基于相对时间;Timer是内部是单一线程,而ScheduledThreadPoolExecutor内部是个线程池,所以可以支持多个任务并发执行。

3.2、用ScheduledExecutorService替代Timer

1、解决问题一:

public class ScheduledExecutorTest {

private  ScheduledExecutorService scheduExec;

public long start;

ScheduledExecutorTest(){

this.scheduExec =  Executors.newScheduledThreadPool(2);

this.start = System.currentTimeMillis();

}

public void timerOne(){

scheduExec.schedule(new Runnable() {

public void run() {

System.out.println(“timerOne,the time:” + (System.currentTimeMillis() – start));

try {

Thread.sleep(4000);

}

catch (InterruptedException e) {

e.printStackTrace();

}

}

},1000,TimeUnit.MILLISECONDS);

}

public void timerTwo(){

scheduExec.schedule(new Runnable() {

public void run() {

System.out.println(“timerTwo,the time:” + (System.currentTimeMillis() – start));

}

},2000,TimeUnit.MILLISECONDS);

}

public static void main(String[] args) {

ScheduledExecutorTest test = new ScheduledExecutorTest();

test.timerOne();

test.timerTwo();

}

}

运行结果:

timerOne,the time:1003timerTwo,the time:2005

2、解决问题二

public class ScheduledExecutorTest {

private  ScheduledExecutorService scheduExec;

public long start;

ScheduledExecutorTest(){

this.scheduExec =  Executors.newScheduledThreadPool(2);

this.start = System.currentTimeMillis();

}

public void timerOne(){

scheduExec.schedule(new Runnable() {

public void run() {

throw new RuntimeException();

}

},1000,TimeUnit.MILLISECONDS);

}

public void timerTwo(){

scheduExec.scheduleAtFixedRate(new Runnable() {

public void run() {

System.out.println(“timerTwo invoked …..”);

}

},2000,500,TimeUnit.MILLISECONDS);

}

public static void main(String[] args) {

ScheduledExecutorTest test = new ScheduledExecutorTest();

test.timerOne();

test.timerTwo();

}

}

运行结果:

timerTwo invoked …..timerTwo invoked …..timerTwo invoked …..timerTwo invoked

作者: chenssy 

出处: http://www.cnblogs.com/chenssy/ 

本文版权归作者和博客园共有,欢迎转载,但未经作者同意必须保留此段声明,且在文章页面明显位置给出原文连接,否则保留追究法律责任的权利。

Java 远程通讯技术及原理分析

来源:伯乐在线专栏作者-陶邦仁

在分布式服务框架中,一个最基础的问题就是远程服务是怎么通讯的,在Java领域中有很多可实现远程通讯的技术,例如:RMI、MINA、ESB、Burlap、Hessian、SOAP、EJB和JMS等,这些名词之间到底是些什么关系呢,它们背后到底是基于什么原理实现的呢,了解这些是实现分布式服务框架的基础知识,而如果在性能上有高的要求的话,那深入了解这些技术背后的机制就是必须的了。

1 基本原理

要实现网络机器间的通讯,首先得来看看计算机系统网络通信的基本原理,在底层层面去看,网络通信需要做的就是将流从一台计算机传输到另外一台计算机,基于传输协议和网络IO来实现,其中传输协议比较出名的有tcp、udp等等,tcp、udp都是在基于Socket概念上为某类应用场景而扩展出的传输协议,网络IO,主要有bio、nio、aio三种方式,所有的分布式应用通讯都基于这个原理而实现,只是为了应用的易用,各种语言通常都会提供一些更为贴近应用易用的应用层协议。

2 消息模式

归根结底,企业应用系统就是对数据的处理,而对于一个拥有多个子系统的企业应用系统而言,它的基础支撑无疑就是对消息的处理。与对象不同,消息本质上是一种数据结构(当然,对象也可以看做是一种特殊的消息),它包含消费者与服务双方都能识别的数据,这些数据需要在不同的进程(机器)之间进行传递,并可能会被多个完全不同的客户端消费。消息传递相较文件传递与远程过程调用(RPC)而言,似乎更胜一筹,因为它具有更好的平台无关性,并能够很好地支持并发与异步调用。

对于Web Service与RESTful而言,则可以看做是消息传递技术的一种衍生或封装。

2.1 消息通道(Message Channel)模式

我们常常运用的消息模式是Message Channel(消息通道)模式,如图所示。

消息通道作为在客户端(消费者,Consumer)与服务(生产者,Producer)之间引入的间接层,可以有效地解除二者之间的耦合。只要实现规定双方需要通信的消息格式,以及处理消息的机制与时机,就可以做到消费者对生产者的“无知”。事实上,该模式可以支持多个生产者与消费者。例如,我们可以让多个生产者向消息通道发送消息,因为消费者对生产者的无知性,它不必考虑究竟是哪个生产者发来的消息。

虽然消息通道解除了生产者与消费者之间的耦合,使得我们可以任意地对生产者与消费者进行扩展,但它又同时引入了各自对消息通道的依赖,因为它们必须知道通道资源的位置。要解除这种对通道的依赖,可以考虑引入Lookup服务来查找该通道资源。例如,在JMS中就可以通过JNDI来获取消息通道Queue。若要做到充分的灵活性,可以将与通道相关的信息存储到配置文件中,Lookup服务首先通过读取配置文件来获得通道。

消息通道通常以队列的形式存在,这种先进先出的数据结构无疑最为适合这种处理消息的场景。微软的MSMQ、IBM MQ、JBoss MQ以及开源的RabbitMQ、Apache ActiveMQ都通过队列实现了Message Channel模式。因此,在选择运用Message Channel模式时,更多地是要从质量属性的层面对各种实现了该模式的产品进行全方位的分析与权衡。例如,消息通道对并发的支持以及在性能上的表现;消息通道是否充分地考虑了错误处理;对消息安全的支持;以及关于消息持久化、灾备(fail over)与集群等方面的支持。

因为通道传递的消息往往是一些重要的业务数据,一旦通道成为故障点或安全性的突破点,对系统就会造成灾难性的影响。

此处也顺带的提下jndi的机制,由于JNDI取决于具体的实现,在这里只能是讲解下jboss的jndi的实现了:

在将对象实例绑定到jboss jnp server后,当远程端采用context.lookup()方式获取远程对象实例并开始调用时,jboss jndi的实现方法是从jnp server上获取对象实例,将其序列化回本地,然后在本地进行反序列化,之后在本地进行类调用。

通过这个机制,就可以知道了,本地其实是必须有绑定到jboss上的对象实例的class的,否则反序列化的时候肯定就失败了,而远程通讯需要做到的是在远程执行某动作,并获取到相应的结果,可见纯粹基于JNDI是无法实现远程通讯的。

但JNDI也是实现分布式服务框架一个很关键的技术点,因为可以通过它来实现透明化的远端和本地调用,就像ejb,另外它也是个很好的隐藏实际部署机制(就像datasource)等的方案。

2.2 发布者-订阅者(Publisher-Subscriber)模式

一旦消息通道需要支持多个消费者时,就可能面临两种模型的选择:拉模型与推模型。拉模型是由消息的消费者发起的,主动权把握在消费者手中,它会根据自己的情况对生产者发起调用。如图所示:

拉模型的另一种体现则由生产者在状态发生变更时,通知消费者其状态发生了改变。但得到通知的消费者却会以回调方式,通过调用传递过来的消费者对象获取更多细节消息。

在基于消息的分布式系统中,拉模型的消费者通常以Batch Job的形式,根据事先设定的时间间隔,定期侦听通道的情况。一旦发现有消息传递进来,就会转而将消息传递给真正的处理器(也可以看做是消费者)处理消息,执行相关的业务。

推模型的主动权常常掌握在生产者手中,消费者被动地等待生产者发出的通知,这就要求生产者必须了解消费者的相关信息。如图所示:

对于推模型而言,消费者无需了解生产者。在生产者通知消费者时,传递的往往是消息(或事件),而非生产者自身。同时,生产者还可以根据不同的情况,注册不同的消费者,又或者在封装的通知逻辑中,根据不同的状态变化,通知不同的消费者。

两种模型各有优势。拉模型的好处在于可以进一步解除消费者对通道的依赖,通过后台任务去定期访问消息通道。坏处是需要引入一个单独的服务进程,以Schedule形式执行。而对于推模型而言,消息通道事实上会作为消费者观察的主体,一旦发现消息进入,就会通知消费者执行对消息的处理。无论推模型,拉模型,对于消息对象而言,都可能采用类似Observer模式的机制,实现消费者对生产者的订阅,因此这种机制通常又被称为Publisher-Subscriber模式,如图所示:

通常情况下,发布者和订阅者都会被注册到用于传播变更的基础设施(即消息通道)上。发布者会主动地了解消息通道,使其能够将消息发送到通道中;消息通道一旦接收到消息,会主动地调用注册在通道中的订阅者,进而完成对消息内容的消费。

对于订阅者而言,有两种处理消息的方式。一种方式是广播机制,这时消息通道中的消息在出列的同时,还需要复制消息对象,将消息传递给多个订阅者。例如,有多个子系统都需要获取从CRM系统传来的客户信息,并根据传递过来的客户信息,进行相应的处理。此时的消息通道又被称为Propagation通道。另一种方式则属于抢占机制,它遵循同步方式,在同一时间只能有一个订阅者能够处理该消息。实现Publisher-Subscriber模式的消息通道会选择当前空闲的唯一订阅者,并将消息出列,并传递给订阅者的消息处理方法。

目前,有许多消息中间件都能够很好地支持Publisher-Subscriber模式,例如JMS接口规约中对于Topic对象提供的MessagePublisher与MessageSubscriber接口。RabbitMQ也提供了自己对该模式的实现。微软的MSMQ虽然引入了事件机制,可以在队列收到消息时触发事件,通知订阅者。但它并非严格意义上的Publisher-Subscriber模式实现。由微软MVP Udi Dahan作为主要贡献者的NServiceBus,则对MSMQ以及WCF做了进一层包装,并能够很好地实现这一模式。

2.3 消息路由(Message Router)模式

无论是Message Channel模式,还是Publisher-Subscriber模式,队列在其中都扮演了举足轻重的角色。然而,在企业应用系统中,当系统变得越来越复杂时,对性能的要求也会越来越高,此时对于系统而言,可能就需要支持同时部署多个队列,并可能要求分布式部署不同的队列。这些队列可以根据定义接收不同的消息,例如订单处理的消息,日志信息,查询任务消息等。这时,对于消息的生产者和消费者而言,并不适宜承担决定消息传递路径的职责。事实上,根据S单一职责原则,这种职责分配也是不合理的,它既不利于业务逻辑的重用,也会造成生产者、消费者与消息队列之间的耦合,从而影响系统的扩展。

既然这三种对象(组件)都不宜承担这样的职责,就有必要引入一个新的对象专门负责传递路径选择的功能,这就是所谓的Message Router模式,如图所示:

通过消息路由,我们可以配置路由规则指定消息传递的路径,以及指定具体的消费者消费对应的生产者。例如指定路由的关键字,并由它来绑定具体的队列与指定的生产者(或消费者)。路由的支持提供了消息传递与处理的灵活性,也有利于提高整个系统的消息处理能力。同时,路由对象有效地封装了寻找与匹配消息路径的逻辑,就好似一个调停者(Meditator),负责协调消息、队列与路径寻址之间关系。

3 应用级协议

远程服务通讯,需要达到的目标是在一台计算机发起请求,另外一台机器在接收到请求后进行相应的处理并将结果返回给请求端,这其中又会有诸如one way request、同步请求、异步请求等等请求方式,按照网络通信原理,需要实现这个需要做的就是将请求转换成流,通过传输协议传输至远端,远端计算机在接收到请求的流后进行处理,处理完毕后将结果转化为流,并通过传输协议返回给调用端。

原理是这样的,但为了应用的方便,业界推出了很多基于此原理之上的应用级的协议,使得大家可以不用去直接操作这么底层的东西,通常应用级的远程通信协议会提供:

  1. 为了避免直接做流操作这么麻烦,提供一种更加易用或贴合语言的标准传输格式;
  2. 网络通信机制的实现,就是替你完成了将传输格式转化为流,通过某种传输协议传输至远端计算机,远端计算机在接收到流后转化为传输格式,并进行存储或以某种方式通知远端计算机。

所以在学习应用级的远程通信协议时,我们可以带着这几个问题进行学习:

  1. 传输的标准格式是什么?
  2. 怎么样将请求转化为传输的流?
  3. 怎么接收和处理流?
  4. 传输协议是?

不过应用级的远程通信协议并不会在传输协议上做什么多大的改进,主要是在流操作方面,让应用层生成流和处理流的这个过程更加的贴合所使用的语言或标准,至于传输协议则通常都是可选的,在java领域中知名的有:RMI、XML-RPC、Binary-RPC、SOAP、CORBA、JMS、HTTP,来具体的看看这些远程通信的应用级协议。

3.1 RMI(远程方法调用)

RMI是个典型的为java定制的远程通信协议,我们都知道,在single vm中,我们可以通过直接调用java object instance来实现通信,那么在远程通信时,如果也能按照这种方式当然是最好了,这种远程通信的机制成为RPC(Remote Procedure Call),RMI正是朝着这个目标而诞生的。

RMI 采用stubs 和 skeletons 来进行远程对象(remote object)的通讯。stub 充当远程对象的客户端代理,有着和远程对象相同的远程接口,远程对象的调用实际是通过调用该对象的客户端代理对象stub来完成的,通过该机制RMI就好比它是本地工作,采用tcp/ip协议,客户端直接调用服务端上的一些方法。优点是强类型,编译期可检查错误,缺点是只能基于JAVA语言,客户机与服务器紧耦合。

来看下基于RMI的一次完整的远程通信过程的原理:

  1. 客户端发起请求,请求转交至RMI客户端的stub类;
  2. stub类将请求的接口、方法、参数等信息进行序列化;
  3. 基于socket将序列化后的流传输至服务器端;
  4. 服务器端接收到流后转发至相应的skelton类;
  5. skelton类将请求的信息反序列化后调用实际的处理类;
  6. 处理类处理完毕后将结果返回给skelton类;
  7. Skelton类将结果序列化,通过socket将流传送给客户端的stub;
  8. stub在接收到流后反序列化,将反序列化后的Java Object返回给调用者。

根据原理来回答下之前学习应用级协议带着的几个问题:

  1. 传输的标准格式是什么?是Java ObjectStream。
  2. 怎么样将请求转化为传输的流?基于Java串行化机制将请求的java object信息转化为流。
  3. 怎么接收和处理流?根据采用的协议启动相应的监听端口,当有流进入后基于Java串行化机制将流进行反序列化,并根据RMI协议获取到相应的处理对象信息,进行调用并处理,处理完毕后的结果同样基于java串行化机制进行返回。
  4. 传输协议是?Socket。

3.2 XML-RPC

RPC使用C/S方式,采用http协议,发送请求到服务器,等待服务器返回结果。这个请求包括一个参数集和一个文本集,通常形成“classname.methodname”形式。优点是跨语言跨平台,C端、S端有更大的独立性,缺点是不支持对象,无法在编译器检查错误,只能在运行期检查。

XML-RPC也是一种和RMI类似的远程调用的协议,它和RMI的不同之处在于它以标准的xml格式来定义请求的信息(请求的对象、方法、参数等),这样的好处是什么呢,就是在跨语言通讯的时候也可以使用。

来看下XML-RPC协议的一次远程通信过程:

  1. 客户端发起请求,按照XML-RPC协议将请求信息进行填充;
  2. 填充完毕后将xml转化为流,通过传输协议进行传输;
  3. 接收到在接收到流后转换为xml,按照XML-RPC协议获取请求的信息并进行处理;
  4. 处理完毕后将结果按照XML-RPC协议写入xml中并返回。

同样来回答问题:

  1. 传输的标准格式是?标准格式的XML。
  2. 怎么样将请求转化为传输的流?将XML转化为流。
  3. 怎么接收和处理流?通过监听的端口获取到请求的流,转化为XML,并根据协议获取请求的信息,进行处理并将结果写入XML中返回。
  4. 传输协议是?Http。

3.3 Binary-RPC

Binary-RPC看名字就知道和XML-RPC是差不多的了,不同之处仅在于传输的标准格式由XML转为了二进制的格式。

同样来回答问题:

  1. 传输的标准格式是?标准格式的二进制文件。
  2. 怎么样将请求转化为传输的流?将二进制格式文件转化为流。
  3. 怎么接收和处理流?通过监听的端口获取到请求的流,转化为二进制文件,根据协议获取请求的信息,进行处理并将结果写入XML中返回。
  4. 传输协议是?Http。

3.4 SOAP

SOAP原意为Simple Object Access Protocol,是一个用于分布式环境的、轻量级的、基于XML进行信息交换的通信协议,可以认为SOAP是XML RPC的高级版,两者的原理完全相同,都是http+XML,不同的仅在于两者定义的XML规范不同,SOAP也是Webservice采用的服务调用协议标准,因此在此就不多加阐述了。

Web Service提供的服务是基于web容器的,底层使用http协议,类似一个远程的服务提供者,比如天气预报服务,对各地客户端提供天气预报,是一种请求应答的机制,是跨系统跨平台的。就是通过一个servlet,提供服务出去。

首先客户端从服务器获得WebService的WSDL,同时在客户端生成一个代理类(Proxy Class),这个代理类负责与WebService服务器进行Request和Response。当一个数据(XML格式的)被封装成SOAP格式的数据流发送到服务器端的时候,就会生成一个进程对象并且把接收到这个Request的SOAP包进行解析,然后对事物进行处理,处理结束以后再对这个计算结果进行SOAP包装,然后把这个包作为一个Response发送给客户端的代理类(Proxy Class),同样地,这个代理类也对这个SOAP包进行解析处理,继而进行后续操作。这就是WebService的一个运行过程。

Web Service大体上分为5个层次:

  1. Http传输信道;
  2. XML的数据格式;
  3. SOAP封装格式;
  4. WSDL的描述方式;
  5. UDDI UDDI是一种目录服务,企业可以使用它对Webservices进行注册和搜索;

3.5 JMS

JMS是实现java领域远程通信的一种手段和方法,基于JMS实现远程通信时和RPC是不同的,虽然可以做到RPC的效果,但因为不是从协议级别定义的,因此我们不认为JMS是个RPC协议,但它确实是个远程通信协议,在其他的语言体系中也存在着类似JMS的东西,可以统一的将这类机制称为消息机制,而消息机制呢,通常是高并发、分布式领域推荐的一种通信机制,这里的主要一个问题是容错。

JMS是Java的消息服务,JMS的客户端之间可以通过JMS服务进行异步的消息传输。JMS支持两种消息模型:Point-to-Point(P2P)和Publish/Subscribe(Pub/Sub),即点对点和发布订阅模型。

来看JMS中的一次远程通信的过程:

  1. 客户端将请求转化为符合JMS规定的Message;
  2. 通过JMS API将Message放入JMS Queue或Topic中;
  3. 如为JMS Queue,则发送中相应的目标Queue中,如为Topic,则发送给订阅了此Topic的JMS Queue。
  4. 处理端则通过轮训JMS Queue,来获取消息,接收到消息后根据JMS协议来解析Message并处理。

同样来回答问题:

  1. 传输的标准格式是?JMS规定的Message。
  2. 怎么样将请求转化为传输的流?将参数信息放入Message中即可。
  3. 怎么接收和处理流?轮训JMS Queue来接收Message,接收到后进行处理,处理完毕后仍然是以Message的方式放入Queue中发送或Multicast。
  4. 传输协议是?不限。

基于JMS也是常用的实现远程异步调用的方法之一。

4 之间的区别

4.1 RPC与RMI

  1. RPC跨语言,而RMI只支持Java。
  2. RMI调用远程对象方法,允许方法返回Java对象以及基本数据类型,而RPC不支持对象的概念,传送到RPC服务的消息由外部数据表示 (External Data Representation, XDR) 语言表示,这种语言抽象了字节序类和数据类型结构之间的差异。只有由 XDR 定义的数据类型才能被传递,可以说 RMI 是面向对象方式的Java RPC。
  3. 在方法调用上,RMI中,远程接口使每个远程方法都具有方法签名。如果一个方法在服务器上执行,但是没有相匹配的签名被添加到这个远程接口上,那么这个新方法就不能被RMI客户方所调用。在RPC中,当一个请求到达RPC服务器时,这个请求就包含了一个参数集和一个文本值,通常形成“classname.methodname”的形式。这就向RPC服务器表明,被请求的方法在为 “classname”的类中,名叫“methodname”。然后RPC服务器就去搜索与之相匹配的类和方法,并把它作为那种方法参数类型的输入。这里的参数类型是与RPC请求中的类型是匹配的。一旦匹配成功,这个方法就被调用了,其结果被编码后返回客户方。
  4. RPC本身没有规范,但基本的工作机制是一样的,即:serialization/deserialization+stub+skeleton,宽泛的讲,只要能实现远程调用,都是RPC,如:rmi .net-remoting ws/soap/rest hessian xmlrpc thrift potocolbuffer。
  5. 在Java里提供了完整的sockets通讯接口,但sockets要求客户端和服务端必须进行应用级协议的编码交换数据,采用sockets是非常麻烦的。一个代替Sockets的协议是RPC(Remote Procedure Call), 它抽象出了通讯接口用于过程调用,使得编程者调用一个远程过程和调用本地过程同样方便。RPC 系统采用XDR来编码远程调用的参数和返回值。但RPC并不支持对象,所以,面向对象的远程调用RMI(Remote Method Invocation)成为必然选择。采用RMI,调用远程对象和调用本地对象同样方便。RMI 采用JRMP(Java Remote Method Protocol)通讯协议,是构建在TCP/IP协议上的一种远程调用方法。

4.2 JMS与RMI

  1. 采用JMS服务,对象是在物理上被异步从网络的某个JVM 上直接移动到另一个JVM 上(是消息通知机制),而RMI对象是绑定在本地JVM 中,只有函数参数和返回值是通过网络传送的(是请求应答机制)。
  2. RMI一般都是同步的,也就是说,当client调用Server的一个方法的时候,需要等到对方的返回,才能继续执行client端,这个过程调用本地方法感觉上是一样的,这也是RMI的一个特点。JMS 一般只是一个点发出一个Message到Message Server,发出之后一般不会关心谁用了这个message。所以,一般RMI的应用是紧耦合,JMS的应用相对来说是松散耦合应用。

4.3 Webservice与RMI

RMI是在tcp协议上传递可序列化的java对象,只能用在java虚拟机上,绑定语言,客户端和服务端都必须是java。webservice没有这个限制,webservice是在http协议上传递xml文本文件,与语言和平台无关。

4.4 Webservice与JMS

Webservice专注于远程服务调用,jms专注于信息交换。

大多数情况下Webservice是两系统间的直接交互(Consumer Producer),而大多数情况下jms是三方系统交互(Consumer Producer)。当然,JMS也可以实现request-response模式的通信,只要Consumer或Producer其中一方兼任broker即可。

JMS可以做到异步调用完全隔离了客户端和服务提供者,能够抵御流量洪峰;WebService服务通常为同步调用,需要有复杂的对象转换,相比SOAP,现在JSON,rest都是很好的http架构方案;

JMS是java平台上的消息规范。一般jms消息不是一个xml,而是一个java对象,很明显,jms没考虑异构系统,说白了,JMS就没考虑非java的东西。但是好在现在大多数的jms provider(就是JMS的各种实现产品)都解决了异构问题。相比WebService的跨平台各有千秋吧。

5 可选实现技术

目前java领域可用于实现远程通讯的框架或library,知名的有:JBoss-Remoting、Spring-Remoting、Hessian、Burlap、XFire(Axis)、ActiveMQ、Mina、Mule、EJB3等等,来对每种做个简单的介绍和评价,其实呢,要做分布式服务框架,这些东西都是要有非常深刻的了解的,因为分布式服务框架其实是包含了解决分布式领域以及应用层面领域两方面问题的。

当然,你也可以自己根据远程网络通信原理(transport protocol+Net IO)去实现自己的通讯框架或library。

那么在了解这些远程通讯的框架或library时,会带着什么问题去学习呢?

  1. 是基于什么协议实现的?
  2. 怎么发起请求?
  3. 怎么将请求转化为符合协议的格式的?
  4. 使用什么传输协议传输?
  5. 响应端基于什么机制来接收请求?
  6. 怎么将流还原为传输格式的?
  7. 处理完毕后怎么回应?

5.1 Spring-Remoting

Spring-remoting是Spring提供java领域的远程通讯框架,基于此框架,同样也可以很简单的将普通的spring bean以某种远程协议的方式来发布,同样也可以配置spring bean为远程调用的bean。

  1. 是基于什么协议实现的?作为一个远程通讯的框架,Spring通过集成多种远程通讯的library,从而实现了对多种协议的支持,例如rmi、http+io、xml-rpc、binary-rpc等。
  2. 怎么发起请求?在Spring中,由于其对于远程调用的bean采用的是proxy实现,发起请求完全是通过服务接口调用的方式。
  3. 怎么将请求转化为符合协议的格式的?Spring按照协议方式将请求的对象信息转化为流,例如Spring Http Invoker是基于Spring自己定义的一个协议来实现的,传输协议上采用的为http,请求信息是基于java串行化机制转化为流进行传输。
  4. 使用什么传输协议传输?支持多种传输协议,例如rmi、http等等。
  5. 响应端基于什么机制来接收请求?响应端遵循协议方式来接收请求,对于使用者而言,则只需通过spring的配置方式将普通的spring bean配置为响应端或者说提供服务端。
  6. 怎么将流还原为传输格式的?按照协议方式来进行还原。
  7. 处理完毕后怎么回应?处理完毕后直接返回即可,spring-remoting将根据协议方式来做相应的序列化。

5.2 Hessian

Hessian是由caucho提供的一个基于binary-RPC实现的远程通讯library。

  1. 是基于什么协议实现的?基于Binary-RPC协议实现。
  2. 怎么发起请求?需通过Hessian本身提供的API来发起请求。
  3. 怎么将请求转化为符合协议的格式的?Hessian通过其自定义的串行化机制将请求信息进行序列化,产生二进制流。
  4. 使用什么传输协议传输?Hessian基于Http协议进行传输。
  5. 响应端基于什么机制来接收请求?响应端根据Hessian提供的API来接收请求。
  6. 怎么将流还原为传输格式的?Hessian根据其私有的串行化机制来将请求信息进行反序列化,传递给使用者时已是相应的请求信息对象了。
  7. 处理完毕后怎么回应?处理完毕后直接返回,hessian将结果对象进行序列化,传输至调用端。

5.3 Burlap

Burlap也是有caucho提供,它和hessian的不同在于,它是基于XML-RPC协议的。

  1. 是基于什么协议实现的?基于XML-RPC协议实现。
  2. 怎么发起请求?根据Burlap提供的API。
  3. 怎么将请求转化为符合协议的格式的?将请求信息转化为符合协议的XML格式,转化为流进行传输。
  4. 使用什么传输协议传输?Http协议。
  5. 响应端基于什么机制来接收请求?监听Http请求。
  6. 怎么将流还原为传输格式的?根据XML-RPC协议进行还原。
  7. 处理完毕后怎么回应?返回结果写入XML中,由Burlap返回至调用端。

5.4 XFire、Axis

XFire、Axis是Webservice的实现框架,WebService可算是一个完整的SOA架构实现标准了,因此采用XFire、Axis这些也就意味着是采用webservice方式了。

  1. 是基于什么协议实现的?基于SOAP协议。
  2. 怎么发起请求?获取到远端service的proxy后直接调用。
  3. 怎么将请求转化为符合协议的格式的?将请求信息转化为遵循SOAP协议的XML格式,由框架转化为流进行传输。
  4. 使用什么传输协议传输?Http协议。
  5. 响应端基于什么机制来接收请求?监听Http请求。
  6. 怎么将流还原为传输格式的?根据SOAP协议进行还原。
  7. 处理完毕后怎么回应?返回结果写入XML中,由框架返回至调用端。

5.5 ActiveMQ

ActiveMQ是JMS的实现,基于JMS这类消息机制实现远程通讯是一种不错的选择,毕竟消息机制本身的功能使得基于它可以很容易的去实现同步/异步/单向调用等,而且消息机制从容错角度上来说也是个不错的选择,这是Erlang能够做到容错的重要基础。

  1. 是基于什么协议实现的?基于JMS协议。
  2. 怎么发起请求?遵循JMS API发起请求。
  3. 怎么将请求转化为符合协议的格式的?不太清楚,猜想应该是二进制流。
  4. 使用什么传输协议传输?支持多种传输协议,例如socket、http等等。
  5. 响应端基于什么机制来接收请求?监听符合协议的端口。
  6. 怎么将流还原为传输格式的?同问题3。
  7. 处理完毕后怎么回应?遵循JMS API生成消息,并写入JMS Queue中。

5.6 Mina

Mina是Apache提供的通讯框架,在之前一直没有提到网络IO这块,之前提及的框架或library基本都是基于BIO的,而Mina是采用NIO的,NIO在并发量增长时对比BIO而言会有明显的性能提升,而java性能的提升,与其NIO这块与OS的紧密结合是有不小的关系的。

  1. 是基于什么协议实现的?基于纯粹的Socket+NIO。
  2. 怎么发起请求?通过Mina提供的Client API。
  3. 怎么将请求转化为符合协议的格式的?Mina遵循java串行化机制对请求对象进行序列化。
  4. 使用什么传输协议传输?支持多种传输协议,例如socket、http等等。
  5. 响应端基于什么机制来接收请求?以NIO的方式监听协议端口。
  6. 怎么将流还原为传输格式的?遵循java串行化机制对请求对象进行反序列化。
  7. 处理完毕后怎么回应?遵循Mina API进行返回。

MINA是NIO方式的,因此支持异步调用是毫无悬念的。

6 RPC框架的发展与现状

RPC(Remote Procedure Call)是一种远程调用协议,简单地说就是能使应用像调用本地方法一样的调用远程的过程或服务,可以应用在分布式服务、分布式计算、远程服务调用等许多场景。说起 RPC 大家并不陌生,业界有很多开源的优秀 RPC 框架,例如 Dubbo、Thrift、gRPC、Hprose 等等。下面先简单介绍一下 RPC 与常用远程调用方式的特点,以及一些优秀的开源 RPC 框架。

RPC 与其它远程调用方式比较,RPC 与 HTTP、RMI、Web Service 都能完成远程调用,但是实现方式和侧重点各有不同。

6.1 RPC与HTTP

HTTP(HyperText Transfer Protocol)是应用层通信协议,使用标准语义访问指定资源(图片、接口等),网络中的中转服务器能识别协议内容。HTTP 协议是一种资源访问协议,通过 HTTP 协议可以完成远程请求并返回请求结果。

HTTP 的优点是简单、易用、可理解性强且语言无关,在远程服务调用中包括微博有着广泛应用。HTTP 的缺点是协议头较重,一般请求到具体服务器的链路较长,可能会有 DNS 解析、Nginx 代理等。

RPC 是一种协议规范,可以把 HTTP 看作是一种 RPC 的实现,也可以把 HTTP 作为 RPC 的传输协议来应用。RPC 服务的自动化程度比较高,能够实现强大的服务治理功能,和语言结合更友好,性能也十分优秀。与 HTTP 相比,RPC 的缺点就是相对复杂,学习成本稍高。

6.2 RPC与RMI

RMI(Remote Method Invocation)是指 Java 语言中的远程方法调用,RMI 中的每个方法都具有方法签名,RMI 客户端和服务器端通过方法签名进行远程方法调用。RMI 只能在 Java 语言中使用,可以把 RMI 看作面向对象的 Java RPC。

6.3 RPC与Web Service

Web Service 是一种基于 Web 进行服务发布、查询、调用的架构方式,重点在于服务的管理与使用。Web Service 一般通过 WSDL 描述服务,使用 SOAP通过 HTTP 调用服务。

RPC 是一种远程访问协议,而 Web Service 是一种体系结构,Web Service 也可以通过 RPC 来进行服务调用,因此 Web Service 更适合同一个 RPC 框架进行比较。当 RPC 框架提供了服务的发现与管理,并使用 HTTP 作为传输协议时,其实就是 Web Service。

相对 Web Service,RPC 框架可以对服务进行更细粒度的治理,包括流量控制、SLA 管理等,在微服务化、分布式计算方面有更大的优势。

RPC 可基于 HTTP 或 TCP 协议,Web Service 就是基于 HTTP 协议的 RPC,它具有良好的跨平台性,但其性能却不如基于 TCP 协议的 RPC。会两方面会直接影响 RPC 的性能,一是传输方式,二是序列化。

众所周知,TCP 是传输层协议,HTTP 是应用层协议,而传输层较应用层更加底层,在数据传输方面,越底层越快,因此,在一般情况下,TCP 一定比 HTTP 快。

7 总结

在远程通讯领域中,涉及的知识点还是相当的多的,例如有:通信协议(Socket/tcp/http/udp/rmi/xml-rpc etc.)、消息机制、网络IO(BIO/NIO/AIO)、MultiThread、本地调用与远程调用的透明化方案(涉及java classloader、Dynamic Proxy、Unit Test etc.)、异步与同步调用、网络通信处理机制(自动重连、广播、异常、池处理等等)、Java Serialization (各种协议的私有序列化机制等)、各种框架的实现原理(传输格式、如何将传输格式转化为流的、如何将请求信息转化为传输格式的、如何接收流的、如何将流还原为传输格式的等等),要精通其中的哪些东西,得根据实际需求来决定了,只有在了解了原理的情况下才能很容易的做出选择,甚至可以根据需求做私有的远程通讯协议,对于从事分布式服务平台或开发较大型的分布式应用的人而言,我觉得至少上面提及的知识点是需要比较了解的。

专栏作者简介


陶邦仁:专注于后端技术研究,前端技术略有涉猎,热衷于构建高性能、高可用网站,对平台服务化、分布式服务、分布式存储等方面的解决方案。目前就职于千丁互联,任技术经理一职,负责社区产品技术研发。曾就职于京东,负责库存组缓存方案技术实现;曾就职于百度糯米,负责PC首页、APP个性化排单服务化解决方案。

C++的反思

来自:Skywind Inside

作者:skywind

链接:http://www.skywind.me/blog/archives/1398

最近两年 C++又有很多人出来追捧,并且追捧者充满了各种优越感,似乎不写 C++你就一辈子是低端程序员了,面对这种现象,要不要出来适时的黑一下 C++呢?呵呵呵。

咱们要有点娱乐精神,关于 C++的笑话数都数不清:

笑话:C++是一门不吉祥的语言,据说波音公司之前用ADA为飞机硬件编程,一直用的好好的,后来招聘了一伙大学生,学生们说我靠还在用这么落后的语言,然后换成C++重构后飞机就坠毁了。

笑话:什么是C++程序员呢?就是本来10行写得完的程序,他非要用30行来完成,并自称“封装”,但每每到第二个项目的时候却将80%打破重写,并美其名曰 “重构”。

笑话:C容易擦枪走火打到自己的脚,用C++虽然不容易,但一旦走火,就会把你整条腿给炸飞了。

笑话:同时学习两年 Java的程序员在一起讨论的是面向对象和设计模式,而同时学习两年 C++的程序员,在一起讨论的是 template和各种语言规范到底怎么回事情。

笑话:教别人学 C++的人都挣大钱了,而很多真正用 C++的人,都死的很惨。

笑话:C++有太多地方可以让一个人表现自己“很聪明”,所以使用C++越久的人,约觉得自己“很聪明”结果步入陷阱都不知道,掉坑里了还觉得估计是自己没学好 C++。

笑话:好多写了十多年 C++程序的人,至今说不清楚 C++到底有多少规范,至今仍然时不时的落入某些坑中。

笑话:很多认为 C++方便跨平台的人,实际编写跨平台代码时,都会发现自己难找到两个支持相同标准的 C++编译器。

—————

Q:那 C++为什么还能看到那么多粉丝呢?

A:其实是因为 Windows,因为 Windows的兴起带动了 C++,C++本来就是一门只适合开发 GUI的语言。

Q:为何 C++只适合开发 GUI呢?

A:你看 Unix下没有 GUI,为啥清一色的 C呀?所有的系统级问题都能在 C里找到成熟的解决方案,应用级问题都能用其他高级语言很好地解决,哪里有 C++什么事情呀?

Q:你强词夺理,Unix下也有 C++的项目呀。

A:有,没错,你任然可以用任何语言编写任何糟糕的代码。

Q:别瞎扯了,你都在说些什么?连C++和 Windows 都扯到一起去了。

A:回想下当年的情景,一个大牛在教一群初学者如何编程。一边开发一边指着屏幕上说,你看,这是一个 Button,我们可以用一个对象来描述它,那是一个 panel我们也可以用一个对象来描述它,并且你们有没有发现,其实 Button和 Panel是有血缘关系的,你们看。。。这样就出来了。。。。下面的学生以前都是学着学校落后的教材,有些甚至还在用 turboc的 bgi库来画一些点和圆。哪里见过这么这么华丽的 Windows 界面呀。大牛说的话,象金科玉律一样的铭刻在自己幼小的心理。一边学着 Windows,一边发现,果然,他们都需要一个基类,果然,他们是兄弟关系,共同包含一些基本属性,可以放到基类去。他们越用越爽,潜意识里觉得因为 C++这么顺利的帮他们解决那么多界面问题,那看来 C++可以帮他们解决一切问题了。于是开发完界面以后,他们继续开发,当他们碰到各种设计问题时,反而认为肯定自己没有用好 C++。于是强迫自己用下去,然后就完蛋了。

(点击 more展开)

—————

关于 C++的笑话我有一箩筐,各位 C++粉用不着对号入座。言归正传,为什么要黑 C++呢?谈不上黑不黑,我从94年开始使用 C++(先前是 C 和 Pascal),一路看着 C++成长壮大,用 C++写过的代码,加起来应该超过 10MB了吧,C++的各种宝典我也都读过,一直到 2004年开始切回 C,主要原因是发现很多没法用 C++思路继续解决下去的问题,或者说用 C++思路解决下去会很糟糕的问题。

那时候(2004-2005)正是 C++满天飞的时候,言必称 C++,用必用模版,我跳出来说你们醒醒吧,别过火了,这个世界并不是都是抽象数据结构和算法就可以描述清楚的。于是很多人激动的跳出来说:“你没领会到 C++精髓,你根本都不会用 C++”。我问他们:“语言是用来解决问题的,如果一个语言学了三四年都会经常掉沟里,算好语言么?如果编写十多年 C++的程序员都很难掌握得了,这算好语言么”。他们又说:“语言是死的,人是活的”。

我记得当时一位国内 C++大牛,为了纠正我的 “错误观点”,给我看过他写的一套十分强大的库,我打开一看,倒吸了一口冷气,全部是 .h文件。我只能回他三个字:“你牛逼”。当然这是一个极端的例子,那家伙后来终于也开始把 .h里面的东西逐步挪到 .cpp里面了,这是好事。

当时和云风在一家公司,2004年新人培训时,他给新人布置了一个实现内存分配器的作业,批改作业的时候,他经常边看边问人家,“不够C++呀,你能不能百分之百OOP?”,“1%的 C都不要留”。我当时在公司内部邮件列表里面发过关于 C++的问题,大部分人都表示:“你看没有C++我们怎么写3D引擎呢?”。我跟他们讲:“John Carmack直到 Quake3都还在用着 ANSI C,后来因为不得不支持 D3D,改用 C++了。为啥 C不能写 3D引擎了?”。他们告诉我:“你看,Point,就是个对象,Matrix也是个对象,那么多 Vector的代数计算,用 C++的算术重载是多么美妙的事情,三维世界就是对象的世界。”。

确实当时客户端 GUI的话,只有 C++,图形引擎也只有 C++,这两个正是C++最强的地方,所以我也没和他们争辩,强迫他们承认 C也可以很漂亮的写图形,而且C写的可以写的很优雅。我又不是闲着没事情,何必去质疑人家的核心价值观呢,呵呵。当年我正在接手一个 C++项目,代码超过 800KB,每次崩溃都需要花费很长时间去定位,项目中大量的前后依赖,改一个地方,前后要看好几处,一处遗漏,整个系统就傻逼了。我开始重构后,画了两个星期,将性能敏感的核心部分剥离出来用 C实现(代码量仅 200KB),然后导出 Python接口,用Python来完成剩下的部分,整个脚本层代码量只有 150KB。整个世界清爽了,整个 C++项目原来的工期为 2个程序员四个月,我一个人重构的时间加起来就 1.5个月,而且代码量比远来少了两倍还多,各种奇特的 BUG也一扫而尽。我看看左边的 800KB一团乱麻的 C++代码,再看看右边整洁的 300多 KB 纯 C + Python,琢磨着,这个项目干嘛不一开始就这么做?

跨语言接口

现代项目开发,不但需要更高的性能,而且需要更强大的语言描述能力。而 C++正处在一个尴尬的地方,比底层,它不如 C能够精确的控制内存和硬件,各种隐式构造让你防不胜防;比描述能力,比快速业务开发和错误定位,它又赶不上 Python, Ruby, Lua等动态语言,处于东线和西线同时遭受挤压和蚕食的地步。

很快,2006-2007年左右,其他项目组各种滥用 C++的问题开始显现出来:当时脚本化已经在工程实践中获得极大的成功,然而某些项目一方面又要追求 100%的 C++,另一方面又需要对脚本导出接口,他们发现问题了,不知道该怎么把大量的 C++基础库和接口导给 Lua。

C的接口有各种方便的方式导给脚本,然而整个项目由一群从来就不消于使用脚本的cpp大牛开发出来,当他们要吧cpp类导出接口给脚本时,他们设计了一套牛逼的系统,lua自动生成机器码,去调用c++的各种类,没错,就是c++版本的cffi或者ctypes。他为调用vc的类写了一套机器码生产,又为调用gcc的类写了一套代码生成。那位cpp大牛写完后四处炫耀他的成果,后来他离职了,项目上线一而再再而三的出现无可查证的问题,后来云风去支援那个项目组,这套盘根错节的c++项目,这套盘大的代码自生成系统深深的把他给恶心到了。后来众所周知云风开始反C++,倡导回归C了,不知道是否和这个项目有关系。

于是发现个有趣的现象,但凡善于使用脚本来提高工程效率的人,基本都是C加动态语言解决大部分问题(除了gui和图形),但凡认为c++统治宇宙的人很多都是从来没使用过脚本或者用了还不知道该怎样去用的人。

凭借这样的方法,我们的产品同竞争对手比拼时,同样一个功能,同样的人力配置,竞争对手用纯C++要开发三月,我们一个月就弄出来了,同样的时间,对手只能试错一次,我们可以试错三次。后来,据我们招聘过来的同事说,竞争对手也开始逐步降低 C++的比例,增加 java的比例了,这是好事,大家都在进步嘛。

ABI的尴尬

ABI级别的 C++接口从来没有标准化过,以类为接口会引入很多隐藏问题,比如内存问题,一个类在一个库里面实例化的,如果再另外一个库里面释放它们就有很多问题,因为两个动态库可能内存管理系统是不一样的。你用这里的 allocator分配一块内存,又用那里的 allocator去释放,不出问题才怪。很多解决方法是加一个 Release 方法(比如 DX),告诉外面的人,用完的时候不要去 delete,而是要调用 Release。

项目写大了各个模块隔离成动态库是很正常的,而各种第三方库和自己写的库为追求高性能引入特定的内存管理机制也是很正常的。很多人不注意该调用release的地方错写成delete就掉沟里去了。更有胜者跨 ABI定义了很多inline方法的类,结果各种隐式构造和析构其实在这个库里生成,那个库里被析构,乱成一团乱麻。C就清晰很多,构造你就调用fopen,析构你就fclose,没有任何歧义。其实C++的矛盾在于一方面承认作为系统级语言内存管理应该交给用户决定,一方面自己却又定义很多不受用户控制的内存操作行为。所以跨 ABI层的c++标准迟迟无法被定义出来,不是因为多态 abi复杂,而是因为语言逻辑出现了相互矛盾。为了弥补这个矛盾,C++引入了operator new,delete,这new/delete重载是一个补丁并没从逻辑上让语言变得完备,它的出现,进一步将使用者拖入bug的深渊。

其实今天我们回过头去看这个问题,能发现两个基本原则:跨abi的级别上引入不可控的内存机制从语言上是有问题的,只能要靠开发者约定各种灵巧的基类和约定开发规范来解决,这个问题在语言层是解决不了的;其次你既然定义了各种隐式构造和析构,就该像java活着动态语言一样彻底接管内存,不允许用户再自定义任何内存管理方法,而不是一方面作为系统极语言要给用户控制的自由,一方面自己又要抢着和用户一起控制。

因此对象层 ABI接口迟迟无法标准化。而纯 C的 ABI不但可以轻松的跨动态库还能轻松的和汇编及各类语言融合,不是因为C设计多好,而是C作为系统层语言没有去管它不该管的东西。当年讨论到这个话题时 C++大牛们又开始重复那几句金科玉律来反驳我:“语言只是招式,你把内功练好,就能做到无招胜有招,拿起草来都可以当剑使,C++虽然有很多坑,你把设计做好不那么用不就行了”。我说:本来应该在语言层解决好的事情,由于语言逻辑不完备,将大量问题抛给开发者去解决极大的增加了开发者的思维负担,就像破屋上表浆糊一样。你金庸看多了吧,武术再高,当你拿到一把枪发现子弹不一定往前射,偶尔还会往后射时,请问你是该专心打敌人呢?还是时刻要提防自己的子弹射向自己?

系统层的挫败

C++遭受挫败是进军嵌入式和操作系统这样靠近硬件层的东西。大家觉得宇宙级别的编程语言,自然能够胜任一切任务,很快发现几个问题:

●无法分配内存:原来用 C可以完全不依赖内存分配,代码写几千行一个 malloc没有都行。嵌入式下处理器加电后,跳到特定地址(比如起始地址0),第一条指令一般用汇编来写,固定在0地址,就是简单初始化一下栈,然后跳转到 C语言的 start函数去,试想此时内存分配机制都还没有建立,你定义了两个类,怎么构造呀?资源有限的微处理器上大部分时候就是使用一块静态内存进行操作。C++写起来写爽了,各种隐式构造一出现,就傻了。

●标准库依赖:在语言层面,C语言的所有特性都可以不用依赖任何库就运行,这为编写系统层和跨平台跨语言代码带来了很方便的特性。而C++就不行,我要构造呀,我要异常呀,你为啥不能给我强大的运行时呢?什么你还想用 stl?不看看那套库有多臃肿呀(内存占用,代码尺寸)。

●异常处理问题:底层开发需要严格的处理所有错误返回,这一行调用,下一行就判断错误。而异常是一种松散的错误处理方式,应用层这么写没问题,系统层这么写就很狼狈了。每行调用都try一下和 C的调用后if判断结果有什么区别?C++的构造函数是没有返回值的,如果构造内部出错,就必须逼迫你catch构造函数的异常,即便你catch住了,构造异常的时候当然会自动触发相关内部对象的析构,但是有很多并没有析构的资源(比如系统资源,比如C接口的资源,他们都没有一个析构),整个过程是很难控制的,此时这个实例是一个半初始化实例,你该怎么处理它呢?于是有人把初始化代码移除构造函数,构造时只初始化一下变量,新增加一个带返回的init函数,这样的代码写的比C冗余很多。何况硬件中断发生时,在你不知道的情况下,同事调到一些第三方的库,你最外层没有把新的exception给 catch住,这个exception该往哪里抛呀?内存不够的时候你想抛出一个 OutOfMemoryException,可是内存已经不够了,此时完全无能力构造这个异常又该怎么办呢?

●处理器兼容:C++的类依赖基地址+偏移地址的寻址方式,很多非 Intel系列的微处理器上只有简单的给定地址寻址,不支持这样一条语句实现BASE+OFFSET的寻址,很多C++代码编译出来需要更多的指令来运算地址,导致性能下降很多,得不偿失。

●隐式操作问题:C的特点是简单直接,每行语句你都能清楚的知道会被翻译成什么样子,系统会严格按照你的代码去执行。而用C++,比如 str1 = str2 + “Hello” + str3; 这样的语句,没几个人真的说得清楚究竟有多少次构造和拷贝,这样的写法编写底层代码是很不负责任的,底层需要更为精细和严格的控制,用C语言控制力更强。

当然,说道这里很多人又说,“C++本来就是 C的超集,特定的地方你完全可以按照C的写法来做呀。没人强迫你构造类或者使用异常呀”,没错,按 Linus的说法:“想要用 C++写出系统级的优秀的可移植和高效的代码,最终还是会限于使用 C本身提供的功能,而这些功能 C都已经完美提供了,所以系统层使用 C的意义就在于在语言层排除 C++的其他特性的干扰”。

很多人都记得 Linus在 2007年因为有人问 Git为什么不用 C++开发炮轰过一次C++。事实上2004年 C++如日中天的时候,有人问 Linux内核为何不用 C++开发,他就炮轰过一次了:

实际上,我们在1992年就尝试过在Linux使用 C++了。很恶心,相信我,用C++写内核是一个 “BLOODY STUPID IDEA”。事实上,C++编译器不值得信任,1992年时它们更糟糕,而一些基本的事实从没改变过:

– 整套 C++异常处理系统是 “fundamentally broken”。特别对于编写内核而言。

– 任何语言或编译器喜欢在你背后隐藏行为(如内存分配)对于开发内核并不是一个好选择。

– 任然可以用 C来编写面向对象代码(比如文件系统),而不需要用 C++写出一坨屎来。

总得来说,对任何希望用 C++来开发内核的人而言,他们都是在引入更多问题,无法象 C一样清晰的看到自己到底在写什么。

C++粉丝们在C++最火热的时候试图将 C++引入系统层开发,但是从来没有成功过。所以不管是嵌入式,还是操作系统,在靠近硬件底层的开发中,都是清一色的 C代码,完全没有 C++的立足之地。

应用层的反思

STL出来后,给人一种 C++可以方便开发应用层逻辑的错觉。由于很多语言层不严密的事情,让STL来以补丁的方式完成,于是很多以为可以象写 java一样写 C++的初学者落入了一个个的坑中。比如 list.size(),在 Windows下vc的 stl是保存了 list的长度的,size()直接 O(1)返回该变量,而在gcc的 stl中,没有保存 list长度,size()将搜索所有节点,O(n)的速度返回。

由于语言层不支持字符串,导致 std::string实现十分不统一,你拷贝构造一个字符串,有的实现是引用,才用 copy-on-write的方法引用。有的地方又是 new,有的实现又是用的内存池,有的实现线程安全,有的实现线程不安全,你完全没法说出同一个语句后面到底做了些什么(见孟岩的《Linux之父话糙理不糙》)。

再比如说我想使用 hash_map,为了跨平台(当你真正编写跨平台代码时,你很难决定目标编译器和他们的版本,想用也用不了 unordered_map),我很难指出一种唯一声明 hash_map的方法,为了保证在不同的编译器下正常的使用 hash_map,你不得不写成这样:

#ifdef __GNUC__

#ifdef __DEPRECATED

#undef __DEPRECATED

#endif

#include

namespace stdext { using namespace __gnu_cxx; }

namespace __gnu_cxx {

template<> struct hash< std::string > {

size_t operator()( const std::string& x ) const {

return hash< const char* >()( x.c_str() );

}

};

}

#else

#ifndef _MSC_VER

#include

#elif (_MSC_VER < 1300) #include

#define IHAVE_NOT_HASH_MAP

#else

#include

#endif

#endif

#ifdef __GNUC__

using namespace __gnu_cxx;

typedef hash_map HashXXXX;

#else

using namespace stdext;

typedef hash_map HashXXXX;

#endif

如果有更好的跨平台写法,麻烦告诉我一下,实在是看不下去了。一个基础容器都让人用的那么辛苦,使得很多 C++程序员成天都在思考各种规范,没时间真正思考下程序设计。

由于语言层要兼容 C,又不肯象 C一样只做好系统层的工作,导致当 C++涉足应用层时,没法接管内存管理,没法支持语言层字符串,没法实现语言层基础容器。所以需要借助一些 stl之类的东西来提供便利,但 stl本身又是充满各种坑的。且不说内存占用大,程序体积大等问题,当编译速度就够呛了。所以为什么 C++下面大家乐意重复造轮子,实现各种基本容器和字符串,导致几乎每个不同的 C++项目,都有自己特定的字符串实现。就是因为大家踩了坑了,才开始觉得需要自己来控制这些细节。stl的出发点是好的,但是只能简单小程序里面随便用一下,真是大项目用,stl就容易把人带沟里了,所以很多大点的 C++项目都是自己实现一套类似 STL的东西,这难道不是违背了 stl设计的初衷了么?

语言层的缺失,让大家为了满足业务开发的快速迭代的需求,创造了很多很基础的设计灵巧的基类,来提供类似垃圾回收,引用计数,copy-on-write,delegate,等数不胜数的功能。每个项目都有一系列 BaseObject 之类的基础类,这样就引入一个误区,两年后你再来看你的代码,发现某个 BaseObject不满足需求了,或者你和另外一个项目 merge代码时,需要合并一些根本属性。图形和GUI这些万年不变的模型还好,应用类开发千变万化,一旦这些设计灵巧的基类不再适应项目发展时,往往面临着全面调整的代价。

打开一个个 C++大牛们 blog,很多地方在教你 std::string的原理,需要注意的事项。map的限制,vector的原理,教你如何实现一个 string。这就叫 “心智负担”,分散你的注意力,这是其他语言里从来见不到的现象。战士不研究怎么上前线杀敌,天天在琢磨抢和炮的原理,成天在思考怎么用枪不会走火,用炮不会炸到自己,这战还怎么打?

所以此后几年,越来越多的人开始反思前两年C++过热所带来的问题,比如高性能网络库 ZeroMQ作者 Martin Sustrik 的:《为什么我希望用C而不是C++来实现ZeroMQ》,比如云风的《云风的 BLOG: C 的回归》,比如引起热议的《Why C++ Is Not “Back”》。

全面被代替

2008年以后,行业竞争越来越激烈,正当大家一边苦恼如何提高开发效率,一边掉到C++的各种坑里的时候,越来越多的应用开发方案涌现出来,他们都能很好的代替 C++。各行各业的开发者逐步相见恨晚的发现了各种更加优秀的方案:需要底层控制追求性能的设计,大家退回到 C;而需要快速迭代的东西大家找到各种动态语言;介于性能和开发速度之间的,有java,知乎上好像很多黑java的,语言是有不足,但是比起C++好很多,没那么多坑,真正考虑面向对象,真正让人把心思放在设计上。所以再黑也不能挡住 java在 tiobe上和 C语言不是第一就是第二的事实,再黑也挡不住 java在云计算,分布式领域的卓越贡献。

所以2005年以后,C++处在一个全面被代替的过程中:

●底层系统:进一步回归 C语言,更强的控制力,更精确的操作。

●网页开发:2006年左右,C++和 fastcgi就被一起赶出 web世界了。

●高性能服务:varnish, nginx, redis 等新的高性能网络服务器都是纯C开发的。

●分布式应用:2007年左右, C++被java和其他动态语言彻底赶跑。

●游戏服务端:2008年后进一步进化为 C 和 脚本,完全看不到胖C++服务端了。

●并行计算:2010年后,go, scala, erlang;而能方便同go接口的,是 C不是C++。

●游戏引擎:没错 C++和脚本,但是这年头越来越多的开源引擎下,引擎类需求越来越少。

●游戏逻辑:脚本

●多媒体:SDL纯C,ffmpeg是纯 C,webrtc的核心部分(DSP, codec)是纯C的。

●移动开发:早年C++还可以开发下塞班,现在基本被 java + objc + swift 赶跑了。

●桌面开发:Qt+Script, C#等都能做出漂亮的跨平台界面。且界面脚本化趋势,不需要C++了。

●网页前端:JavaScript, Html5, Flash

●操作系统:FreeBSD, Open Solaris, Linux, RTOS, Darwin(OS X 底层),都是纯 C

●虚拟技术:qemu / kvm (云计算的基石)纯 C,Xen 纯 C

●数据库:MySQL (核心纯C,外围工具 C++),SQLite 纯 C, PostgreSQL / BDB / unqlite 纯C

●编译器:C/C++并存,不过编译器用脚本写都没关系,我还在某平台用 java写的 C/C++编译器

●大数据:kafka, hadoop, storm, spark 都使用 Java / Jvm 系列技术

●云存储:openstack swift python, hdfs java, 还有好多方案用 go

可以看出,即便 C++的老本行,GUI和图形(确实也还存在一些短期内 C++无法替代的领域,就像交易系统里还有 COBOL一样),这年头也面临的越来越多的挑战,比如新发布的 Rust (如何看待 Rust 的应用前景? – 知乎用户的回答)。可以发现,开发技术多元化,用最适合的技术开发最适合的应用是未来的趋势。而为这些不同的技术编写高性能的可控的公共组件,并轻松的和其他语言接口,正是 C语言的强项。所以不管应用层语言千变万化,对系统级开发语言C的需求还是那么的稳定,而这个过程中,哪里还有 C++的影子呢?

话题总结

所以说未来的趋势是:C x 各种语言混搭 的趋势,从TIOBE上 C++的指数十年间下跌了三倍可以看出,未来还会涌现出更多技术来代替各个角落残存的C++方案,C++的使用情况还会进一步下降。所以题主问学习纯C是否有前途,我觉得如果题主能够左手熟练的掌握 C语言,培养系统化的思维习惯和精确控制内存和硬件的技巧;右手继续学习各种新兴的开发技术,能够应对各个细分领域的快速开发,碰到新问题时能左右开弓,那么未来工作上肯定是能上一个大台阶的。至于C++ 嘛,有时间看看就行,逼不得已要维护别人代码的情况下写两行即可。

故事分享

古代用弓箭进行远距离攻击时,对射手要求较高,瞄准难度大,需要一直使劲保持准心。战斗中一个弓箭手开弓二十次就需要比较长的休息时间。弩的威力远胜于弓,秦弩的制造就如现代的自动步枪一般精密无二,它既可以延长射击,又可以精确瞄准。弩箭的发射速度更是弓箭的数倍,威力惊人。因为弩的操作非常简单,不需要射击技巧,平民很容易掌握它的使用方法。秦国靠着弩兵,在战争中取得了不少优势,被人称为 “虎狼之师”。

日本投降时,天皇下罪己诏。很多士兵不愿意相信这时真的,找种种理由拒绝相信。有的士兵甚至以为天皇的广播是敌人诱降的把戏,于是躲到丛林里继续三五成群的收集情报,袭击可以攻击的目标,等待上司来给他们下达新命令。直到好几年后看到周围的人都穿着日常的便装了,而来巡山的 “敌人” 也从士兵变为了巡逻队,他们都还觉得这是敌人的伪装。而同时,德国战败时,最后的党卫军一直战斗到 1957年才肯投降。

—————————————–

很多人觉得Java慢,C++快Java 10倍以上已经是上世纪的事情了,现代的 Java 只比 C/C++慢 70%,C++连1倍都快不了 Java。也不要觉得动态语言慢,javascript只比C/C++慢 2.7倍。luajit只比 C++慢 5.8倍。在 jit技术发展的今天,C++在性能上离动态语言/java的差距越来越小,可易用性和生产效率上的差距,却和动态语言/java 比起来越来越大。

—————————
最后,补充一张图:

机器学习中的梯度下降法

来自: Datartisan数据工匠(微信号: shujugongjiang)

链接:http://datartisan.com/article/detail/99.html

最优化问题是机器学习算法中非常重要的一部分,几乎每一个机器学习算法的核心都是在处理最优化问题。

本文中我讲介绍一些机器学习领域中常用的且非常掌握的最优化算法,看完本篇文章后你将会明白:
  • 什么是梯度下降法?
  • 如何将梯度下降法运用到线性回归模型中?
  • 如何利用梯度下降法处理大规模的数据?
  • 梯度下降法的一些技巧

让我们开始吧!

梯度下降法
梯度下降法是一个用于寻找最小化成本函数的参数值的最优化算法。当我们无法通过分析计算(比如线性代数运算)求得函数的最优解时,我们可以利用梯度下降法来求解该问题。

梯度下降法的直觉体验

想象一个你经常用来吃谷物或储存受过的大碗,成本函数的形状类似于这个碗的造型。

碗表面上的任一随机位置表示当前系数对应的成本值,碗的底部则表示最优解集对应的成本函数值。梯度下降法的目标就是不断地尝试不同的系数值,然后评估成本函数并选择能够降低成本函数的参数值。重复迭代计算上述步骤直到收敛,我们就能获得最小成本函数值对应的最优解

梯度下降法的过程

梯度下降法首先需要设定一个初始参数值,通常情况下我们将初值设为零(coefficient=0coefficient=0),接下来需要计算成本函数 cost=f(coefficient)cost=f(coefficient) 或者 cost=evaluate(f(coefficient))cost=evaluate(f(coefficient))。然后我们需要计算函数的导数(导数是微积分的一个概念,它是指函数中某个点处的斜率值),并设定学习效率参数(alpha)的值。

coefficient=coefficient−(alpha∗delta) coefficient=coefficient−(alpha∗delta) 重复执行上述过程,直到参数值收敛,这样我们就能获得函数的最优解。

你可以看出梯度下降法的思路多么简单,你只需知道成本函数的梯度值或者需要优化的函数情况即可。接下来我将介绍如何将梯度下降法运用到机器学习领域中。

批量梯度下降法
所有的有监督机器学习算法的目标都是利用已知的自变量(X)数据来预测因变量(Y)的值。所有的分类和回归模型都是在处理这个问题。

机器学习算法会利用某个统计量来刻画目标函数的拟合情况。虽然不同的算法拥有不同的目标函数表示方法和不同的系数值,但是它们拥有一个共同的目标——即通过最优化目标函数来获取最佳参数值。
线性回归模型和逻辑斯蒂回归模型是利用梯度下降法来寻找最佳参数值的经典案例。
我们可以利用多种衡量方法来评估机器学习模型对目标函数的拟合情况。成本函数法是通过计算每个训练集的预测值和真实值之间的差异程度(比如残差平方和)来度量模型的拟合情况。
我们可以计算成本函数中每个参数所对应的导数值,然后通过上述的更新方程进行迭代计算。
在梯度下降法的每一步迭代计算后,我们都需要计算成本函数及其导数的情况。每一次的迭代计算过程就被称为一批次,因此这个形式的梯度下降法也被称为批量梯度下降法。

批量梯度下降法是机器学习领域中常见的一种梯度下降方法。

随机梯度下降法
处理大规模的数据时,梯度下降法的运算效率非常低。

因为梯度下降法在每次迭代过程中都需要计算训练集的预测情况,所以当数据量非常大时需要耗费较长的时间。
当你处理大规模的数据时,你可以利用随机梯度下降法来提高计算效率。
该算法与上述梯度下降法的不同之处在于它对每个随机训练样本都执行系数更新过程,而不是在每批样本运算完后才执行系数更新过程。
随机梯度下降法的第一个步骤要求训练集的样本是随机排序的,这是为了打乱系数的更新过程。因为我们将在每次训练实例结束后更新系数值,所以系数值和成本函数值将会出现随机跳跃的情况。通过打乱系数更新过程的顺序,我们可以利用这个随机游走的性质来避免模型不收敛的问题。
除了成本函数的计算方式不一致外,随机梯度下降法的系数更新过程和上述的梯度下降法一模一样。

对于大规模数据来说,随机梯度下降法的收敛速度明显高于其他算法,通常情况下你只需要一个小的迭代次数就能得到一个相对较优的拟合参数。

梯度下降法的一些建议
本节列出了几个可以帮助你更好地掌握机器学习中梯度下降算法的技巧:

  • 绘制成本函数随时间变化的曲线:收集并绘制每次迭代过程中所得到的成本函数值。对于梯度下降法来说,每次迭代计算都能降低成本函数值。如果无法降低成本函数值,那么可以尝试减少学习效率值。
  • 学习效率:梯度下降算法中的学习效率值通常为0.1,0.001或者0.0001。你可以尝试不同的值然后选出最佳学习效率值。
  • 标准化处理:如果成本函数不是偏态形式的话,那么梯度下降法很快就能收敛。隐蔽你可以事先对输入变量进行标准化处理。
  • 绘制成本均值趋势图:随机梯度下降法的更新过程通常会带来一些随机噪声,所以我们可以考虑观察10次、100次或1000次更新过程误差均值变化情况来度量算法的收敛趋势。
总结 
本文主要介绍了机器学习中的梯度下降法,通过阅读本文,你了解到:

  • 最优化理论是机器学习中非常重要的一部分。
  • 梯度下降法是一个简单的最优化算法,你可以将它运用到许多机器学习算法中。
  • 批量梯度下降法先计算所有参数的导数值,然后再执行参数更新过程。
  • 随机梯度下降法是指从每个训练实例中计算出导数并执行参数更新过程。

你不需要Hadoop做数据分析的10个理由 —— 使用之前必须测试其他替代品

来自:开源中国社区

链接:http://www.oschina.net/translate/hadoop-when-to-use

原文:http://www.fromdev.com/2013/06/hadoop-when-to-use.html

为你的业务使用大数据技术是一个非常有吸引力的事情,现在Apache Hadoop使得它更加吸引人了。

Hadoop是一个大规模可伸缩的数据存储平台,被用作许多大数据项目的基础。

Hadoop很强大,但是它有一个很陡峭的学习曲线,需要公司在时间和其他资源上作大量的投资。

如果正确地应用它,对你的公司来说,Hadoop可以成为一个真正的游戏规则改变者,但它存在很多被错误使用的可能。

另一方面,许多企业(不像是谷歌、Facebook或Twitter)都没有真正的“大数据”来需要用一个巨大的hadoop集群分析事物,然而 hadoop 这个流行语却吸引着他们。

如大卫惠勒所说的:“所有计算机科学的问题都可以用另一个间接的中间层来解决”。 Hadoop提供了这样一种间接层;作为一个软件架构师,当你的最高管理层对一些流行语有很不专业的偏颇认识时,也许真的很难采取正确的决定。

在本文中,我想要建议“应在投资到Hadoop之前尝试一些替代品”。

了解你的数据

总体数据的大小

Hadoop被设计用来在大型数据集上能进行有效的工作。简单给点提示:

  • Hadoop有一个专为大尺寸文件(如几G)设计的文件系统(HDFS)。因此,如果你的数据文件尺寸只是几M的话,建议你合并(通过zip或tar)多个文件到一个文件中,使其尺寸在几百M到几G范围内。
  • HDFS把大文件们拆分存储到以64MB或128MB或更大的块单元中。

如果你的数据集相对较小,那它就不会是hadoop的巨型生态系统的最佳使用之地。这需要你去对你的数据比以往理解更多一些,分析需要什么类型的查询,看看你的数据是否真得“大”。

另一方面,只是通过数据库的大小来测量数据可能是骗人的,因为你的计算量可能会更大。 有时你可能会做更多的数学计算或分析小数据集的排列,这些可以远远大于实际的数据。所以关键是要“了解你的数据,并且很清楚它”。

数据增长数度(增长速率)

你的数据仓库或是其它数据源中可能拥有数个TB的数据。然而,在建立 Hadoop 集群前,你必须考虑到数据的增长。

向数据分析师问几个简单的问题:

  • 数据增长的有多快?这个数据增长的步伐很快么?
  • 数月或数年之后,这个数据将会达到什么样的尺寸?

许多公司的数据增长是以数年而非数月或数日计算的。如果你的数据增长数度非常快,我见建议你考虑一下归档及清理技术(将在本文后面的内容中详述),而非立即上马 Hadoop 集群。

如何减少你的数据量

如果你觉得你的数据实在是太大了,你可以考虑使用下面的方法将数据减少到相对可控的规模上。下面的几个选项都已经被业内成功使用多年。

归档

数据归档是将陈旧数据移动到一个独立数据储存器以长期保留(如果需要)的过程。

这需要对数据、对应用使用情况的充分了解。处理大数据的电子商务公司在现场数据库中保存近期3个月的订单细节数据,而早期订单则保存在一个独立的数据存储器中。

这个方法也可以使用到你的数据仓库中。你可以保存近期的数据以便更快的查询和报告,而将访问频率较低的数据保存在一个其它不同的存储设备中。

考虑清除数据

我们忙于收集数据时经常并不真正确定我们应该保留多少。如果你存储大量可能不是很有用的数据,它就会拖慢你近期数据的处理。弄清你的业务需求,看看是否可以删除旧的数据,把从那些数据分析的趋势存储起来以供后用。这不仅会节省你的空间,而且还可以在分析近期数据时帮助你加快速度。

对这种情况的一个常见的最佳实践是在您的数据仓库中有一些标准列,像创建日期,创建者,更新日期,更新者。现在根据这些列创建一个每日/每月的cron作业,用它清除你不想在你的数据仓库中看到的时段的数据。清除数据的逻辑基于你的领域可能不同,因此在实施它之前应作一些考虑。

如果您正在使用一个归档工具,它也可能是通过很轻松地配置就能清除无用的存档数据。

所有的数据都不重要

你可能受不了为你的业务保留所有数据的诱惑。你的数据有各种各样的来源,比如日志文件、现场交易、供应商整合、ETL工作、营销活动数据等等。但你应该知道,不是所有的数据都是关键业务,把它们都保存在一个数据仓库中可能不是很有帮助反而有害。在它们被存储到你的数据仓库之前,应从源头上过滤不需要的数据。如果你真需要在你的数据库的表里每一列存储和分析那些数据,就准备好发疯吧。

想好你想收集哪些作为数据

假设你进入一个在线视频编辑的业务。你想保存你的用户在每个视频上做的全部更改吗?这会产生巨大的体积。当你感觉到你的数据仓库可能无法处理它的情况下,你可能需要考虑只存储元数据。视频编辑是一个很可能的例子,不过它可能适用于许多其他与你存储数据相关的信息。

一般来说,如果你有一些有关系的数据,你就有机会从多个来源得到它们,而且不是所有的都需要存储在你的数据仓库中。

更智能的分析

聘请理解业务的分析师

现在,你可能已经明白“了解数据”对于有效地管理它们来说是非常重要的。相信我,当你觉得我已经试了所有这些东西时,这一步会帮到你。是时候让我们进入一个如Hadoop这样的大数据解决方案中了。

如果你的数据分析师不懂应从中提取什么出来,Hadoop就将几乎无用。应寄希望于那些理解业务的人。鼓励他们做实验和学习新的方法来看待相同的数据。找出哪些可以与现有基础设施取得唾手可得的收益。

为制订决策使用统计抽样

统计抽样是研究人员和数学家为了对大型数据推断合理结论而使用的一种非常古老的技术。

通过执行一个统计的样本,我们的体积可以极大地减少。不用跟踪数百万或数十亿的数据点,我们只需要随机挑选几千或几百个即可。

该技术不能提供准确的结果,但是它可以被用于对一个大型数据集获得高水平的理解。

定标技术

你真地把关系数据库的处理发挥到极致了吗? 

在你真去探索其他技术之前,我希望你去看看关系型数据库是否能够处理它。人们使用关系数据库已经很久了,已经托管了一些几T字节大小的数据仓库。在你决定进入hadoop之前,你可以对关系数据库尝试以下方法。

数据分区

数据分区就是逻辑上和/或物理上把数据划分成一些更容易维护或访问的部分的过程。分区支持最流行的开放源代码关系数据库(MySQL 分区 和 Postgres 分区 )。

对关系数据库尝试数据库分片的方法

数据库分片可以作为对关系数据库的处理速度发挥到极限的最后一个手段。这种方法可以应用于你可以逻辑上分离数据到不同的节点,并在你的分析中有更少的交叉节点连接的时候。在web应用程序中,一个常见的分片方法是基于把用户和所有与一个用户相关的信息存储在一个节点上来确保最佳的速度。

分片并不容易,如果你有很多复杂的关系,并且没有简单的方法来分离数据到不同的节点上,这个方案可能不适合你。如果你的应用需要有很多交叉节点连接,分片的打算可能会失败。

结论

我曾在不同的公司被高层管理人员要求把Hadoop作为一个可选项去做某些事。要说服他们总是很难,但是当我把这个信息告诉他们后,他们不得不三思而后行。我很幸运,能为我工作的这些公司节省一些钱。

如果你发现为了扩大你的关系数据库,你已经尝试了所有可能的选项,这才是你应该开始考虑建立一个Hadoop集群的时候。

首先,您可能应该使用cloudera提供的虚拟机镜像。它们对于在你现有的基础设施上使用hadoop做快速的概念证明真的是很方便。

你对大数据有何经验?请在评论部分与我们分享。

实际项目中的常见算法

来自:InfoQ

链接:http://www.infoq.com/cn/news/2013/11/Core-algorithms-deployed

原文:http://cstheory.stackexchange.com/questions/19759/core-algorithms-deployed/19773#19773

【编者按】本文原始内容来源于stackexchange,遵循cc-wiki协议;

Emanuele Viola在Stackexchange上提了这样的一个问题,他希望有人能够列举一些目前软件、硬件中正在使用的算法的实际案例来证明算法的重要性,对于大家可能给到的回答,他还提出了几点要求:

1、使用这些算法的软件或者硬件应该是被广泛应用的;

2、例子需要具体,并给出确切的系统、算法的引用地址;

3、在经典的本科生或者博士的课程中应该教过这些算法或者数据结构;

Vijay D的回复获得了最佳答案,他的具体回复内容如下:

Linux内核中的基本数据结构和算法

1、链表、双向链表和无锁链表

2、B+ 树,代码中的注释将会告诉你一些教科书中不能学到的内容:

这是一个简单的B+树实现,我写它的目的是作为练习,并以此了解B+树的工作原理。结果该实现发挥了它的实用价值。

一个不经常在教科书中提及的技巧:最小值应该放在右侧,而不是左侧。一个节点内所有被使用的槽位应该在左侧,没有使用的节点应该为NUL,大部分的操作只遍历一次所有的槽位,在第一个NUL处终止。

3、带权重的有序列表用于互斥锁、驱动等;

4、红黑树用于调度、虚拟内存管理、跟踪文件描述符和目录条目等;

5、区间树

6、Radix树,用于内存管理、NFS相关查找和网络相关的功能;

radix树的一个常见的用法是保存页面结构体的指针;

7、优先级堆,文字上的描述,主要是在教科书中实现,用于control group系统;

包含指针的只允许简单插入的静态大小优先级堆,基于CLR(算法导论)第七章

8、哈希函数,引用Knuth和他的一篇论文:

Knuth建议选择与机器字长所能表达的最大整数约成黄金比例的素数来做乘法散列,Chuck Lever 证实了这个技术的有效性;

http://www.citi.umich.edu/techreports/reports/citi-tr-00-1.pdf

这些选择的素数是位稀疏的,也就是说对他们的操作可以使用位移和加法来替换机器中很慢的乘法操作;

9、有些代码,比如这个驱动,他们是自己实现的哈希函数

10、哈希表,用于实现索引节点、文件系统完整性检查等;

11、位数组,用于处理flags、中断等,在Knuth第四卷中有对其特性的描述;

12、Semaphores 和 spin locks

13、二叉树搜索用于中断处理、登记缓存查找等;

14、使用B-树进行二叉树查找;

15、深度优先搜索和他的变体被应用于目录配置;

在命名空间树中执行一个修改过的深度优先算法,开始(和终止于)start_handle所确定的节点。当与参数匹配的节点被发现以后,回调函数将会被调用。如果回调函数返回一个非空的值,搜索将会立即终止,这个值将会回传给调用函数;

16、广度优先搜索用于在运行时检查锁的正确性;

17、链表上的合并排序用于垃圾回收、文件系统管理等;

18、在某个驱动程序的库函数里,冒泡排序居然也被实现了

19、Knuth-Morris-Pratt 字符串匹配;

Knuth、Morris和 Pratt [1]实现了一个线性时间复杂度字符串匹配算法。该算法完全规避了对转换函数DELTA的显式计算。其匹配时间为O(n)(其中n是文本长度),只使用一个辅助函数PI[1…m](其中m是模式的长度),模式的预处理时间是O(m)。PI这个数组允许DELTA函数在需要时能迅速运行。大体上,对任意状态q=0,1,…,m和任意SIGMA中的字符”a”,PI[“q”]保存了独立于”a”的信息,并用于计算DELTA(“q”, “a”)。由于PI这个数组只包含m个条目,而DELTA包含O(m|SIGMA|)个条目,我们通过计算PI进而在预处理时间保存|SIGMA|的系数,而非计算DELTA。

[1] Cormen, Leiserson, Rivest, Stein Introdcution to Algorithms, 2nd Edition, MIT Press

[2] See finite automation theory

20、Boyer-Moore模式匹配,如下是引用和对其他算法的使用建议;

Boyer-Moore字符串匹配算法:

[1] A Fast String Searching Algorithm, R.S. Boyer and Moore. Communications of the Association for Computing Machinery, 20(10), 1977, pp. 762-772.http://www.cs.utexas.edu/users/moore/publications/fstrpos.pdf

[2] Handbook of Exact String Matching Algorithms, Thierry Lecroq, 2004 http://www-igm.univ-mlv.fr/~lecroq/string/string.pdf

注意:由于Boyer-Moore(BM)自右向左做匹配,有一种可能性是一个匹配分布在不同的块中,这种情况下是不能找到任何匹配的。

如果你想确保这样的事情不会发生,使用Knuth-Pratt-Morris(KMP)算法来替代。也就是说,根据你的设置选择合适的字符串查找算法。

如果你使用文本搜索架构来过滤、网络入侵检测(NIDS)或者任何安全为目的,那么选择KMP。如果你关乎性能,比如你在分类数据包,并应用服务质量(QoS)策略,并且你不介意可能需要在分布在多个片段中匹配,然后就选择BM。

Chromium 浏览器中的数据结构和算法

1、伸展树

此树会被分配策略参数化,这个策略负责在C的自由存储空间和区域中分配列表,参见zone.h

2、Demo中使用了Voronoi图

3、基于Bresenham算法的标签管理

同时,代码中还包含了一些第三方的算法和数据结构,例如:

1、二叉树

2、红黑树

3、AVL树

4、用于压缩的Rabin-Karp字符串匹配

5、计算自动机的后缀

6、苹果实现的布隆过滤器

7、布氏算法

编程语言类库

1、C++ STL,包含的有列表、堆、栈、向量、排序、搜索和堆操作算法

2、Java API 非常广泛,包含的太多

3、Boost C++ 类库,包含了诸如Boyer-Moore和Knuth-Morris-Pratt字符串匹配算法等;

分配和调度算法

1、最近最少使用算法有多种实现方式,在Linux内核中是基于列表实现的;

2、其他可能需要了解的是先入先出、最不常用和轮询;

3、VAX、VMS系统中大量使用FIFO的变体;

4、Richard Carr的时钟算法被用于Linux中页面帧替换;

5、Intel i860处理器中使用了随机替换策略;

6、自适应缓存替换被用于一些IBM的存储控制中,由于专利原因在PostgreSQL只有简单的应用;

7、Knuth在TAOCP第一卷中提到的伙伴内存分配算法被用于Linux内核中,FreeBSD和Facebook都在使用jemalloc并发分配器;

*nix系统中的核心组件

1、grep和awk都实现了使用Thompson-McNaughton-Yamada构建算法实现从正则表达式中创建NFA

2、tsort实现了拓扑排序

3、fgrep实现了Aho-Corasick 字符串匹配算法;

4、GNU grep,据作者Mike Haertel所说,实现了Boyer-Moore算法;

5、Unix中的crypt(1)实现了哑谜机(Enigma Machine)中的加密算法的变种;

6、Doug Mcllroy基于和James合作的原型实现的Unix diff,比用来计算Levenshtein距离的标准动态规划算法更好,Linux版本被用来计算最短编辑距离;

加密算法

1、Merkle树,尤其是Tiger Tree Hash的变种,用于点对点的程序,例如GTK Gnutella 和LimeWire;

2、MD5用于为软件包提供校验码,还用于*nix系统(Linux实现)中的完整性校验,同时他还支持Windows和OS X系统;

3、OpenSSL实现了需要加密算法,诸如AES,Blowfish,DES,SHA-1,SHA-2,RSA,DES等;

编译器

1、yacc和bison实现了LALR解析器

2、支配算法用于基于SSA形式的最优化编译器;

3、lex和flex将正则表达式编译为NFA;

压缩和图片处理

1、为GIF图片格式而出现的Lempel-Zivsraf算法在图片处理程序中经常被应用,从一个简单的*nix组件转化为一个复杂的程序;

2、运行长度编码被用于生成PCX文件(用于Paintbrush这个程序中),压缩BMP文件和TIFF文件;

3、小波压缩(Wavelet压缩)是JPEG 2000的基础,所以所有生成JPEG 2000文件的数码相机都是实现了这个算法;

4、Reed-Solomon纠错用于Linux内核、CD驱动、条形码读取,并且结合卷积从航行团队进行图片传输;

冲突驱动条款学习算法(Conflict Driven Clause Learning)

自2000年以来,在工业标准中的SAT(布尔满足性问题)求解器的运行时间每年都在成倍减少。这一发展的一个非常重要的原因是冲突驱动条款学习算法(Conflict Driven Clause Learning)的使用,它结合了Davis Logemann和Loveland的约束编程和人工智能研究技术的原始论文中关于布尔约束传播的算法。具体来说,工业建模中SAT被认为是一个简单的问题(见讨论)。对我来说,这是近代最伟大的成功故事之一,因为它结合了先进的算法、巧妙的设计思路、实验反馈,并以一致的共同努力来解决这个问题。Malik和Zhang的CACM论文是一个很好的阅读材料。许多大学都在教授这个算法,但通常是在逻辑或形式化方法的课程中。

微博热议
Databricks大数据公司联合创始人@hashjoin首先并在微博上传播了这个内容:

很多学生和软件工程师都会好奇自己过去学习的算法有什么实际应用的价值。这个StackExchange的回答列出了各种经典算法在几个开源项目中的应用。http://t.cn/8kAP4yG 作者罗列出了从最基础的hash table到字符串匹配和加密算法等在Chromium和Linux内核的代码。查看开源代码是学习算法实现一个好途径。

@GeniusVczh:

所谓的算法实现就跟背书一样,所以如果不是为了学习语法,千万不要看那些带代码的编程书,或者编程书里面的代码。以学习为目的的话,东西就自己做,然后自己用,用出翔了,你就知道他为什么不好了。

@左耳朵耗子:

说算法没啥用的人基本上说明他只在简单的堆砌业务功能代码的井底中。

@薛正华-中国科学院:

我一直觉得在讲述每一个技术前,最好先让大家知道这个技术能干什么,曾经干过什么,将来或许能用在什么地方。这会增加大家对技术的兴趣、理解和灵活运用,会让大家学的更好。

计算几何常用算法,ACM竞赛必备~

来自2010年百度文库

原作者不详

1、矢量减法

设二维矢量 P = (x1,y1) ,Q = (x2,y2)
则矢量减法定义为: P – Q = ( x1 – x2 , y1 – y2 )
显然有性质 P – Q = – ( Q – P )
如不加说明,下面所有的点都看作矢量,两点的减法就是矢量相减;

2、矢量叉积

设矢量P = (x1,y1) ,Q = (x2,y2)
则矢量叉积定义为: P × Q = x1*y2 – x2*y1   得到的是一个标量
显然有性质 P × Q = – ( Q × P )   P × ( – Q ) = – ( P × Q )
如不加说明,下面所有的点都看作矢量,点的乘法看作矢量叉积;
叉乘的重要性质:
> 若 P × Q > 0 , 则P 在Q的顺时针方向
> 若 P × Q < 0 , 则P 在Q的逆时针方向 > 若 P × Q = 0 , 则P 与Q共线,但可能同向也可能反向

3、判断点在线段上

设点为Q,线段为P1P2 ,判断点Q在该线段上的依据是:
( Q – P1 ) × ( P2 – P1 ) = 0 且 Q 在以 P1,P2为对角顶点的矩形内

4、判断两线段是否相交

我们分两步确定两条线段是否相交:

(1)快速排斥试验
设以线段 P1P2 为对角线的矩形为R, 设以线段 Q1Q2 为对角线的矩形为T,如果R和T不相
交,显然两线段不会相交;

(2)跨立试验
如果两线段相交,则两线段必然相互跨立对方,如图1所示。在图1中,P1P2跨立Q1Q2 ,则
矢量 ( P1 – Q1 ) 和( P2 – Q1 )位于矢量( Q2 – Q1 ) 的两侧,即
( P1 – Q1 ) × ( Q2 – Q1 ) * ( P2 – Q1 ) × ( Q2 – Q1 ) < 0 上式可改写成 ( P1 - Q1 ) × ( Q2 - Q1 ) * ( Q2 - Q1 ) × ( P2 - Q1 ) > 0
当 ( P1 – Q1 ) × ( Q2 – Q1 ) = 0 时,说明   ( P1 – Q1 ) 和 ( Q2 – Q1 )共线,

但是因为已经通过快速排斥试验,所以 P1 一定在线段 Q1Q2上;同理,( Q2 – Q1 ) ×(
P2 – Q1 ) = 0 说明 P2 一定在线段 Q1Q2上。

所以判断P1P2跨立Q1Q2的依据是:
( P1 – Q1 ) × ( Q2 – Q1 ) * ( Q2 – Q1 ) × ( P2 – Q1 ) ≥ 0
同理判断Q1Q2跨立P1P2的依据是:
( Q1 – P1 ) × ( P2 – P1 ) * ( P2 – P1 ) × ( Q2 – P1 ) ≥ 0
至此已经完全解决判断线段是否相交的问题。

5、判断线段和直线是否相交

如果线段 P1P2和直线Q1Q2相交,则P1P2跨立Q1Q2,即:
( P1 – Q1 ) × ( Q2 – Q1 ) * ( Q2 – Q1 ) × ( P2 – Q1 ) ≥ 0

6、判断矩形是否包含点

只要判断该点的横坐标和纵坐标是否夹在矩形的左右边和上下边之间。
判断线段、折线、多边形是否在矩形中
因为矩形是个凸集,所以只要判断所有端点是否都在矩形中就可以了。

6、判断矩形是否在矩形中

只要比较左右边界和上下边界就可以了。

7、判断圆是否在矩形中

圆在矩形中的充要条件是:圆心在矩形中且圆的半径小于等于圆心到矩形四边的距离的最
小值。

8、判断点是否在多边形中

以点P为端点,向左方作射线L,由于多边形是有界的,所以射线L的左端一定在多边形外,
考虑沿着L从无穷远处开始自左向右移动,遇到和多边形的第一个交点的时候,进入到了多
边形的内部,遇到第二个交点的时候,离开了多边形,……所以很容易看出当L和多边形的
交点数目C是奇数的时候,P在多边形内,是偶数的话P在多边形外。
但是有些特殊情况要加以考虑。如果L和多边形的顶点相交,有些情况下交点只能计算一个
,有些情况下交点不应被计算(你自己画个图就明白了);如果L和多边形的一条边重合,
这条边应该被忽略不计。为了统一起见,我们在计算射线L和多边形的交点的时候,1。对
于多边形的水平边不作考虑;2。对于多边形的顶点和L相交的情况,如果该顶点是其所属
的边上纵坐标较大的顶点,则计数,否则忽略;3。对于P在多边形边上的情形,直接可判
断P属于多边行。由此得出算法的伪代码如下:

1、count ← 0;
2、以P为端点,作从右向左的射线L;
3、for 多边形的每条边s
4、do if P在边s上
5、then return true;
6、if s不是水平的
7、then if s的一个端点在L上且该端点是s两端点中纵坐标较大的端点
9、then count ← count+1
10、else if s和L相交
11、then count ← count+1;
12i、f count mod 2 = 1
13、then return true
14、else return false;

其中做射线L的方法是:设P’的纵坐标和P相同,横坐标为正无穷大(很大的一个正数),
则P和P’就确定了射线L。这个算法的复杂度为O(n)。

9、判断线段是否在多边形内

线段在多边形内的一个必要条件是线段的两个端点都在多边形内;
如果线段和多边形的某条边内交(两线段内交是指两线段相交且交点不在两线段的端点)
,因为多边形的边的左右两侧分属多边形内外不同部分,所以线段一定会有一部分在多边
形外。于是我们得到线段在多边形内的第二个必要条件:线段和多边形的所有边都不内交

线段和多边形交于线段的两端点并不会影响线段是否在多边形内;但是如果多边形的某个
顶点和线段相交,还必须判断两相邻交点之间的线段是否包含与多边形内部。因此我们可
以先求出所有和线段相交的多边形的顶点,然后按照X-Y坐标排序,这样相邻的两个点就是
在线段上相邻的两交点,如果任意相邻两点的中点也在多边形内,则该线段一定在多边形
内。证明如下:
命题1:
如果线段和多边形的两相邻交点P1 ,P2的中点P’ 也在多边形内,则P1, P2之间的所有点
都在多边形内。
证明:
假设P1,P2之间含有不在多边形内的点,不妨设该点为Q,在P1, P’之间,因为多边形是闭
合曲线,所以其内外部之间有界,而P1属于多边行内部,Q属于多边性外部,P’属于多边性
内部,P1-Q-P’完全连续,所以P1Q和QP’一定跨越多边形的边界,因此在P1,P’之间至少还
有两个该线段和多边形的交点,这和P1P2是相邻两交点矛盾,故命题成立。证毕
由命题1直接可得出推论:
推论2:
设多边形和线段PQ的交点依次为P1,P2,……Pn,其中Pi和Pi+1是相邻两交点,线段PQ在多
边形内的充要条件是:P,Q在多边形内且对于i =1, 2,……, n-1,Pi ,Pi+1的中点也在多
边形内。

在实际编程中,没有必要计算所有的交点,首先应判断线段和多边形的边是否内交,倘若
线段和多边形的某条边内交则线段一定在多边形外;如果线段和多边形的每一条边都不内
交,则线段和多边形的交点一定是线段的端点或者多边形的顶点,只要判断点是否在线段
上就可以了。
至此我们得出算法如下:
1、f 线端PQ的端点不都在多边形内
2、hen return false;
3、点集pointSet初始化为空;
4、for 多边形的每条边s
5、do if 线段的某个端点在s上
6、then 将该端点加入pointSet;
7、else if s的某个端点在线段PQ上
8、then 将该端点加入pointSet;
9、else if s和线段PQ相交           // 这时候可以肯定是内交
10、 then return false;
11、将pointSet中的点按照X-Y坐标排序,X坐标小的排在前面,对于X坐标相同的点,Y坐
标小的排在前面;
12、for pointSet中每两个相邻点 pointSet[i] , pointSet[ i+1]
13、do if pointSet[i] , pointSet[ i+1] 的中点不在多边形中
14、then return false;
15、return true;

这个算法的复杂度也是O(n)。其中的排序因为交点数目肯定远小于多边形的顶点数目n,所
以最多是常数级的复杂度,几乎可以忽略不计。

10、判断折线在多边形内

只要判断折线的每条线段是否都在多边形内即可。设折线有m条线段,多边形有n个顶点,
则复杂度为O(m*n)。

11、判断多边形是否在多边形内
只要判断多边形的每条边是否都在多边形内即可。判断一个有m个顶点的多边形是否在一个
有n个顶点的多边形内复杂度为O(m*n)。

12、判断矩形是否在多边形内

将矩形转化为多边形,然后再判断是否在多边形内。

13、判断圆是否在多边形内

只要计算圆心到多边形的每条边的最短距离,如果该距离大于等于圆半径则该圆在多边形
内。计算圆心到多边形每条边最短距离的算法在后文阐述。

14、判断点是否在圆内

计算圆心到该点的距离,如果小于等于半径则该点在圆内。

15、判断线段、折线、矩形、多边形是否在圆内

因为圆是凸集,所以只要判断是否每个顶点都在圆内即可。

16、判断圆是否在圆内

设两圆为O1,O2,半径分别为r1, r2,要判断O2是否在O1内。先比较r1,r2的大小,如果r
117、计算点到线段的最近点

如果该线段平行于X轴(Y轴),则过点point作该线段所在直线的垂线,垂足很容易求得,
然后计算出垂足,如果垂足在线段上则返回垂足,否则返回离垂足近的端点;
如果该线段不平行于X轴也不平行于Y轴,则斜率存在且不为0。设线段的两端点为pt1和pt
2,斜率为:
k = ( pt2.y – pt1. y ) / (pt2.x – pt1.x );
该直线方程为:
y = k* ( x – pt1.x) + pt1.y
其垂线的斜率为 – 1 / k,
垂线方程为:
y = (-1/k) * (x – point.x) + point.y
联立两直线方程解得:
x = ( k^2 * pt1.x + k * (point.y – pt1.y ) + point.x ) / ( k^2 + 1)
y = k * ( x – pt1.x) + pt1.y;
然后再判断垂足是否在线段上,如果在线段上则返回垂足;如果不在则计算两端点到垂足
的距离,选择距离垂足较近的端点返回。

18、计算点到折线、矩形、多边形的最近点

只要分别计算点到每条线段的最近点,记录最近距离,取其中最近距离最小的点即可。

19、计算点到圆的最近距离
如果该点在圆心,则返回UNDEFINED
连接点P和圆心O,如果PO平行于X轴,则根据P在O的左边还是右边计算出最近点的横坐标为
centerPoint.x – radius 或 centerPoint.x + radius, 如图4 (a)所示;如果如果PO平
行于Y轴,则根据P在O的上边还是下边计算出最近点的纵坐标为 centerPoint.y -+radius
或 centerPoint.y – radius, 如图4 (b)所示。
如果PO不平行于X轴和Y轴,则PO的斜率存在且不为0,如图4(c)所示。这时直线PO斜率为

k = ( P.y – O.y )/ ( P.x – O.x )
直线PO的方程为:
y = k * ( x – P.x) + P.y
设圆方程为:
(x – O.x ) ^2 + ( y – O.y ) ^2 = r ^2,
联立两方程组可以解出直线PO和圆的交点,取其中离P点较近的交点即可。

20、计算两条共线的线段的交点

对于两条共线的线段,它们之间的位置关系有图5所示的几种情况。
图5(a)中两条线段没有交点;图5 (b) 和 (d) 中两条线段有无穷焦点;图5 (c) 中两条线
段有一个交点。设line1是两条线段中较长的一条,line2是较短的一条,如果line1包含了
line2的两个端点,则是图5(d)的情况,两线段有无穷交点;如果line1只包含line2的一个
端点,那么如果line1的某个端点等于被line1包含的line2的那个端点,则是图5(c)的情况
,这时两线段只有一个交点,否则就是图5(c)的情况,两线段也是有无穷的交点;如果li
ne1不包含line2的任何端点,则是图5(a)的情况,这时两线段没有交点。

21、计算线段或直线与线段的交点
设一条线段为L0 = P1P2,另一条线段或直线为L1 = Q1Q2 ,要计算的就是L0和L1的交点。

1、首先判断L0和L1是否相交(方法已在前文讨论过),如果不相交则没有交点,否则说
明L0和L1一定有交点,下面就将L0和L1都看作直线来考虑。
2、如果P1和P2横坐标相同,即L0平行于Y轴
a) 若L1也平行于Y轴,
i. 若P1的纵坐标和Q1的纵坐标相同,说明L0和L1共线,假如L1是直线的话他们有无穷的交
点,假如L1是线段的话可用”计算两条共线线段的交点”的算法求他们的交点(该方法在前
文已讨论过);
ii. 否则说明L0和L1平行,他们没有交点;
b) 若L1不平行于Y轴,则交点横坐标为P1的横坐标,代入到L1的直线方程中可以计算出交
点纵坐标;
3、如果P1和P2横坐标不同,但是Q1和Q2横坐标相同,即L1平行于Y轴,则交点横坐标为Q
1的横坐标,代入到L0的直线方程中可以计算出交点纵坐标;
4、如果P1和P2纵坐标相同,即L0平行于X轴
a) 若L1也平行于X轴,
i. 若P1的横坐标和Q1的横坐标相同,说明L0和L1共线,假如L1是直线的话他们有无穷的交
点,假如L1是线段的话可用”计算两条共线线段的交点”的算法求他们的交点(该方法在前
文已讨论过);
ii. 否则说明L0和L1平行,他们没有交点;
b) 若L1不平行于X轴,则交点纵坐标为P1的纵坐标,代入到L1的直线方程中可以计算出交
点横坐标;
5、如果P1和P2纵坐标不同,但是Q1和Q2纵坐标相同,即L1平行于X轴,则交点纵坐标为Q
1的纵坐标,代入到L0的直线方程中可以计算出交点横坐标;
6、剩下的情况就是L1和L0的斜率均存在且不为0的情况
a) 计算出L0的斜率K0,L1的斜率K1 ;
b) 如果K1 = K2
i. 如果Q1在L0上,则说明L0和L1共线,假如L1是直线的话有无穷交点,假如L1是线段的话
可用”计算两条共线线段的交点”的算法求他们的交点(该方法在前文已讨论过);
ii. 如果Q1不在L0上,则说明L0和L1平行,他们没有交点。
c) 联立两直线的方程组可以解出交点来

说明:这个算法并不复杂,但是要分情况讨论清楚,尤其是当两条线段共线的情况需要单
独考虑,所以在前文将求两条共线线段的算法单独写出来。另外,一开始就先利用矢量叉
乘判断线段与线段(或直线)是否相交,如果结果是相交,那么在后面就可以将线段全部
看作直线来考虑。

22、求线段或直线与折线、矩形、多边形的交点

分别求与每条边的交点即可。

23、求线段或直线与圆的交点

设圆心为O,圆半径为r,直线(或线段)L上的两点为P1,P2。
1、如果L是线段且P1,P2都包含在圆O内,则没有交点;否则进行下一步
2、如果L平行于Y轴,
a) 计算圆心到L的距离dis
b) 如果dis > r 则L和圆没有交点;
c) 利用勾股定理,可以求出两交点坐标,如图6(a)所示;但要注意考虑L和圆的相切情况
3、如果L平行于X轴,做法与L平行于Y轴的情况类似;
4、如果L既不平行X轴也不平行Y轴,可以求出L的斜率K,然后列出L的点斜式方程,和圆方程联立即可求解出L和圆的两个交点;
5、如果L是线段,对于2,3,4中求出的交点还要分别判断是否属于该线段的范围内。

实时处理日均 50 亿会话,解析 Twitter Answers 的架构

英文:Twitter

译者:伯乐在线-刘志成

链接:http://blog.jobbole.com/87067/

去年我们发布了Answers,至今移动社区产生了惊人的使用量,让我们感到兴奋不已。现在Answers每天处理50亿次会话,并且这个数量在持续增加。上亿设备每秒向Answers端点发送数以百万计的请求。在你已经阅读到此处的这段时间里,Answers后台收到并处理了一千万次分析事件。

其中的挑战是如何利用这些信息向移动开发者提供可靠的、实时的、有实际价值的洞见(视角)去了解他们的移动应用。

在高层,我们依靠 组件解耦、异步通信、在应对灾难性故障时优雅地服务降级等原则来帮助架构决策。我们使用Lambda架构将数据完整性和实时数据更新结合起来。

在实践过程中,我们需要设计一个能够接收并保存事件、执行离线和实时计算且能将上述两种计算结果整合成相关信息的系统。这些行为全部都要以百万次每秒的规模执行。

让我们从第一个挑战开始:接受并处理这些事件。

事件接收

在设计设备-服务器通信的时候,我们的目标是:减少对电池和网络使用的影响;确保数据的可靠性;接近实时地获取数据。为了减少对设备的影响,我们批量地发送分析数据并且在发送前对数据进行压缩。为了保证这些宝贵的数据始终能够到达我们的服务器,在传输失败随机退避后以及达到设备存储达到上限时,设备会进行重传。为了确保数据能够尽快到达服务器,我们设置来多个触发器来使设备尝试发送:当程序运行于前台的时候,事件触发器每分钟触发一次;一个消息数量触发器和程序转入后台触发器。

这样的通信协议导致设备每秒发送来数以万计压缩过的有效载荷。每一个载荷都包含数十条事件。为了能够可靠的、易于线性伸缩的方式去处理载荷,接收事件的服务必须极度简单。

这个服务使用GO语言编写,这个服务使用了亚马逊弹性负载均衡器(ELB),并将每一个消息负荷放入一个持久化的Kafka队列。

存储

Kafka是一个持久存储器,因为它把收到的消息写入磁盘并且每个消息都有多份冗余。因此一旦我们知道信息到了Kafka队列,我们就可以通过延迟处理、再处理来容忍下游延迟和下游失败。然而,Kafka不是我们历史数据的永久真理之源——按照上文提到的速度,仅仅是几天的数据,我们也需要数以百计的box来存储。因此我们把Kafka集群配置为将消息只保留几个小时(这些时间足够我们处理不期而至的重大故障)并且将数据尽快地存入永久存储——亚马逊简易存储服务(Amazon S3)。

我们广泛地使用Storm来进行实时数据处理,第一个相关的Topology就是从Kafka读取信息并存储到Amazon S3上。

批量计算

一旦这些数据存到了S3上,我们可以使用亚马逊弹性MapReduce(Amazon EMR)来计算我们的数据能够计算的任何东西。这既包括要展示在客户的仪表盘上的数据,也包括我们为了开发新功能而开发的实验性的任务。

我们使用Cascading框架编写、Amazon EMR执行MapReduce程序。 Amazon EMR将我们存储到S3上的数据作为输入,处理完毕后,再将结果存入S3。我们通过运行在Storm上的调度topology来探测程序执行完毕,并将结果灌入Cassandra集群,这样结果就能用于亚秒级查询API。

实时计算

迄今,我们描述的是一个能够执行分析计算的持久的容错的框架。然而,存在一个显眼的问题——这个框架不是实时的。一些计算每小时计算一次,有的计算需要一整天的数据作为输入。计算时间从几分钟到几小时不等,把S3上的输出导入到服务层也需要这么多时间。因此,在最好情况下,我们的数据也总是拖后几个小时,显然不能满足实时和可操作的目标。

为了达成实时的目标,数据涌入后进行存档的同时,我们对数据进行流式计算。

就像我们的存储Topology读取数据一样,一个独立的Storm Topology实时地从Kafka Topic中读取数据然后进行实时计算,计算的逻辑和MapReduce任务一样。这些实时计算的结果放在另一个独立的Cassandra集群里以供实时查询。

为了弥补我们在时间以及在资源方面可能的不足,我们没有在批量处理层中而是在实时计算层中使用了一些概率算法,如布隆过滤器、HyperLogLog(也有一些自己开发的算法)。相对于那些蛮力替代品,这些算法在空间和时间复杂度上有数量级的优势,同时只有可忽略的精确度损失。

合并

现在我们拥有两个独立生产出的数据集(批处理和实时处理),我们怎么将二者合并才能得到一个一致的结果?

我们在API的逻辑中,根据特定的情况分别使用两个数据集然后合并它们。

因为批量计算是可重现的,且相对于实时计算来说更容错,我们的API总是倾向于使用批量产生的数据。例如,API接到了一个三十天的时间序列的日活跃用户数量数据请求,它首先会到批量数据Cassandra集群里查询全范围的数据。如果这是一个历史数据检索,所有的数据都已经得到。然而,查询的请求更可能会包含当天,批量产生的数据填充了大部分结果,只有近一两天的数据会被实时数据填充。

错误处理

让我们来温习几个失效的场景,看一下这样的架构在处理错误的时候, 是如何避免宕机或者损失数据,取之以优雅地降级。

我们在上文中已经讨论过设备上的回退重试策略。在设备端网络中断、服务器端短时无服务情况下,重试保证数据最终能够到达服务器。随机回退确保设备不会在某区域网络中断或者后端服务器短时间不可用之后,不会压垮(DDos攻击)服务器。

当实时处理层失效时,会发生什么?我们待命的工程师会受到通知并去解决问题。因为实时处理层的输入是存储在持久化的Kafka集群里,所以没有数据会丢失;等实时处理恢复之后,它会赶上处理那些停机期间应该处理的数据。

因为实时处理和批处理是完全解耦的,批处理层完全不会受到影响。因此唯一的影响就是实时处理层失效期间,对数据点实时更新的延迟。

如果批处理层有问题或者严重延迟的话,会发生什么?我们的API会无缝地多获取实时处理的数据。一个时间序列数据的查询,可能先前只取一天的实时处理结果,现在就需要查询两到三天的实时处理结果。因为实时处理和批处理是完全解耦的,实时处理不受影响继续运行。同时,我们的待命工程师会得到消息并且解决批处理层的问题。一旦批处理层恢复正常,它会执行那些延迟的数据处理任务,API也会无缝切换到使用现在可以得到的批处理的结果。

我们系统后端架构由四大组件构成:事件接收,事件存储,实时计算和批量计算。各个组件之间的持久化队列确保任意组件的失效不会扩散到其他组件,并且后续可以从中断中恢复。API可以在计算层延迟或者失效时无缝地优雅降级,在服务恢复后重新恢复;这些都是由API内部的检索逻辑来保证的。

Answer的目标是创建一个仪表盘,这个仪表盘能够把了解你的用户群变得非常简单。因此你可以将时间花费在打造令人惊叹的用户体验上,而不是用来掘穿数据。

非常感谢致力于将此架构实现(付诸现实)的Answers团队。还有《Big Data》这本书的作者Nathan Marz。

几款主流 NoSQL 数据库的对比

来源:VaJoy Larn

链接:http://www.cnblogs.com/vajoy/p/5471308.html

最近小组准备启动一个 node 开源项目,从前端亲和力、大数据下的IO性能、可扩展性几点入手挑选了 NoSql 数据库,但具体使用哪一款产品还需要做一次选型。

我们最终把选项范围缩窄在 HBase、Redis、MongoDB、Couchbase、LevelDB 五款较主流的数据库产品中,本文将主要对它们进行分析对比。

鉴于缺乏项目中的实战经验沉淀,本文内容和观点主要还是从各平台资料搜罗汇总,也不会有太多深入或底层原理探讨。

本文所引用的资料来源将示于本文尾部。所汇总的内容仅供参考,若有异议望指正。

HBase

HBase 是 Apache Hadoop 中的一个子项目,属于 bigtable 的开源版本,所实现的语言为Java(故依赖 Java SDK)。HBase 依托于 Hadoop 的 HDFS(分布式文件系统)作为最基本存储基础单元。

HBase在列上实现了 BigTable 论文提到的压缩算法、内存操作和布隆过滤器。HBase的表能够作为 MapReduce任务的输入和输出,可以通过Java API来访问数据,也可以通过REST、Avro或者Thrift的API来访问。
1. 特点

1.1 数据格式

HBash 的数据存储是基于列(ColumnFamily)的,且非常松散—— 不同于传统的关系型数据库(RDBMS),HBase 允许表下某行某列值为空时不做任何存储(也不占位),减少了空间占用也提高了读性能。

不过鉴于其它NoSql数据库也具有同样灵活的数据存储结构,该优势在本次选型中并不出彩。
我们以一个简单的例子来了解使用 RDBMS 和 HBase 各自的解决方式:

⑴ RDBMS方案:

其中Article表格式:

Author表格式:

⑵ 等价的HBase方案:

对于前端而言,这里的 Column Keys 和 Column Family 可以看为这样的关系:

columId1 = { //id=1的行

    article: {  //ColumnFamily-article

        title: XXX,  //ColumnFamily-article下的key之一

        content: XXX,

        tags: XXX

    },

    author: {  //ColumnFamily-author

        name: XXX

        nickname: XXX

    }

}

1.2 性能

HStore存储是HBase存储的核心,它由两部分组成,一部分是MemStore,一部分是StoreFiles。

MemStore 是 Sorted Memory Buffer,用户写入的数据首先会放入MemStore,当MemStore满了以后会Flush成一个StoreFile(底层实现是HFile),当StoreFile文件数量增长到一定阈值,会触发Compact合并操作,将多个StoreFiles合并成一个StoreFile,合并过程中会进行版本合并和数据删除,因此可以看出HBase其实只有增加数据,所有的更新和删除操作都是在后续的compact过程中进行的,这使得用户的写操作只要进入内存中就可以立即返回,保证了HBase I/O的高性能。

1.3 数据版本

Hbase 还能直接检索到往昔版本的数据,这意味着我们更新数据时,旧数据并没有即时被清除,而是保留着:

Hbase 中通过 row+columns 所指定的一个存贮单元称为cell。每个 cell都保存着同一份数据的多个版本——版本通过时间戳来索引。

时间戳的类型是 64位整型。时间戳可以由Hbase(在数据写入时自动 )赋值,此时时间戳是精确到毫秒的当前系统时间。时间戳也可以由客户显式赋值。如果应用程序要避免数据版本冲突,就必须自己生成具有唯一性的时间戳。每个 cell中,不同版本的数据按照时间倒序排序,即最新的数据排在最前面。

为了避免数据存在过多版本造成的的管理 (包括存贮和索引)负担,Hbase提供了两种数据版本回收方式。一是保存数据的最后n个版本,二是保存最近一段时间内的版本(比如最近七天)。用户可以针对每个列族进行设置。

1.4 CAP类别
属于CP类型。

2. Node下的使用

HBase的相关操作可参考下表:

在node环境下,可通过 node-hbase 来实现相关访问和操作,注意该工具包依赖于 PHYTHON2.X(3.X不支持)和Coffee。

如果是在 window 系统下还需依赖 .NET framwork2.0,64位系统可能无法直接通过安装包安装。

官方示例:

var assert = require(‘assert’);

var hbase = require(‘hbase’);

 

hbase({ host: ‘127.0.0.1’, port: 8080 })

.table(‘my_table’ )

//创建一个Column Family

.create(‘my_column_family’, function(err, success){

  this.row(‘my_row’)   //定位到指定行

  .put(‘my_column_family:my_column’, ‘my value’, function(err, success){

    this.get(‘my_column_family’, function(err, cells){

      this.exists(function(err, exists){

        assert.ok(exists);

      });

    });

  });

});

数据检索:

client

.table(‘node_table’)

.scan({

  startRow: ‘my_row’,  //起始行

  maxVersions: 1  //版本

}, function(err, rows){

  console.log(err, rows);

});

另有 hbase-client 也是一个不错的选择,具体API参照其文档。

3. 优缺点

优势

1. 存储容量大,一个表可以容纳上亿行,上百万列;

2. 可通过版本进行检索,能搜到所需的历史版本数据;

3. 负载高时,可通过简单的添加机器来实现水平切分扩展,跟Hadoop的无缝集成保障了其数据可靠性(HDFS)和海量数据分析的高性能(MapReduce);

4. 在第3点的基础上可有效避免单点故障的发生。

缺点

1. 基于Java语言实现及Hadoop架构意味着其API更适用于Java项目;

2. node开发环境下所需依赖项较多、配置麻烦(或不知如何配置,如持久化配置),缺乏文档;

3. 占用内存很大,且鉴于建立在为批量分析而优化的HDFS上,导致读取性能不高;

4. API相比其它 NoSql 的相对笨拙。

适用场景

1. bigtable类型的数据存储;

2. 对数据有版本查询需求;

3. 应对超大数据量要求扩展简单的需求。

Redis

Redis 是一个开源的使用ANSI C语言编写、支持网络、可基于内存亦可持久化的日志型、Key-Value数据库,并提供多种语言的API。目前由VMware主持开发工作。
1. 特点

1.1 数据格式
Redis 通常被称为数据结构服务器,因为值(value)可以是 字符串(String), 哈希(Hash/Map), 列表(list), 集合(sets) 和 有序集合(sorted sets)五种类型,操作非常方便。比如,如果你在做好友系统,查看自己的好友关系,如果采用其他的key-value系统,则必须把对应的好友拼接成字符串,然后在提取好友时,再把value进行解析,而redis则相对简单,直接支持list的存储(采用双向链表或者压缩链表的存储方式)。
我们来看下这五种数据类型。

⑴ String

  • string 是 Redis 最基本的类型,你可以理解成与 Memcached 一模一样的类型,一个key对应一个value。
  • string 类型是二进制安全的。意思是 Redis 的 string 可以包含任何数据。比如 jpg 图片或者序列化的对象 。
  • string 类型是 Redis 最基本的数据类型,一个键最大能存储512MB。

实例:

redis 127.0.0.1:6379> SET name zfpx

OK

redis 127.0.0.1:6379> GET name

“zfpx”

在以上实例中我们使用了 Redis 的 SET 和 GET 命令。键为 name,对应的值为”zfpx”。 注意:一个键最大能存储512MB。

⑵ Hash

  • Redis hash 是一个键值对集合。
  • Redis hash 是一个 string 类型的 field 和 value 的映射表,hash 特别适合用于存储对象。

实例:

redis 127.0.0.1:6379> HMSET user:1 username zfpx password 123

OK

redis 127.0.0.1:6379> HGETALL user:1

1) “username”

2) “zfpx”

3) “password”

4) “123”

以上实例中 hash 数据类型存储了包含用户脚本信息的用户对象。 实例中我们使用了 Redis HMSET, HGETALL 命令,user:1 为键值。 每个 hash 可以存储 232 – 1 键值对(40多亿)。

⑶ List

Redis 列表是简单的字符串列表,按照插入顺序排序。你可以添加一个元素导列表的头部(左边)或者尾部(右边)。

实例:

redis 127.0.0.1:6379> lpush name zfpx1

(integer) 1

redis 127.0.0.1:6379> lpush name zfpx2

(integer) 2

redis 127.0.0.1:6379> lpush name zfpx3

(integer) 3

redis 127.0.0.1:6379> lrange name 01

1) “zfpx3”

2) “zfpx2”

3) “zfpx1”

列表最多可存储 232 – 1 元素 (4294967295, 每个列表可存储40多亿)。

⑷ Sets

Redis的Set是string类型的无序集合。 集合是通过哈希表实现的,所以添加,删除,查找的复杂度都是O(1)。

添加一个string元素到 key 对应的 set 集合中,成功返回1,如果元素已经在集合中返回0,key对应的set不存在返回错误,指令格式为

sadd key member

实例:

redis 127.0.0.1:6379> sadd school zfpx1

(integer) 1

redis 127.0.0.1:6379> sadd school zfpx1

(integer) 0

redis 127.0.0.1:6379> sadd school zfpx2

(integer) 1

redis 127.0.0.1:6379> sadd school zfpx2

(integer) 0

redis 127.0.0.1:6379> smembers school

 

1) “zfpx1”

2) “zfpx2”

注意:以上实例中 zfpx1 添加了两次,但根据集合内元素的唯一性,第二次插入的元素将被忽略。 集合中最大的成员数为 232 – 1 (4294967295, 每个集合可存储40多亿个成员)。

⑸ sorted sets/zset

Redis zset 和 set 一样也是string类型元素的集合,且不允许重复的成员。 不同的是每个元素都会关联一个double类型的分数。redis正是通过分数来为集合中的成员进行从小到大的排序。

zset的成员是唯一的,但分数(score)却可以重复。可以通过 zadd 命令(格式如下) 添加元素到集合,若元素在集合中存在则更新对应score

zadd key score member

实例:

redis 127.0.0.1:6379> zadd school 0 zfpx1

(integer) 1

redis 127.0.0.1:6379> zadd school 2 zfpx2

(integer) 1

redis 127.0.0.1:6379> zadd school 0 zfpx3

(integer) 1

redis 127.0.0.1:6379> zadd school 1 zfpx4

(integer) 0

redis 127.0.0.1:6379> ZRANGEBYSCORE school 0 100

 

1) “zfpx1”

2) “zfpx3”

3) “zfpx4”

4) “zfpx2”

1.2 性能

Redis数据库完全在内存中,因此处理速度非常快,每秒能执行约11万集合,每秒约81000+条记录。

Redis的数据能确保一致性——所有Redis操作是原子性(Atomicity,意味着操作的不可再分,要么执行要么不执行)的,这保证了如果两个客户端同时访问的Redis服务器将获得更新后的值。

1.3 持久化

通过定时快照(snapshot)和基于语句的追加(AppendOnlyFile,aof)两种方式,redis可以支持数据持久化——将内存中的数据存储到磁盘上,方便在宕机等突发情况下快速恢复。

1.4 CAP类别

属于CP类型。

2. Node下的使用

node 下可使用 node_redis 来实现 redis 客户端操作:

var redis = require(“redis”),

    client = redis.createClient();

 

// if you’d like to select database 3, instead of 0 (default), call

// client.select(3, function() { /* … */ });

 

client.on(“error”, function (err) {

    console.log(“Error “ + err);

});

 

client.set(“string key”, “string val”, redis.print);

client.hset(“hash key”, “hashtest 1”, “some value”, redis.print);

client.hset([“hash key”, “hashtest 2”, “some other value”], redis.print);

client.hkeys(“hash key”, function (err, replies) {

    console.log(replies.length + ” replies:”);

    replies.forEach(function (reply, i) {

        console.log(”    “ + i + “: “ + reply);

    });

    client.quit();

});

3. 优缺点

优势

1. 非常丰富的数据结构;

2. Redis提供了事务的功能,可以保证一串 命令的原子性,中间不会被任何操作打断;

3. 数据存在内存中,读写非常的高速,可以达到10w/s的频率。

缺点

1. Redis3.0后才出来官方的集群方案,但仍存在一些架构上的问题(出处);

2. 持久化功能体验不佳——通过快照方法实现的话,需要每隔一段时间将整个数据库的数据写到磁盘上,代价非常高;而aof方法只追踪变化的数据,类似于mysql的binlog方法,但追加log可能过大,同时所有操作均要重新执行一遍,恢复速度慢;

3. 由于是内存数据库,所以,单台机器,存储的数据量,跟机器本身的内存大小。虽然redis本身有key过期策略,但是还是需要提前预估和节约内存。如果内存增长过快,需要定期删除数据。

适用场景

适用于数据变化快且数据库大小可遇见(适合内存容量)的应用程序。更具体的可参照这篇《Redis 的 5 个常见使用场景》译文。

MongoDB

MongoDB 是一个高性能,开源,无模式的文档型数据库,开发语言是C++。它在许多场景下可用于替代传统的关系型数据库或键/值存储方式。

1.特点

1.1 数据格式

在 MongoDB 中,文档是对数据的抽象,它的表现形式就是我们常说的 BSON(Binary JSON )。

BSON 是一个轻量级的二进制数据格式。MongoDB 能够使用 BSON,并将 BSON 作为数据的存储存放在磁盘中。

BSON 是为效率而设计的,它只需要使用很少的空间,同时其编码和解码都是非常快速的。即使在最坏的情况下,BSON格式也比JSON格式再最好的情况下存储效率高。

对于前端开发者来说,一个“文档”就相当于一个对象:

{name“:”mengxiangyue“,”sex“:”nan}

对于文档是有一些限制的:有序、区分大小写的,所以下面的两个文档是与上面不同的:

{sex:“nan”,“name”:“mengxiangyue”}  

{“Name”:“mengxiangyue”,“sex”:“nan”}

另外,对于文档的字段 MongoDB 有如下的限制:

_id必须存在,如果你插入的文档中没有该字段,那么 MongoDB 会为该文档创建一个ObjectId作为其值。_id的值必须在本集合中是唯一的。

多个文档则组合为一个“集合”。在 MongoDB 中的集合是无模式的,也就是说集合中存储的文档的结构可以是不同的,比如下面的两个文档可以同时存入到一个集合中:

{“name”:“mengxiangyue”}  

{“Name”:“mengxiangyue”,“sex”:“nan”}

1.2 性能

MongoDB 目前支持的存储引擎为内存映射引擎。当 MongoDB 启动的时候,会将所有的数据文件映射到内存中,然后操作系统会托管所有的磁盘操作。这种存储引擎有以下几种特点:

* MongoDB 中关于内存管理的代码非常精简,毕竟相关的工作已经有操作系统进行托管。

* MongoDB 服务器使用的虚拟内存将非常巨大,并将超过整个数据文件的大小。不用担心,操作系统会去处理这一切。

在《Mongodb亿级数据量的性能测试》一文中,MongoDB 展现了强劲的大数据处理性能(数据甚至比Redis的漂亮的多)。

另外,MongoDB 提供了全索引支持:包括文档内嵌对象及数组。Mongo的查询优化器会分析查询表达式,并生成一个高效的查询计划。通常能够极大的提高查询的效率。

1.3 持久化

MongoDB 在1.8版本之后开始支持 journal,就是我们常说的 redo log,用于故障恢复和持久化。

当系统启动时,MongoDB 会将数据文件映射到一块内存区域,称之为Shared view,在不开启 journal 的系统中,数据直接写入shared view,然后返回,系统每60s刷新这块内存到磁盘,这样,如果断电或down机,就会丢失很多内存中未持久化的数据。

当系统开启了 journal 功能,系统会再映射一块内存区域供 journal 使用,称之为 private view,MongoDB 默认每100ms刷新 privateView 到 journal,也就是说,断电或宕机,有可能丢失这100ms数据,一般都是可以忍受的,如果不能忍受,那就用程序写log吧(但开启journal后使用的虚拟内存是之前的两倍)。

1.4 CAP类别

MongoDB 比较灵活,可以设置成 strong consistent (CP类型)或者 eventual consistent(AP类型)。

但其默认是 CP 类型。

2. Node下的使用

MongoDB 在 node 环境下的驱动引擎是 node-mongodb-native ,作为依赖封装到 mongodb 包里,我们直接安装即可:

npm install mongodb

实例:

var mongodb = require(‘mongodb’);

 

var mongodbServer = new mongodb.Server(‘localhost’, 27017, { auto_reconnect: true, poolSize: 10 });

var db = new mongodb.Db(‘mydb’, mongodbServer);

 

/* open db */

db.open(function() {

    /* Select ‘contact’ collection */

    db.collection(‘contact’, function(err, collection) {

        /* Insert a data */

        collection.insert({

            name: ‘Fred Chien’,

            email: ‘cfsghost@gmail.com’,

            tel: [

                ‘0926xxx5xx’,

                ‘0912xx11xx’

            ]

        }, function(err, data) {

            if (data) {

                console.log(‘Successfully Insert’);

            } else {

                console.log(‘Failed to Insert’);

            }

        });

 

        /* Querying */

        collection.find({ name: ‘Fred Chien’ }, function(err, data) {

            /* Found this People */

            if (data) {

                console.log(‘Name: ‘ + data.name + ‘, email: ‘ + data.email);

            } else {

                console.log(‘Cannot found’);

            }

        });

    });

});

另外我们也可以使用MongoDB的ODM(面向对象数据库管理器) —— mongoose 来做数据库管理,具体参照其API文档。

3. 优缺点

优势

1. 强大的自动化 shading 功能;

2. 全索引支持,查询非常高效;

3. 面向文档(BSON)存储,数据模式简单而强大。

4. 支持动态查询,查询指令也使用JSON形式的标记,可轻易查询文档中内嵌的对象及数组。

5. 支持 javascript 表达式查询,可在服务器端执行任意的 javascript函数。

缺点

1. 单个文档大小限制为16M,32位系统上,不支持大于2.5G的数据;

2. 对内存要求比较大,至少要保证热数据(索引,数据及系统其它开销)都能装进内存;

3. 非事务机制,无法保证事件的原子性。
适用场景

1. 适用于实时的插入、更新与查询的需求,并具备应用程序实时数据存储所需的复制及高度伸缩性;

2. 非常适合文档化格式的存储及查询;

3. 高伸缩性的场景:MongoDB 非常适合由数十或者数百台服务器组成的数据库。

4. 对性能的关注超过对功能的要求。

Couchbase 

本文之所以没有介绍 CouchDB 或 Membase,是因为它们合并了。合并之后的公司基于 Membase 与 CouchDB 开发了一款新产品,新产品的名字叫做 Couchbase。

Couchbase 可以说是集合众家之长,目前应该是最先进的Cache系统,其开发语言是 C/C++。

Couchbase Server 是个面向文档的数据库(其所用的技术来自于Apache CouchDB项目),能够实现水平伸缩,并且对于数据的读写来说都能提供低延迟的访问(这要归功于Membase技术)。

1.特点

1.1 数据格式

Couchbase 跟 MongoDB 一样都是面向文档的数据库,不过在往 Couchbase 插入数据前,需要先建立 bucket —— 可以把它理解为“库”或“表”。

因为 Couchbase 数据基于 Bucket 而导致缺乏表结构的逻辑,故如果需要查询数据,得先建立 view(跟RDBMS的视图不同,view是将数据转换为特定格式结构的数据形式如JSON)来执行。

Bucket的意义 —— 在于将数据进行分隔,比如:任何 view 就是基于一个 Bucket 的,仅对 Bucket 内的数据进行处理。一个server上可以有多个Bucket,每个Bucket的存储类型、内容占用、数据复制数量等,都需要分别指定。从这个意义上看,每个Bucket都相当于一个独立的实例。在集群状态下,我们需要对server进行集群设置,Bucket只侧重数据的保管。

每当views建立时, 就会建立indexes, index的更新和以往的数据库索引更新区别很大。 比如现在有1W数据,更新了200条,索引只需要更新200条,而不需要更新所有数据,map/reduce功能基于index的懒更新行为,大大得益。

要留意的是,对于所有文件,couchbase 都会建立一个额外的 56byte 的 metadata,这个 metadata 功能之一就是表明数据状态,是否活动在内存中。同时文件的 key 也作为标识符和 metadata 一起长期活动在内存中。

1.2 性能

couchbase 的精髓就在于依赖内存最大化降低硬盘I/O对吞吐量的负面影响,所以其读写速度非常快,可以达到亚毫秒级的响应。

couchbase在对数据进行增删时会先体现在内存中,而不会立刻体现在硬盘上,从内存的修改到硬盘的修改这一步骤是由 couchbase 自动完成,等待执行的硬盘操作会以write queue的形式排队等待执行,也正是通过这个方法,硬盘的I/O效率在 write queue 满之前是不会影响 couchbase 的吞吐效率的。

鉴于内存资源肯定远远少于硬盘资源,所以如果数据量小,那么全部数据都放在内存上自然是最优选择,这时候couchbase的效率也是异常高。

但是数据量大的时候过多的数据就会被放在硬盘之中。当然,最终所有数据都会写入硬盘,不过有些频繁使用的数据提前放在内存中自然会提高效率。

1.3 持久化

其前身之一 memcached 是完全不支持持久化的,而 Couchbase 添加了对异步持久化的支持:

Couchbase提供两种核心类型的buckets —— Couchbase 类型和 Memcached 类型。其中 Couchbase 类型提供了高可用和动态重配置的分布式数据存储,提供持久化存储和复制服务。

Couchbase bucket 具有持久性 —— 数据单元异步从内存写往磁盘,防范服务重启或较小的故障发生时数据丢失。持久性属性是在 bucket 级设置的。

1.4 CAP类型

Couchbase 群集所有点都是对等的,只是在创建群或者加入集群时需要指定一个主节点,一旦结点成功加入集群,所有的结点对等。

对等网的优点是,集群中的任何节点失效,集群对外提供服务完全不会中断,只是集群的容量受影响。

由于 couchbase 是对等网集群,所有的节点都可以同时对客户端提供服务,这就需要有方法把集群的节点信息暴露给客户端,couchbase 提供了一套机制,客户端可以获取所有节点的状态以及节点的变动,由客户端根据集群的当前状态计算 key 所在的位置。

就上述的介绍,Couchbase 明显属于 CP 类型。

2. Node下的使用

Couchbase 对 Node SDK 提供了官方文档:http://docs.couchbase.com/couchbase-sdk-node-1.2/index.html

实例:

var couchbase = require(“couchbase”);

 

var bucket = new couchbase.Connection({

  ‘bucket’:‘beer-sample’,

  ‘host’:‘127.0.0.1:8091’

}, function(err) {

  if (err) {

    // Failed to make a connection to the Couchbase cluster.

    throw err;

  }

 

  // 获取文档

  bucket.get(‘aass_brewery-juleol’, function(err, result) {

    if (err) {

      // Failed to retrieve key

      throw err;

    }

 

    var doc = result.value;

 

    console.log(doc.name + ‘, ABV: ‘ + doc.abv);

 

    doc.comment = “Random beer from Norway”;

 

    bucket.replace(‘aass_brewery-juleol’, doc, function(err, result) {

      if (err) {

        // Failed to replace key

        throw err;

      }

 

      console.log(result);

 

      // Success!

      process.exit(0);

    });

  });

});

3. 优缺点

优势

1. 高并发性,高灵活性,高拓展性,容错性好;

2. 以 vBucket 的概念实现更理想化的自动分片以及动态扩容;

缺点

1. Couchbase 的存储方式为 Key/Value,但 Value 的类型很为单一,不支持数组。另外也不会自动创建doc id,需要为每一文档指定一个用于存储的 Document Indentifer;

2. 各种组件拼接而成,都是c++实现,导致复杂度过高,遇到奇怪的性能问题排查比较困难,(中文)文档比较欠缺;

3. 采用缓存全部key的策略,需要大量内存。节点宕机时 failover 过程有不可用时间,并且有部分数据丢失的可能,在高负载系统上有假死现象;

4. 逐渐倾向于闭源,社区版本(免费,但不提供官方维护升级)和商业版本之间差距比较大。

适用场景

1. 适合对读写速度要求较高,但服务器负荷和内存花销可遇见的需求;

2. 需要支持 memcached 协议的需求。

LevelDB 

LevelDB 是由谷歌重量级工程师(Jeff Dean 和 Sanjay Ghemawat)开发的开源项目,它是能处理十亿级别规模 key-value 型数据持久性存储的程序库,开发语言是C++。

除了持久性存储,LevelDB 还有一个特点是 —— 写性能远高于读性能(当然读性能也不差)。

1.特点

LevelDB 作为存储系统,数据记录的存储介质包括内存以及磁盘文件,当LevelDB运行了一段时间,此时我们给LevelDb进行透视拍照,那么您会看到如下一番景象:

LevelDB 所写入的数据会先插入到内存的 Mem Table 中,再由 Mem Table 合并到只读且键值有序的 Disk Table(SSTable) 中,再由后台线程不时的对 Disk Table 进行归并。

内存中存在两个 Mem Table —— 一个是可以往里面写数据的table A,另一个是正在合并到硬盘的 table B。

Mem Table 用 skiplist 实现,写数据时,先写日志(.log),再往A插入,因为一次写入操作只涉及一次磁盘顺序写和一次内存写入,所以这是为何说LevelDb写入速度极快的主要原因。如果当B还没完成合并,而A已经写满时,写操作必须等待。

DiskTable(SSTable,格式为.sst)是分层的(leveldb的名称起源),每一个大小不超过2M。最先 dump 到硬盘的 SSTable 的层级为0,层级为0的 SSTable 的键值范围可能有重叠。如果这样的 SSTable 太多,那么每次都需要从多个 SSTable 读取数据,所以LevelDB 会在适当的时候对 SSTable 进行 Compaction,使得新生成的 SSTable 的键值范围互不重叠。

进行对层级为 level 的 SSTable 做 Compaction 的时候,取出层级为 level+1 的且键值空间与之重叠的 Table,以顺序扫描的方式进行合并。level 为0的 SSTable 做 Compaction 有些特殊:会取出 level 0 所有重叠的Table与下一层做 Compaction,这样做保证了对于大于0的层级,每一层里 SSTable 的键值空间是互不重叠的。

SSTable 中的某个文件属于特定层级,而且其存储的记录是 key 有序的,那么必然有文件中的最小 key 和最大 key,这是非常重要的信息,LevelDB 应该记下这些信息 —— Manifest 就是干这个的,它记载了 SSTable 各个文件的管理信息,比如属于哪个Level,文件名称叫啥,最小 key 和最大 key 各自是多少。下图是 Manifest 所存储内容的示意:

图中只显示了两个文件(Manifest 会记载所有 SSTable 文件的这些信息),即 Level0 的 Test1.sst 和 Test2.sst 文件,同时记载了这些文件各自对应的 key 范围,比如 Test1.sstt 的 key 范围是“an”到 “banana”,而文件 Test2.sst 的 key 范围是“baby”到“samecity”,可以看出两者的 key 范围是有重叠的。

那么上方图1中的 Current 文件是干什么的呢?这个文件的内容只有一个信息,就是记载当前的 Manifest 文件名。因为在 LevleDB 的运行过程中,随着 Compaction 的进行,SSTable 文件会发生变化,会有新的文件产生,老的文件被废弃,Manifest 也会跟着反映这种变化,此时往往会新生成 Manifest 文件来记载这种变化,而 Current 则用来指出哪个 Manifest 文件才是我们关心的那个 Manifest 文件。

注意,鉴于 LevelDB 不属于分布式数据库,故CAP法则在此处不适用。

2. Node下的使用

Node 下可以使用 LevelUP 来操作 LevelDB 数据库:

var levelup = require(‘levelup’)

 

// 1) Create our database, supply location and options.

//    This will create or open the underlying LevelDB store.

var db = levelup(‘./mydb’)

 

// 2) put a key & value

db.put(‘name’, ‘LevelUP’, function (err) {

  if (err) return console.log(‘Ooops!’, err) // some kind of I/O error

 

  // 3) fetch by key

  db.get(‘name’, function (err, value) {

    if (err) return console.log(‘Ooops!’, err) // likely the key was not found

 

    // ta da!

    console.log(‘name=’ + value)

  })

})

LevelUp 的API非常简洁实用,具体可参考官方文档。

3. 优缺点

优势

1. 操作接口简单,基本操作包括写记录,读记录和删除记录,也支持针对多条操作的原子批量操作;

2. 写入性能远强于读取性能,

3. 数据量增大后,读写性能下降趋平缓。

缺点

1. 随机读性能一般;

2. 对分布式事务的支持还不成熟。而且机器资源浪费率高。

适应场景

适用于对写入需求远大于读取需求的场景(大部分场景其实都是这样)。