• 2020-03-06

    不用 git rebase 合并 commit 历史

    Views: 3493 | No Comments

    不通过 git rebase 来合并 commit logs. 实在没弄明白 git rebase 为什么会要求我解决我从来没有修改过的文件冲突, 真是莫名其妙. 网上一大堆人深受其害. 大家 rebase 的目的非常简单, 就是要合并 commit logs. 在已经 merge from master 的情况下.

    通过新建一个临时本地分支, 然后将代码合并(其实就是拷贝过来), 这样新分支就只有一条 commit log 了, 然后回去你的分支, 把你的分支重置为临时分支, 然后提交到远程.

    为什么 git rebase 不能做这么简单的事?!

    git checkout -b tmp master
    git merge --squash my_feature
    git commit
    git checkout my_feature
    git reset --hard tmp
    git push -f
    git branch -D tmp
    

    据说, rebase 的原理是一个版本一个版本地 merge, 所以同一个文件你可能要解决一百次冲突, 而这个冲突是别人导致的别人已经解决过的, 然后你又重复解决别人引入和已经解决的冲突.

    好像 git rebase -i 然后把中间的版本(pick xxx)删除即可?

    git 这样解释:

    当您执行 git rebase 操作时,通常会移动提交。 因此,您可能会遇到引入合并冲突的情况。 这意味着您的两个提交修改了同一个文件中的同一行,而 Git 不知道要应用哪个更改。

    What the FUCK? 开什么玩笑? 我修改了同一行两次, 当然保留最新的修改! 谁神经病要保留旧的修改!

    Posted by ideawu at 2020-03-06 18:22:59
  • 2020-03-06

    Paxos 与分布式强一致性

    Views: 3813 | No Comments

    Paxos 有着"难以理解"的恶劣名声, 事实确实如此. 它用大段篇幅来做证明, 却对现实问题避而不谈. 例如最简单(常见)的问题: 怎么实现一致性读功能?

    因为 Paxos 太难以理解, 所以无数人用各自不同的角度去理解 Paxos, 而且实现上千差万别和漏洞百出. 我觉得这种现象和一句名言类似: 不幸的家庭各有各的不幸. 但是, 学习 Raft 的人都很开心, 而且大家在实现(implement) Raft 协议时, 代码基本是一样的. 正如名言所说: 幸福的家庭都是相似的.

    我也用我自己的角度去理解 Paxos, 我认为它最大的特点是不区别读和写. 简单说, Paxos 的读过程就是写操作, 就是在做数据同步.

    首先, 无论使用何种一致性协议, 都无法解决在任何时刻副本数据不一致的问题. 也就是说, 一定存在某个时间点, 多个副本不一致. 这是无法解决的. 要解决的是读一致性, 即从观察者(用户)的角度看, 数据是一致的. 写操作永远都是"最终一致"的.

    其次, Paxos "暗示"在读操作的时候进行数据同步, 以修复数据达到"最终一致性". 而工程上的常识是, 多个副本必须自动地最终一致, 而不依赖外界触发. 如果某个系统依赖 Paxos 的这种"暗示", 那么这个系统将是不可靠的, 也不是(最终)一致性的, 因为它没有时间概念, 只有操作序列概念.

    补充一点: Paxos 充满了各种工程上的错误暗示, 如果按它的暗示来, 你会犯各种错误. 例如, Paxos 暗示同步的是一个(唯一的一个) key 和对应的全量值, 工程上你不可能每一次都同步整个全量数据库, 对吧? 不要提 multi-paxos, 因为你会被它错误地暗示而独立地处理每一个 key, 然后你实现不了数据 Catch Up, 无法实现副本的最终一致性.

    对于读操作, Paxos 要求收到读请求的节点(Proposer)向其它节点发起数据同步操作, 也即所谓的 prepare-accept 两阶段. 在 prepare 的过程中, Proposer 收集其它节点的数据. Prepare 阶段除了同步数据, 还有一个作用是更新版本号(num), 之后就是 Proposer 将其所知的最新的数据同步到其它节点. 注意, 两阶段中间如果有失败, 不做回滚, 而是继续重试, 等最终成功, 或者放弃并告知用户.

    再次注意, Paxos 并不是按数据版本号来返回最新的数据, 这种想法是错误的. 也不是所谓的多数派读(Quorum Read). 仅仅 Quorum Read 并不能保证强一致性, 因为某个节点可能随时上下线, 导致一会是多数派一会是少数派, 这种结果不是一致性的. 提一句, 这是个经典误解. Paxos 对一致性的保证, 来源于其无法读写, 都必须达成新的共识.

    总结:

    1. Paxos 读即是写, 读即是数据同步.
    2. Paxos 既不依赖版本号返回最新的数据, 也不是所谓的多数派读.

    Posted by ideawu at 13:57:02 Tags: ,
  • 2020-02-21

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

    Views: 3930 | No Comments

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

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

    Docker镜像常用操作

    Views: 4622 | 1 Comment

    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
    
    Posted by ideawu at 2020-02-20 20:06:05
  • 2020-02-13

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

    Views: 3981 | 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: 3875 | 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
|<<<123456789>>>| 4/129 Pages, 773 Results.