​ 递归是个很神奇的思想，与迭代不同的地方在于，迭代通过原来的变量推出新值，接着以新值为初始值继续递推，直到满足条件，而递归则是A循环调用本身。举个简单的例子，计算1到n的和：

​ 迭代实现：

1
2
3
4
5

def a(n):
    sum = 0
    for i in range(1, n + 1):
        sum += i
    return sum

​ 每次都以sum的新值为基础,以sum+=i这个式子递推，直到实现功能。

​ 递归实现：

1
2
3
4

def b(n):
    if n == 1:
        return 1
    return n + b(n - 1)

​ 重复调用n+b(n-1)操作，直到n==1结束。

​ 从上面的对比我们可以看出，要想写一个递归程序，需要关注两个部分，一个是程序的出口（如果没有会造成死循环），另一个则是调用的函数推导式，上述程序的推导式可写为：n+(n-1)+(n-2)+(n-3)+……+1。

​ 递归的思想比较简单，通俗易懂，难就难在怎么去应用。接下来我们举两个经典的例子。

• 计算n的阶乘：

  1 2 3 4 5

  def func(n): if n == 1 or n == 2: return 1 else: return func(n-1) + func(n-2)

  阶乘在各种算法题目解法的出现频率非常高，例如爬楼梯问题，兔子问题等。

• 汉诺塔问题

  这里简述一下。有三个立柱，其中一个立柱上按从下往上，从大到小的顺序依次叠放n个中空圆盘，现要求将圆盘转移到另一个立柱上，且顺序依旧为从下往上，从大到小。

  解决方案就是利用第三个立柱进行中转。以两个圆盘为例，先将小圆盘移到三柱，再将大圆盘移到二柱，然后将三柱的小盘移到二柱，转移完成。如果有n个盘该怎么办呢？其实还是上述的操作，直接上代码：

  1 2 3 4 5 6 7 8 9 10

  def move(n,a,b,c): #a是起始柱，b是辅助柱，c是目标柱 if n == 1: print(a,'->',c) else: # 将n-1个盘子从a --> b move(n-1,a,c,b) # 将剩余的最后一个盘子从a --> c print(a,'->',c) # 将剩余的n-1个盘子从 b --> c move(n-1,b,a,c)

​ 要想实现递归，最关键的地方就在于找到出口条件和可重复的操作式，需要大量的练习。

​ 在体量较大的网络中，线路往往错综复杂，物理上存在大量环路，会引发大量问题，STP协议便是在二层进行逻辑上防环。

​ 生成树协议（STP）中，交换设备被称之为桥，优先级最高的被选为根桥，根据拓扑计算实现逻辑上阻塞冗余链路，消除环路，同时这样也有个好处，当某条活跃链路发生故障时，可以激活冗余链路，恢复网络连通性，具有一定的HA。

BPDU

​ 生成树协议所用的信息段，被封装在以太网数据帧中，根据场景可分为配置BPDU与TCN BPDU。

​ 配置BPDU用于生成树计算和维护拓扑，后文提到的BPDU除非特殊说明皆为配置BPDU，其中包含主要包含这些信息：

• Root Identifier：当前根桥的BID

• Root Path Cost：根路径开销。一个端口变量，表示到达根桥的开销，计算方式为去往根桥所经过端口路径开销的总和。

• Bridge Identifier：本设备的BID。

• Port Identifier：发送该BPDU的端口ID。PID由两部分组成，端口优先级与端口号。

  ​ 端口优先级占4位，步长为16，范围是0~240，默认值为128。

• Message age：BPDU的传播周期。

• Max age：BPDU最大生存周期，默认为20秒，当Message age大于Max age时，BPDU将被丢弃。

• Hello time：发送BPDU的间隔时间，默认值为2秒，当拓扑稳定后，根桥负责发送此信息，如需更改此值，必须在根桥上修改才有效。

• Forward Delay time：设备状态迁移时间，默认为15秒。

​ TCN BPDU是用于下游拓扑变化时向上游发送通知（TC置为1），根节点收到后回复（TCA置为1）并广播（TC置为1的BPDU），直到所有交换设备知晓拓扑变化。

端口角色

​ STP中的端口角色有种：

• 根端口：去往根端口路径开销最小的端口。
• 指定端口：转发信息的端口，包含根端口。
• 阻塞端口：未被选举为根端口或指定端口的端口，不转发，只接收BPDU。

端口状态

​ STP的端口状态：

• Disabled：端口状态为Down，不处理BPDU报文，也不转发用户流量。
• Listening：过渡状态，进行生成树计算，端口开始接收BPDU，但不转发用户流量。
• Learning：过渡状态，建立无环的MAC地址转发表，不转发用户流量，防止环路。
• Forwarding：端口可以接收和发送BPDU，也可以转发用户流量。
• Blocking：阻塞状态，此状态下不转发用户流量，只接收处理BPDU。

拓扑计算

​ 根桥选举：

​ 网络中所有交换机启动时都认为自己是根桥，所有端口皆为指定端口，交互信息，比较BID（数值越小优先级越高），如果相同则比较MAC地址，越小越优先。

​ 根端口选举：

​ 先比较开销值，选最小的。如果两个及以上链路连接同一台交换机。选择PID最小的端口。

​ 指定端口选举：

​ 先比较累计路径开销，最小的为指定端口，如果相同比较BID，依然相同则比较PID。

​ 选举过程：

1. 选举一个根桥；
2. 每个非根交换机选举一个根端口；
3. 每个网段选举一个指定端口；
4. 阻塞预备端口（非根、非指定端口；
5. 收敛完成后，根桥每隔一个hello time发送BPDU，非根桥进行中继。

​ 本文将着重介绍直接插入排序，直接选择排序，冒泡排序，归并排序与快排排序，以下实现皆为升序。

直接插入排序

​ 特点：稳定，时间复杂度：O(n^2)。

1
2
3
4
5
6

def insertion_sort(a):
    for i in range(1, len(a)):
        while a[i] < a[i-1]:
            a[i], a[i - 1] = a[i - 1], a[i]
            i -= 1
    return a

​ 排序过程：第一个数一定有序，从第二个值开始，将第二个值放入一个temp中，与第一个进行比较，大于放到第一个后面，不大于则将第一位向后移，将第二个数插入到第一位，此时前两个数已经排列好，第三位重复上述过程，在前部已排好的序列中找到位置并插入，原来插入位置极之后的值向后移。继续执行上述过程，直至排序完毕。

​ 上述程序经过优化，将需要进行排序的数直接与前一位值比较，小于则换位置，然后继续向前比较，换位，直到本轮排序完毕，将向后移与插入的过程转换为比较换位。

直接选择排序

​ 特点：不稳定，时间复杂度：O(n^2)。

1
2
3
4
5
6
7

def selection_sort(a):
    for i in range(len(a) - 1):
        m = i
        for j in range(i + 1, len(a)):
            if a[m] > a[i]:
                a[m], a[i] = a[i], a[m]
    return a

​ 排序过程：从第一位开始，与之后位的值进行比较，直到找出最小值，放到第一位，然后从第二位开始比较，直到找出第二小的数放到第二位，重复上述过程，直到排序完成。

冒泡排序

​ 特点：稳定，平均时间复杂度：O(n^2)。

1
2
3
4
5
6

def bubble_sort(a):
    for i in range(len(a) - 1):
        for j in range(len(a) - 1 - i):
            if a[j] > a[j + 1]:
                a[j], a[j + 1] = a[j + 1], a[j]
    return a

​ 排序过程：从第一个数开始，如果第一个数大于第二个，两者换位，继续向后比较，如果不大于则不换位，用第二位向后一位比较，重复上述比较过程。

​ 上述程序经过优化，已排好顺序的部分将不参与比较。

归并排序

​ 特点：稳定，时间复杂度O(nlog2n)

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

def merge_sort(a):
    if len(a) > 1:
        mid = len(a) // 2
        left = merge(a[:mid])
        right = merge(a[mid:])
        i = 0
        j = 0
        k = 0
        l = len(left)
        r = len(right)
        while i < l and j < r:
            if left[i] < right[j]:
                a[k] = left[i]
                i += 1
                k += 1
            else:
                a[k] = right[i]
                j += 1
                k += 1
    return a

​ 排序过程：采取分治法，将每组都排好序，

快排

​ 特点：不稳定，时间复杂度：O(nlog2n)

1
2
3
4
5
6
7

def quick_sort(a):
    if len(a) <= 1:
        return a
    p = a[0]
    g = [e for e in a[1:] if e > p]
    lq = [e for e in a[1:] if e <= p]
    return quick(lq) + [p] + quick(g)

​ 排序过程：选择一个基值（一般为第一个数），将其放在中间位置，定义两个游标，从左边寻找比基值大的数，从右边找比基值小的数，左右两个游标的值交换，执行此操作直至两个指针相遇。一轮结束后，对基数左右两边的数组继续执行上述操作，直到排序完毕。

​ 快排的每一轮的操作本质上来说就是将大的数放到基值右边，小的数放到基值左边，上述的代码就是通过递归来实现上述思想。

总结

​ Kubernentes起源于谷歌内部的Borg，是现在最流行的容器编排工具，被誉为云时代的操作系统，至于其多牛，无需再赘述，为方便叙述，接下来皆以K8S称呼。我们首先鸟瞰一下K8S的基本组件结构。

核心组件

• etcd：保存了整个集群的状态；
• controller manager：负责管理控制器；
• controller：控制器，负责控制其对应的资源；
• Container runtime：负责镜像管理以及Pod和容器的运行（CRI）；
• kube-proxy：负责为service提供Cluster内部的服务发现与负载均衡；
• scheduler：负责资源的调度，按照预定的策略将Pod调度到合适的设备上；
• Kubelet：负责维护容器的生命周期，并负责Volume（CVI）和网络（CNI）的管理；
• apisever：提供了资源操作的唯一入口，提供了认证、访问控制，API注册与发现等机制。

部署安装

​ 可以选择安装经过简化单机即可运行的minikube，也可以选择完整安装，本文将采用一master与两Node的二进制部署方式。

1. 载入BIOS的硬件信息与自我检测，找到第一个可开机设备；

2. 读取并执行第一个开机设备中MBR的boot Loader；

   ​ 执行Boot loader主程序

   ​ 主程序载入配置文件（包括文件系统定义与主要配置文件grub.cfg）

3. 根据boot loader载入Kernel，kernel会开始侦测硬件并载入驱动；

   在这一步Kernel（核心文件为/boot/vmlinuz）接管开机流程，以自己的功能重新侦测一边硬件，不一定使用BIOS侦测到的。之后挂载虚拟文件系统（/boot/initramfs），加载开机过程中所需的重要模块。

4. 硬件驱动成功后，kennel主动调用systemd程序，并以default.target启动。

   systemd负责准备软件执行的环境，包含系统的主机名称，网络设置，语系处理、文件系统格式等。default.target位于/etc/systemd/system/，其中包含启动的目标态（对应老版本的runlevel）与默认启动服务单元集合。

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

   cat /etc/systemd/system/default.target # This file is part of systemd. # # systemd is free software; you can redistribute it and/or modify it # under the terms of the GNU Lesser General Public License as published by # the Free Software Foundation; either version 2.1 of the License, or # (at your option) any later version. [Unit] Description=Multi-User System Documentation=man:systemd.special(7) Requires=basic.target Conflicts=rescue.service rescue.target After=basic.target rescue.service rescue.target AllowIsolate=yes

   可以使用systemctl list-dependencies查看服务启动的服务，实验机结果如下：

   1 2 3 4 5 6 7

   systemctl list-dependencies default.target ● ├─auditd.service ● ├─chronyd.service ● ├─crond.service ● ├─dbus.service ...

5. 执行sysinit.target，初始化系统，加载基本的核心驱动，文件系统和驱动等。

6. 执行basic.target加载更多功能，执行完之后，系统就已经启动完毕。

7. 执行mutli-user.target载入用户服务，如果目标态为图形界面，则继续加载graphical.target。

​ TCP/IP功能较为简单，缺少了很多功能，ICMP协议便是其中的一块补充，为IP增添了通知差错信息与控制信息的功能。

报头

常见类型与编码

​ 这只是ICMP类型与编码的一部分，具体可以看RFC792，以及其它相关ICMP拓展。

具体应用

• ping

  ping命令是ICMP应用的典型代表之一，运用type8进行请求，如果目的地可到达则回复type0，否则根据情况返回对应类型编码。

• tracert（windows)/ traceroute（Linux）

  用于判断转发路径的命令，它的原理是先向目的端发送一个UDP测试报文，TTL值为1，目的端口为一个极其不常用的端口，沿途节点收到后拆包判断自己是不是目的地，不是的话TTL-1=0，向源端返回ICMP超时报文，报文中含有本机IP。源端收到后，再向目的端发送以个UDP报文，这次的TTL值+1=2。重复上述过程，每次TTL值+1，直到到达目的地后停止。

路由重定向

​ 不同的系统对于路由重定向报文有着不同的处理方案，绝大多数往往会直接忽略ICMP重定向报文。因为如果支持重定向，设备将需要维护一个非常庞大的路由表，会极其浪费服务器的性能，而且ICMP重定向存在着安全隐患。

​ 当遇到对临界资源进行并发访问的时候，一方面要最大化的性能，另一方面还要保障数据的一致性，而锁机制可以很好的达成这样的效果。本文主要介绍InnoDB中的锁。

​ InnoDB中锁按照粒度来分可分为行级锁与表级锁。行级锁通过索引上的索引项实现，其中包含共享锁与排他锁：

• 共享锁（S）：允许事务读一行数据。

• 排他锁（X）：允许事务delete或update一行数据

  S与S兼容，其它情况都不兼容。在使用索引进行检索时，InnoDB会加上S锁，这一点可能会引起大量的锁冲突，需要注意。

​ 表级锁包含意向共享锁和意向排他锁：

• 意向共享锁（IS）：事务想要获得一个表中某几行的共享锁。

• 意向排他锁（IX）：事务想要获得一个表中某几行的排他锁。

  意向锁不会阻塞除全表扫描外的请求。

​ 可以通过三张表查询现在事务与锁的状态：

• INNODB_TRX：现在正在执行的事务的情况。

• INNODB_LOCKS：现在锁的情况。

• INNODB_LOCK_WAITS：现在被阻塞的事务与锁情况。

  如果在锁不兼容的情况下需要读取行的数据，就需要使事务读取行的一个快照数据。原理是通过Undo段回滚数据。一行可能有多个版本的快照数据，此时就需要多版本并发控制技术（MVCC）。在read committed的书屋隔离条件下，InnoDB使用非锁定的一致性读，总是读取被锁定行的最新一份快照数据，而在Repeatable的事务隔离级别下，InnoDB则是读取事务开始前的快照数据版本。

​ 在InnoDB中行锁的算法有3种，分别是：

• Record Lock：单个行记录上的锁；

• Gap Lock：间隙锁，锁定除记录本身的范围；

• Next-Key Lock：锁定一个范围并锁定记录本身，是默认的算法。

​ 当然锁虽然可以提高并发，满足事务的隔离性需求，但锁也带来了问题。

• 丢失更新：事务的更新操作丢失。这是件非常严重的问题，尤其是在金融领域。想在数据库层面解决这个问题，就需要将操作串行化，按次序执行。

• 脏读：读到了未提交的数据，违反了隔离性。解决方案是将事务隔离级别提升到read uncommit。

• 不可重复读：一个事务多次读取同一数据期间数据被其他事务修改，导致两次读取的数据不一样。解决方案是将事务隔离级别提升到Read Repeatable。

• 死锁：A等待B，B等待A。解决方案是进行回滚操作，往往InnoDB会解决大多数的死锁。

​ 算法与数据结构是程序员的内功之一，要想写出高质量高性能代码，优秀的算法基础是不可或缺的。这个系列将以python实现，探讨一些常用的算法与数据结构。

​ 首先何为算法，将解决问题的方法共性进行的高度抽象，从思想的层面而言，便是道。数据结构则是在数组或链表的基础上附加特定的属性方法以获得性能的提升与所占空间的优化。为了量化程序的执行效率与存储空间的额外使用情况，引入了时间复杂度与空间复杂度。

​ 时间复杂度是对代码执行效率的量化指标，即程序的执行次数，当程序的执行次数会由于某个变量变化时，我们以以变化函数来表示其复杂度。

​ 我们输出一个正整数n：

1

print(n)

​ 此程序的只需一次执行便可完成操作，我们可将其时间复杂度记为O(1)。

​ 我们再来写一个简单的for循环输出1~n(正整数)：

1
2

for i in range(1,n+1):
    print(i)

​ 这个程序得运行次数取决于n值的大小不断变化，但始终为常数次，其时间复杂度我们便可记为O(n)。

​ 怎么样，是不是很简单？我们再来一题，输出n*n的矩阵：

1
2
3
4

for i in range(n):
    print("\n")
    for j in range(n):
        print("*", end=" ")

​ 这个程序的执行次数为ij，由于i与j相等于n，执行次数为n\n，复杂度便可记为O(n^2^)。

​ 以上的程序由于都没有额外开辟空间，所以空间复杂度皆为0。接下来我们举个简单的例子看下利用到额外空间的情况，换位:

1
2
3

z=x
x=y
y=z

​ 此时我们运用到一个额外的空间，那么空间复杂度记为O(1)。

​ 有没有感到复杂度的计算十分简单？当然，这才刚刚开始，之后会根据具体题目，逐渐深入。以下是常见复杂度的大小效率排序。

​ O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n)

​ 学习算法与数据结构是一件不是很愉快的事，那我们什么时候可以不用学算法与数据结构呢？现代科技的进步让设备的性能快速提升， 但至少就现在而言，性能依然是远远不够的，在实现相同结果的情况下，经过优化的代码在效率与存储空间的利用上往往强于未经优化的代码，如之后会提到的排序算法。我想等到设备的性能强悍到可以忽略代码上的优化提升（量子计算机），存储的成本变得极其低廉吧，希望有生之年可以实现。

​ 腾讯的业务运维面试一直显示初始状态，应该是挂了。吃一堑长一智，这篇将对这次面试进行一个完整的复盘，保证错误不犯第二次。

1. 自我介绍

   自我介绍的时候有些紧张，说得结结巴巴，没有啥逻辑性，这是个很大的问题，自我介绍这里需要精心地准备下。

2. 聊下项目

   用4台阿里云ECS虚拟机，其中一台由于和其他三台不在一个区域，在其上搭建测试环境与Showdoc文档中心。另外三台做了内网互通，一台配置了nginx作为负载均衡调度器，另外两台提供服务。数据库是mysql，做了主从。缓存用redis，也做了主从，监控选择使用Netdata。

3. mysql的主从的原理

   从节点开了两个线程，I/O线程与SQL线程。I/O线程负责从Master节点读取Bin log到Relay log，Sql线程负责执行。

4. 了解过主主嘛，具体配置过程。

   主主就是互为主从，具体配置过程没有答上来，现在复盘来看，其实很简单，互为主从，不就是角色互换再配置一次主从，这个问题没答出来真是怪自己太菜。

5. 你是进行过压测嘛，有哪些指标。

   这个问题肯定是看到项目才问出来的。我事先没有准备，回答是用低轨道离子炮进行压测，看看能顶住多少流量。指标我只回答了三个，页面的响应时间，吞吐量，qps，回答的不行。

6. 有没有尝试过用docker进行部署，怎样更安全地docker部署。

   我的回答是尝试过，至于更安全的部署我直接说了kata。现在来看应该这样回答，docker是直接在内核上隔离资源进行容器的创建，黑客可以直接通过容器攻击到内核，有安全隐患，所以可以先创建KVM，在KVM中使用容器，这样即使容器收到攻击，也很难对宿主机造成危害。但这个方案的资源消耗较高，所以可以使用更加轻量化的VM与容器技术的结合方案，OpenStack基金会的kata，在VM层上创建容器，资源消耗更少。

7. TCP4次挥手

   这个是基础，没啥好说的。

8. 红黑树

   这个在面试的时候有些紧张，答得很烂。

9. 堆栈

   堆在数据结构上的实现一般为二叉堆，斐波那契堆等，按照排列顺序分为最大堆，最小堆。栈的特点为元素后进先出。

10. 模拟退火算法

    没听说过，直接去世。

​ 以上是本次面试比较有价值的问题，总体来说答得非常不好，表述不严谨，缺乏逻辑性。下次面试一定不能犯这些低级的错误。

​ 常见的Mysql高可用策略，Master配上Slave（可多个），Slave与Master的数据进行同步，当Master宕机时可以顶上去。

原理：

​ 从节点开两个线程，I/O线程负责读取主节点中的二进制日志到本机的relay日志，SQL线程负责数据重放。

​ 有很多主从复制的方法，SBR（基于SQL语句复制）、RBR（基于行复制）、MBR（混合模式（默认使用SBR））以及现在Mysql版本的GITDs（基于事务复制）。

• SBR优势在于记录了所有语句，日志较小且方便日后审计。但弊端也较多，有些语句无法被正确地复制，有些语句会执行大量的行级锁。

• RBR则是记录了数据变化，是较为安全的复制方式，并且有更少的行级锁，但相对而言日志较大，不能直接进行审计。

• GITDs的优势在于完全基于事务，大大简化了复制过程。

配置：

1.首先准备两台安装好Mysql的server，安装教程请看使用RPM安装安装Mysql。

主节点：

2.配置主节点my.cnf

1
2
3
4
5

[mysqld]

log-bin=mysql-bin	#开启二进制日志

server-id=1		    #配置服务器ID

3.创建用户

​ 从服务器需要账户来连接主服务器，一从一账号或者多从一账号

1

mysql > grant replication slave on *.* to 'share'@'10.1.1.%' identified by '1234';

​ 如果出现以下报错：

1

ERROR 1819 (HY000): Your password does not satisfy the current policy requirements

​ 报错内容：您设置的密码不满足当前要求。请执行以下命令调整数据库的密码级别：

1
2

mysql> set global validate_password_length=4; --设置密码的长度为4
mysql> set global validate_password_policy=0; --将策略级别设为0

从节点：

1.配置my.cnf

1
2
3

[mysqld]

server-id=2

2.配置同步参数

1
2
3

mysql> change master to
    -> MASTER_HOST='10.1.1.133',
    -> MASTER_USER='share';

3.执行show slave status\G;

1
2

Slave_IO_Running: connecting
Slave_SQL_Running: No

双主

​ master与slave可以做读写分离，增强读的性能，但如果从节点进行写入操作会使数据不一致，这就诞生了双主，两台mysql server互为主从，皆可读写。

​ 配置方案与上面相似，但需要两步：

1. 执行show master status;命令查看bin日志。
2. 在change master to 配置时需要加上MASTER_LOG_FILE=‘bin日志的名字’。