东风草堂博客

漏桶算法

把请求比作是水，水来了都先放进桶里，并以限定的速度出水，当水来得过猛而出水不够快时就会导致水直接溢出，即拒绝服务。

可以看出，漏桶算法可以很好的控制流量的访问速度，一旦超过该速度就拒绝服务。

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
52
53
54
55
56

#include <iostream>
#include <chrono>
#include <thread>
using namespace std;
using namespace std::chrono;

class LeakyBucket {
public:
    LeakyBucket(int capacity, int rate){
        this->capacity = capacity;
        this->rate = rate;
        this->water_count = 0;
        this->last_leak_time = duration_cast<milliseconds>(system_clock::now().time_since_epoch());
    }

    bool take_request(){
        auto now = duration_cast<milliseconds>(system_clock::now().time_since_epoch());
        int passed_time = (int)(now - last_leak_time).count();

        water_count -= passed_time * rate; // 固定的速度流水
        if(water_count < 0){
            water_count = 0;
        }

        if(water_count < capacity){ // 请求就是加入的水，加满了就拒绝服务
            water_count++;
            last_leak_time = now;
            return true;
        }

        return false;
    }

private:
    int capacity;
    int rate;
    int water_count;
    time_point<system_clock> last_leak_time;
};

int main() {
    LeakyBucket bucket(10, 2);

    for(int i = 0; i < 20; i++){
        if(bucket.take_request()){
            cout << "request " << i + 1<< " passed" << endl;
        } else {
            cout << "request " << i + 1 << " discarded" << endl;
        }
        if(i != 19){
            std::this_thread::sleep_for(100ms);
        }
    }

    return 0;
}

令牌桶算法

令牌桶算法的原理是系统会以一个恒定的速度往桶里放入令牌，而如果请求需要被处理，则需要先从桶里获取一个令牌，当桶里没有令牌可取时，则拒绝服务。从原理上看，令牌桶算法和漏桶算法是相反的，一个“进水”，一个是“漏水”。

进程和线程的区别？

1. 一个线程只能属于一个进程，而一个进程可以有多个线程，但至少有一个线程。线程依赖于进程而存在。
2. 进程在执行过程中拥有独立的内存单元，而多个线程共享进程的内存。（资源分配给进程，同一进程的所有线程共享该进程的所有资源。同一进程中的多个线程共享代码段（代码和常量），数据段（全局变量和静态变量），扩展段（堆存储）。但是每个线程拥有自己的栈段，栈段又叫运行时段，用来存放所有局部变量和临时变量。）
3. 进程是资源分配的最小单位，线程是CPU调度的最小单位；
4. 系统开销： 由于在创建或撤消进程时，系统都要为之分配或回收资源，如内存空间、I／o设备等。因此，操作系统所付出的开销将显著地大于在创建或撤消线程时的开销。类似地，在进行进程切换时，涉及到整个当前进程CPU环境的保存以及新被调度运行的进程的CPU环境的设置。而线程切换只须保存和设置少量寄存器的内容，并不涉及存储器管理方面的操作。可见，进程切换的开销也远大于线程切换的开销。
5. 通信：由于同一进程中的多个线程具有相同的地址空间，致使它们之间的同步和通信的实现，也变得比较容易。进程间通信IPC，线程间可以直接读写进程数据段（如全局变量）来进行通信——需要进程同步和互斥手段的辅助，以保证数据的一致性。在有的系统中，线程的切换、同步和通信都无须操作系统内核的干预。
6. 进程编程调试简单可靠性高，但是创建销毁开销大；线程正相反，开销小，切换速度快，但是编程调试相对复杂。
7. 进程间不会相互影响 ；线程一个线程挂掉将导致整个进程挂掉。
8. 进程适应于多核、多机分布；线程适用于多核。
9. 线程必须放在fork之后，因为fork之前创建的线程不会被继承.

在 Linux 内核中，0 号进程（也称为 idle 进程）是系统中唯一一个没有被正常进程显式创建的进程，它是在内核启动时创建的，负责消耗 CPU 时间，以保证系统不会浪费 CPU 资源。
1 号进程（也称为 init 进程）是 Linux 系统启动后第一个被创建的进程，它是所有进程的祖先进程。init 进程负责启动系统上其他进程和服务，并在系统关闭时关闭这些进程和服务。
2 号进程（也称为 kthreadd 进程）是一个守护进程，它是内核中的一个主要线程。它是内核线程的创建者，也是唯一的内核线程，其主要职责是协调内核中的各种子系统，如内存管理、进程管理、文件系统等。
需要注意的是，0 号进程、1 号进程和 2 号进程是内核级别的进程，它们不同于普通进程，不会被用户显式创建、销毁或操纵。

进程间通信的方式

进程间通信主要包括管道、系统IPC（包括消息队列、信号量、信号、共享内存等）、以及套接字socket。

缓存方案主要用于缓存用户定义的热点数据，用户可以通过缓存来获取数据，从而降低数据库的压力。
内存访问速度远大于磁盘访问速度，mysql缓存的数据跟业务无关，缓存的是最近操作的数据。mysql作为项目的主要数据库，缓存数据库只是辅助功能。

缓存一致性

• mysql有，redis无，正常
• mysql无，redis有，不正常
• 都有，数据不一致，不正常
• 都有，数据一致，正常
• 都没有，正常

读写策略

• 读策略：先读缓存，缓存存在直接返回，缓存不存在，去访问Mysql获取，若存在，再写缓存
• 写策略：
  • 安全：先删除缓存中数据，再写mysql，再同步到redis.这样mysql的压力会大
  • 效率：先写缓存，设置过期时间（防止mysql写失败），再写mysql，最后将mysql中的数据同步到redis中

找完全二叉树最底层最右边的结点

给定一个二叉树的 根节点 root，请找出该二叉树的 最底层 最右边 节点的值。
假设二叉树中至少有一个节点。

完全二叉树的特点，即除了最后一层外，每一层都是满的，并且最后一层上的节点都集中在该层最左边的若干位置上。所以，如果我们按照层次遍历这个完全二叉树，最后遍历到的节点即为底层最右节点。

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

#include <iostream>
#include <queue>

using namespace std;

struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

// 求完全二叉树的底层最右节点
TreeNode* findBottomRightNode(TreeNode* root) {
    if (!root) return NULL;

    queue<TreeNode*> q;
    q.push(root);

    TreeNode* cur = NULL;
    while (!q.empty()) {
        int n = q.size();
        for (int i = 0; i < n; i++) {
            cur = q.front();
            q.pop();

            if (cur->left) q.push(cur->left);
            if (cur->right) q.push(cur->right);
        }
    }

    return cur;
}

int main() {
    // 手动构建一个完全二叉树
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);
    root->right->left = new TreeNode(6);

    TreeNode* br = findBottomRightNode(root);
    cout << "底层最右节点的值为：" << br->val << endl;

    return 0;
}

二叉树的最近公共祖先

网络通信模型

TCP/IP与OSI最大的不同在于：OSI是一个理论上的网络通信模型，而TCP/IP则是实际运行的网络协议。

为什么连接的时候是三次握手，关闭的时候却是四次挥手？

三次握手

第一次握手：第一次握手是客户端发送同步报文到服务端，这个时候客户端是知道自己具备发送数据的能力的，但是不知道服务端是否有接收和发送数据的能力；

自旋锁

自旋锁是最基本的一种无锁技术，采用基于 CAS（Compare-and-Swap）的操作，尝试获取锁，失败时采用轮询的方式等待资源，避免线程被阻塞，不需要系统调用，从而减少上下文切换和性能损耗。
原子操作使用 CPU 提供的原子性指令，属于硬件层面的，实现数据的原子性访问和修改，避免使用锁导致的线程阻塞和竞争，同时也避免了死锁的发生。
加锁区执行速度快的情况下可以使用该锁。
atomic提供的常见方法：

• store：原子写操作。
• load：原子读操作。
• compare_exchange_strong：传入[期望原值]和[设定值]，当前值与期望值相等时，修改当前值为设定值，返回true；当前值与期望值不等时，将期望值修改为当前值，返回false。
• compare_exchange_weak：同上，但允许偶然出乎意料的返回（比如在字段值和期待值一样的时候却返回了false），比strong性能更好些，但需要循环来保证逻辑的正确性。
• exchange：交换2个数值，并保证整个过程是原子的。

C++11标准中提供了 std::atomic 模板类，用于实现原子操作，可用于实现 CAS 操作，从而实现无锁编程。
在非并发条件下，实现一个栈的Push操作，通常有如下操作：

• 步骤1：新建一个节点，node* const new_node = new node(data);
• 步骤2：将该节点的next指针指向现有栈顶，new_node->next = head;
• 步骤3：更新栈顶，head = new_node

系统梳理软件开发中常用的设计模式，深入解析策略模式、观察者模式、责任链模式等核心模式的实现原理与应用场景，提供完整的C++代码示例，帮助开发者掌握设计模式在实际项目中的灵活运用。

双指针相关题型

几个数之和系列

目前还有不少朋友对留言功能开通不是很了解，已经很久没有更新文章了，还是决定将一些大家都存在的疑惑问题再集中整理一下，写成一篇文章，希望能对大家有帮助。

网上已经有各种资料已经说的很清楚了，18年3月后就关闭了留言功能，政策原因，理解一下。

下面介绍两种开通留言功能的方法。

公众号迁移

如果你是个人类型订阅号，建议直接看第二种开通留言的小程序留言方法或本方法的最后一点，如果你是企业类型订阅号，有条件的还是建议进行迁移，一步到位，只是迁移的过程麻烦一点。下面分几个方向对迁移进行说明。