基础技术 - ImportNew
策略模式定义了算法族，分别封装起来，让它们之间可以互相替换，此模式让算法的变化独立于使用算法的客户。
工厂方法模式定义了一个创建对象的接口，但由子类决定要实例化的类是哪一个。工厂方法让类把实例化推迟到了子类。
抽象工厂模式提供一个接口，用于创建相关或依赖对象的家族，而不需要明确指定具体类。
有一些对象我们只需要一个，比方说：线程池、缓存、对话框、处理器偏好设置和注册表的对象等等。事实上，这类对象只能有一个实例，如果制造出多个实例，就会导致许多问题产生，例如：程序的行为异常、资源使用过量，或者是不一致的结果。
命令模式将“请求”封装成对象，以便使用不同的请求、队列或者日志来参数化其他对象。命令模式也支持可撤销的操作。
适配器模式将一个类的接口，转换成客户期望的另一个接口。适配器让原本接口不兼容的类可以合作无间。
外观模式提供了一个统一的接口，用来访问子系统中的一群接口。外观定义了一个高层接口，让子系统更容易使用。
模板方法模式在一个方法中定义了一个算法的骨架，而将一些步骤延迟到子类中。模板方法使得子类可以在不改变算法结构的情况下，重新定义算法中的某些步骤。
迭代器模式提供一种方法顺序访问一个聚合对象中的各个元素，而又不暴露其内部的表示。
给你1个文件bigdata，大小4663M，5亿个数，文件中的数据随机,现在要对这个文件进行排序，怎么搞？
这是一篇学习笔记。学习的材料来自Jay Kreps的一篇讲Log的博文。原文很长，但是我坚持看完了，收获颇多，也深深为Jay哥的技术能力、架构能力和对于分布式系统的理解之深刻所折服。
本文简要探讨了：如何根据opcode和寻址模式，将bytecode生成汇编码。
实时计算是什么？最热的微博话题是什么？如何定义时间？本文会针对这些问题，给出自己的解答。
最近在做WebMagic的后台，遇到一个问题：后台用到了数据库，本来理想情况下是用Mysql，但是为了做到开箱即用，也整合了一个嵌入式数据库H2。这里面就有个问题了，如何用一套代码，提供对Mysql和H2两种方案的支持？博主收集了一些资料，也调试了很久，终于找到一套可行方案，记录下来。代码贴的有点多，主要是为了以后方便自己查找。
这是一篇很有意思的Java值传递、引用传递问题讨论。
这篇文章详细讨论了JVM字节码的resolve过程。
本文通过一个实例介绍了spring整合ehcache注解实现查询缓存，并实现实时缓存更新或删除。
Java 8 update 20中引入的字符串去重特性，本文通过示例介绍了其工作原理。
最近应用在测试中出现Out Of Memory的问题， 通过jmap查看，发现JVM heap全用满了。有很多工具可以查看JVM堆的信息，本文介绍了通过MAT的命令行工具分析了dump出来的snapshot，查找到OOM的元凶。
如何在Java生态圈选择一个轻量级的RESTful框架？本文对Java RESTful框架的性能进行了比较。
log4j 是延迟写入。意味着info了之后，就马上执行其他的代码了。非阻塞的log不应该用刷盘时间...
关于ImportNew
ImportNew 专注于 Java 技术分享。于日 11:11正式上线。是的，这是一个很特别的时刻 :)
ImportNew 由两个 Java 关键字 import 和 new 组成，意指：Java 开发者学习新知识的网站。 import 可认为是学习和吸收， new 则可认为是新知识、新技术圈子和新朋友……
新浪微博：
推荐微信号
反馈建议：@
广告与商务合作QQ：
– 好的话题、有启发的回复、值得信赖的圈子
– 写了文章？看干货？去头条！
– 为IT单身男女服务的征婚传播平台
– 优秀的工具资源导航
– 活跃 & 专业的翻译小组
– 国内外的精选博客文章
– UI,网页，交互和用户体验
– JavaScript, HTML5, CSS
– 专注Android技术分享
– 专注iOS技术分享
– 专注Java技术分享
– 专注Python技术分享
& 2017 ImportNew966,690 一月 独立访问用户
语言 & 开发
架构 & 设计
文化 & 方法
您目前处于：
小文件大问题——海量小文件解决方案初探
小文件大问题——海量小文件解决方案初探
日. 估计阅读时间:
相关厂商内容
相关赞助商
QCon北京-18日，北京&国家会议中心，
Facebook的Haystack对小文件的解决办法是。将小文件数据依次追加到数据文件中，并且生成索引文件，通过索引来查找小文件在数据文件中的offset和size，对文件进行读取。
Haystack的数据文件部分
Haystack的数据文件，将每个小文件封装成一个needle，包含文件的key、size、data等数据信息。所有小文件按写入的先后顺序追加到数据文件中。
Haystack的索引文件部分：
Haystack的索引文件保存每个needle的key，以及该needle在数据文件中的offset、size等信息。程序启动时会将索引加载到内存中，在内存中通过查找索引，来定位在数据文件中的偏移量和大小。
Haystack面临的问题
Facebook的Haystack特点是将文件的完整key都加载到内存中，进行文件定位。机器内存足够大的情况下，Facebook完整的8字节key可以全部加载到内存中。
但是现实环境下有两个主要问题：
存储服务器内存不会太大，一般为32G至64G；
小文件对应的key大小难控制，一般选择文件内容的MD5或SHA1作为该文件的key。
场景举例：
一台存储服务器有12块4T磁盘，内存为32GB左右。
服务器上现需存储大小约为4K的头像、缩略图等文件，约为10亿个。
文件的key使用MD5，加上offset和size字段，平均一个小文件对应的索引信息占用28字节。
在这种情况下，索引占用内存接近30GB，磁盘仅占用4TB。内存消耗近100%，磁盘消耗只有8%。
所以索引优化是一个必须要解决的问题。
Haystack_plus
Haystack_plus的核心也由数据文件和索引文件组成。
1. Haystack_plus的数据文件
与Facebook的Haystack类似，Haystack_plus将多个小文件写入到一个数据文件中，每个needle保存key、size、data等信息。
2. Haystack_plus的索引文件
索引是我们主要优化的方向：
索引文件只保存key的前四字节，而非完整的key；
索引文件中的offset和size字段，通过512字节对齐，节省1个字节；并根据整个Haystack_plus数据文件实际大小计算offset和size使用的字节数。
3. Haystack_plus的不同之处
数据文件中的needle按照key的字母顺序存放。
由于索引文件的key，只保存前四字节，如果小文件key的前四字节相同，不顺序存放，就无法找到key的具体位置。可能出现如下情况：
例如：用户读取的文件key是0x ab cd ef ac ee，但由于索引文件中的key只保存前四字节，只能匹配0x ab cd ef ac这个前缀，此时无法定位到具体要读取的offset。
我们可以通过needle顺序存放，来解决这个问题：
例如：用户读取文件的key是0x ab cd ef ac bb，匹配到0x ab cd ef ac这个前缀，此时offset指向0x ab cd ef ac aa这个needle，第一次匹配未命中。
通过存放在needle header中的size，我们可以定位0x ab cd ef ac bb位置，匹配到正确needle，并将数据读取给用户。
4. 索引搜索流程为
5. 请求不存在的文件
问题：我们应用折半查找算法在内存查找key，时间复杂度为O(log(n))，其中n为needle数目。索引前缀相同时，需要在数据文件中继续查找。此时访问的文件不存在时，容易造成多次IO查找。
解决方法：在内存中，将存在的文件映射到bloom filter中。此时只需要通过快速搜索，就可以排除不存在的文件。
时间复杂度为O(k)，k为一个元素需要的bit位数。当k为9.6时，误报率为1%，如果k再增加4.8，误报率将降低为0.1%。
6. 前缀压缩，效果如何
Haystack_plus与Facebook Haystack内存消耗的对比，场景举例，文件（如：头像、缩略图等）大小4K，key为MD5：
内存消耗对比
全量key，16字节
Haystack_plus
注：Haystack的needle为追加写入，因此offset和size大小固定。Haystack_plus的key使用其前4字节，offset根据Haystack_plus数据文件的地址空间计算字节数，并按512字节对齐；size根据实际文件的大小计算字节数，并按512对齐。
从上图可以看出在文件数量为10亿的情况下，使用Facabook的Haystack消耗的内存超过26G，使用Haystack_plus仅消耗9G多内存，内存使用降低了2/3。
7.索引优化根本就停不下来
10亿个4K小文件，消耗内存超过9G。Key占用4字节，Offset占用4字节，还需要再小一些。
根据文件key的前缀，进行分层，相同的前缀为一层。
分层的好处
减少key的字节数
通过分层，只保存一份重复的前缀，节省key的字节数。
减少offset的字节数
优化前的offset，偏移范围为整个Haystack_plus的数据文件的地址空间。
优化后，只需在数据文件中的层内进行偏移，根据最大的层地址空间可以计算所需字节数。
分层后的效果
从上图可以看出，进行分层后，内存消耗从优化前的9G多，降低到4G多，节省了一半的内存消耗。
Haystack_plus整体架构
1. Haystack_plus组织
每台服务器上，我们将所有文件分成多个group，每个group创建一个Haystack_plus。系统对所有的Haystack_plus进行统一管理。
读、写、删除等操作，都会在系统中定位操作某个Haystack_plus，然后通过索引定位具体的needle，进行操作。
2. 索引组织
之前已经介绍过，所有needle顺序存放，索引做前缀压缩，并分层。
3. 文件组成
chunk文件：小文件的实际数据被拆分保存在固定数量的chunk数据文件中，默认为12个数据块；
needle list文件：保存每个needle的信息(如文件名、offset等)；
needle index和layer index文件：保存needle list在内存中的索引信息；
global version文件：保存版本信息，创建新version时自动将新版本信息追加到该文件中；
attribute文件：保存系统的属性信息(如chunk的SHA1等)；
original filenames：保存所有文件原始文件名。
A、Haystack_plus数据文件被拆分为多个chunk组织，chunk1，chunk2，chunk3&&
B、分成多个chunk的好处：
1. 数据损坏时，不影响其它chunk的数据；
2. 数据恢复时，只需恢复损坏的chunk。
C、每个chunk的SHA1值存放在attribute文件中。
4. 版本控制
由于needle在数据文件中按key有序存放，为不影响其顺序，新上传的文件无法加入Haystack_plus，而是首先被保存到hash目录下，再通过定期自动合并方式，将新文件加入到Haystack_plus中。
合并时将从needle_list文件中读取所有needle信息，将删除的needle剔除，并加入新上传的文件，同时重新排序，生成chunk数据文件、索引文件等。
重新合并时将生成一个新版本Haystack_plus。版本名称是所有用户的文件名排序的SHA1值的前4字节。
每半个月系统自动进行一次hash目录检查，查看是否有新文件，并计算下所有文件名集合的SHA1，查看与当前版本号是否相同，不同时说明有新文件上传，系统将重新合并生成新的数据文件。
同时，系统允许在hash目录下超过指定的文件数时，再重新创建新版本，从而减少重新合并次数。
版本的控制记录在global_version文件中，每次创建一个新版本，版本号和对应的crc32将追加到global_version文件（crc32用于查看版本号是否损坏）。
每次生成新版本时，自动通知程序重新载入索引文件、attribute文件等。
5. 数据恢复
用户的文件将保存成三副本存放，因此Haystack_plus也会存放在3台不同的机器上。
恢复场景一：
当一个Haystack_plus的文件损坏时，会在副本机器上，查找是否有相同版本的Haystack_plus，如果版本相同，说明文件的内容都是一致，此时只需将要恢复的文件从副本机器下载下来，进行替换。
恢复场景二：
如果副本机器没有相同版本的Haystack_plus，但存在更高版本，那此时可以将该版本的整个Haystack_plus从副本机器上拷贝下来，进行替换。
恢复场景三：
如果前两种情况都不匹配，那就从另外两台副本机器上，将所有文件都读到本地上的hash目录下，并将未损坏的chunk中保存的文件也提取到hash目录下，用所有文件重新生成新版本的Haystack_plus。
Haystack_plus效果如何
在使用Haystack_plus后一段时间，我们发现小文件的整体性能有显著提高，RPS提升一倍多，机器的IO使用率减少了将近一倍。同时，因为优化了最小存储单元，碎片降低80%。
使用该系统我们可以为用户提供更快速地读写服务，并且节省了集群的资源消耗。
作者简介：陈闯，花名&战士雷欧&，白山超级工程师。Linux内核、Nginx模块、存储架构资深开发人员，7年以上存储架构、设计及开发经验，先后就职于东软、中科曙光、新浪、美团，擅长独立进行Haystack、纠删码等各种项目研发，爱好不断降低IO、挑战冗余度底线。白山滑板车选手专业十级，会漂移，正积极备战方庄街道第6届动感滑板车运动会，家庭梦想是为爱妻赢得无硅油洗发水。
感谢对本文的审校。
给InfoQ中文站投稿或者参与内容翻译工作，请邮件至。也欢迎大家通过新浪微博（，），微信（微信号：）关注我们。
Author Contacted
告诉我们您的想法
允许的HTML标签: a,b,br,blockquote,i,li,pre,u,ul,p
当有人回复此评论时请E-mail通知我
花名“战士雷欧”，白山超级工程师。
允许的HTML标签: a,b,br,blockquote,i,li,pre,u,ul,p
当有人回复此评论时请E-mail通知我
允许的HTML标签: a,b,br,blockquote,i,li,pre,u,ul,p
当有人回复此评论时请E-mail通知我
赞助商链接
InfoQ每周精要
通过个性化定制的新闻邮件、RSS Feeds和InfoQ业界邮件通知，保持您对感兴趣的社区内容的时刻关注。
架构 & 设计
文化 & 方法
<及所有内容，版权所有 &#169;
C4Media Inc.
服务器由 提供, 我们最信赖的ISP伙伴。
北京创新网媒广告有限公司
京ICP备号-7
注意：如果要修改您的邮箱，我们将会发送确认邮件到您原来的邮箱。
使用现有的公司名称
修改公司名称为：
公司性质：
使用现有的公司性质
修改公司性质为:
使用现有的公司规模
修改公司规模为：
使用现在的国家
使用现在的省份
Subscribe to our newsletter?
Subscribe to our industry email notices?
我们发现您在使用ad blocker。
我们理解您使用ad blocker的初衷，但为了保证InfoQ能够继续以免费方式为您服务，我们需要您的支持。InfoQ绝不会在未经您许可的情况下将您的数据提供给第三方。我们仅将其用于向读者发送相关广告内容。请您将InfoQ添加至白名单，感谢您的理解与支持。5亿整数的大文件，如何排 - Java相关当前位置:& &&&5亿整数的大文件，如何排5亿整数的大文件，如何排&&网友分享于：&&浏览：0次5亿整数的大文件，怎么排？问题
给你1个文件bigdata，大小4663M，5亿个数，文件中的数据随机,如下一行一个整数：
现在要对这个文件进行排序，怎么搞？
先尝试内排，选2种排序方式：
private final int cutoff = 8;
public &T& void perform(Comparable&T&[] a) {
perform(a,0,a.length - 1);
private &T& int median3(Comparable&T&[] a,int x,int y,int z) {
if(lessThan(a[x],a[y])) {
if(lessThan(a[y],a[z])) {
else if(lessThan(a[x],a[z])) {
if(lessThan(a[z],a[y])){
}else if(lessThan(a[z],a[x])) {
private &T& void perform(Comparable&T&[] a,int low,int high) {
int n = high - low + 1;
//当序列非常小，用插入排序
if(n &= cutoff) {
InsertionSort insertionSort = SortFactory.createInsertionSort();
insertionSort.perform(a,low,high);
//当序列中小时，使用median3
}else if(n &= 100) {
int m = median3(a,low,low + (n &&& 1),high);
exchange(a,m,low);
//当序列比较大时，使用ninther
int gap = n &&& 3;
int m = low + (n &&& 1);
int m1 = median3(a,low,low + gap,low + (gap && 1));
int m2 = median3(a,m - gap,m,m + gap);
int m3 = median3(a,high - (gap && 1),high - gap,high);
int ninther = median3(a,m1,m2,m3);
exchange(a,ninther,low);
if(high &= low)
//lessThan
//greaterThan
Comparable&T& pivot =
int i = low + 1;
* 不变式：
* a[low..lt-1] 小于pivot -& 前部(first)
* a[lt..i-1] 等于 pivot -& 中部(middle)
* a[gt+1..n-1] 大于 pivot -& 后部(final)
* a[i..gt] 待考察区域
while (i &= gt) {
if(lessThan(a[i],pivot)) {
//i-& ,lt -&
exchange(a,lt++,i++);
}else if(lessThan(pivot,a[i])) {
exchange(a,i,gt--);
// a[low..lt-1] & v = a[lt..gt] & a[gt+1..high].
perform(a,low,lt - 1);
perform(a,gt + 1,high);
归并排序：
* 小于等于这个值的时候，交给插入排序
private final int cutoff = 8;
* 对给定的元素序列进行排序
* @param a 给定元素序列
public &T& void perform(Comparable&T&[] a) {
Comparable&T&[] b = a.clone();
perform(b, a, 0, a.length - 1);
private &T& void perform(Comparable&T&[] src,Comparable&T&[] dest,int low,int high) {
if(low &= high)
//小于等于cutoff的时候,交给插入排序
if(high - low &= cutoff) {
SortFactory.createInsertionSort().perform(dest,low,high);
int mid = low + ((high - low) &&& 1);
perform(dest,src,low,mid);
perform(dest,src,mid + 1,high);
//考虑局部有序 src[mid] &= src[mid+1]
if(lessThanOrEqual(src[mid],src[mid+1])) {
System.arraycopy(src,low,dest,low,high - low + 1);
//src[low .. mid] + src[mid+1 .. high] -& dest[low .. high]
merge(src,dest,low,mid,high);
private &T& void merge(Comparable&T&[] src,Comparable&T&[] dest,int low,int mid,int high) {
for(int i = low,v = low,w = mid + 1; i &= i++) {
if(w & high || v &= mid && lessThanOrEqual(src[v],src[w])) {
dest[i] = src[v++];
dest[i] = src[w++];
数据太多，递归太深 -&栈溢出？加大Xss？数据太多，数组太长 -& OOM？加大Xmx?
耐心不足，没跑出来.而且要将这么大的文件读入内存，在堆中维护这么大个数据量，还有内排中不断的拷贝，对栈和堆都是很大的压力，不具备通用性。
sort命令来跑
sort -n bigdata -o bigdata.sorted
跑了多久呢？24分钟.
为什么这么慢？
粗略的看下我们的资源：
内存 jvm-heap/stack，native-heap/stack,page-cache，block-buffer
外存 swap + 磁盘
数据量很大，函数调用很多，系统调用很多，内核/用户缓冲区拷贝很多，脏页回写很多，io-wait很高，io很繁忙，堆栈数据不断交换至swap，线程切换很多，每个环节的锁也很多.
总之，内存吃紧，问磁盘要空间，脏数据持久化过多导致cache频繁失效，引发大量回写，回写线程高，导致cpu大量时间用于上下文切换，一切，都很糟糕，所以24分钟不细看了，无法忍受.
private BitS
public void perform(
String largeFileName,
int total,
String destLargeFileName,
Castor&Integer& castor,
int readerBufferSize,
int writerBufferSize,
boolean asc) throws
System.out.println(&BitmapSort Started.&);
long start = System.currentTimeMillis();
bits = new BitSet(total);
InputPart&Integer& largeIn = PartFactory.createCharBufferedInputPart(largeFileName, readerBufferSize);
OutputPart&Integer& largeOut = PartFactory.createCharBufferedOutputPart(destLargeFileName, writerBufferSize);
largeOut.delete();
int off = 0;
while (true) {
data = largeIn.read();
if (data == null)
largeIn.close();
int size = bits.size();
System.out.println(String.format(&lines : %d ,bits : %d&, off, size));
for (int i = 0; i & i++) {
if (get(i)) {
largeOut.write(i);
for (int i = size - 1; i &= 0; i--) {
if (get(i)) {
largeOut.write(i);
largeOut.close();
long stop = System.currentTimeMillis();
long elapsed = stop -
System.out.println(String.format(&BitmapSort Completed.elapsed : %dms&,elapsed));
}finally {
largeIn.close();
largeOut.close();
private void set(int i) {
bits.set(i);
private boolean get(int v) {
return bits.get(v);
nice!跑了190秒，3分来钟.以核心内存4663M/32大小的空间跑出这么个结果，而且大量时间在用于I/O，不错.
问题是，如果这个时候突然内存条坏了1、2根，或者只有极少的内存空间怎么搞？
该外部排序上场了.外部排序干嘛的？
内存极少的情况下，利用分治策略，利用外存保存中间结果，再用多路归并来排序;
map-reduce的嫡系.
内存中维护一个极小的核心缓冲区memBuffer，将大文件bigdata按行读入，搜集到memBuffer满或者大文件读完时，对memBuffer中的数据调用内排进行排序，排序后将有序结果写入磁盘文件bigdata.xxx.part.sorted. 循环利用memBuffer直到大文件处理完毕，得到n个有序的磁盘文件：
现在有了n个有序的小文件，怎么合并成1个有序的大文件？把所有小文件读入内存，然后内排？(⊙o⊙)…no!
利用如下原理进行归并排序：我们举个简单的例子：
文件1：3,6,9文件2：2,4,8文件3：1,5,7
第一回合：文件1的最小值：3 , 排在文件1的第1行文件2的最小值：2，排在文件2的第1行文件3的最小值：1，排在文件3的第1行那么，这3个文件中的最小值是：min(1,2,3) = 1也就是说，最终大文件的当前最小值，是文件1、2、3的当前最小值的最小值，绕么？上面拿出了最小值1，写入大文件.
第二回合：文件1的最小值：3 , 排在文件1的第1行文件2的最小值：2，排在文件2的第1行文件3的最小值：5，排在文件3的第2行那么，这3个文件中的最小值是：min(5,2,3) = 2将2写入大文件.
也就是说，最小值属于哪个文件，那么就从哪个文件当中取下一行数据.（因为小文件内部有序，下一行数据代表了它当前的最小值）
最终的时间，跑了771秒，13分钟左右.
less bigdata.sorted.text
12345678910
12345678910
12345678910 上一篇：下一篇：文章评论相关解决方案 1234567891011 Copyright & &&版权所有