服务端

请求处理模型

• 单线程阻塞模型
• 多线程/进程模型
• 线程池模型
• 异步非阻塞模型
• 协程模型

异步非阻塞模型

epoll

epoll（event poll） 是 Linux 内核提供的一种高级 IO 多路复用机制，可以监听多个文件描述符上的事件，并将这些事件通知给应用程序，从而实现异步的 IO 操作。

epoll 监听的 fd（file descriptor）集合是常驻内核的，它有 3 个系统调用 （epoll_create, epoll_wait, epoll_ctl），通过 epoll_wait 可以多次监听同一个 fd 集合，只返回可读写那部分。

来自 ChatGPT

epoll 是 Linux 内核提供的一种高级 IO 多路复用机制，它可以同时监听多个文件描述符上的事件，并将这些事件通知给应用程序。与传统的 Select 和 Poll 机制相比，epoll 具有更高的性能和更好的可扩展性。

具体来说，epoll 通过以下几个关键部分来实现 IO 多路复用：

1. epoll_create：创建一个 epoll 对象，并返回其对应的文件描述符。
2. epoll_ctl：向 epoll 对象中添加或删除指定的文件描述符，以及设置相应的事件类型等参数。
3. epoll_wait：等待指定文件描述符上的事件发生，并将这些事件收集起来返回给应用程序。

在使用 epoll 进行 IO 多路复用时，通常采取如下的处理流程：

1. 创建 epoll 对象，并将需要监听的文件描述符添加到 epoll 的事件列表中。
2. 使用 epoll_wait 等待事件的发生，当某个文件描述符上有事件发生时，就会触发 epoll_wait 返回。
3. 根据事件类型进行相应的处理。如果是可读事件，则读取数据并进行处理；如果是可写事件，则进行写操作。
4. 处理完毕后，将文件描述符从 epoll 的事件列表中删除。

需要注意的是，epoll 机制支持三种事件触发模式，包括边缘触发（Edge Triggered）、水平触发（Level Triggered）和一次性触发（One-Shot）。其中，边缘触发模式是最高效的一种模式，它只在文件描述符状态发生变化时才会通知应用程序；而水平触发和一次性触发模式需要更多的系统调用，因此相对较慢。

总的来说，epoll 机制具有高效、可扩展、灵活等优点，在高并发场景下被广泛使用。

epoll 如何通知应用程序

在 epoll 机制中，当 I/O 事件发生时，应用程序通过调用 epoll_wait 函数等待事件的发生。该函数会阻塞当前线程，直到有事件发生或者超时，然后将所有已经就绪的文件描述符加入到一个由 epoll_event 结构体组成的数组中，最后返回数组中的事件数量。

每个 epoll_event 结构体包含了一个就绪的文件描述符和该文件描述符上发生的事件类型。应用程序随后可以遍历这个数组，并根据文件描述符和其对应的事件类型进行相应的处理（如读取数据、写入数据等）。

需要注意的是，在边缘触发模式下，如果有多个事件同时发生，epoll_wait 只会返回一次通知。因此，应用程序在处理完某个文件描述符上的事件后，需要重新调用 epoll_wait 函数获取下一轮事件通知。

总之，epoll 机制的通知方式是通过将就绪的文件描述符和相应的事件类型打包成一个结构体，并返回给应用程序，从而实现了高效、可扩展、高并发的 IO 处理。

select

select 只有一个系统调用，每次要监听都要将其从用户态传到内核，有事件时返回整个集合。

来自 ChatGPT

select 是一种基于 IO 多路复用的系统调用，它可以同时监听多个文件描述符上的事件，并在其中有事件发生时通知应用程序进行处理。select 机制主要由以下三个部分组成：

1. fd_set 数据结构：用于存储需要监听的文件描述符集合。
2. select 函数：用于将需要监听的文件描述符集合传递给内核，以及等待事件的发生并返回事件列表。
3. 相应的文件操作函数：例如 read、write 等，用于对文件描述符执行相应的 IO 操作。

在使用 select 进行 IO 多路复用时，通常采取如下的处理流程：

1. 创建 fd_set 数据结构，并将需要监听的文件描述符添加到该数据结构中。
2. 调用 select 函数等待事件的发生。当某个文件描述符上有事件发生时，就会触发 select 返回。
3. 使用相应的文件操作函数对事件进行处理。如果是可读事件，则读取数据并进行相应的处理；如果是可写事件，则进行写操作。
4. 循环执行上述过程，直到关闭连接或出现异常。

需要注意的是，在 select 模式下，文件描述符数量受到限制，通常不能超过系统默认值（例如 1024）。此外，在高并发情况下，select 的效率较低，因为每次都需要对所有监控的文件描述符进行扫描，无法有效利用 CPU 和内存等资源。因此，在实现高并发服务器时，通常采用更为高效的机制，如 epoll 和 kqueue 等。

自定义协议

示例

1
2
3
4
5
6
7
8
9
10

Protocol protocol = { ParseMessage,
                      SerializeRequest, PackRequest,
                      ProcessHttpRequest, ProcessResponse,
                      VerifyRequest, ParseServerAddress,
                      GetMethodName,
                      CONNECTION_TYPE_SINGLE,
                      "h2" };
if (RegisterProtocol(PROTOCOL_H2, protocol) != 0) {
    exit(1);
}

客户端调用顺序

• 去程
  • SerializeRequest
  • PackRequest
• 回程
  • ParseMessage
  • ProcessResponse

bthread

初始化

1
2
3
4
5
6
7
8
9
10

bthread_t bid;
bthread_attr_t attr;
bthread_attr_init(&attr);

auto s = [](void *) -> void * {
    auto r = bthread_usleep(1000 * 1000 * 3);
    return nullptr;
};
bthread_start_urgent(&bid, &attr, s, nullptr);
bthread_join(bid, nullptr);

使用

1
2
3
4
5
6
7
8

#include "bthread/bthread.h"
auto s = [](void *) -> void * {
    bthread_usleep(1000 * 15);
};

bthread_t th1;
bthread_start_urgent(&th1, &attr, s, nullptr);
bthread_join(th1, nullptr);

timer_thread

NOTE: 执行一次，且时间为时间戳（通常是未来时间），非间隔执行。

1
2
3
4
5
6

#include "bthread/timer_thread.h"
bthread::TimerThread timer;
bthread::TimerThreadOptions options;
timer.start(&options); 
// 或者 timer.start(nullptr); 
timer.schedule(ConfigData::load, this, {butil::seconds_from_now{5}}); // 5秒后执行一次

自定义 Period Timer

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
57
58
59
60
61
62
63
64
65
66
67

// brpc_period_timer.h
typedef void (*BrpcPeriodTimerFunction)(void *);

struct BrpcTimerContext {
    BrpcPeriodTimerFunction function;
    void *argument;
    int interval_s;
    bthread::TimerThread *timer;
};

class BrpcPeriodTimer {
public:
    BrpcPeriodTimer();
    ~BrpcPeriodTimer();

    static void Wrapper(void *ctx);
    void Schedule(BrpcTimerContext *);
private:
    bthread::TimerThread timer_;
};

// brpc_period_timer.cpp
BrpcPeriodTimer::BrpcPeriodTimer() {
    timer_.start(nullptr);
}

BrpcPeriodTimer::~BrpcPeriodTimer() {
    timer_.stop_and_join();
}

void BrpcPeriodTimer::Wrapper(void *ctx) {
    auto c = (BrpcTimerContext *) ctx;
    c->function(c->argument);
    c->timer->schedule(BrpcPeriodTimer::Wrapper, ctx, butil::seconds_from_now(c->interval_s));
}

void BrpcPeriodTimer::Schedule(BrpcTimerContext *ctx) {
    auto c = (BrpcTimerContext *) ctx;
    ctx->timer = &timer_;
    timer_.schedule(BrpcPeriodTimer::Wrapper, ctx, butil::seconds_from_now(c->interval_s));
}

// test
TEST(Utils, PeriodTimer) {
    auto payload = [](void *) {
        std::cout << "run payload" << std::endl;
    };

    BrpcPeriodTimer timer;
    BrpcTimerContext ctx{payload, nullptr, 1};
    timer.Schedule(&ctx);

    sleep(10);
}

// output
Testing started at 17:45 ...
run payload
run payload
run payload
run payload
run payload
run payload
run payload
run payload
run payload
Process finished with exit code 0

数据结构

树

数据结构及存储结构

算法

排序

sort

• 底层实现：C++ 标准库中的 sort() 函数通常使用一种名为 “introsort” 的混合排序算法来实现。这是一种综合了快速排序、堆排序和插入排序的排序算法。
• 工作原理：sort() 函数首先会尝试使用快速排序算法进行排序，通过选择一个枢轴元素来将序列分割成两个部分，并递归地对子序列进行排序。当递归深度达到一定阈值时，为了避免最坏情况下的时间复杂度，算法会转而采用堆排序算法。如果序列较小，则会使用插入排序算法进行排序。
• 复杂度：平均时间复杂度为 O(n log n)，其中 n 是待排序序列的大小。空间复杂度为 O(log n)。

quick_sort

• 底层实现：quick_sort() 函数是基于快速排序算法的一种实现。

• 工作原理：快速排序算法通过选取一个枢轴元素将序列分割为两个子序列，较小的元素放在枢轴的左侧，较大的元素放在右侧。然后对这两个子序列递归地应用相同的操作，直到子序列的大小为 1 或 0，此时递归结束。

• 复杂度：平均时间复杂度为 O(n log n)，其中 n 是待排序序列的大小。最坏情况下的时间复杂度为 O(n^2)。空间复杂度为 O(log n)。

常见问题

STL 是什么

STL（Standard Template Library，标准模板库）是C++编程语言的一个标准库，主要包含了许多常用的数据结构和算法，并为其提供了一系列的通用接口，方便开发者进行快速开发、高效地复用代码。

STL包括容器、迭代器、算法以及仿函数等组件，它们的设计思想是基于泛型编程和模板元编程。STL允许用户通过重载运算符或定义函数对象对其现有的模板进行扩展，支持自定义类型和算法，从而大大增强了程序的可扩展性和可维护性。

STL标准库中包含了很多容器（如vector、list、map、set等）、算法（如sort、search、find等）和迭代器（如输入输出流迭代器、反向迭代器等），这些组件可以帮助程序员实现许多常见的数据结构和算法，例如线性表、树、图、排序、查找等，从而提高了程序的开发效率和代码质量。

总之，STL是一种非常强大和实用的C++库，广泛应用于软件开发、算法竞赛等领域，是C++程序员必须掌握的一个重要工具。

STL中包含哪些容器？它们之间有什么区别？

STL（Standard Template Library，标准模板库）中包含了多种容器，主要分为以下三类：

顺序容器

顺序容器是指元素按照一定的顺序存储和访问的容器。常见的顺序容器有vector、list、deque、array等。其中，vector和deque都是基于数组实现的可变长度容器，而list则是基于双向链表实现的容器。

关联容器

关联容器是指元素按照一定规则排序后存储和访问的容器。常见的关联容器有set、multiset、map、multimap等。其中，set和map是基于平衡二叉树实现的，而multiset和multimap允许重复元素。

无序容器

无序容器是指元素不按照任何特定顺序存储和访问的容器。常见的无序容器有unordered_set、unordered_multiset、unordered_map、unordered_multimap等。这些容器通常使用哈希表来实现，具有O(1)的插入、查找和删除操作。

这些容器之间的区别主要包括以下几个方面：

1. 存储方式不同：顺序容器按照逻辑顺序存储元素，而关联容器和无序容器则根据元素的键值进行存储。
2. 插入和查找的时间复杂度不同：顺序容器在尾部插入元素和访问尾元素时速度较快，而关联容器和无序容器则可以通过键值快速查找元素。
3. 内存分配方式不同：顺序容器通常使用连续内存块来存储元素，而关联容器和无序容器则需要动态分配内存。
4. 支持的操作不同：不同的容器支持的操作有所区别。例如，只有顺序容器和关联容器支持排序操作，而只有无序容器支持哈希相关操作。

在选择容器时，需要根据具体的应用场景和需要进行权衡和选择。例如，如果需要对元素进行频繁的插入和删除操作，可以选择使用list或deque；如果需要高效地进行查找操作，则可以选择使用set、map等关联容器；如果需要快速进行元素的插入、查找和删除操作，则可以选择使用unordered_set、unordered_map等无序容器。

STL中包含哪些算法？它们的时间复杂度分别是多少？

STL（Standard Template Library，标准模板库）中包含了大量的算法，这些算法主要分为以下几类：

1. 查找和排序算法：如find、find_if、sort、stable_sort等。
2. 变动操作算法：如copy、replace、remove、unique等。
3. 数值算法：如accumulate、inner_product、partial_sum、adjacent_difference等。
4. 集合操作算法：如set_union、set_intersection、set_difference、merge等。
5. 堆算法：如make_heap、pop_heap、push_heap等。
6. 其他算法：如count、for_each、transform、reverse等。

这些算法的时间复杂度各不相同，具体如下：

1. 查找和排序算法：通常具有O(nlogn)或O(n)的时间复杂度。
2. 变动操作算法：通常具有O(n)的时间复杂度。
3. 数值算法：通常具有O(n)的时间复杂度。
4. 集合操作算法：通常具有O(n)的时间复杂度。
5. 堆算法：通常具有O(logn)的时间复杂度。

STL中的迭代器有哪些种类？它们之间有什么区别？

STL（Standard Template Library）中的迭代器是一种用于遍历容器中各个元素的对象。根据其所支持的操作和能力，可以将迭代器分为以下五类：

1. 输入迭代器（Input Iterator）：支持读取元素的值，但不允许修改或重复读取元素。例如std::istream_iterator。
2. 输出迭代器（Output Iterator）：支持写入元素的值，但不允许读取或重复写入元素。例如std::ostream_iterator。
3. 前向迭代器（Forward Iterator）：支持在容器中沿着一个方向遍历每个元素，并且能够多次读取或写入同一元素。例如std::forward_list::iterator。
4. 双向迭代器（Bidirectional Iterator）：支持前向迭代器的所有操作，同时还支持反向遍历容器并进行修改操作。例如std::list::iterator。
5. 随机访问迭代器（Random Access Iterator）：支持双向迭代器的所有操作，同时还支持随机访问容器中任意元素的操作，并支持指针算术、取下标等高级操作。例如std::vector::iterator。

这些迭代器之间的区别在于它们所支持的操作和能力不同。输入迭代器和输出迭代器都只能向前遍历容器中的元素，且不能进行修改、重复访问等操作。前向迭代器可以在容器中向前遍历每个元素，并且能够多次读取或写入同一元素。双向迭代器可以支持反向遍历容器并进行修改操作，而随机访问迭代器则可以支持高级的指针算术、下标操作等。

使用迭代器可以方便地对STL中的容器进行遍历和操作，从而简化代码的编写和维护。在实际应用中，我们可以根据需要选择合适的迭代器类型来完成相应的任务。

什么是STL中的迭代器失效？如何避免迭代器失效？

STL中的迭代器失效是指，当容器发生插入、删除或移动元素等操作时，之前获取的某些迭代器可能会失效，导致使用这些迭代器访问容器时出现未定义行为。

为了避免迭代器失效，可以采取以下措施：

1. 避免在循环中对容器进行插入、删除或移动操作，因为这可能会导致循环内的迭代器失效。
2. 使用emplace()函数而不是insert()函数来插入新元素。emplace()函数可以直接在容器中构造新元素，避免复制或移动现有元素，从而减少迭代器失效的可能性。
3. 对于需要对容器中的元素进行操作的情况，可以使用智能指针（如shared_ptr）来管理容器中的元素，这样即使容器发生变化，指向元素的智能指针仍然有效。
4. 在进行容器操作时，尽量使用下标或者迭代器来访问容器中的元素，而不是使用指针。因为指针可能会受到容器重新分配内存的影响，从而失效。

STL中的容器和算法都是采用什么方式实现的？

STL中的容器和算法都是采用模板类和泛型编程的方式实现的。

容器是通过模板类来实现的，每个容器都有自己的特定类型、迭代器和操作方法。例如，vector容器是使用动态数组来实现的，list容器是使用双向链表来实现的，map容器是使用红黑树来实现的等等。

算法是通过函数模板来实现的，它们可以接受不同类型的容器和迭代器作为参数，并提供了一系列通用的操作方法。例如，sort()函数可以对任何支持随机访问迭代器的容器进行排序，find()函数可以在任何支持正向迭代器的容器中查找指定元素等等。

这种基于模板类和泛型编程的设计模式，使得STL中的容器和算法具有高度的灵活性和可重用性，可以适应各种数据结构和算法的实现需求。同时还能够提高代码的可读性和可维护性，减少了重复代码的写作量，提高了开发效率。

什么是STL中的仿函数？它们的作用是什么？

什么是STL中的适配器？它们有哪些种类？如何使用？

STL中如何实现自定义类型的排序和查找？

STL中的vector和list有什么区别？它们的优缺点是什么？

STL中的set和map有什么区别？它们的底层实现是什么？

STL中的迭代器与指针有何异同？

如何在STL中使用自定义的比较函数来进行排序？

STL中的关联式容器和无序容器有什么区别？它们的底层实现是什么？

安装

在 这里 选择规格，并下载。以 amd64 的 ubuntu 为例，下面是在线安装命令。

1
2
3
4

wget https://developer.download.nvidia.com/compute/cuda/repos/ubuntu2204/x86_64/cuda-keyring_1.0-1_all.deb
sudo dpkg -i cuda-keyring_1.0-1_all.deb
sudo apt-get update
sudo apt-get -y install cuda

文档参考这里，代码示例参考这里。

文档

官方

• 编码手册
• 最佳实践

博客

• ref 1
• ref 2
• ref 3
• ref 4

描述

端口扫描工具，地址。

安装

brew

1

brew instsall rustscan

docker

1

docker pull rustscan/rustscan:2.0.0

使用

1
2
3
4
5
6
7

rustscan -a 192.168.6.100 --ulimit 5000

# 指定端口
rustscan -a 192.168.6.100 --ulimit 5000 -p 21,22,80

# 指定范围
rustscan -a 192.168.6.2 --ulimit 500 -r 1-65535

查看监听的端口

1

sudo netstat -tunlp

socks5

server

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

# 安装
sudo apt install dante-server

# 配置
sudo vim /etc/danted.conf
# 修改配置
logoutput: /var/log/danted.log
internal: eth0 port = 1080
external: eth0
clientmethod: none
socksmethod: username
user.privileged: root
user.notprivileged: nobody

client pass {
	from: 0.0.0.0/0 to: 0.0.0.0/0
	log: error connect disconnect
}

socks pass {
	from: 0.0.0.0/0 to: 0.0.0.0/0
	command: connect
	log: error connect disconnect
	socksmethod: username
}

# 启动服务
sudo service danted start

不启用认证配置

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

logoutput: /var/log/danted.log
internal: ens18 port = 1080
external: ens18
clientmethod: none
method: none
user.privileged: root
user.notprivileged: nobody

client pass {
	from: 0.0.0.0/0 to: 0.0.0.0/0
	log: error connect disconnect
}

socks pass {
	from: 0.0.0.0/0 to: 0.0.0.0/0
	command: connect
	log: error connect disconnect
	method: none
}

ShadowSocks

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

# 安装
sudo apt install shadowsocks-libev

# 配置
sudo nano /etc/shadowsocks-libev/config.json
{
    "server":["::1", "127.0.0.1"],
    "mode":"tcp_and_udp",
    "server_port":8388,
    "local_port":1080,
    "password":"ACRrobo9ymXb",
    "timeout":60,
    "method":"chacha20-ietf-poly1305"
}

# 服务
sudo systemctl restart shadowsocks-libev.service
sudo systemctl enable shadowsocks-libev.service
systemctl status shadowsocks-libev.service

Http

squid

ubuntu

• ubuntu

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

# 安装
sudo apt install squid

# 配置
sudo vim /etc/squid/squid.conf
## 配置项
http_port <port>
dns_nameservers 8.8.8.8 8.8.4.4

# 认证
sudo apt install apache2-utils
# 生成账号 & 密码并写入文件
sudo touch /etc/squid/passwords
sudo htpasswd /etc/squid/passwords <user-name>  
# htpasswd -c 选项会重新生成文件

# 修改配置
sudo vim /etc/squid/squid.conf
## 添加如下内容
auth_param basic program /usr/lib/squid/basic_ncsa_auth /etc/squid/passwords
auth_param basic realm proxy
acl authenticated proxy_auth REQUIRED
http_access allow authenticated
# 放在 http_access deney all 之前

# 其他配置
tcp_outgoing_address    198.18.192.194		# 设置出网端口(网络端口分配的ip)

# 启动服务
sudo systemctl start squid.service
# 或重启服务
sudo systemctl restart squid.service

# 开机启动
sudo systemctl enable squid.service

# 测试
curl -v -x http://<user-name>:<password>@<host>:3128 https://www.google.com/

Command

1
2
3
4
5
6
7
8
9
10

# local
rsync [OPTION]... SRC [SRC]... DEST

# remote
rsync [OPTION]... SRC [SRC]... [USER@]HOST:DEST
rsync [OPTION]... SRC [SRC]... [USER@]HOST::DEST
rsync [OPTION]... SRC [SRC]... rsync://[USER@]HOST[:PORT]/DEST
rsync [OPTION]... [USER@]HOST:SRC [DEST]
rsync [OPTION]... [USER@]HOST::SRC [DEST]
rsync [OPTION]... rsync://[USER@]HOST[:PORT]/SRC [DEST]

参数

1
2
3
4
5
6
7

-r 递归同步
-R 使用相对路径名称
-c 文件比较使用校验和替代时间和大小
-P 显示进度并保留未传输完成的文件

--delete	  删除目标文件夹无关的文件
--progress  显示进度

通过域名解析内网机器

打开 高级设置 / 内部网络，修改路由器网络名称为 host。

这里选 host 是应为 host 是合法的定级域名，浏览器输入不添加协议头 (http:// 等) 时不会调用搜索。

修改机器名称

在下面的 手动指定 IP 的 DHCP 列表 中添加内网机器记录。

检查 Hosts

1
2
3
4
5
6
7
8
9
10
11

$ ssh admin@192.168.6.1

$ cat /etc/hosts
127.0.0.1 localhost.localdomain localhost
192.168.6.1 RT-AX88U-BD78.host RT-AX88U-BD78
192.168.6.1 RT-AX88U-BD78.local
192.168.6.1 router.asus.com
192.168.6.1 www.asusnetwork.net
192.168.6.1 www.asusrouter.com
192.168.6.6 unraid.host
...

浏览器访问

注意

上面示例使用了 host，但是出现了一些意外的情况。有一台新的机器初始化，不知道为何，连接公司网络后，网络连接配置里面的 Search Domain 仍然保留了 host，按道理来说，更换网络后 Search Domain 会从新的网络获取。如果继续配置 Search Domain 为 host，那么会出现这么一种情况：如果访问的域名不存在，那么会尝试搜索 domain.host，然而 .host 是一个可用的顶级域名，然后出现了跳转到 domain.host ，有些公司的 dOmain 恰巧被一些大聪明利用，就出现了实际不存在但是会跳转到不可言状的站点（比如访问 git.compony.com 有可能被解析为 git.compony.com.host 并被重定向到某些网站）。

总之，不用 .host，选择一个和顶级域名不冲突的 search domain。

回刷官方固件

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

1. 下载固件并解压
https://www.netgear.com/support/download/

2. 路由器恢复模式
 - 路由器关机
 - 按住 Reset
 - 开机
 - 等待一二十秒，电源灯白灯闪烁
 
3. 上传固件 
// 不同系统的命令稍有差异
$ tftp 192.168.1.1
tftp> binary
tftp> put R9000-V1.0.5.42.img

4. 等待刷新完成