idea's blog

Continue reading »

Docker 导出镜像:

docker export container_id -o abc.tar
docker import abc.tar rep:tag

image 只能用 import 导入, 不能用 load 导入. image 不包含 docker 的配置文件? 例如用哪个用户登录?

减少镜像体积

启动一个新的 container, 在 container 内删除数据, export(体积变大), 然后 import(体积变小).

保存运行中的 container:

docker commit $container_id repo_name
docker save repo_name_or_tag -o abc-i.tar
docker load -i abc-i.tar

tag 和 untag

docker tag $TAG $repo:$tag
docker rmi $image_id

用某个用户运行镜像, 登录后进入某个目录. 相当于用哪个用户登录虚拟机.

docker run -it -v ~/Works:/root/work -p 22:22 --workdir /root --hostname dev --name dev dev bash

重启容器

docker start $container

例如要检测如下的环, 找出 a 点到 b 点的距离 mu, 以及环的周长 lam.

                +----------------+
                |                | 
+---------------+----------------+
a    mu         b                c
                |       v        |

用快慢指针同时遍历. 首先可知, 如果环存在, 快慢指针会在 c 点相遇. c 到 b 点的距离是 v. 那么可知, 相遇时, 快慢指针走过的距离是:

慢: mu + m * lam + v
快: mu + n * lam + v

它们是两倍关系, 所以:

2 * (mu + m * lam + v) = mu + n * lam + v
2 * mu + 2 * v + 2 * m * lam = mu + n * lam + v
v = n*lam - 2*m*lam - mu

这时, 两个指针再以同样的速度前进. s 从 a 点出发, f 从 c 点出发. 可以知道, 当 s 走了 mu 距离后, 到达 b 点. 而 f 走了 mu 距离后, 也到达 b 点. 两者相遇.

n*lam - 2*m*lam - mu + mu = n*lam - 2*m*lam

1. 问题可分而治之且 BFS

首先, 问题必须是可分而治之的, 并在最后合并. 分而治之(递归)是为了穷举, 合并是为了找最优.

Result r(costs[], target){
	args = [];
	for(cost in costs){
		tmp = r(costs - cost, target - cost) + cost;
		args += tmp;
	}
	return G(args);
}

虽然上面的代码是 DFS, 但形式上是 BFS, 而且也应该写成 BFS, 只不过 BFS 的代码不简洁而已.

思考: 与贪婪算法的区别.

2. 合并函数 G(...) 可迭代处理

因为 G() 是可以转换成迭代的, 所以代码变成:

Result r(costs[], target){
	ret = PRE;
	for(cost in costs){
		tmp = r(costs - cost, target - cost) + cost;
		ret = G(ret, tmp);
	}
	return ret;
}

PRE(开始之前)是引入的边界外的参数, 以便让代码处理逻辑简化, 不然要加 if 条件判断, 就无法在形式化上统一.

3. 增加缓存

Result r(costs[], target, dp){
	cache_key = make_cache_key(costs, target);
	if(dp[cache_key]){
		return dp[cache_key];
	}
	ret = PRE;
	for(cost : costs){
		tmp = r(costs - cost, target - cost, dp) + cost;
		ret = G(ret, tmp);
	}
	dp[cache_key] = ret;
	return ret;
}

4. 将递归转成迭代

#### 推导型

Result forward(costs, target){
	init(dp);
	cc[PRE] = costs;
	for(curr in range(PRE, target)){
		costs = cc[curr];
		for(cost : costs){
			dp[next] = G(dp[next], dp[curr] + cost);
			cc[next] = costs - cost if dp[next] updated;
		}
	}
	return dp[target];
}

#### 回溯型

Result backtrack(costs[], target){
	dp[PRE] = PRE;
	cc[PRE] = costs;
	for(curr in range(atomic, target)){
		for(prev in get_prev_list(curr)){
			costs = cc[prev];
			cost = costs.link(prev, curr); 
			dp[curr] = G(dp[curr], dp[prev] + cost);
			cc[curr] = costs - cost if dp[curr] updated;
		}
	}
	return dp[target];
}

5. 缓存可淘汰: 滑动窗口

这一条件不是必须的, 因为很多动态规划解法无法淘汰缓存. 如果缓存可淘汰, 而且是可以用滑动窗口的方式淘汰, 那么就是非常**经典且巧妙的**动态规划解法.

对于推导型动态规划, 只需要缓存最长的推导距离. 对于回溯型动态规划, 只需要缓存最长的回溯距离.

这里举的例子是单节点推导, 下一节点只依赖单一的前序节点, 但有些问题需要依赖多个前序节点才能出方案, 例如斐波那契数列. 需要注意.

在某些场景, 特别是一次性删除大量的连续 key 的情况下, LevelDB 的 Seek() 操作将变得特别慢. 我在源码中打点, 简单分析了其出现的原因.

首先, LevelDB 对 Delete 操作处理, 是将被删除的 Key 做标记, 并在未来某个时间将真正的数据和这个标记从硬盘上删除. 在真正的删除之前, 标记本身也会排序(即 key-type)存储在 sst 文件中.

所以, 如果删除大量的连续 key, 那么这些 key 会聚集在一起, 存储在某个 sst 文件中. 当 Seek() 操作时, 会定位到这个 sst 文件头部, 然后开始扫描, 跳过所有标记, 直到找到非标记的 key. 显然, 跳过的 key 越多, 耗时就越长. 而一个 sst 可能存储几十万个 key 标记, 这样操作就是秒级别, 甚至是数秒级别! 而且 CPU 占用是 100%.

对应的源码在 db_iter.cc 中:

void DBIter::FindNextUserEntry(bool skipping, std::string* skip) {
    // Loop until we hit an acceptable entry to yield
    do {
        ParsedInternalKey ikey;
        if (ParseKey(&ikey) && ikey.sequence <= sequence_) {
            switch (ikey.type) {
                case kTypeDeletion:
                    // Arrange to skip all upcoming entries for this key since
                    // they are hidden by this deletion.
                    SaveKey(ikey.user_key, skip);
                    skipping = true;
                    break;
                case kTypeValue:
                    if (skipping &&
                            user_comparator_->Compare(ikey.user_key, *skip) <= 0) {
                        // Entry hidden
                    } else {
                        valid_ = true;
                        saved_key_.clear();
                        return;
                    }
                    break;
            }
        }
        iter_->Next();
    } while (iter_->Valid());
}

其中, case kTypeDeletion 分支就是跳过删除标记. 这个缺陷目前来看, 是无法解决的, 只能期待 compaction 把这些 obsoleted 的数据真正地从硬盘上删除.

另一种方案是重新设计数据结构, 把删除标记分开存储, 这样就可以快速的跳过, 而不用扫描遍历.

新机器莫名其妙 git 提示

error:  while accessing https://github.com/ideawu/ssdb/info/refs

fatal: HTTP request failed

原来要升级 nss:

sudo yum update nss