• 2020-02-21

    分布式一致性协议-Raft和Paxos

    Views: 2171 | No Comments

    分布式一致性协议-以Paxos和Raft为例.001
    Continue reading »

    Posted by ideawu at 2020-02-21 16:45:39 Tags: ,
  • 2020-02-20

    Docker镜像常用操作

    Views: 2862 | 1 Comment

    Docker 导出镜像成 container:

    docker create --name container_name from_REPOSITORY_name
    docker export container_name -o abc.tar
    docker import abc.tar
    

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

    保存运行中的镜像:

    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 --user dev --workdir /home/dev d4
    

    重启容器

    docker start $container
    
    Posted by ideawu at 2020-02-20 20:06:05
  • 2020-02-13

    龟兔赛跑问题和Floyd环检测算法

    Views: 2603 | No Comments

    例如要检测如下的环, 找出 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
    
    Posted by ideawu at 2020-02-13 18:12:10
  • 2020-02-12

    动态规划算法的发现

    Views: 2682 | No Comments

    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. 缓存可淘汰: 滑动窗口

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

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

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

    Posted by ideawu at 2020-02-12 15:57:31
  • 2020-02-12

    LevelDB Seek() 特别慢的场景

    Views: 1726 | No Comments

    在某些场景, 特别是一次性删除大量的连续 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 的数据真正地从硬盘上删除.

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

    Posted by ideawu at 15:22:23
  • 2020-02-11

    Git 提示 fatal: HTTP request failed

    Views: 1591 | No Comments

    新机器莫名其妙 git 提示

    error:  while accessing https://github.com/ideawu/ssdb/info/refs
    
    fatal: HTTP request failed
    

    原来要升级 nss:

    sudo yum update nss
    
    Posted by ideawu at 2020-02-11 21:07:51
|<<<123456789>>>| 2/127 Pages, 759 Results.