• 首页
  • 关于

我自然

每月存档:3月 2012

Java使用”指针”快速比较字节

在 2012年3月16日 上公布 作者为 yankay

如何才能快速比较两个字节数组呢?我将问题描述成下面的接口:

 
public int compareTo(byte[] b1, int s1, int l1, byte[] b2, int s2,int l2);

最直观的做法是同时遍历两个数组,两两比较。

 
public int compareTo(byte[] buffer1, int offset1, int length1,
		byte[] buffer2, int offset2, int length2) {
	// Short circuit equal case
	if (buffer1 == buffer2 && offset1 == offset2
		&& length1 == length2) {
		return 0;
	}
	// Bring WritableComparator code local
	int end1 = offset1 + length1;
	int end2 = offset2 + length2;
	for (int i = offset1, j = offset2; i < end1 && j < end2; i++, j++) {
		int a = (buffer1[i] & 0xff);
		int b = (buffer2[j] & 0xff);
		if (a != b) {
return a - b;
		}
	}
	return length1 - length2;
}

如果事情这么简单就结束了,就没有意思了。

如果要提升性能,可以做循环展开等等优化,但这些优化应该依赖JVM来做,新的JVM可以做的很好。那还有什么办法可以提高性能呢?
可以将字节数组合并!!上面的例子中,每个byte被迫转型成了int,再比较。其实我们可以将8个byte转换成一个long,在比较long,这样效果会不会好些?用什么方法转换才是最优的?

 
long sun.misc.Unsafe.getLong(Object o,int offset)

Java提供了一个本地方法,可以最快最好转换byte与long。该函数是直接访问一个对象的内存,内存地址是对象指针加偏移量,返回该地址指向的值。有人说Java很安全,不可以操作指针,所以有的时候性能也不高。其实不对,有了这个Unsafe类,Java一样也不安全。所以Unsafe类中的方法都不是public的,不过没关系,我们有反射。言归正传,下面是使用这种技术手段的实现代码。

 
public int compareTo(byte[] buffer1, int offset1, int length1,
		byte[] buffer2, int offset2, int length2) {
	// Short circuit equal case
	if (buffer1 == buffer2 && offset1 == offset2
			&& length1 == length2) {
		return 0;
	}
	int minLength = Math.min(length1, length2);
	int minWords = minLength / Longs.BYTES;
	int offset1Adj = offset1 + BYTE_ARRAY_BASE_OFFSET;
	int offset2Adj = offset2 + BYTE_ARRAY_BASE_OFFSET;

	/*
	 * Compare 8 bytes at a time. Benchmarking shows comparing 8
	 * bytes at a time is no slower than comparing 4 bytes at a time
	 * even on 32-bit. On the other hand, it is substantially faster
	 * on 64-bit.
	 */
	for (int i = 0; i < minWords * Longs.BYTES; i += Longs.BYTES) {
		long lw = theUnsafe.getLong(buffer1, offset1Adj + (long) i);
		long rw = theUnsafe.getLong(buffer2, offset2Adj + (long) i);
		long diff = lw ^ rw;

		if (diff != 0) {
			if (!littleEndian) {
				return (lw + Long.MIN_VALUE) < (rw + Long.MIN_VALUE) ? -1
						: 1;
			}

			// Use binary search,一下省略若干代码
			.....
			return (int) (((lw >>> n) & 0xFFL) - ((rw >>> n) & 0xFFL));
		}
	}

	// The epilogue to cover the last (minLength % 8) elements.
	for (int i = minWords * Longs.BYTES; i < minLength; i++) {
		int result = UnsignedBytes.compare(buffer1[offset1 + i],
				buffer2[offset2 + i]);
		if (result != 0) {
			return result;
		}
	}
	return length1 - length2;
}

实现比原来复杂了一些。但这次一次可以比较8个字节了。这种getLong函数和系统的字节序是紧紧相关的,如果是小端序操作起来有点麻烦,代码先省略掉。这样操作实际效果如何?我们需要对比测试下。对比两个1M的字节数组,如果使用第一个版本,每次比较平均需要2.5499ms,如果使用第二个版本,需要0.8359ms,提升了3倍。对应这种CPU密集型的操作,这样的提升可是很可观的。

如果要提升性能,使用Unsafe直接访问内存也是不错的选择。

文章分类 软件技术 | 标签: Java, Java字节数组比较, Java字节比较, 字节, 比较 | 发表评论 |

HBase介绍PPT

在 2012年3月14日 上公布 作者为 yankay

Hbase介绍 from kaiyannju
文章分类 软件技术 | 标签: Hbase | 1 条评论 |

Amazon EBS架构猜想

在 2012年3月8日 上公布 作者为 yankay

Amazon EBS是专门为Amazon EC2 虚拟机设计的弹性块存储服务。Amazon EBS可以为Amazon EC2的虚拟机创建卷volumes,Amazon EBS卷类似没有格式化的外部卷设备。卷有设备名称,同时也提供了块设备接口。你可以在Amazon EBS 卷上驻留自己的文件系统,或者直接作为卷设备使用。也就是说EBS就是一个基于集群的完美的“大磁盘”,可以随机读写,较高性能,完美的一致性和高可靠。本来以为这只是幻象,十分不好做。杨公一席话让我茅塞顿开。所以猜测EBS的架构如下,内部人士不要笑话我。

架构

  • EBS虚拟磁盘驱动器:EBS客户端构件,和EC2部署在一起,同生共死。作为操作系统的磁盘驱动器存在。作用是管理该磁盘的块,接受磁盘请求。
  • 缓冲存储:我猜测,如果要想保证高性能,同时保证数据不丢失,需要使用一个本地的持久化存储作为缓冲和缓存。直接对集群进行大量的细碎的操作,延迟是不可接受的。如果使用长连接,多网卡,可以让延迟变得可以接受,那么这个组件就不是必须的。
  • 类S3:类似S3的Key-Value存储。有高可靠,高延时,高吞吐的特点。肯定不是S3,也许也不是Key-value,但是大致是类似的。不可修改和按块存储的特性是相似的。
  • 类Mysql:类似Mysql的DB,用来存储块的信息,必须高可靠,容量不比太大,压力也不大。
  • Slave:可选组件,Slave会记录磁盘驱动器的每个操作,同步其日志。如果EC2那台机器的缓冲存储损坏,可以使用Slave上面的来恢复最近这段时间没有同步到S3的数据。

存储方式

存储的基本单位是块。每个块由Key和Value组成。块的Key分三部分:diskNo-blockNo-version,Value就是Block的内容。块存储在”S3″中,每个块都是不可以修改的,逻辑上的修改通过增加版本来实现。同时不是每一次修改都必须增加版本的。具体方式下面说。块的大小估计在4M左右,要综合”S3″的性能来决定。

一个“盘”由若干个“块”构成,需要记录每一个”块版本号”,blockNo和块的个数在盘创建的时候就已经决定了。“块版本号”信息持久化存储在Mysql中。

这个架构分两层,S3是底层,负责不断存储“盘”的快照。本地缓冲提供低延迟读写。

实现

下面分几种情况,分别来讨论如何实现。

创建,挂载盘

当创建一个盘的时候,只要在Mysql生成一个新的DiskNo。根据盘的大小和Block的大小,计算出Block数量,在Mysql中初始化元信息,将每个Block的版本标记为0(Block在物理上还不存在)。

然后“磁盘驱动器”挂载他,将Mysql中的源信息,加载到内存中。如果上次非正常关闭,可以通过缓冲存储中的数据,执行恢复操作。因为这个盘不是共享的只有该EC2可以使用。所以挂载后不需要再读Mysql.所以对元数据的操作都发生在内存中,每隔一段时间(比如10分钟),将元数据增量添加到Mysql。

有一点需要注意的是,如果一个块在元数据中有,这个块的数据可能在本地缓冲也可能在S3上。但是如果在Mysql的元数据中有,S3上必须存在有该块。

读块

根据blockId,可以得之其最近版本,并且是在本地缓冲存储还是在”S3″,直接访问即可。读过的块可以放入缓冲。

写块

写块比较复杂。当发起一个写操作的时候,如果本地不存在或者正在同步,本地会先写入一个临时块,写入成功就返回成功。然后会找到”S3″上的块,下载合并修改。如果本地存在,并且该块不在同步中,就直接修改。

每隔一段时间,系统会建立一个check point,将修改的块增加一个版本号,同步到“S3”中去。这里的同步是异步的。全部完成算完成,不存在中间状态。如果操作系统对一个块修改10次,但这些修改操作在两次同步之间,只增加一个版本,避免重复。

缓冲存储损坏

如果缓冲存储损坏,如果没有Slave。由于S3和Mysql中有上一次的快照信息,所以可以恢复到最近的快照状态。不会出现一致性问题。但Check Point之间的时间间隔可能比较长,如果无法忍受的话,可以建立一个Slave用来记录所有的写操作,但缓冲存储损坏的时候,可以通过Slave上的数据恢复到最近的点。

总结

分布式的虚拟磁盘,可以通过两层存储架构,同时满足严格的一致性和分区要求,也有好的随机读写性能。之所以可以采取两层存储,是因为一块“盘”只能一台机器独享,不要求共享,相当于在可分区的特性上打了个折扣,所以这样应该是没问题的。

亚马逊的测试报告也是写的性能远远大于读性能,和这个架构的特点也是相似的。暂时没有发现什么冲突的地方。当然这个架构只是我的猜想,做不得数的。

好像除了亚马逊,没有其他公司对这种磁盘系统感兴趣,也许是没有必要吧。这样虚拟出来的磁盘性能有限,而且系统层次越多越不稳定。但“云计算”招摇撞骗,大行其道,探索一下也好。

文章分类 软件技术 | 标签: Amazon EBS, EBS, EBS架构 | 发表评论 |

近期文章

  • 听说 Docker 被 kubenetes 抛弃了,怎么办?containerd
  • 公告 – 博客重开了
  • CloudFoundry v2面面谈,内赠MicroCFv2福利
  • Docker能够运行任何应用的“PaaS”云
  • Scala Tour – 精选

近期评论

  • Gao发表在《公告 – 博客重开了》
  • Impala:新一代开源大数据分析引擎 – FIXBBS发表在《Google Dremel 原理 – 如何能3秒分析1PB》
  • 何建兵发表在《NoSQL数据库笔谈v0.2》
  • Pony发表在《Docker能够运行任何应用的“PaaS”云》
  • Pony发表在《Docker能够运行任何应用的“PaaS”云》

归档

  • 2021年6月
  • 2021年3月
  • 2014年2月
  • 2013年9月
  • 2013年5月
  • 2013年1月
  • 2012年11月
  • 2012年9月
  • 2012年8月
  • 2012年3月
  • 2012年2月
  • 2012年1月
  • 2011年11月
  • 2011年10月
  • 2011年9月
  • 2010年10月
  • 2010年8月
  • 2010年7月
  • 2010年6月
  • 2010年5月
  • 2010年4月
  • 2010年3月
  • 2010年2月
  • 2010年1月
  • 2009年10月
  • 2009年9月
  • 2009年8月
  • 2009年7月
  • 2009年6月
  • 2008年10月
  • 2008年8月
  • 2008年7月
  • 2008年6月

分类

  • 家庭生活
  • 未分类
  • 每日心得
  • 软件技术

友情链接

  • DaoCloud Enterprise
  • DaoCloud 云原生一体机

CyberChimps WordPress Themes

沪ICP备2021008917号-1 © 颜开