距离上次写博文还是2020的年度总结，转岗之后比较忙，一直没有时间和精力产出内容。最近换到了新的部门，临近新年，分享最近看过的两篇比较有意思的博文。

单元化

浅谈双十一背后的蚂蚁 LDC 架构和其 CAP 分析

最近在准备组内的分享，关于容灾相关的话题，包括数据中心容灾架构&业务降级方案设计等等。偶然在内网看到了架构同学关于单元化的分享，是个之前未接触过的知识点，看了几遍没能理解透彻，知道单元化最初的时间是来源于阿里，在网上搜索了下发现了这篇文章，读了一遍发现很多解释都非常形象，十分推荐阅读，下面是一些摘抄的笔记

• 因为数据库存储层瓶颈的存在再多水平扩展的服务器都无法绕开，而从整个互联网的视角看，全世界电商的交易 TPS 可以轻松上亿。这个例子带给我们一些思考：为啥几家互联网公司的 TPS 之和可以那么大，服务的用户数规模也极为吓人，而单个互联网公司的 TPS 却很难提升？究其本质，每家互联网公司都是一个独立的大型单元，他们各自服务自己的用户互不干扰。这就是单元化的基本特性，任何一家互联网公司，其想要成倍的扩大自己系统的服务能力，都必然会走向单元化之路

• 分库分表不仅可以对相同的库进行拆分，还可以对相同的表进行拆分，对表进行拆分的方式叫做水平拆分。不同功能的表放到不同的库里，一般对应的是垂直拆分（按照业务功能进行拆分），此时一般还对应了微服务化。这种方法做到极致基本能支撑 TPS 在万级甚至更高的访问量了。然而随着相同应用扩展的越多，每个数据库的链接数也巨量增长，这让数据库本身的资源成为了瓶颈。这个问题产生的本质是全量数据无差别的分享了所有的应用资源，比如 A 用户的请求在负载均衡的分配下可能分配到任意一个应用服务器上，因而所有应用全部都要连接 A 用户所在的分库，数据库连接数就变成笛卡尔乘积了。在本质点说，这种模式的资源隔离性还不够彻底。要解决这个问题，就需要把识别用户分库的逻辑往上层移动，从数据库层移动到路由网关层。这样一来，从应用服务器 a 进来的来自 A 客户的所有请求必然落库到 DB-A，因此 a 也不用链接其他的数据库实例了，这样一个单元化的雏形就诞生了。

• 比如实时风控系统，如果多地部署，某个 RZone 直接读取本地的话，很容易读取到旧的风控状态，这是很危险的。这时蚂蚁架构师们问了自己一个问题——难道所有数据受不了延时么？这个问题像是打开了新世界的大门，通过对 RZone 已有业务的分析，架构师们发现 80% 甚至更高的场景下，数据更新后都不要求立马被读取到。也就是上文提到的”写读时间差现象”，那么这就好办了，对于这类数据，我们允许每个地区的 RZone 服务直接访问本地，为了给这些 RZone 提供这些数据的本地访问能力，蚂蚁架构师设计出了 CZone。在 CZone 的场景下，写请求一般从 GZone 写入公共数据所在库，然后同步到整个 OB 集群，然后由 CZone 提供读取服务。比如支付宝的会员服务就是如此。

数学与编程

康托尔、哥德尔、图灵——永恒的金色对角线 by 刘未鹏

源于V2EX上一篇提问帖下的回复，看到标题比较好奇就添加到了阅读清单，趁着年前不那么忙在公司细细读了下。什么是对角线方法？哥德尔的不完备性定理，图灵的停机问题，lambda算子理论和神奇的Y combinator…… 作者是个搞计算机的但是文笔很好，内容层层递进，剖析问题也很准确，读起来有一种感觉：一个很难的数学问题不知不觉的就讲述完了，数学之美也仿佛不那么难理解了。下面是摘抄的一段内容

• 性质倒是找出来了，怎么构造出这个Y却又成了难题。一个办法就是使用抽象法，这是从工程学的思想的角度，也就是通过不断迭代、重构，最终找到问题的解。然而对于这里的Y combinator，接近问题解的过程却显得复杂而费力，甚至过程中的有些点上的思维跳跃有点如羚羊挂角无迹可寻。然而，在这整个Y combinator介绍完了之后我们将会介绍著名的哥德尔不完备性定理，然后我们就会发现，通过哥德尔不完备性定理证明中的一个核心构造式，只需一步自然的推导就能得出我们的Y combinator。而且，最美妙的是，还可以再往下归约，把一切都归约到康托尔当初提出的对角线方法，到那时我们就会发现原来同样如羚羊挂角般的哥德尔的证明其实是对角线方法的一个自然推论。数学竟是如此奇妙，我们由简单得无法再简单的lambda calculus系统的两条公理居然能够导出如此复杂如此令人目眩神迷的Y Combinator，而这些复杂性其实也只是荡漾在定理海洋中的涟漪，拨开复杂性的迷雾我们重又发现它们居然寓于极度的简洁之中。这就是数学之美。

费马小定理

\[ a^p \bmod p = a \] 其中p为素数

欧拉函数

\(\varphi(n)\)代表小于等于n的所有与n互质的正整数。 \[ \varphi(pq) = \varphi(p)*\varphi(q) = (p-1)*(q-1) \] 其中pq为素数。 更通用的求解： \[ \varphi(n) = n\displaystyle\prod_{p|n}(1-\frac{1}{p}) \]

What Is The Problem

初始化git，创建master分支 1. master分支： commit init"

1

master:  ---init---

1
2

master:  ---init---
feature: ---init---feat 2---feat 3---

1
2

master:  ---init---feat 2---feat 3---
feature: ---init---feat 2---feat 3---

Memory Model

引自wiki: > In computing, a memory model describes the interactions of threads through memory and their shared use of the data.

如上所述，Memory Model是定义多个线程之间穿过内存交互影响（或者叫”干扰“），以及多个线程如何共享的使用数据。 首先，这是一个多线程的概念，具体来说，比如编译器在编译的时候做的一些编译优化，可能会导致程序的编写顺序和执行顺序不一致，在单线程模型下，这种优化对于程序的最后执行结果是没有任何影响的；但是在多线程模型下就可能会导致一些问题。

总结

假期针对性的学习了一下Golang和MySQL相关的知识，其中主要Golang，跟着网上的一个系列教程7days-golang在学习，，三个用Golang实现的框架：

• gee-web：HTTP框架
• gee-cache：分布式缓存
• gee-orm：orm库

教程通俗易懂，并且对新手非常友好，强烈建议跟着学习一遍，学习到了很多以前不清楚或者理解很模糊的知识，受益颇深，写一篇博客总结和梳理一下学习到的知识点，加深理解。

前言

本周一共刷了6道medium，重点是学习了后面两道比较巧妙的解题思路，以及一些老问题的新题型，总体来说比较简单。

Unique Paths II

1
2
3
4
5
6
7
8
9
10
11
12

给定一个带障碍的mxn的方格和一个初始位置在方格左上角的机器人，机器人每次可以从当前位置往右或者下方移动，遇到障碍会停止移动，问一共有多少走法能让机器人走到方格的右下角？其中1代表是障碍，0代表无障碍

输入:
[
  [0,0,0],
  [0,1,0],
  [0,0,0]
]
输出: 2
解释:
1. Right -> Right -> Down -> Down
2. Down -> Down -> Right -> Right

总结

本周一共刷了5道medium，巩固了一下背包算法，以及了解了一下Minimax算法的含义和使用场景。

Ones And Zeros

1
2
3
4
5

给一个字符串数组strs，其中的字符串只包含'0'或者'1'，输入m和n分别代表可以使用的0和1的个数，问这m个0和n个1，最多能从数组里取出多少个字符串来组成？

比如输入：strs = ["10","0001","111001","1","0"], m = 5, n = 3
输出： 4
解释: 用5个0和3个1最多可以取出"10","0001","1","0"四个字符串

分析

0x00 总结

• 本周一共刷了三道题，medium
• 两道常规dp题，一道背包问题，会重点介绍一下这道背包问题

0x01 Combination Sum IV

1

给定一个无重复数字的正整数数组和一个target，尝试从数组中取和为target的数字，问共有多少种数字的组合？

1
2
3
4
5
6
7
8
9
10
11

比如nums = [1, 2, 3]，target = 4
所有可能的组合有7种:
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)

注意不同数字顺序算不同的组合，比如(1, 1, 2)和(1, 2, 1)是两种

0x00 本周刷题总结

• 一共刷了11道题，主要还是DP专题，有一些题比如买股票的题目类似，为了理解题意和其中的差距，把之前的题也一起做了
• 收获：理解DP的常见套路
• 这周的部分分析不会这么细，比较浪费时间，相同题型或者某些优化点不再赘述。

0x01 Ugly Number and Ugly Number II

Ugly Number

1

检查输入的正整数num是否是Ugly数，Ugly数的定义是一个质因子只有2、3、5的正整数。

分析与求解

难度是Easy，分析一下可以得出解题思路：不断的尝试用2、3、5整除数字num，知道2、3、5都无法被整除或者num被除到1，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

func isUgly(num int) bool {
    if num <= 0 {
        return false
    } 
    for ; num>1;  {
        if num%5 == 0 {
            num /= 5
        } else if num%3 == 0 {
            num /= 3
        } else if num%2 == 0 {
            num /= 2
        } else {
            return false
        }
    }
    return true
}

0x00

本周刷题总结： * 本周刷题集中在动态规划专题，语言是Golang * 一共刷了八道题，全部是medium * 收获：了解基础的动态规划题型，掌握了基本的解题套路和优化方式

0x01

下面就针对每一道题大概写一下解题思路，权当复习和巩固知识。 ## Unique Paths 给一个m*n的矩阵，计算从左上角走到右下角共有多少种走法，每一步只能向右或者向下走。

思路分析

• 状态方程： 对于走到矩阵第i,j点来说，有两种走法，从i-1,j或者从i,j-1，因此设f(i,j)为走到点i,j的走法，则：f(i,j) = f(i-1, j) + f(i, j-1)
• 求解：用一个m*n的dp数组存储走到点i,j的走法，遍历求解dp[i][j] = dp[i-1][j] + dp[i][j-1]，时间复杂度和空间复杂度为O(mn)。dp初始化全部为1，然后i,j从1开始遍历，因为第一列和第一行的每个点都只有一种走法