文档章节

LevelDB的算分逻辑

强子1985
 强子1985
发布于 2017/07/23 11:07
字数 882
阅读 40
收藏 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;
	}

 

© 著作权归作者所有

共有 人打赏支持
强子1985

强子1985

粉丝 862
博文 932
码字总数 644385
作品 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
Derek解读Bytom源码-持久化存储LevelDB

作者:Derek 简介 Github地址:https://github.com/Bytom/bytom Gitee地址:https://gitee.com/BytomBlockchain/bytom 本章介绍Derek解读-Bytom源码分析-持久化存储LevelDB 作者使用MacOS操作...

比原链bytom
08/24
0
0
一个参考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

没有更多内容

加载失败,请刷新页面

加载更多

Delphi 常用API 函数(好多都没见过)

AdjustWindowRect 给定一种窗口样式,计算获得目标客户区矩形所需的窗口大小 AnyPopup 判断屏幕上是否存在任何弹出式窗口 ArrangeIconicWindows 排列一个父窗口的最小化子窗口 AttachThread...

dillonxiao
22分钟前
1
0
阿里云ubuntu配置Android开发环境编译Apk

1.命令行下载Android SDK $ wget https://dl.google.com/android/android-sdk_r24.4.1-linux.tgz $ tar zxvf android-sdk_r24.4.1-linux.tgz 2.列出可以现在的SDK ./android list sdk  -a 3......

SuShine
22分钟前
1
0
maven导出项目依赖的jar包

一、导出到默认目录 targed/dependency 从Maven项目中导出项目依赖的jar包:进入工程pom.xml 所在的目录下,执行如下命令: mvn dependency:copy-dependencies 二、导出到自定义目录中 在mav...

来来来来来
22分钟前
1
0
Win10下React Native环境安装教程及错误处理办法(实测)

https://blog.csdn.net/zhangatle/article/details/53289471 准备工作 注意:小米手机MIUI有坑,文末有解决方法 1 首先,你需要先安装Node.js并进行环境变量的配置,具体可以参考我的另一篇文...

james_laughing
23分钟前
1
0
IDEA2018 Mybatis plugin破解

IDEA2018 Mybatis plugin破解 Mybatis Plugin 一、Mybatis Plugin插件是什么 提供Mapper接口与配置文件中对应SQL的导航 编辑XML文件时自动补全 根据Mapper接口, 使用快捷键生成xml文件及SQL...

DemonsI
23分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部