文档章节

LevelDB的算分逻辑

强子哥哥
 强子哥哥
发布于 2017/07/23 11:07
字数 882
阅读 30
收藏 0
点赞 0
评论 0

每次1个新文件,先算放到哪层上,这是根据是否有key的overlap来决定的,这个逻辑见

stop in org.iq80.leveldb.impl.Version.pickLevelForMemTableOutput

int pickLevelForMemTableOutput(Slice smallestUserKey, Slice largestUserKey) {
		System.out.println("" + new String(smallestUserKey.getBytes()));
		System.out.println("" + new String(largestUserKey.getBytes()));
		// ================岁月静好,现世安稳===================
		int level = 0;
		// ================岁月静好,现世安稳===================
		// ================岁月静好,现世安稳===================
		// ================岁月静好,现世安稳===================
		if (!overlapInLevel(0, smallestUserKey, largestUserKey)) {
			// ================岁月静好,现世安稳===================
			// Push to next level if there is no overlap in next level,
			// and the #bytes overlapping in the level after that are limited.
			// ================岁月静好,现世安稳===================
			InternalKey start = new InternalKey(smallestUserKey, MAX_SEQUENCE_NUMBER, ValueType.VALUE);
			InternalKey limit = new InternalKey(largestUserKey, 0, ValueType.VALUE);
			// ================岁月静好,现世安稳===================
			while (level < MAX_MEM_COMPACT_LEVEL) {
				// ================岁月静好,现世安稳===================
				if (overlapInLevel(level + 1, smallestUserKey, largestUserKey)) {
					break;
				}
				// ================岁月静好,现世安稳===================
				long sum = Compaction.totalFileSize(versionSet.getOverlappingInputs(level + 2, start, limit));
				if (sum > MAX_GRAND_PARENT_OVERLAP_BYTES) {
					break;
				}
				// ================岁月静好,现世安稳===================
				level++;
			}
		}
		return level;
		// ================岁月静好,现世安稳===================
	}

 

选好了层之后,需要apply一下,这个见

stop in  org.iq80.leveldb.impl.VersionSet$Builder.apply --- 选好level,放到对应的层级上

/**
		 * Apply the specified edit to the current state.
		 */
		public void apply(VersionEdit edit) {
			// 看到这里了
			// Update compaction pointers
			for (Entry<Integer, InternalKey> entry : edit.getCompactPointers().entrySet()) {
				Integer level = entry.getKey();
				InternalKey internalKey = entry.getValue();
				versionSet.compactPointers.put(level, internalKey);
			}
			// 看到这里了=======================
			// Delete files
			for (Entry<Integer, Long> entry : edit.getDeletedFiles().entries()) {
				Integer level = entry.getKey();
				Long fileNumber = entry.getValue();
				levels.get(level).deletedFiles.add(fileNumber);
				// todo missing update to addedFiles?
			}
			// 看到这里了=======================
			// Add new files
			for (Entry<Integer, FileMetaData> entry : edit.getNewFiles().entries()) {
				Integer level = entry.getKey();
				FileMetaData fileMetaData = entry.getValue();

				// We arrange to automatically compact this file after
				// a certain number of seeks. Let's assume:
				// (1) One seek costs 10ms
				// (2) Writing or reading 1MB costs 10ms (100MB/s)
				// (3) A compaction of 1MB does 25MB of IO:
				// 1MB read from this level
				// 10-12MB read from next level (boundaries may be misaligned)
				// 10-12MB written to next level
				// This implies that 25 seeks cost the same as the compaction
				// of 1MB of data. I.e., one seek costs approximately the
				// same as the compaction of 40KB of data. We are a little
				// conservative and allow approximately one seek for every 16KB
				// of data before triggering a compaction.
				int allowedSeeks = (int) (fileMetaData.getFileSize() / 16384);
				if (allowedSeeks < 100) {
					allowedSeeks = 100;
				}
				fileMetaData.setAllowedSeeks(allowedSeeks);

				levels.get(level).deletedFiles.remove(fileMetaData.getNumber());
				levels.get(level).addedFiles.add(fileMetaData);
			}
			// 看到这里了=======================
		}

 

 

接下来开始算分

stop in  org.iq80.leveldb.impl.VersionSet.finalizeVersion  --- 算分

private void finalizeVersion(Version version) {
		{
			printFile(version);
		}
		// Precomputed best level for next compaction
		// ==================================================================
		int bestLevel = -1;
		double bestScore = -1;
		// ==================================================================
		for (int level = 0; level < version.numberOfLevels() - 1; level++) {
			double score;
			if (level == 0) {
				// We treat level-0 specially by bounding the number of files
				// instead of number of bytes for two reasons:
				//
				// (1) With larger write-buffer sizes, it is nice not to do too
				// many level-0 compactions.
				//
				// (2) The files in level-0 are merged on every read and
				// therefore we wish to avoid too many files when the individual
				// file size is small (perhaps because of a small write-buffer
				// setting, or very high compression ratios, or lots of
				// overwrites/deletions).
				// ==================================================================
				score = 1.0 * version.numberOfFilesInLevel(level) / L0_COMPACTION_TRIGGER;
			} else {
				// Compute the ratio of current size to size limit.
				long levelBytes = 0;
				for (FileMetaData fileMetaData : version.getFiles(level)) {
					levelBytes += fileMetaData.getFileSize();
				}
				score = 1.0 * levelBytes / maxBytesForLevel(level);
			}

			if (score > bestScore) {
				bestLevel = level;
				bestScore = score;
			}
		}
		// 看到这里了
		version.setCompactionLevel(bestLevel);
		version.setCompactionScore(bestScore);
		// ==================================================================
	}

 

算完分后,开始选择是否需要compaction

stop in  org.iq80.leveldb.impl.VersionSet.pickCompaction ---根据分数来决定是否要compaction

public Compaction pickCompaction() {
		// ================岁月静好,现世安稳===================
		// We prefer compactions triggered by too much data in a level over
		// the compactions triggered by seeks.
		// ================岁月静好,现世安稳===================
		boolean sizeCompaction = (current.getCompactionScore() >= 1);
		boolean seekCompaction = (current.getFileToCompact() != null);

		int level;
		List<FileMetaData> levelInputs;
		// ================岁月静好,现世安稳===================
		if (sizeCompaction) {
			level = current.getCompactionLevel();
			// ================岁月静好,现世安稳===================
			Preconditions.checkState(level >= 0);
			Preconditions.checkState(level + 1 < NUM_LEVELS);
			// ================岁月静好,现世安稳===================
			// Pick the first file that comes after compact_pointer_[level]
			levelInputs = newArrayList();
			// ================岁月静好,现世安稳===================
			for (FileMetaData fileMetaData : current.getFiles(level)) {
				if (!compactPointers.containsKey(level)
						|| internalKeyComparator.compare(fileMetaData.getLargest(), compactPointers.get(level)) > 0) {
					levelInputs.add(fileMetaData);
					break;
				}
			}
			if (levelInputs.isEmpty()) {
				// Wrap-around to the beginning of the key space
				levelInputs.add(current.getFiles(level).get(0));
			}
		}
		// ================岁月静好,现世安稳===================
		else if (seekCompaction) {
			level = current.getFileToCompactLevel();
			levelInputs = ImmutableList.of(current.getFileToCompact());
		} else {
			return null;
		}

		// Files in level 0 may overlap each other, so pick up all overlapping
		// ones
		if (level == 0) {
			Entry<InternalKey, InternalKey> range = getRange(levelInputs);
			// Note that the next call will discard the file we placed in
			// c->inputs_[0] earlier and replace it with an overlapping set
			// which will include the picked file.
			levelInputs = getOverlappingInputs(0, range.getKey(), range.getValue());

			Preconditions.checkState(!levelInputs.isEmpty());
		}

		Compaction compaction = setupOtherInputs(level, levelInputs);
		return compaction;
	}

 

© 著作权归作者所有

共有 人打赏支持
强子哥哥

强子哥哥

粉丝 859
博文 926
码字总数 640946
作品 8
南京
架构师
leveldb-rust-b Rust 编译出错

src/leveldb/lib.rs:12:1: 12:19 warning: this inner attribute syntax is deprecated. The new syntax is , with a bang and no semicolon. src/leveldb/lib.rs:12 #[feature(globs)]; ^~ ......

MtrS
2014/05/27
0
0
发布一个参考ssdb,用go实现的类似redis的高性能nosql:ledisdb

起因 ledisdb是一个参考ssdb,采用go实现,底层基于leveldb,类似redis的高性能nosql数据库,提供了kv,list,hash以及zset数据结构的支持。 我们现在的应用极大的依赖redis,但随着我们用户...

siddontang
2014/05/11
0
1
一个参考ssdb,使用go类似的实现redis高性能nosql:ledisdb

起因 ledisdb是一个參考ssdb。採用go实现,底层基于leveldb,相似redis的高性能nosql数据库,提供了kv,list,hash以及zset数据结构的支持。 我们如今的应用极大的依赖redis。但随着我们用户...

mickelfeng
06/08
0
0
高性能nosql ledisdb设计与实现(1)

ledisdb是一个用go实现的基于leveldb的高性能nosql数据库,它提供多种数据结构的支持,网络交互协议参考redis,你可以很方便的将其作为redis的替代品,用来存储大于内存容量的数据(当然你的...

siddontang
2014/06/04
0
0
盘点移动开发中最流行的5个数据库

嵌入式数据库是轻量级的,独立的库,没有服务器组件,无需管理,一个小的代码尺寸,以及有限的资源需求。目前有几种嵌入式数据库,你可以在移动应用程序中使用。让我们来看看这些最流行的数据...

kouxunli1
2014/11/21
0
0
ledisdb作为嵌入式存储引擎入门例程

ledis包使用 基于 ubuntu 14.04 安装依赖包 下载go项目 安装snappy leveldb ledisdb提供脚本,安装 leveldb,snappy 很简单 编辑 main.go 输出:ccc...

智深
2014/08/15
0
3
Reveldb 与 Kyoto Tycoon 性能对比(一)

一、概述 Reveldb 是个人在空余时间和周末完成(应该说还远远未完善)的一个基于 google leveldb 的 NoSQL 数据服务器,网络连接采用了 libevent 的 HTTP 接口,因此 reveldb 天生就适合处理 ...

大卷卷
2013/01/03
0
1
Level DB中的BloomFliter及Murmur Hash算法

1、LevleDb bloomfilter存储格式 在LevelDb 1.4版本中,加入了bloomfilter的支持,这样在DB::Get()方法的调用过程中,可以直接读取到bloom filter的block部分,从而减少了不存在key的大量的s...

天天顺利
2015/05/15
0
1
基于zookeeper+leveldb搭建activemq集群实现高可用

自从activemq5.9.0开始,activemq的集群实现方式取消了传统的Master-Slave方式,增加了基于zookeeper+leveldb的实现方式,其他两种方式:目录共享和数据库共享依然存在。本文主要阐述基于zoo...

chaun
2015/08/17
0
2
基于zookeeper+leveldb搭建activemq集群

自从activemq5.9.0开始,activemq的集群实现方式取消了传统的Master-Slave方式,增加了基于zookeeper+leveldb的实现方式,其他两种方式:目录共享和数据库共享依然存在。本文主要阐述基于zoo...

萧十一郎君
2014/09/12
0
7

没有更多内容

加载失败,请刷新页面

加载更多

下一页

TensorFlow 作用域与操作符的受限范围

variable_scope 影响变量和操作符 name_scope 只影响操作符 with tf.name_scope(""),使用空字符串将作用域返回到顶层 tf.variable_scope("") 相当于添加一个空层 import tensorflow as tf...

阿豪boy
9分钟前
0
0
Java面试基础篇——第六篇:常见Map类的区别

常见的map类有: HashMap, ConcurrentHashMap (Jdk1.8) , LinkedHashMap, TreeMap, Hashtable。 其中我们最常用的莫过于HashMap, 和并发情况下使用的ConcurrentHashMap了,它们的主要区别就在...

developlee的潇洒人生
11分钟前
0
0
崛起于Springboot2.X之前端模版freemaker(23)

1、配置文件 spring: freemarker: allow-request-override: false cache: true check-template-location: true charset: UTF-8 content-type: text/html ......

木九天
27分钟前
1
0
spring-boot:run启动时,指定spring.profiles.active

Maven启动指定Profile通过-P,如mvn spring-boot:run -Ptest,但这是Maven的Profile。 如果要指定spring-boot的spring.profiles.active,则必须使用mvn spring-boot:run -Drun.profiles=test......

夜黑人模糊灬
29分钟前
0
0
大数据分析挖掘技术学习:Python文本分类

引言 文本分类作为自然语言处理任务之一,被广泛应用于解决各种商业领域的问题。文本分类的目的是将 文本/文档 自动地归类为一种或多种预定义的类别。常见的文本分类应用如下: • 理解社交媒...

加米谷大数据
34分钟前
0
0
istio-0.8 指标监控,prometheus,grafana

配置: https://istio.io/docs/tasks/telemetry/metrics-logs/ https://istio.io/docs/tasks/telemetry/tcp-metrics/ envoy拦截请求>上报mixer>对接prometheus>grafana 效果截图: promethe......

xiaomin0322
36分钟前
0
0
公众号推荐

阿里技术 书籍:《不止代码》

courtzjl
39分钟前
0
0
关于改进工作效率

1.给不同的业务线建立需求群,所有的数据需求都在群里面提。 2.对于特别难搞定的事情,到对应的技术哪去做,有问题随时沟通。 3.定期给工作总结形成方法论。 4.学习新的技术,尝试用新的方法...

Avner
45分钟前
0
0
关于thinkphp 框架开启路径重写,无法获取Authorization Header

今天遇到在thinkphp框架中获取不到header头里边的 Authorization ,后来在.htaccess里面加多一项解决,记录下: <IfModule mod_rewrite.c> Options +FollowSymlinks -Multiviews Rewrite......

殘留回憶
49分钟前
0
0
centos 使用yum安装nginx后如何添加模块 10

centos 使用yum安装nginx后如何添加模块 10 centos6.2版本,使用yum来安装了nginx,但是最近需要重新添加模块,所以就傻了,询问下有人知道怎么重新添加模块吗? PS:俺是新手,需要高手救助...

linjin200
52分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部