• 首页
  • 关于

我自然

每月存档:11月 2011

查询利器-bloom-filter详解

在 2011年11月13日 上公布 作者为 yankay

布隆过滤器(Bloom Filter)是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都远远超过一般的算法,缺点是有一定的误识别率和删除困难。本文着重于在实现Bloom Filter的时候会使用到的一些技巧。

布隆过滤器的原理不难理解。相对于一个精简的HashMap的数据结构,存入数据的时候,不存入数据本身,只保存其Hash的值。可以用于判断该数据是否存在。其本质是用Hash对数据进行”有损压缩”的位图索引。详细参见。

Bloom_filter

 

错误率

如果用来存放Hash值的槽位足够多,那么碰撞的概率就会比较小。但是所占用的空间就会比较大。所以当分配空间的时候,需要通过你能容忍的错误率和需要存放的Key的数量来指定。如果所需存储的Key数量是n,错误率是p,所需要的槽位是m。有计算槽位的公式$$m=-frac{nln p}{(ln 2)^2}.$$,也有计算概率的公式$$p = left( 1-e^{-(m/nln 2) n/m} right)^{(m/nln 2)}$$。这些公式当然不是我推导出来的,想来也不太难,就不赘述推导过程了。下面这张图可以很好的表示n和m取不同的值的时候,p的值。

Bloom_filter

根据这张图。我们可以计算出所需要的内存使用量。如果把错误率控制在1%以下的话。

保存key数 占用空间
1万 64KB
10万 1MB
100万 16MB
1000万 256MB
1亿 <4GB

 

可见占用的空间在key的数量在百万级别还是很划算的,但到了上亿的级别就不那么划算了。

Bloom Filter的插入和查询都是常数级别的,所以最大的问题就是占用内存过大。而初次分配内存的时候,如果没有能够确认槽位的个数。如果分配过多会导致内存浪费,太少就会倒是错误率过高。下面提到的两个改进方案可以分别解决这两个问题。

折叠

折叠是指当你初始化一个Bloom Filter的时候,可以分配足够大的槽位,等到Key导入完毕后,可以对使用的槽位进行合并操作。具体方法是将槽位切成两半,一边完全叠加到另一边上。减少内存的使用量。检查key的代码要做稍许改变。例:

 

通过这个操作,可以使实际使用的内存量减半。多执行几次,能减少更多。

动态扩展

通过折叠操作,可以解决分配过大的问题,但是如果一开始分配过小,就需要扩展槽位才行。如何扩展呢?只要按原尺寸再建立一个Bloom Filter数组。原来的那个保存起来,不再写入。有新的写请求的时候,就将数据写入到新的那个Bloom Filter数组里面去。等到新的也写满了,就再建立一个,以此类推。查询的时候,就需要遍历每一个Bloom Filter数组才行。但因为查询一个Bloom Filter数组的速度很快,查询一组Bloom Filter数组也不会太影响性能。使用这种手段可以是Bloom Filter的大小可以轻易的扩展。但这样做有个的缺陷,就是错误率会随着数组的增加而上升,因为实际的数组长度并没有增加。

d-bloom-filter

通过上面的两个方法,就可以解决BloomFilter的分配内存的问题。但无论哪种方法都有自己局限性,折叠每次只能减半,不是很精确。动态增加的方法会造成错误率增加。最好还是能预先估计到这个BloomFilter的容量。

文章分类 软件技术 | 标签: Bloom Filter, Hadoop | 1 条评论 |

多核平台下的JAVA优化

在 2011年11月5日 上公布 作者为 yankay

现在多核CPU是主流。利用多核技术,可以有效发挥硬件的能力,提升吞吐量,对于Java程序,可以实现并发垃圾收集。但是Java利用多核技术也带来了一些问题,主要是多线程共享内存引起了。目前内存和CPU之间的带宽是一个主要瓶颈,每个核可以独享一部分高速缓存,可以提高性能。JVM是利用操作系统的”轻量级进程”实现线程,所以线程每操作一次共享内存,都无法在高速缓存中命中,是一次开销较大的系统调用。所以区别于普通的优化,针对多核平台,需要进行一些特殊的优化。

代码优化

线程数要大于等于核数

如果使用多线程,只有运行的线程数比核数大,才有可能榨干CPU资源,否则会有若干核闲置。要注意的是,如果线程数目太多,就会占用过多内存,导致性能不升反降。JVM的垃圾回收也是需要线程的,所以这里的线程数包含JVM自己的线程

尽量减少共享数据写操作

每个线程有自己的工作内存,在这个区域内,系统可以毫无顾忌的优化,如果去读共享内存区域,性能也不会下降。但是一旦线程想写共享内存(使用volatile关键字),就会插入很多内存屏障操作(Memory Barrier或者Memory Fence)指令,保证处理器不乱序执行。相比写本地线程自有的变量,性能下降很多。处理方法是尽量减少共享数据,这样也符合”数据耦合”的设计原则。

使用synchronize关键字

在Java1.5中,synchronize是性能低效的。因为这是一个重量级操作,需要调用操作接口,导致有可能加锁消耗的系统时间比加锁以外的操作还多。相比之下使用Java提供的Lock对象,性能更高一些。但是到了Java1.6,发生了变化。synchronize在语义上很清晰,可以进行很多优化,有适应自旋,锁消除,锁粗化,轻量级锁,偏向锁等等。导致在Java1.6上synchronize的性能并不比Lock差。官方也表示,他们也更支持synchronize,在未来的版本中还有优化余地。

使用乐观策略

传统的同步并发策略是悲观的。表现语义为:多线程操作一个对象的时候,总觉得会有两个线程在同时操作,所以需要锁起来。乐观策略是,假设平时就一个线程访问,当出现了冲突的时候,再重试。这样更高效一些。Java的AtomicInteger就是使用了这个策略。

使用线程本地变量(ThreadLocal)

使用ThreadLocal可以生成线程本地对象的副本,不会和其他线程共享。当该线程终止的时候,其本地变量可以全部回收。

类中Field的排序

可以将一个类会频繁访问到的几个field放在一起,这样他们就有更多的可能性被一起加入高速缓存。同时最好把他们放在头部。基本变量和引用变量不要交错排放。

批量处理数组

现在处理器可以用一条指令来处理一个数组中的多条记录,例如可以同时向一个byte数组中读或者写store记录。所以要尽量使用System.arraycopy()这样的批量接口,而不是自己操作数组。

JVM优化

启用大内存页

现在一个操作系统默认页是4K。如果你的heap是4GB,就意味着要执行1024*1024次分配操作。所以最好能把页调大。这个配额设计操作系统,单改Jvm是不行的。Linux上的配置有点复杂,不详述。

在Java1.6中UseLargePages是默认开启的,LasrgePageSzieInBytes被设置成了4M。笔者看到一些情况下配置成了128MB,在官方的性能测试中更是配置到256MB。

启用压缩指针

Java的64的性能比32慢,原因是因为其指针由32位扩展到64位,虽然寻址空间从4GB扩大到256 TB,但导致性能的下降,并占用了更多的内存。所以对指针进行压缩。压缩后的指针最多支持32GB内存,并且可以获得32位JVM的性能。

在JDK6 update 23默认开启了,之前的版本可以使用-XX:+UseCompressedOops来启动配置。

性能可以看这个评测,性能的提升是很可观。

benchmarka

启用NUMA

numa是一个CPU的特性。SMP架构下,CPU的核是对称,但是他们共享一条系统总线。所以CPU多了,总线就会成为瓶颈。在NUMA架构下,若干CPU组成一个组,组之间有点对点的通讯,相互独立。启动它可以提高性能。

NUMA需要硬件,操作系统,JVM同时启用,才能启用。Linux可以用numactl来配置numa,JVM通过-XX:+UseNUMA来启用。

激进优化特性

在Java1.6中,激进优化(AggressiveOpts)是默认开启的。激进优化是一般有一些下一个版本才会发布的优化选项。但是有可能造成不稳定。前段时间以讹传讹的JDK7的Bug,就是开启这个选项后测到的。

逃逸分析

让一个对象在一个方法内创建后,如果他传递出去,就可以称为方法逃逸;如果传递到别的线程,成为线程逃逸。如果能知道一个对象没有逃逸,就可以把它分配在栈而不是堆上,节约GC的时间。同时可以将这个对象拆散,直接使用其成员变量,有利于利用高速缓存。如果一个对象没有线程逃逸,就可以取消其中一切同步操作,很大的提高性能。

但是逃逸分析是很有难度的,因为花了cpu去对一个对象去分析,要是他不逃逸,就无法优化,之前的分析血本无归。所以不能使用复杂的算法,同时现在的JVM也没有实现栈上分配。所以开启之后,性能也可能下降。

可以使用-XX:+DoEscapeAnalysis来开启逃逸分析。

高吞吐量GC配置

对于高吞吐量,在年轻态可以使用Parallel Scavenge,年老态可以使用Parallel Old垃圾收集器。
使用-XX:+UseParallelOldGC开启

可以将-XX:ParallelGCThreads根据CPU的个数进行调整。可以是CPU数的1/2或者5/8

低延迟GC配置

对于低延迟的应用,在年轻态可以使用ParNew,年老态可以使用CMS垃圾收集器。

可以使用-XX:+UseConcMarkSweepGC和-XX:+UseParNewGC打开。

可以将-XX:ParallelGCThreads根据CPU的个数进行调整。可以是CPU数的1/2或者5/8

可以调整-XX:MaxTenuringThreshold(晋升年老代年龄)调高,默认是15.这样可以减少年老代GC的压力

可以-XX:TargetSurvivorRatio,调整Survivor的占用比率。默认50%.调高可以提供Survivor区的利用率

可以调整-XX:SurvivorRatio,调整Eden和Survivor的比重。默认是8。这个比重越小,Survivor越大,对象可以在年轻态呆更多时间。

等等

 

参见:《Java优化白皮书》,《深入理解Java虚拟机》

文章分类 软件技术 | 标签: Java, 优化, 多核 | 1 条评论 |

HBase中文官方文档

在 2011年11月1日 上公布 作者为 yankay

 

hbase

HBase – Hadoop Database,是一个构建在Apache Hadoop上的列数据。Hbase有很好的扩展性,被认为是BigTable的一个克隆,可以存储数以亿计的行。

在Hbase的官网,我们看到一篇很好的官方文档。我花了很长的时间,把他汉化了。请点击这里:《HBase中文官方文档》

这篇文档非常的详尽,从Hbase的安装,配置,使用,原理,优化,维护都做了非常全面的介绍。还提供了很多扩展阅读,方便我们知道更多Hbase的工作机制。通过翻译这篇文档,我细细读了这篇文档,受益良多。

翻译是一个吃进去再吐出来的过程,我的Hbase的理解也可能会发生一些偏差,所以如果有地方发生错误,请告诉我,大家一起进步。

 

文章分类 软件技术 | 标签: Hbase, 中文, 官方文档, 文档 | 发表评论 |

近期文章

  • 听说 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 © 颜开