白菜君の技术库

前言

由于最近写了一篇关于 TCP 协议的文章，所以一些更加细节的内容，更偏向 TCP 独立协议的，拿出来独立记录。

为了获得最优的连接速率，使用 TCP 窗口来控制流速率（flow control），滑动窗口就是一种主要的机制。这个窗口允许源端在给定连接传送数据分段而不用等待目标端返回 ACK，一句话描述：窗口的大小决定在不需要对端响应（acknowledgement）情况下传送数据的数量。​ 官方定义：“The amount of octets that can be transmitted without receiving an acknowledgement from the other side”。

前言

由于最近看了 Redis5 的源码，所以对网络编程又进一步加深了了解，在这里，由于没有很系统的整理过 TCP/IP 协议相关的内容，所以写下这篇文章，以此来记录我最近学习到的内容，内容会分为以下几个方面。

• TCP/IP 协议，三次握手，四次挥手，协议细节
• 协议相关的细节，优化调整内核参数
• 模拟异常连接，优化调整内核参数
• 利用 C 语言，基于 epoll 写一个支持高并发的 TCP 聊天服务器

前言

从 main 函数开始，沿着代码执行路径，实际上我们可以一直追下去。但为了让本文不至于太过冗长，我们还是限定一下范围。本文的目标就定为：引领读者从 main 函数开始，一步步追踪下去，最终到达任一 Redis 命令的执行入口。

后续，再剖析各个命令的内部实现

本文基于 redis5.0 分支

为了表述清楚，本文按照如下思路进行：

• 先概括地介绍整个代码初始化流程（从 main 函数开始）和事件循环的结构；
• 再概括地介绍对于 Redis 命令请求的处理流程；
• 重点介绍事件机制；
• 对于前面介绍的各个代码处理流程，给出详细的代码调用关系，方便随时查阅；

根据这样几部分的划分，如果你只想粗读大致的处理流程，那么只需要阅读前两个部分就可以了。而后两部分则会深入到某些值得关注的细节。

数据结构中有很多树的结构，其中包括二叉树、二叉搜索树、2-3 树、红黑树等等。本文中对数据结构中常见的几种树的概念和用途进行了汇总，不求严格精准，但求简单易懂。

二叉树是数据结构中一种重要的数据结构，也是树表家族最为基础的结构。

二叉树的定义：二叉树的每个结点至多只有二棵子树(不存在度大于 2 的结点)，二叉树的子树有左右之分，次序不能颠倒。二叉树的第 i 层至多有 2^(i-1) 个结点；深度为 k 的二叉树至多有 (2^k)-1 个结点；对任何一棵二叉树 T，如果其终端结点数为 n0，度为 2 的结点数为 n2，则 n0=n2+1。

前言

什么是 makefile？或许很多 Winodws 的程序员都不知道这个东西，因为那些 Windows 的 IDE 都为你做了这个工作，但我觉得要作一个好的和 professional 的程序员，makefile 还是要懂。这就好像现在有这么多的 HTML 的编辑器，但如果你想成为一个专业人士，你还是要了解 HTML 的标识的含义。特别在 Unix 下的软件编译，你就不能不自己写 makefile 了，会不会写 makefile，从一个侧面说明了一个人是否具备完成大型工程的能力。因为，makefile 关系到了整个工程的编译规则。一个工程中的源文件不计数，其按类型、功能、模块分别放在若干个目录中，makefile 定义了一系列的规则来指定，哪些文件需要先编译，哪些文件需要后编译，哪些文件需要重新编译，甚至于进行更复杂的功能操作，因为 makefile 就像一个 Shell 脚本一样，其中也可以执行操作系统的命令。makefile 带来的好处就是——“自动化编译”，一旦写好，只需要一个 make 命令，整个工程完全自动编译，极大的提高了软件开发的效率。make 是一个命令工具，是一个解释 makefile 中指令的命令工具，一般来说，大多数的 IDE 都有这个命令，比如：Delphi 的 make，Visual C++的 nmake，Linux 下 GNU 的 make。可见，makefile 都成为了一种在工程方面的编译方法。

其实在我眼中，感觉 makefile 文件其实就是等于一个 shell 文件，用于处理“自动化”的内容，只不过它是由 C 语言程序本身解析的。

题目

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀，返回空字符串 “”。

示例 1:

1
2

输入: ["flower","flow","flight"]
输出: "fl"

示例 2:

1
2
3
4

输入: ["dog","racecar","car"]
输出: ""
解释: 输入不存在公共前缀。
说明:

所有输入只包含小写字母 a-z 。

解法

解法一：水平扫描法

首先，我们将描述一种查询一组字符串的最长公共前缀 LCP(S1...Sn)，我们得到结论是：

LCP(S1...Sn)=LCP(LCP(LCP(S1,S2),S3),...Sn)

从公式可以看出，两两比较的字符串的公共字符串就是我们的运算过程。

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

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

char *longestCommonPrefix(char **strs, int strSize)
{
  int i, j;

  if (strSize == 0)
  {
    return "";
  }

  char *str = (char *)malloc(sizeof(char) * 1000);

  strcpy(str, strs[0]);

  for (i = 1; i < strSize; i++)
  {
    j = 0;
    while (str[j] && strs[i][j] && str[j] == strs[i][j])
    {
      j++;
    }
    str[j] = '\0';
  }

  return str;
}

int main()
{
  char *strs[] = {"lees", "leetcode", "leet", "leets"};

  int size = sizeof(strs) / sizeof(char *);

  char *lcp;

  lcp = longestCommonPrefix(strs, size);

  printf("%s\n", lcp);

  return 0;
}

具体请查看我的 github 仓库项目

leetcode-practice

前言

版本：0.7

API 网关/网关，充当的职责无非以下几点：

• 鉴权
• 限流
• 分流
• 负载均衡

隐含的功能就是动态 upstream

大多与的 API 网关都是用利用 lua 实现的 Openresty 来实现的，因为它可以很好的和 nginx 结合在一起，可以同时运行 lua 脚本和 C 库，并且由于 lua 在协程上实现得十分早，对于 IO 密集型的处理十分的高效。

在给予 Openresty 实现的 API 网关中，有一些是比较出名的，例如 kong/orange

• kong 算是行业认为最强大成熟的一个组件的，但是过于复杂了。

• orange 利用插件的形式来处理请求，并且间接直接，易于二次开发和扩展

Etcd is a distributed, consistent key-value store for shared configuration and service discovery

是一个分布式的，一致的 key-value 存储，主要用途是共享配置和服务发现

服务注册与服务发现是在分布式服务架构中常常会涉及到的东西，业界常用的服务注册与服务发现工具有 ZooKeeper、etcd、Consul 和 Eureka。

服务注册与服务发现是在分布式服务架构中常常会涉及到的东西，业界常用的服务注册与服务发现工具有 ZooKeeper、etcd、Consul 和 Eureka。Consul 的主要功能有服务发现、健康检查、KV 存储、安全服务沟通和多数据中心。Consul 与其他几个工具的区别可以在这里查看 Consul vs. Other Software。

前言

map 指令是由 ngx_http_map_module 模块提供的，默认情况下安装 nginx 都会安装该模块。

map 的主要作用是创建自定义变量，通过使用 nginx 的内置变量，去匹配某些特定规则，如果匹配成功则设置某个值给自定义变量。 而这个自定义变量又可以作于他用。