• 2021-05-28

    分布式系统升级所遇到的问题

    Views: 954 | No Comments

    常规的单机软件升级, 一般认为是一个原子操作, 也就是说, 软件会在"瞬间"完成升级, 即使不能在"瞬间"完成升级, 也要中断服务, 等升级完成后再提供服务.

    对于需要中断服务的情况, 在分布式系统中是不能接受的. 同时, 分布式系统的升级永远不可能在"瞬间"完成. 因此, 分布式系统升级会面临一个长时间的中间态, 新旧版本的软件同时运行, 这就涉及到兼容性问题.

    假如, 新版本的软件的数据格式改变了, 那么, 新版本写入的数据就无法被旧版本识别, 旧版本就会报错. 因为, 新版本的软件很容易做到向后兼容(新的兼容旧的), 但是, 向前兼容(旧的兼容新的)依赖预见性, 不可能预见全部未来.

    如果分布式系统无法做到向前兼容, 这时候, 应该怎么办呢? 难道要停服升级?

    一个常用的解决方案是在旧版本和新版本之间插入一个中间版本. 这个中间版本的主要特点是不写入新格式的数据, 但能识别新格式的数据.

    我们先逐步把旧版本替换为中间版本, 在这个过程中, 因为没有新格式的数据产生, 所以没有兼容问题. 等旧版本全部替换完毕后, 逐步升级为新版本, 在这个过程中, 虽然新旧格式的数据都有, 但新版本都能识别, 也没有兼容问题

    Posted by ideawu at 2021-05-28 21:09:45
  • 2021-04-17

    并发编程的核心技术 – 多版本(Multi Version)

    Views: 2384 | No Comments

    在单机编程时代, 每一项数据只有唯一的一份, 对数据的修改也是 in-place 的. 但是, 在并发编程领域, 包括分布式系统, 数据多版本(Multi Version, Versioning)是核心.

    我们先从单机编程的内存操作出发. 对于内存的操作, 都是原地(in-place)更新的. 对象和内存空间强绑定, 当更新对象时, 是将对象的内存空间擦除然后用新数据写覆盖. 到了多线程编程时代, 就引入了锁机制, 因为擦除和写操作过程不是原子性的, 可能擦除到一半时, 就被其它线程读取了, 因此要加锁.

    单机的硬盘操作, 基本也是借鉴内存操作, 也是对象和硬盘空间强绑定. 至少大部分程序员的思想是这样的, 这样比较直观. 跟内存操作一样, in-place 也遇到了操作的原子性挑战. 内存本来就是易失的(掉电后丢失), 但硬盘不一样, 数据需要持久化(掉电不丢失), 即使靠加锁解决了访问原子性问题, 但解决不了数据丢失问题. 所以, 硬盘操作是最先引入多版本技术的. 当需要修改某个对象时, 在另外的地方保存对象的新数据, 然后在另外的地方原子性地修改指向新数据的"指针". 事实上, 指针的修改也是多版本的, 不是 in-place 的, 后面会细说.
    Continue reading »

    Posted by ideawu at 2021-04-17 18:20:34
  • 2020-02-13

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

    Views: 5194 | 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: 4927 | 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-01-21

    算法题分类及解题思路

    Views: 3968 | No Comments

    * 暴力破解(brute force)

    暴力破解, 就是穷举. 穷举的方式一般用递归, O(n^2). 优化的思路是减少递归步骤:

    1. 更加严格的静态递归条件
    2. 增加 close_list, 动态地判断是否需要进行递归, close_list 根据执行情况动态变化

    另外的一种优化方向是消除递归. 因为递归是可以通过递归栈 open_list 来消除的. 可以对栈进行动态排序, 优先进行最可能成功的下一个步骤(A*). 这种排序优化, 导致可以使用不同的数据结构来存储递归栈: stack, queue, priority_queue.

    有序性, 有序子集: 有一种非常常用的优化思路是利用输入条件的局部有序性(存在有序的子集), 不再穷举这些有序的子集. 在处理这些有序子集时, 采用 O(n) 或者 O(K) 算法, 最差也能采用二分法 O(logN), 而且其它元素与这些有序子集结合时, 也不再需要穷举.

    A* 算法: open_list 根据沉没成本G和未来成本(H)之和来决定下一个处理步骤, 达成即最优.

    * 动态规划(dynamic programming)

    动态规划与暴力破解类似, 都是分而治之的思路, 但又不相同. 动态规划的下一个处理步骤是唯一的, 而且 open_list 初始可以确定, 后续单调递减. 下一个步骤的处理除了依赖自身的静态条件, 还依赖之前的处理结果集, 并维护这个结果集. 有点像消除了递归之后的暴力破解, 但暴力破解的 open_list 不是初始固定的.

    * 直观解法(coding)

    这类问题的解法非常直观, 一般没有算法上的优化空间, 也不需要技巧, 纯粹是为了训练编程能力. 考察做题者对变量的状态判断是否完备充分, 判断路径是否最简, if 分支是否可以合并等等. 所以, 就是考察边界条件的判断, 还有逻辑条件精减, 要求有非常强的逻辑思维能力.

    一般这类题就是链表翻转, 有序链表合并, 删除重复元素, 数组遍历(螺旋向内, 螺旋向外, 蛇形, 等等), partition 等.

    要点是: 边界判断, 分支合并, 简化重合边界的处理, 增加虚拟节点进行辅助.

    Posted by ideawu at 2020-01-21 09:38:57
  • 2020-01-21

    蛇形遍历数组

    Views: 6660 | No Comments

    蛇形遍历数组, 我的思路是使用两个点坐标再加上一个方向变量, 两个点同时在边缘上移动, 然后连线.

    但是, 其实这个问题本质就是从一点出发, 不断地 walk, 一次只 walk 一步, 需要保留方向状态. 如果一次 walk 完斜线, 则不用方向状态, 因为可以根据 walk 的起点来判断.

    Continue reading »

    Posted by ideawu at 01:43:19
|<<<12>>>| 1/2 Pages, 7 Results.