一、网络的性能指标

• 带宽：表示链路的最大传输速率，单位通常为 b/s（比特/秒）
• 吞吐量：表示单位时间内成功传输的数据量，单位通常为 b/s（比特/秒）或者 B/s（字节/秒）。吞吐量受带宽限制，而吞吐量/带宽，就是该网络的使用率
• 延时：表示从网络请求发出后，一直到收到远端响应，所需要的时间延迟。在不同场景中，这一指标可能会有不同含义。比如，他可以表示，建立连接需要的时间（比如 TCP 握手延时），或一个数据包往返所需的时间（比如 RTT）
• PPS：（Packet Per Second（包/秒）），表示以网络包为单位的传输速率。PPS 通常用来评估网络的转发能力，比如硬件交换机，通常可以达到线性转发（即 PPS 可以达到或者接近理论最大值）。而基于 Linux 服务器的转发，则容易受网络包大小的影响

系统启动

1
2
3
4

1. BIOS(主板的操作系统)，自检。根据设置的启动引导硬盘找到BootLoader。
2. BootLoader 引导器，linux 的 BootLoader 就是GRUB(现版本为2)。之前是 LILO
3. kernel 内核 
4. systemd(init) 初始化环境

1
2
3

MBR  446
DPT  64
MN   2  填充 55 aa 

评估系统的网络性能

对于各协议层的性能进行测试

一、转发性能

网络接口层和网络层，他们主要负责网络包的封装、寻址、路由以及发送和接收。在这两个网络协议层中，每秒可处理的网络包数 PPS，就是最重要的性能指标。特别是 64B 小包的处理能力。

测试网络包的处理能力，使用 pktgen 。详情：https://time.geekbang.org/column/article/81497

二、TCP/UDP 性能

使用 iperf 。详情：https://time.geekbang.org/column/article/81497

三、HTTP性能

ab 是 Apache 自带的 HTTP 压测工具，主要测试 HTTP 服务的每秒请求数、请求延迟、吞吐量以及请求延迟的分布情况等

用户在线波峰计算

题目：

输入： 用户日志(time, user_id, login | logout)
输出：同时在线人数的峰值，精确到秒

峰值会出现于在线人数最多的时候，那么某个时间点在线的人数就是：所有在这个时间点之前登入的 -（减去）在这个时间点之前所有登出的

实现：

二叉树专题–输出根节点到所有叶子节点的路径：https://blog.csdn.net/SHENMEGUI_32/article/details/77661785

求二叉树的一条最长路径并且打印，如果有多条，输出其中一条。利用二叉树的套路来做。树形 DP 问题，想要从子树要什么信息？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

// 求二叉树的最长直径并且打印
struct ReturnValuePath {
    int length;
    std::vector<int> nodes;
public:
    explicit ReturnValuePath(int length, std::vector<int> nodes) : length(length), nodes(std::move(nodes)) {}
};

// 可以得到当前输入的节点，左右子树中最长的路径和长度
ReturnValuePath* getMaxPathSub(TreeNode* root) {
    if (root == nullptr) {
        return new ReturnValuePath(0, std::vector<int>());
    }
    if (root->left == nullptr && root->right == nullptr) {
        return new ReturnValuePath(1, std::vector<int>{root->val});
    }
    auto left_ret = getMaxPathSub(root->left);
    auto right_ret = getMaxPathSub(root->right);
    int length = 0;
    std::vector<int> nodes;
    // 此时对于 root 节点来说，要判断 root 的左树和右树之间，那个树的长度更长
    if (left_ret->length > right_ret->length) {
        length = left_ret->length + 1;
        nodes.insert(nodes.end(), left_ret->nodes.begin(), left_ret->nodes.end());

    } else {
        length = right_ret->length + 1;
        nodes.insert(nodes.end(), right_ret->nodes.begin(), right_ret->nodes.end());
    }
    nodes.push_back(root->val);
    return new ReturnValuePath(length, nodes);
}

int max_length_path = INT_MIN;
std::vector<int> max_nodes_path;

// 然后可以遍历所有节点，然后进行比较对比
void getMaxPath(TreeNode* root) {
    if (root == nullptr) return;
    auto left_ret = getMaxPathSub(root->left);
    auto right_ret = getMaxPathSub(root->right);
    if (left_ret->length + right_ret->length + 1 > max_length_path) {
        max_length_path = left_ret->length + right_ret->length + 1;
        std::vector<int> cur_nodes(left_ret->nodes.begin(), left_ret->nodes.end());
        cur_nodes.push_back(root->val);
        cur_nodes.insert(cur_nodes.end(), right_ret->nodes.rbegin(), right_ret->nodes.rend());
        max_nodes_path.swap(cur_nodes);
    }
    getMaxPath(root->left);
    getMaxPath(root->right);
}

哈希表和红黑树对比

一、场景对比

1. 速度对比

哈希查找和删除的时间复杂度都是 O(1)，而且查找速度基本上和数据量大小无关。红黑树查找和删除的时间复杂度为 O(logN)

2. 内存消耗

对内存要求严格的地方，建议使用红黑树，因为红黑树仅为其存在的节点分配内存；而哈希表需要事先分配足够的内存存储散列表，较为浪费内存。

因此，如果对数据可以预知，也就是静态数据，比如 Top10 名单， 就可以使用哈希的方式。如果是动态数据，比如 统计 IP 地址，无法判断数量，用红黑树较好一点

3. 有序性

红黑树是有序的，哈希是无序的。

64匹马，8赛道，找到最快的4匹马至少要几次

一共需要 11 次赛马。

1. 首先每一匹马都要跑一次，64 匹马，8个赛道，那就将马随机分成 8 组跑 8 次

2. 每一组都会得到当前组中 8 匹马的相对速度，也就是同一组内的名次。每一组都会诞生第一名

HashMap的大小为什么必须是 2 的倍数

为了加快哈希计算以及减少哈希冲突

一、加快哈希计算

我们为了找到 key 的位置在哈希表的那个槽中，需要计算 hash(key) % 数组长度 。而 HashMap 一般使用 hash值 & (数组大小-1)。 2 的倍数意味着该数的二进制位只有一位为 1，而该数 -1 就可以得到二进制位上 1 变成 0，后面的 0 变成 1，再通过 & 运算，就可以达到和 % 一样的效果，并且位运算比 % 的效率高很多。

二、减少哈希冲突

当 length 为偶数时，length-1 为奇数，奇数的二进制最后一位是 1，这样便保证了 hash & (length -1) 的最后一位可能为 0，也可能为 1，即 & 运算后的结果可能为偶数，也可能为奇数，这样便可以保证哈希的均匀性

如果 length 为奇数时，很明显 length-1 为偶数，它的最后一位是 0，这样 hash & (length-1) 的最后一位肯定为 0，即只能为偶数，这样任何 hash 值都只会被哈希到数组的偶数下标位置上，这便浪费了近一半的空间

因此，length 取 2 的整数次幂，是为了使不同 hash 值发送碰撞的概率变小，这样就能使元素在哈希表中均匀的哈希。

基本思想和模式

可扩展架构的背后的核心思想就是拆。按照不同的思路来拆分软件系统，就会得到不同的架构，常见的拆分思路如下：

• 面向流程拆分：将整个业务流程拆分成几个阶段，每个阶段作为一部分
• 面向服务拆分：将系统提供的服务拆分，每个服务作为一部分
• 面向功能拆分：即系统提供的功能拆分，每个功能作为一部分

微服务

微服务的核心是服务治理，而服务治理的关键是服务划分。故微服务架构的本质就是对码农的分化和治理

SOA 和微服务对比：

微服务就是一些协同工作小而自治的服务。2014年，Martin Fowler 与 James Lewis 共同提出了微服务的概念，定义了微服务是由以单一应用程序构成的小服务，自己拥有自己的进程与轻量化处理，服务依业务功能设计，以全自动的方式部署，与其他服务使用HTTP API通信。同时服务会使用最小的规模的集中管理 (例如 Docker) 能力，服务可以用不同的编程语言与数据库等组件实现