wenfengsun

Archive for the ‘java’ Category

jmap-jmap是java自带的jvm内存工具,可以通过在服务器执行:jmap -dump:format=b,file=heap.bin pid 将jvm内存dump到一个文件里。
这里可以通过jhat-也是一个java自带的内存分析工具 ,来分析dump出来的heap.bin,它会启动一个7000端口的服务,你可以在浏览器访问这个端口,获取堆栈信息;命令: jhat -J-Xmx512m heap.bin
另外一个工具就是mat:http://www.eclipse.org/mat/ 可以在eclipse上安装这个插件,通过eclipse打开这个文件就可以分析jvm的内存情况。如下图:
另外一个分析jvm中native stack的分析工具是google的perftools,这个没有深入研究,先mark一下。
分析jvm行为的工具,btrace,可以通过编写源码的方式来观察jvm中方法调用等一些行为。

Advertisements

JNI:Java Native Interface,它允许Java代码和其他语言写的代码进行交互。
问题描述:
以JNI方式实现的jmagick在调用imagemagick的接口时,一直出现高内存消耗,最高达到10G内存。但是无论以jmx方式启动后,用jconsole监控Java Heap内存状况,还是用jmap-jhat方式dump并察看java Heap内存状况,都发现java Heap只占用了几百M内存。
这让人联想到了JNI的内存占用机制,首先,JVM内存结构如下图:

这个结构中,Nativeinterface组件:
与nativelibraries交互,是其它编程语言交互的接口。当调用native方法的时候,就进入了一个全新的并且不再受虚拟机限制的世界,所以也很容易出现JVM无法控制的nativeheapOutOfMemory。
好,至此,我们大约知道了,JNI这种native方式产生的内存消耗是位于NativeMethodStack中,而不是Heap中,这也就解释了为何Heap内存消耗很小,而整个JVM占用内存很大的原因。
再次,来分析一下JNI编程时的实现方式:
Local Reference 和 Local Reference 表
理解 Local Reference 表的存在是理解 JNI Local Reference 的关键。
JNI Local Reference 的生命期是在 native method 的执行期(从 Java 程序切换到 native code 环境时开始创建,或者在 native method 执行时调用 JNI function 创建),在 native method 执行完毕切换回 Java 程序时,所有 JNI Local Reference 被删除,生命期结束(调用 JNI function 可以提前结束其生命期)。
实际上,每当线程从 Java 环境切换到 native code 上下文时(J2N),JVM 会分配一块内存,创建一个 Local Reference 表,这个表用来存放本次 native method 执行中创建的所有的 Local Reference。每当在 native code 中引用到一个 Java 对象时,JVM 就会在这个表中创建一个 Local Reference。比如,实例 1 中我们调用 NewStringUTF() 在 Java Heap 中创建一个 String 对象后,在 Local Reference 表中就会相应新增一个 Local Reference。

⑴运行 native method 的线程的堆栈记录着 Local Reference 表的内存位置(指针 p)。
⑵ Local Reference 表中存放 JNI Local Reference,实现 Local Reference 到 Java 对象的映射。
⑶ native method 代码间接访问 Java 对象(java obj1,java obj2)。通过指针 p 定位相应的 Local Reference 的位置,然后通过相应的 Local Reference 映射到 Java 对象。
⑷当 native method 引用一个 Java 对象时,会在 Local Reference 表中创建一个新 Local Reference。在 Local Reference 结构中写入内容,实现 Local Reference 到 Java 对象的映射。
⑸ native method 调用 DeleteLocalRef() 释放某个 JNI Local Reference 时,首先通过指针 p 定位相应的 Local Reference 在 Local Ref 表中的位置,然后从 Local Ref 表中删除该 Local Reference,也就取消了对相应 Java 对象的引用(Ref count 减 1)。
⑹当越来越多的 Local Reference 被创建,这些 Local Reference 会在 Local Ref 表中占据越来越多内存。当 Local Reference 太多以至于 Local Ref 表的空间被用光,JVM 会抛出异常,从而导致 JVM 的崩溃。
结论:
在每次调用JNI创建对象,并且执行完操作后,执行destroy方法释放回收native mem中的对象和内存,重新发布程序后,问题解决。

facebook将他们的thrift开源,thrift是一个用于不同系统间通信的协议,它大大提高了系统间数据通信的效率。more about thrift

thrift为linux和windows都提供了相应的gen命令,安装之后只需要调用thrift命令就可以生产对应语言的程序。
thrift生成的java源文件主要是描述object和interface,实现接口的代码需要自己实现;
下面是一个简单的例子,通过定义一个message,和一个获取message对象的接口,来实现client获取数据对象的结果。
首先要定义thrift脚本,thrift的基本介绍:

基本名词

  • Types: 为了满足多语言平台的要求,需要提供基本数据类型来进行转换。比如在C++的Map和Python的Dict之间能够相互转换。
  • Transport: 对于每一种语言,都应该有一个抽象的公共层来完成对应的双向数据传输。
  • Protocal: 数据需要有一种方式来使用对应的传输层的code,而不用关心传输层的具体实现细节。
  • Versioning:数据需要有自己的版本号来实现对应的健壮性。
  • Processing : 产生code来完成RPC调用。

类型
1. Goals:

  • 1. 使用最基本的数据类型,不管上层使用怎么样的编程语言。
  • 2. 不使用动态数据类型,也不需要开发者写对象序列化或者传输的代码(已经封装)。
  • 3. IDL 用来告诉代码生成器如何在多语言之上安全地传输数据。

2. Base Types:

  • 1. 选取了大多数语言中都存在的基本数据类型,忽略了一些语言中特别的类型。(无符号类型), 所有的基本
  • 类型都是有符号的。
  • 2. 基本类型包括bool, byte,i16,i32,i64,double,string。分别对应java中的boolean,byte,short,int,long,double,String

3. Structs:

  • 1. 提供了一种common的对象来代表面向对象语言中的对象类型,每一个filed都有一个标志符。
  • 2. 每个filed必须有一个标志符和一个给定的默认值。标志符如果没有给定的话,会自动分配一个,但是强烈建议给定标志符,为了方便版本控制。

4. Container:

  • 1. List, set, Map。其中List被翻译成STL中的vector, 或者Java中的ArrayList,set和map类似。
  • 2. 要求对应的基本语言类型支持对应的Thrift的基本数据类型。
  • 3. 在每一种目标语言中,对于每一种定义的类型,生成两个接口,read和write,用于序列化和传输对应的数据结构。

5. Exceptions:

  • 1. 使用Exception关键字来代替对应的structs关键字,得到对应的基本类。
  • 2. 生成的对象继承自每一种语言中的对应的Exception的基类。

6. Services:

  • 1. 提供了服务端的接口调用,通过代码生成器会生成Client端和Server端的桩函数接口,共上层调用使用。
  • 2. 在每一个函数前面可以加上async关键字,这个关键字能够实现对应的一部方法。
  • 3. 一个纯void函数也会返回一个response,用来保证该操作在服务端已经被执行。
  • 4. async call只保证消息在传输层是没有问题的,因此,在使用async的时候需要保证当前的使用环境对于丢包是可以接受的。

3. Transport
1. 接口

  • 1. 传输层用来促进数据传输。一个关键的设计是Thrift将数据传输层和代码生成器分开。
  • 2. 由于抽象的IO炒作产生的tradoff相比起实际的IO操作显得微不足道。
  • 3. 需要满足的基本功能:如何读写数据,不管是在网络中,还是共享内存,还是从磁盘文件中读写。
  • 4. 提供的接口如下:open, close,isOpen, read, write, flush。还有一些用于batch操作的接口
  • 5. 对于TServerTransport,还有接口用来创建对应的Transport对象。如open, listen, accept, close。

2. 实现

  • 1. TSocket 类对于TCP/IP的流式套接字实现了一个通用,简单的接口。
  • 2. TFileTransport类实现了一个抽象接口,用于将磁盘文件导入到数据流中。

3. Utilities

  • 1. 网络传输层设计的支持简单的扩展,比如组合,TBufferdTransport实现在传输层实现了buffer的功能,TFrameTransport实现了数据头定长大小,用于Noblocking传输。TMemoryBuffer允许读和写直接在进程的堆顶完成。

4. Protocal
1. 接口

  • 1. 另外一块主要的部分是thrift中将数据结构和传输层分离,thrift定义了一些传输时的基本类型,但是没有强制定义需要实现的编码格式,只要能被代码生成器识别就好。
  • 2. thrift协议的接口简单明了,支持两种功能:双向有序的消息,基本类型,容器,结构的编码。

2. 结构

  • 1. Thrift中默认使用流式结构来传输对应的协议,这样避免了因为需要分片或者在发送前整体计算带来的性能损失。当有的场景需要使用分片,或者分片的性能优势更加明显的时候,可以使用TFramedTransport这个抽象接口类。

3. 实现

  • 1. Thrift的实现了一个空间高效的二进制协议,所有的数据都以一个扁平的二进制格式存在,整形被转换为网络字节序,字符串在头上加上它的长度,所有的消息和field 头都用它的整数序列号,忽略这些filed中的字符串名字。
  • 2. 我们没有做过多的性能优化,为了代码的整洁和高效。如果有需要,可以加入这些优化方案。

5.Versioning
1. 域标志符

  • 1. Thrift在版本控制上面是健壮的,它可以接受旧客户端过来的请求并正确处理。
  • 2. Thrift中的版本控制是通过域标志符来确定的,thrift结构中的每一项前面都有一个对应的标志符,标志符和数据类型唯一化开item。
  • 3. 为了避免冲突,自动分配的标志符从-1开始递减,人工定义的标志符只能为整数。
  • 4. 在数据是自定义的前提下,当反序列化的时候,thrift的code 生成器可以根据标识符来判断读取到的数据是否对齐,也可以跳过不能识别的域,保证兼容性。
  • 5. 域标志符也可以在参数列表中声。

2. Isset

  • 1. 用来标注必须存在于结构体中的域,如果必须存在,标注为true,这样可以当该域不存在的时候,可以通知上层调用者。

3. 场景分析
1. 4种场景,加减域/新旧client或者server。
4. Protocal/Transport Versioning
1. 实现了TProtocal的抽象接口,用来让协议的实现自己来管理版本。
6. RPC 实现
1. TProcessor
1. 核心类,抽象出client和server的基类,核心功能是处理input和output。
2. Generated code
2. 自动生成client端和server端的调用接口。
3. TServer
1. Tserver 可以有多种实现,来满足不同的需求。如单线程的TSimpleServer, 每个连接一个线程的TThreadedServer, 还有基于线程库的TThreadPoolServer.
2. 开发者可以实现自己的TServer。
下面是message的简单例子:
1. 定义message.thrift
namespace java com.company.thrift.model
struct Message {
1: i64 id,
2: string body,
3: string content,
4: i64 userId,
5: string picpath,
}

2. 定义service
namespace java com.company.thrift
include "message.thrift"
service MessageService{
message.Message getMessage(1: i64 id);
}

3. 执行生成命令
# thrift –gen java message.thrift
# thrift –gen java messageService.thrift
将生成的Message.java和messageService.java拷贝到你的工程中。
4. 编写接口实现:
public class MessageServiceImpl implements MessageService.Iface{

@Override
public Message getMessage(long id) throws TException {
Message message = new Message();
message.setId(id);
message.setBody(“Test body value”);
message.setContent(“”);
message.setPicpath(“http://www.google.com.hk/images/nav_logo86.png”);
message.setUserId(1001);
return message;
}

}
5. 编写服务器端调用
import org.apache.thrift.protocol.TBinaryProtocol;
import org.apache.thrift.protocol.TBinaryProtocol.Factory;
import org.apache.thrift.server.TServer;
import org.apache.thrift.server.TThreadPoolServer;
import org.apache.thrift.server.TThreadPoolServer.Args;
import org.apache.thrift.transport.TServerSocket;
import org.apache.thrift.transport.TTransportException;

import com.conpany.thrift.MessageService.Processor;

public class Server {
public void startServer() {
try {
TServerSocket serverTransport = new TServerSocket(1234);
MessageService.Processor process = new Processor(new MessageServiceImpl());
Factory portFactory = new TBinaryProtocol.Factory(true, true);
Args args = new Args(serverTransport);
args.processor(process);
args.protocolFactory(portFactory);
TServer server = new TThreadPoolServer(args);
server.serve();
} catch (TTransportException e) {
e.printStackTrace();
}
}

public static void main(String[] args) {
Server server = new Server();
server.startServer();
}
}
6. 编写客户端代码:
public class Client {
public void startClient() {
TTransport transport;
try {
transport = new TSocket("localhost", 1234);
TProtocol protocol = new TBinaryProtocol(transport);
MessageService.Client client = new MessageService.Client(protocol);
transport.open();
Message msg = client.getMessage(1020);
System.out.println(msg);
transport.close();
} catch (TTransportException e) {
e.printStackTrace();
} catch (TException e) {
e.printStackTrace();
}
}

public static void main(String[] args) {
Client client = new Client();
client.startClient();
}
}
7. 启动Server,并执行客户端代码,可以看到客户端会打印一行服务器生成的message数据

Message(id:1020, body:Test body value, content:, userId:1001, picpath:http://www.google.com.hk/images/nav_logo86.png)

Redis的sorted set用于高频率的变换排序十分方便,例如论坛,贴吧,微博等。

Redis是用C语言实现的,sorted set的实现方式是通过ZSET。

ZSET的实现用到了两个数据结构:hash table 和 skip list(跳跃表),其中hash table是具体使用redis中的dict来实现的,主要是为了保证查询效率为O(1) ,而skip list(跳跃表)主要是保证元素有序并能够保证INSERT和REMOVE操作是O(logn)的复杂度。

关于skip list这里简单介绍下:skip list是链表的一种特殊形式,对链表的一种优化;保证INSERT和REMOVE操作是O(logn)的负载读,而通用链表的复杂度为O(n);

下面是关于skip list的介绍:

这是一个链表。上面链表是有序排列的,那么如果想查找某一个元素x,则可以如下操作

  1. node *p = head;
  2. while(p->next <x) p=p->next;
  3. return p->next;

如此以来,得到了p之前的元素均小于x,而p之后的元素均不小于x,p是不小于x的第一个元素节点指针.
如果要按照顺序插入一个元素x,则可以如下操作。

  1. node *p = find(x);
  2. p1->next=p->next;
  3. p->next = p1;

删除操作,删除不小于x的第一个元素

  1. node *p = find(x);
  2. node *p1 = new node;
  3. p1 = p;
  4. p = p->next;
  5. delete p1;
  6. p1 = NULL;

以上是顺序链表,而skip list能够在这三个操作上节省时间。将时间由原来的O(n)节省到O(log(n))。

  1. node *p = top;
  2. while(1)
  3. {
  4. while(p->next->key<x) p = p->next;
  5. if(p->down == NULL) return p;
  6. p=p->down;
  7. }

1.如何构建一个skip list?

按照顺序排列的链表作为底层;

将链表中随机抽取一些元素,作为第二层,而第二层的每一个元素均有向下的一个指针,指向第一层中与其相同的元素;

而后再在第二层元素中,随机选取一部分元素,作为第三层,而第三层中的元素也均有向下的指针指向第二层与其相同的元素;以此类推,

直到构建了一层只有最大值最小值(-1,1)指针的元素。如此构建一个skip list。

skip list有以下特征:

最下面得一层具有所有元素;

上面每一层的元素均是来自其下面一层的元素;

每层元素均有向下的指针与其下一层相同的元素相关联;

有一个top指针指向最高一层的第一个元素。

在skip list中,要实现查找、插入、删除等操作时,只需要操作O(log(n))次。

插入元素,假设要在第k层插入元素x,k的值不同也会有不同:

Determine k the number of levels in which x participates (explained later)
Do find(x), and insert x to the appropriate places in the lowest k levels. (after the elements at which the search path turns down or terminates)
Example – inserting 119. k=2
If k is larger than the current number of levels, add new levels (and update top)
Example – inser(119) when k=4
详见SkipList的PPT,是Arizona的一个guy写的,感觉很NICE,很形象。可惜很多图我无法粘贴。不知道为何。
下面是来自另外一个网站的资料。
目的:向跳跃表中插入一个元素x
首先明确,向跳跃表中插入一个元素,相当于在表中插入一列从S0中某一位置出发向上的连续一段元素。有两个参数需要确定,即插入列的位置以及它的“高度”。
关于插入的位置,我们先利用跳跃表的查找功能,找到比x小的最大的数y。根据跳跃表中所有链均是递增序列的原则,x必然就插在y的后面。
而 插入列的“高度”较前者来说显得更加重要,也更加难以确定。由于它的不确定性,使得不同的决策可能会导致截然不同的算法效率。为了使插入数据之后,保持该 数据结构进行各种操作均为O(logn)复杂度的性质,我们引入随机化算法(Randomized Algorithms)。
我们定义一个随机决策模块,它的大致内容如下:
产生一个0到1的随机数r                            r ← random()
如果r小于一个常数p,则执行方案A,  if  r<p then do A
否则,执行方案B                                     else do B
初始时列高为1。插入元素时,不停地执行随机决策模块。如果要求执行的是A操作,则将列的高度加1,并且继续反复执行随机决策模块。直到第i次,模块要求执行的是B操作,我们结束决策,并向跳跃表中插入一个高度为i的列。
性质1: 根据上述决策方法,该列的高度大于等于k的概率为p^(k-1)。
此处有一个地方需要注意,如果得到的i比当前跳跃表的高度h还要大的话,则需要增加新的链,使得跳跃表仍满足先前所提到的条件。
三、删除
目的:从跳跃表中删除一个元素x
删除操作分为以下三个步骤:
(1) 在跳跃表中查找到这个元素的位置,如果未找到,则退出  *
(2) 将该元素所在整列从表中删除        *
(3) 将多余的“空链”删除         *
【复杂度分析】
一个数据结构的好坏大部分取决于它自身的空间复杂度以及基于它一系列操作的时间复杂度。跳跃表之所以被誉为几乎能够代替平衡树,其复杂度方面自然不会落后。我们来看一下跳跃表的相关复杂度:
空间复杂度: O(n)    (期望)
跳跃表高度: O(logn)  (期望)
相关操作的时间复杂度:
查找:  O(logn)  (期望)
插入:   O(logn)  (期望)
删除:  O(logn)  (期望)

之所以在每一项后面都加一个“期望”,是因为跳跃表的复杂度分析是基于概率论的。有可能会产生最坏情况,不过这种概率极其微小。

一、 空间复杂度分析  O(n)
假设一共有n个元素。根据性质1,每个元素插入到第i层(Si)的概率为pi-1 ,则在第i层插入的期望元素个数为npi-1,跳跃表的元素期望个数为  ,当p取小于0.5的数时,次数总和小于2n。
所以总的空间复杂度为O(n)
二、跳跃表高度分析  O(logn)
根据性质1,每个元素插入到第i层(Si)的概率为p^i ,则在第i层插入的期望元素个数为np^(i-1)。
考虑一个特殊的层:第1+ 层。
层的元素期望个数为 np^0+np^1+…+np^(h-1),当n取较大数时,这个式子的值接近0,故跳跃表的高度为O(logn)级别的。
三、查找的时间复杂度分析  O(logn)
我们采用逆向分析的方法。假设我们现在在目标节点,想要走到跳跃表最左上方的开始节点。这条路径的长度,即可理解为查找的时间复杂度。
设当前在第i层第j列那个节点上。
i) 如果第j列恰好只有i层(对应插入这个元素时第i次调用随机化模块时所产生的B决策,概率为1-p),则当前这个位置必然是从左方的某个节点向右跳过来的。
ii) 如果第j列的层数大于i(对应插入这个元素时第i次调用随机化模块时所产生的A决策,概率为p),则当前这个位置必然是从上方跳下来的。(不可能从左方来,否则在以前就已经跳到当前节点上方的节点了,不会跳到当前节点左方的节点)
设C(k)为向上跳k层的期望步数(包括横向跳跃)
有:
C(0) = 0
C(k) = (1-p)(1+向左跳跃之后的步数)+p(1+向上跳跃之后的步数)
= (1-p)(1+C(k)) + p(1+C(k-1))
C(k) = 1/p + C(k-1)
C(k) = k/p
而跳跃表的高度又是logn级别的,故查找的复杂度也为logn级别。
对于记忆化查找(Search with fingers)技术我们可以采用类似的方法分析,很容易得出它的复杂度是O(logk)的(其中k为此次与前一次两个被查找元素在跳跃表中位置的距离)。
四、插入与删除的时间复杂度分析  O(logn)
插入和删除都由查找和更新两部分构成。查找的时间复杂度为O(logn),更新部分的复杂度又与跳跃表的高度成正比,即也为O(logn)。
所以,插入和删除操作的时间复杂度都为O(logn)
最后,概率因子一般用1/2或1/e

jedis–https://github.com/xetorthio/jedis

是一个java client for redis,它在初始化pool的时候,实际上使用了apache commons的GenericObjectPool

默认构造方法:

        setTestWhileIdle(true);//对没有过期的池对象进行检查
        setMinEvictableIdleTimeMillis(60000);//休眠了1分钟的对象过期
        setTimeBetweenEvictionRunsMillis(30000);//每隔30秒进行一次后台对象检查
        setNumTestsPerEvictionRun(-1);//每次检查池内所有的对象

maxWait:指明若在对象池空时调用borrowObject方法的行为被设定成等待,最多等待多少毫秒。如果等待时间超过了这个数值,则会抛出一个java.util.NoSuchElementException异常。如果这个值不是正数,表示无限期等待。
testOnBorrow:设定在借出对象时是否进行有效性检查。

timeBetweenEvictionRunsMillis:设定间隔每过多少毫秒进行一次后台对象清理的行动。如果这个值不是正数,则实际上不会进行后台对象清理。

numTestsPerEvictionRun:设定在进行后台对象清理时,每次检查几个对象。如果这个值不是正数,则每次检查的对象数是检查时池内对象的总数乘以这个值的负倒数再向上取整的结果――也 就是说,如果这个值是-2(-3、-4、-5……)的话,那么每次大约检查当时池内对象总数的1/2(1/3、1/4、1/5……)左右。

minEvictableIdleTimeMillis:设定在进行后台对象清理时,视休眠时间超过了多少毫秒的对象为过期。过期的对象将被回收。如果这个值不是正数,那么对休眠时间没有特别的约束。

testWhileIdle:则设定在进行后台对象清理时,是否还对没有过期的池内对象进行有效性检查。不能通过有效性检查的对象也将被回收。

maxActive:控制在某个时间点最大能被pool分配的对象数。 当这个参数小于等于零的时候,表示无限制. 当maxActive到达后,pool就无法再分配对象了. 这个参数的默认值是8.

maxIdel:控制在任何时间池内能够保持idel状态的对象数字.当小于零时表示无限制。默认值是8.