computer science►engineering architecture►rpc

brpc

自定义协议

示例

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
data struct

data struct

数据结构

树

概念 标签 说明
平衡树 二叉树 可以保证在插入、删除等操作后维持树的平衡性，以保证其查找效率
B树 多路搜索树、自平衡搜索树 每个节点可以拥有多于两个的子节点，常用于磁盘文件系统和数据库索引等场景
B+树 多路搜索树、自平衡搜索树 优化了B树的节点结构和叶子节点指针，提供了更好的范围查询性能。它在数据库索引和文件系统中广泛应用，能够高效地支持各种查询操作
B-树 多路搜索树、自平衡搜索树 具有多个关键字的非叶子节点和链表连接的叶子节点。它在节点结构、关键字排序和范围查询性能等方面与B树和B+树有所不同。B-树适用于大规模数据集的存储和检索，能够提供高效的访问性能
红黑树 平衡二叉查找树 gpt-3.5-turbo-0613由于其插入、删除和查找的时间复杂度均为O(log(n))，因此被广泛应用于STL中的set和map容器
Trie树（字典树） 多叉树结构 用于检索字符串数据集中的键值，常用于搜索引擎词频统计等场景
堆 完全二叉树 连续内存存储，可用于实现优先队列等数据结构。堆分为大根堆和小根堆两种类型
Huffman树 二叉树 一种带权路径长度最短的二叉树，常用于数据压缩和编码等场景
coding►c++

c++ STL

数据结构及存储结构

数据结构 底层存储 复杂度
map 红黑树 O(logn)
unordered_map 散列表 O(1)
list 双向链表 O(n)
priority_queue 堆（数组实现） O(logn)

算法

排序

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中的关联式容器和无序容器有什么区别？它们的底层实现是什么？

tools►rustscan

rustscan

描述

端口扫描工具，地址。

安装

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
工具►vpn

vpn

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

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/
linux►software

rsync

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  显示进度
play►router

华硕路由器

通过域名解析内网机器

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

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

image-20221106215611021

修改机器名称

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

image-20221106224817651

检查 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
...

浏览器访问

image-20221106220852396

注意

上面示例使用了 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。

play►soft router

ikuai

远程访问

生成证书

1
$ openssl req -x509 -days 7200 -newkey rsa:2048 -keyout server.key -out server.crt -nodes -subj "/C=CN/ST=Beijing/L=Beijing/O=Wii/OU=IT/CN={your.domain}" -addext "subjectAltName = DNS:{your.domain}"

将生成的 crt 和 key 文件内容拷贝到爱快远程访问的证书管理里面。

image-20241016122718014

证书认证问题导致的无法访问

Chrome 浏览器 + Mac OS 会触发这个问题，访问方式如下。

  • 点击页面空白处（位置随意）
  • 然后使用键盘输入 thisisunsafe （对，没有任何输入框，盲输。注意，一定要先点击页面空白处）

或者使用 Safari 浏览器（或者其他），在显示详细信息里面点继续访问即可。

VPN

L2TP 服务端

只需要启动服务端、添加账号，无需其他配置。

启动服务端

image-20241016121909165

  • 预共享密钥选填

配置账号

image-20241016122101208

  1. 输入账号密码
  2. 输入收款金额 0

问题排查

无法访问内网

官网排查手册

image-20241016122215464

客户端排查

Mac os 用户，需要开启 VPN 里面的 通过 VPN 连接发送所有流量，如果不开启的话部分内网 ip 网段可能不走 VPN，导致无法访问远端内网。

image-20241016122318114

play►router

netgear

回刷官方固件

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. 等待刷新完成