东风草堂博客

包完整性

1. 以特殊符号来分界，如每个包都以特定的字符来结尾（如\r\n，http的header就是），当在字节流中读取到该字符时，则表明上一个包到此为止。
2. 固定包头+包体结构，包头一般时一个固定字节长度的结构，并且包头中会有一个特定的字段指定包体的大小。收包时，先接收固定字节数的头部，解出这个包的完整长度，按此长度接收包体。header+body 目前应用最多的一种包格式。
3. 在序列化后的buffer前面增加一个字符流的头部，其中有一个字段存储包总长度，根据特殊字符（比如\n或者\0）判断头部的完整性。这样通常比2麻烦些，http和redis（$6\r\nfoobar\r\n）采用的这种形式，收包的时候，先判断已经收到的数据中是否包含结束符，收到结束符后解析包头，解出这个包完整长度，按此长度接收包体。

协议设计

序列号：tcp只能保证数据到达，不能保证数据是否处理。

type表示协议类型，如xml，json。

版本号尽量放在前面，读取版本号的时候可以少读一些字节，如下nginx。protobuf封装后是放在body里面的。header也是定长的，就不用序列化。body做序列化即可。

http请求头为文本，但是body如果传的是jpeg就是二进制。

xml、json序列化后都是文本，protobuf序列化后就是二进制，这里指的是将对象序列化，对象里面一些变长的字段不进行序列化不方便传输。

采用proto buffer作为idl语言。
采用http2进行通信，body采用protobuf序列化后的二进制传输，将字段名去掉，以数字代替。

四种模式：一个端口可以对应多个service

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

syntax = "proto3";
package helloworld; // 命名空间
option go_package = "grpc/helloworld/proto";
import "google/protobuf/timestamp.proto";
import "google/protobuf/any.proto"; // go 里面的interface类型

service Greeter {
// simple rpc
rpc GetFeature(Point) returns (Feature) {}

// server-to-client streaming rpc，下载文件
rpc ListFeatures(Rectangle) returns (stream Feature) {}

// client-to-server streaming rpc，上传文件
rpc RecoredRoute(stream Point) returns (RouteSummary) {}

// Bidirectional streaming rpc，开多线程读写实现，问答场景
rpc RouteChat(stream RouteNote) returns (stream RouteNote) {}
}

// 结构体以message开头
message Feature {
    // 1-15 占一个字节
    string name = 1;
    Point location = 2;
    google.protobuf.Timestamp birthday = 9;
    Address address = 10; // 自定义类型
    repeated string hobys = 11; // 多个兴趣
    map<string, google.protobuf.Any> data = 12;
    reserved 3, 4 to 8; // 保留字段
    reserved "phone", "email";
}

enum Gender {
    FEMALE = 0; // 必须0开始
}

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

// ListFeatures
std::unique_ptr<ClientReader<Feature>> reader(stub_->ListFeatures(&context, rect)); // 通过stub_
while (reader->Read(&feature)) { // 重复接收
    std::cout << "Found feature called " << feature.name() << " at " << feature.location().latitude() / kCoordFactor_ << ", " << feature.location().longitude() / kCoordFactor_ << << std::endl;
}
Status status = reader->Finish();
if (status.ok()) {
    std::cout << "ListFeatures rpc success." << std::endl;
} else {
    std::cout << "ListFeatures rpc failed." << std::endl;
}

// 主线程读
RouteNote server_note;
while (stream->Read(&server_note)) {
    std::cout << "Got message " << server_note.message() << " at " << server_note.location().latitude() << ", " << server_note.location().longitude() << std::endl;
}
writer.join(); // 等待写线程完成

grpc用于微服务所面临的问题：

1. 用户鉴权问题，鉴权方案的具体实现还包括了多种场景下的解决方案，例如：基于 JWT 或 OAuth 认证、基于多种细粒度授权方案进行授权、支持 OIDC 等。开发者需要根据具体的业务需求和安全要求，选择合适的鉴权方案。

docker

1
2
3

docker run -itd --name redis -p 6379:6379 --restart unless-stopped redis
docker exec -ti redis bash
redis-cli

redis

内存数据库、kv数据库、数据结构数据库
对象类型有哪些？底层使用了哪些数据结构

• string
  • int，字符串长度小于等于20且能转成整数，set teacher 1000000，type teacher，object encoding teacher
  • raw，字符串长度大于44
  • embstr，字符串长度小于等于44，cpu缓存中基本单位为cacheline 64字节，sdshdr头为9字节，加上’\0’，buf的最大长度为44，set teacher 1000000a，object encoding teacher
• list
  • quicklist，双向循环链表
  • ziplist，压缩链表
• hash，hmset role:1001 age 30 name mark sex 1, hgetall role:1001, hget role:1001 age，散列表：指针数组+数组长度+hash函数
  • dict/hashtable,节点数量大于512，或字符串长度大于64
  • ziplist，压缩列表，节点数量小于等于512（hash-max-ziplist-entries），且字符串长度小于等于64(hash-max-ziplist-value)
• set，sadd set 1 2 3 4 5,object encoding set,sadd set mark,object encoding set
  • intset，整数数组，元素都为整数，且节点数量小于等于512(set-max-intset-entries)
  • dict/hashtable，字典，元素有一个不为整数或者数量大于512
• zset，有序的结构
  • skiplist，跳表，数量大于128或者有一个字符串长度大于64
  • ziplist，压缩列表，节点数量小于等于128（zset-max-ziplist-entries）且字符串长度小于等于64(zset-max-ziplist-value)

单调栈分为单调递增栈和单调递减栈

1. 单调递增栈即栈内元素保持单调递增的栈
2. 同理单调递减栈即栈内元素保持单调递减的栈
   操作规则（下面都以单调递增栈为例）
3. 如果新的元素比栈顶元素大，就入栈
4. 如果新的元素较小，那就一直把栈内元素弹出来，直到栈顶比新元素小

柱状图中最大的矩形

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积。

1
2
3
4
5
6
7
8
9

stack<int> st;
for(int i = 0; i < nums.size(); i++)
{
	while(!st.empty() && st.top() > nums[i])
	{
		st.pop();
	}
	st.push(nums[i]);
}

什么是递归

周末你带着女朋友去电影院看电影，女朋友问你，咱们现在坐在第几排啊？电影院里面太黑了，看不清，没法数，现在你怎么办？

别忘了你是程序员，这个可难不倒你，递归就开始排上用场了。于是你就问前面一排的人他是第几排，你想只要在他的数字上加一，就知道自己在哪一排了。但是，前面的人也看不清啊，所以他也问他前面的人。就这样一排一排往前问，直到问到第一排的人，说我在第一排，然后再这样一排一排再把数字传回来。直到你前面的人告诉你他在哪一排，于是你就知道答案了。

这就是一个非常标准的递归求解问题的分解过程，去的过程叫“递”，回来的过程叫“归”。基本上，所有的递归问题都可以用递推公式来表示。刚刚这个生活中的例子，我们用递推公式将它表示出来就是这样的：

1

f(n)=f(n-1)+1 其中，f(1)=1

因为这些排序算法的时间复杂度是线性的，所以我们把这类排序算法叫作线性排序（Linear sort）。之所以能做到线性的时间复杂度，主要原因是，这三个算法是非基于比较的排序算法，都不涉及元素之间的比较操作。

桶排序（Bucket sort）

核心思想是将要排序的数据分到几个有序的桶里，每个桶里的数据再单独进行排序。桶内排完序之后，再把每个桶里的数据按照顺序依次取出，组成的序列就是有序的了。

如果要排序的数据有 n 个，我们把它们均匀地划分到 m 个桶内，每个桶里就有 k=n/m 个元素。每个桶内部使用快速排序，时间复杂度为 O(k * logk)。m 个桶排序的时间复杂度就是 O(m * k * logk)，因为 k=n/m，所以整个桶排序的时间复杂度就是 O(n*log(n/m))。当桶的个数 m 接近数据个数 n 时，log(n/m) 就是一个非常小的常量，这个时候桶排序的时间复杂度接近 O(n)。

桶排序对要排序数据的要求是非常苛刻的。要排序的数据需要很容易就能划分成 m 个桶，并且，桶与桶之间有着天然的大小顺序。这样每个桶内的数据都排序完之后，桶与桶之间的数据不需要再进行排序。

测速原理

往一个测速服务器post发送chunked数据，固定发到多少为止，可以采用多线程进行发送，统计发送的时间，这个时间是客户端的，仅仅作为参考，实际最后的测速结果是由服务端给出的。
要发送分块编码（chunked）格式的数据，可以使用以下步骤：

1. 设置HTTP请求头中的Transfer-Encoding字段为chunked。
2. 将数据分成多个块（chunk），每个块都包含一个长度和数据本身。
3. 将每个块发送到服务器，以回车换行符（\r\n）作为分隔符。
4. 在所有块发送完成后，发送一个长度为0的块作为结束符，以回车换行符（\r\n）结尾。

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

# 发送请求头
s.sendall(b'POST /api HTTP/1.1\r\n')
s.sendall(b'Host: example.com\r\n')
s.sendall(b'Content-Type: text/plain\r\n')
s.sendall(b'Transfer-Encoding: chunked\r\n')
s.sendall(b'\r\n')

# 发送第一个块
chunk1 = bytes('{:X}\r\n'.format(len(data1)), 'utf-8') + data1
s.sendall(chunk1)

# 发送第二个块
chunk2 = bytes('{:X}\r\n'.format(len(data2)), 'utf-8') + data2
s.sendall(chunk2)

# 发送结束块
s.sendall(b'0\r\n\r\n')

但测速可以不完全按照这个格式，只需要固定Transfer-Encoding: chunked就行，因为客户端是一直发数据，知道发到指定大小才停止发送，测速服务器在间隔1s没有接收到数据后，会告诉客户端的测速结果，等于是结束条件由服务端来决定了。

功能与实现原理

允许多个线程同时加读锁，但只允许一个线程加写锁，可以写嵌套，即一个线程里面加写锁了，可以继续在这个线程加写锁，不会阻塞。
当有线程在读取时，写入线程阻塞，当写入线程执行时，所有的读取线程都被阻塞。
允许嵌套加锁

1. 当前线程写入加锁时可以嵌套加读锁或写锁
2. 当前线程读取加锁时可以嵌套加读锁，但不能嵌套加写锁，否则当前线程会陷入死锁，原理为：已经作为只读区了，就不应该存在写了

加读锁的时候：

• 判断当前线程是不是使用写锁的线程，如果是的话，可以加读锁。
• 如果当前线程不是使用写锁的线程，需要等待写锁线程使用完、以及正在等待写的先使用完写锁，因为写的优先级高。

mem

读取文件：/proc/meminfo
MemTotal: 总内存
freeMem: Cached + MemFree + Buffers
程序占用mem：/proc/%d/status
VmRSS: 进程占用内存

cpu

读取文件：/proc/stat
包括：系统cpu、空闲、io等待、irq中断、软中断等。

1

fscanf(file, "%s%lld%lld%lld%lld%lld%lld%lld%lld%lld", temp, &user, &nice, &sys, &idle, &iowait, &irq, &softirq, &steal, &guest);