发表于

「这是我参与11月更文挑战的第15天，活动详情查看：2021最后一次更文挑战」。

前言

上一篇文章写了openldap快速入门，这篇来写写相关api的调用

ldap基于go客户端包传送门: github.com/go-ldap/lda…

该包的功能如下:

  • 支持连接ldap服务器(加密，不加密等)
  • 支持admin和普通用户认证
  • 支持增删改查用户
  • 支持搜索、过滤以及条件查找

安装

先使用go将包下载到本地,因我们使用的openldap目前是v3版本

1
js复制代码go get github.com/go-ldap/ldap/v3

在代码编辑器里面引入既可使用

1
js复制代码import "github.com/go-ldap/ldap"

使用

连接，管理员认证

调用api的dial来创建一个新实例，后续直接调用

1
2
3
4
5
6
7
8
js复制代码l, err := ldap.Dial("tcp", "IP:389")
if err != nil {
   fmt.Println("连接失败",err)
}
err = l.Bind("cn=admin,dc=libaigo,dc=com", "密码")
if err != nil {
   fmt.Println("管理员认证失败",err)
}

创建用户

这部分第一步先创建用户，接着设置密码,可以用常规的方式设置固定的密码，也可以使用随机生成，这里演示一下随机生成

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
js复制代码//创建新用户
addResponse := ldap.NewAddRequest("uid=java1,ou=java,dc=libaigo,dc=com", []ldap.Control{})
addResponse.Attribute("cn",[]string{"java1"})
addResponse.Attribute("sn",[]string{"java1"})
addResponse.Attribute("uid",[]string{"java1"})
addResponse.Attribute("homeDirectory",[]string{"/home/java1"})
addResponse.Attribute("loginShell",[]string{"java1"})
addResponse.Attribute("gidNumber",[]string{"0"})
addResponse.Attribute("uidNumber",[]string{"8001"})
addResponse.Attribute("objectClass",[]string{"shadowAccount","posixAccount","top","inetOrgPerson"})
err = l.Add(addResponse)
if err != nil {
   fmt.Println("创建用户失败")
}

//随机给用户生成密码，并将新密码输出
passwordModifyRequest2 := ldap.NewPasswordModifyRequest("uid=java1,ou=java,dc=libaigo,dc=com", "", "")
passwordModifyResponse2, err := l.PasswordModify(passwordModifyRequest2)
if err != nil {
   fmt.Println(err)
}
generatedPassword  := passwordModifyResponse2.GeneratedPassword
fmt.Println("生成的密码: ",generatedPassword)

普通用户认证

普通用户只有认证权限，没有查询权限

1
2
3
4
5
6
7
8
9
10
11
12
js复制代码l, err := ldap.Dial("tcp", "IP:389")
if err != nil {
   fmt.Println("连接失败",err)
}

_, err = l.SimpleBind(&ldap.SimpleBindRequest{
   Username: "uid=node1,ou=node1,dc=libaigo,dc=com",
   Password: "node1",
})
if err != nil {
   fmt.Println(err)
}

修改用户信息

修改一些用户的描述之类的，用处不大

1
2
3
4
5
js复制代码modify := ldap.NewModifyRequest("uid=node1,ou=node1,dc=libaigo,dc=com",nil)
modify.Add("description",[]string{"this is test."})
modify.Replace("mail",[]string{"node1@test.com"})

err = l.Modify(modify)

修改用户密码

这个修改密码的函数支持不输入旧密码

1
2
3
4
5
6
js复制代码passwordModifyRequest := ldap.NewPasswordModifyRequest("uid=go,ou=go,dc=libaigo,dc=com", "", "123456")
//passwordModifyRequest := NewPasswordModifyRequest("", "OldPassword", "NewPassword") //设置新密码
_, err = l.PasswordModify(passwordModifyRequest)
if err != nil {
   fmt.Println("密码不能修改，错误信息: ",err.Error())
}

搜索全部用户

如果没有设置过滤条件，会查找出所有用户

1
2
3
4
5
6
7
8
9
10
11
js复制代码searchRequest := ldap.NewSearchRequest("dc=libaigo,dc=com",
   ldap.ScopeWholeSubtree, ldap.NeverDerefAliases, 0, 0, false,
   "(&(objectClass=organizationalPerson))",
   []string{"dn", "cn"}, nil)
search, err := l.Search(searchRequest)
if err != nil {
   fmt.Println(err)
}
for _,entry := range search.Entries {
   fmt.Printf("%s: %v\n", entry.DN, entry.GetAttributeValue("cn"))
}

搜索指定用户

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
js复制代码username := "node1"

searchRequest := ldap.NewSearchRequest("dc=libaigo,dc=com",
   ldap.ScopeWholeSubtree, ldap.NeverDerefAliases, 0, 0, false,
   fmt.Sprintf("(&(objectClass=organizationalPerson)(uid=%s))", ldap.EscapeFilter(username)),
   []string{"dn"},
   nil, )

sr,err := l.Search(searchRequest)
if err != nil {
   fmt.Println(err)
}

if len(sr.Entries) !=1 {
   fmt.Println("用户不存在或返回条目过多")
}

删除用户

构造一个用户传入到Del函数中既可

1
2
3
4
5
6
7
js复制代码err= l.Del(&ldap.DelRequest{
   DN:       "uid=java1,ou=java1,dc=libaigo,dc=com",
   Controls: nil,
})
if err != nil {
   fmt.Println("删除用户错误")
}

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

发表于

[这是我参与11月更文挑战的第9天，活动详情查看：2021最后一次更文挑战]

一、 安装

官方文档：doc.rust-lang.org/book/

1.编译环境选择

rust底层是依赖C环境，所以需要先安装C/C++编译环境, 有两种选择:

  • 安装微软的C++ build tools，即 Visual Studio 2019 生成工具；
  • 安装mingw/cygwin（模拟linux） ，需要配置 gnu toolchain开发环境（stable-x86_64-pc-windows-gnu）：
    • Cygwin 提供了Windows下的类Unix环境（Window）；
    • MinGW 是提供用于开发Window应用的开发环境（Linux）。

二、配置Cygwin

  1. 初始化与更新 Cygwin 包

为 64 位版本的 Windows 安装和更新 Cygwin：当您想要更新或安装适用于 64 位 Windows 的 Cygwin 软件包 时，请运行setup-x86_64.exe。该签名的设置，x86_64.exe可以用来验证这个二进制文件的有效性。

验证安装程序的签名：

  • 1
    2
    css复制代码gpg --recv-key 1A698DE9E2E56300
    gpg --keyid-format=long --with-fingerprint --verify setup-x86_64.exe.sig setup-x86_64.exe

通过Cygwin Setup 可以更新包，为了能够通过命令安装软件，可以先使用该程序添加GIT。

  • 打开后，直接下一步即可；
  • 到了包管理页面找到GIT选择版本号即可；
  • 再通过GIT安装apt-cyg。
1
2
3
4
5
bash复制代码git clone https://github.com/transcode-open/apt-cyg.git
cd apt-cyg/
chmod +x apt-cyg
cp apt-cyg /bin
apt-cyg install wget

注：wget安装会提示缺少lynx，需要通过Cygwin安装程序安装。

  1. 在windows命令下使用cygwin

需要添加环境变量，Path 添加 D:\cygwin64\bin,刷新环境变量set PATH=C。

在Window下通过以下命令可以进入类unix环境：

1
2
3
bash复制代码D:\Environment\Rust>bash
	86178@LAPTOP-KFPIFLPS /cygdrive/d/Environment/Rust
	86178@LAPTOP-KFPIFLPS /cygdrive/d/Environment/Rust exit
  1. Rustup前置程序

为了通过 Cygwin配置Rustup，需要通过Cygwin安装程序安装以下包：

  • httpd
  • make
  • ls
  • curl

三、Rustup

Rustup是Rust 安装程序和版本管理工具，相关资源

  1. 配置环境变量
1
2
3
4
5
6
7
ini复制代码CARGO_HOME=D:\Environment\Rust\.cargo
RUSTUP_HOME=D:\Environment\Rust\.rustup
RUSTUP_UPDATE_ROOT=http://mirrors.ustc.edu.cn/rust-static/rustup
RUSTUP_DIST_SERVER=http://mirrors.ustc.edu.cn/rust-static
path 添加%CARGO_HOME%\bin

set PATH=C
  1. 安装程序

打开rustup-init.exe文件，输入2，自定义安装选项，如下：

1
2
3
4
vbnet复制代码host triple：x86_64-pc-windows-gnu 版本
default toolchain：stable 稳定版
profile: complete 表示完全安装
modify PATH variable：y 表示按照环境变量定义的路径安装

查看安装结果：

1
2
makefile复制代码C:\Users\86178>cargo version
cargo 1.52.0 (69767412a 2021-04-21)

查看版本：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
sql复制代码C:\Users\86178>rustup show
Default host: x86_64-pc-windows-gnu
rustup home:  D:\Environment\Rust\.rustup

installed toolchains
--------------------

stable-x86_64-pc-windows-gnu (default)
stable-x86_64-pc-windows-msvc

active toolchain
----------------

stable-x86_64-pc-windows-gnu (default)
rustc 1.52.1 (9bc8c42bb 2021-05-09)
  1. Hello World

一个Hello World的例子。

3.1 配置

在windows配置项目：

1
2
3
4
shell复制代码> mkdir "%USERPROFILE%\projects"
> cd /d "%USERPROFILE%\projects"
> mkdir hello_world
> cd hello_world

创建一个新的源文件并将其命名为main.rs。Rust 文件总是以.rs扩展名结尾。如果您在文件名中使用多个单词，请使用下划线将它们分开。例如，使用hello_world.rs而不是 helloworld.rs。

1
2
3
rust复制代码fn main() {
    println!("Hello, world!");
}

注：将左大括号与函数声明放在同一行是一种很好的风格，中间加一个空格。如果你想在 Rust 项目中坚持标准风格，你可以使用一个自动格式化工具rustfmt来以特定的风格格式化你的代码.

  • Rust 风格是缩进四个空格，而不是一个制表符;
  • println!调用一个 Rust 宏。如果它改为调用函数，则输入为println（不带!）
  • 大多数 Rust 代码行都以分号结尾。

3.2 编译与运行

在运行 Rust 程序之前，您必须使用 Rust 编译器通过输入rustc命令并将源文件的名称传递给它来编译它

运行方式如下：

1
2
3
4
5
6
7
8
9
shell复制代码-- Linux
$ rustc main.rs  # 编译
$ ./main  # 运行
Hello, world!

-- Window
> rustc main.rs
> .\main.exe
Hello, world!

Rust 是一种提前编译语言，这意味着您可以编译程序并将可执行文件提供给其他人，他们甚至可以在没有安装 Rust 的情况下运行它。如果你给某人一个.rb、.py或 .js文件，他们需要安装一个 Ruby、Python 或 JavaScript 实现（分别）。但是在这些语言中，您只需要一个命令来编译和运行您的程序。一切都是语言设计的权衡。

四、Cargo

Cargo 是 Rust 的构建系统和包管理器。大多数 Rustaceans 使用这个工具来管理他们的 Rust 项目，因为 Cargo 为你处理了很多任务，比如构建代码、下载代码依赖的库以及构建这些库。（我们将您的代码需要的库称为依赖项。）

  1. Cargo创建项目

查看是否安装cargo：

1
rust复制代码cargo --version

使用 Cargo 创建项目：

1
2
3
4
5
rust复制代码$ cargo new hello_cargo
$ cd hello_cargo

-- 使用现成的git存储库创建项目
cargo new --vcs=git.
  1. 文件结构

生成以下文件

  • src
    • main.rs
  • Cargo.toml
  • .gitignore
  • .git Git存储库

Cargo.toml（Tom's Obvious, Minimal Language）的内容如下：

1
2
3
4
5
6
7
8
9
ini复制代码[package]
name = "hello_cargo"
version = "0.1.0"
authors = ["XXX <XXX@gmail.com>"]
edition = "2018"

# See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html

[dependencies]

使用 Cargo 可以组织项目结构，使所有对象都有迹可循。

  1. 编译与运行项目
1
2
3
4
5
6
7
8
9
10
scss复制代码$ cargo build
   Compiling hello_cargo v0.1.0 (file:///projects/hello_cargo)
    Finished dev [unoptimized + debuginfo] target(s) in 2.85 secs
$ cargo run

// 此命令会快速检查您的代码以确保它可以编译但不生成可执行文件
$ cargo check 

// 为发布而构建
cargo build --release
  1. 相关实例
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
rust复制代码use std::io; //使用use 语句将该类型显式引入作用域

fn main() {
    println!("Hello, world!");
    println!("Guess Number");
    // 存储用户输入
    let mut guess = String::new();
    // stdin函数返回 的一个实例std::io::Stdin，它是一种表示终端标准输入句柄的类型。
    // read_line 表示读取一行到缓冲区guess
    // expect 表示异常处理
    io::stdin()
        .read_line(&mut guess)
        .expect("faild");
    
    println!("You guessed: {}", guess);
}

read_line函数源码如下：

1
2
3
4
rust复制代码    #[stable(feature = "rust1", since = "1.0.0")]
    pub fn read_line(&self, buf: &mut String) -> io::Result<usize> {
        self.lock().read_line(buf)
    }

read_line将用户输入的内容放入我们传递给它的字符串中，但它也返回一个值Result，表示函数运行结果，这个模块有不同的实现，例如io::Result。Result类型是enum，通常被称为枚举。枚举是一种可以具有一组固定值的类型，这些值称为枚举的变体。对于Result，变体是Ok或Err。所述Ok变体指示操作是成功的，并且内部Ok是成功生成值。该Err变种意味着操作失败，并Err包含有关操作如何或为何失败的信息。

如果您不调用expect，程序将编译，但会收到警告。

五、参考资料

Cygwin安装新的软件或者程序

Windows 下不污染环境安装 Rust 编译器

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

发表于

这是我参与11月更文挑战的第16天，活动详情查看：2021最后一次更文挑战

近段时间需要实现一个转发 post 请求到指定后端服务的小工具，由于一直想学习 gin 框架，所以就使用这个框架进行尝试，预计会产生几篇文章。本文研究如何利用 nginx 容器和后端服务进行转发工具的测试。

概述

转发的工具实现起来比较简单，但为了验证，还需要使用其它工具配合，本文自编后端程序，并使用 nginx 实现多个后端程序的转发。

为方便理解，下面给出示例图。

不使用 nginx 实现转发如下图所示：

1.png

使用 nginx 实现转发如下图所示：

2.png

注1：两个图片相近，注意图中 URL 的变化。

注2：在本文中，客户端可以跨过 nginx 直接访问后端的服务，在实际中似乎不太好，因只做演示，故不再深入考虑。

后端服务

前面文章已经实现了简单的后端服务响应函数，此处不再列出。需要注意的是，因本系列转发和后端均用同一套代码，如果要在程序中启动后端服务，必须修改后端服务可执行文件名称，参考前文代码。

nginx容器启动及重启

本文使用镜像centos/nginx-116-centos7进行测试。简单启动如下：

1
ruby复制代码docker run -itd --name nginx -p 8080:8080 -v $PWD:/opt/bin centos/nginx-116-centos7 bash

实践中使用docker-compose启动，docker-compose.yml文件如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
bash复制代码version: '2'

services:
  nginx:
    image: centos/nginx-116-centos7
    container_name: nginx
    command: /bin/bash -c "/home/latelee/bin/run.sh"
    volumes:
      - $PWD/bin:/home/latelee/bin
      - $PWD/nginx/log:/var/opt/rh/rh-nginx116/log/nginx
      - $PWD/nginx/etc:/etc/nginx
      - /etc/localtime:/etc/localtime
    #environment:
    #  - ORACLE_HOME=/work/instantclient_12_1
    #  - TNS_ADMIN=$ORACLE_HOME
    ports:
      - 8080:8080
      - 8090:8090

注：后端服务程序（和启动脚本）以及 nginx 配置文件均放到主机目录，因为这样更容易更新。

为了在容器启动时运行自定义的命令，需要关闭 nginx 服务的后台执行，启动脚本 run.sh 内容如下：

1
2
3
4
5
6
7
8
9
bash复制代码#!/bin/bash

echo "run..."
cd /home/latelee/bin

nginx -g "daemon off;"&

sleep 1
./httpforward.exe -p 8090

关于在容器中启动 nginx 的方法，官方 docker 有介绍：

If you add a custom CMD in the Dockerfile, be sure to include -g daemon off; in the CMD in order for nginx to stay in the foreground, so that Docker can track the process properly (otherwise your container will stop immediately after starting)!

大意是说，当我们自定义启动命令时，必须添加-g daemon off，否则自定义命令启动完毕后，容器就会自动退出。

启动容器：

1
复制代码docker-compose up -d

查看日志：

1
复制代码docker-compose logs -f

默认情况下 nginx 已经启动了。如果修改了配置。可以重启容器，也可以在容器内重启，重启命令为nginx -s reload。nginx -s仅支持4个参数：stop, quit, reopen, reload，官方文档将其称为信号（signal）。如果执行nginx -s stop停止 nginx，再次重启，会提示nginx: [error] open() "/var/opt/rh/rh-nginx116/run/nginx/nginx.pid" failed (2: No such file or directory)。因此，修改 nginx 配置后，使用reload即可。

nginx 转发的一些测试

在笔者环境中，不论在容器内，还是在物理机，nginx 配置文件为/etc/nginx/nginx.conf（注：实际，nginx 还会读取/etc/nginx/conf.d目录，但不在本文讨论范围），修改该文件后，必须执行nginx -s reload重启 nginx。

对于 location 的配置，一般如下：

1
2
3
4
5
6
bash复制代码location /fee/9000 {
        proxy_pass http://127.0.0.1:9000;
        proxy_set_header Host $proxy_host;
        proxy_set_header X-Real-IP $remote_addr;
        proxy_set_header X-Forwarded-For $proxy_add_x_forwarded_for;
}

发送到 nginx 服务器的请求，如果 URL 为/fee/9000，则转发到本地的 9000 端口的服务。（注：/fee/9000还可以继续添加后缀 URL，但不是本次讨论的范围），其它转发类似。

经测试，直接用proxy_pass字段指定后端服务地址即可。如下：

1
2
3
arduino复制代码location /fee/9000 {
        proxy_pass http://127.0.0.1:9000;
}

测试中发现，当使用上述转发规则时，后端程序必须实现/fee/9000的响应，即在容器中能正常请求http://127.0.0.1:9000/fee/9000。如果不实现，会提示 404。而本文的后端不能响应带后缀的URL。

经查，在后端程序 URL 后添加斜杠/可解决问题，如下：

1
2
3
arduino复制代码location /fee/9000 {
        proxy_pass http://127.0.0.1:9000/;
}

两者对比如下：

1
2
3
4
ruby复制代码不加斜杠：http://127.0.0.1:8080/fee/9000  --> http://127.0.0.1:9000/fee/9000
添加斜杠：http://127.0.0.1:8080/fee/9000  --> http://127.0.0.1:9000/

添加斜杠的扩展：http://127.0.0.1:8080/fee/9000/foo  --> http://127.0.0.1:9000/foo

对于笔者的应用，请求后端程序的URL必须是http://127.0.0.1:9000/的形式，不能再额外添加后缀，由于对 nginx 研究未深，暂不展开讨论。

实验结果

请求命令：

1
2
3
4
css复制代码$ curl http://192.168.28.11:8090/fee/test -X POST -F  "file=@sample.json"
  % Total    % Received % Xferd  Average Speed   Time    Time     Time  Current
                                 Dload  Upload   Total   Spent    Left  Speed
100   434  100    98  100   336   3920  13440 --:--:-- --:--:-- --:--:-- 18083{"code":0,"data":{"result":"ok in back end server, port: 9001 info: run in port 9001"},"msg":"ok"}

转发工具：

1
2
arduino复制代码nginx    | got url:  http://127.0.0.1:8080/fee/9001
nginx    | [GIN] 2021/11/14 - 11:45:30 | 200 |   10.002826ms |    192.168.28.5 | POST     "/fee/test"

nginx 日志：

1
2
c复制代码==> nginx/log/access.log <==
127.0.0.1 - - [14/Nov/2021:11:45:30 +0800] "POST /fee/9001 HTTP/1.1" 200 98 "-" "Go-http-client/1.1" "-"

小结

本文中，自编的转发工具要管理和配置后端程序以及 nginx，即启动若干后端程序，根据规则分配端口号（从9000开始）和 URL，将其写到 nginx 配置文件，最后重启 nginx 服务。——当然，这些都是使用较简单的方法。

在启动后端程序中，由于笔者使用相同的代码，因此花了一些时间排查问题。

在测试 nginx 转发 URL 时，也花了较多的时间（前后大概2个深夜的时间）。

在后续中，笔者将研究如何自实现负载均衡算法。——计划做此事已了大半年，趁此机会抽点时间搞下。

参考

关于转发 URL 的讨论 stackoverflow.com/questions/4…

nginx镜像： hub.docker.com/_/nginx

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

发表于

面试官：要不你来讲讲你最近在看的点呗？可以拉出来一起讨论下

候选者：最近在看「去重」和「幂等」相关的内容

面试官：那你就先来聊聊你对「去重」和「幂等」的理解吧

候选者：我认为「幂等」和「去重」它们很像，我也说不出他们之间的严格区别

候选者：我说下我个人的理解，我也不知道对不对

候选者：「去重」是对请求或者消息在「一定时间内」进行去重「N次」

候选者：「幂等」则是保证请求或消息在「任意时间内」进行处理，都需要保证它的结果是一致的

候选者：不论是「去重」还是「幂等」，都需要对有一个「唯一 Key」，并且有地方对唯一Key进行「存储」

候选者：以项目举例，我维护的「消息管理平台」是有「去重」的功能的：「5分钟相同内容消息去重」「1小时内模板去重」「一天内渠道达到N次阈值去重」…

候选者：再次强调下「幂等」和「去重」的本质：「唯一Key」+「存储」

面试官：那你是怎么做的呢

候选者：不同的业务场景，唯一Key是不一样的，由业务决定

候选者：存储选择挺多的，比如「本地缓存」/「Redis」/「MySQL」/「HBase」等等，具体选取什么，也跟业务有关

候选者：比如说，在「消息管理平台」这个场景下，我存储选择的「Redis」（读写性能优越），Redis也有「过期时间」方便解决「一定时间内」的问题

候选者：而唯一Key，自然就是根据不同的业务构建不同的。

候选者：比如说「5分钟相同内容消息去重」，我直接MD5请求参数作为唯一Key。「1小时模板去重」则是「模板ID+userId」作为唯一Key，「一天内渠道去重」则是「渠道ID+userId」作为唯一Key…

面试官：既然提到了「去重」了，你听过布隆过滤器吗？

候选者：自然是知道的啦

面试官：来讲讲布隆过滤器吧，你为什么不用呢？

候选者：布隆过滤器的底层数据结构可以理解为bitmap，bitmap也可以简单理解为是一个数组，元素只存储0和1，所以它占用的空间相对较小

候选者：当一个元素要存入bitmap时，其实是要去看存储到bitmap的哪个位置，这时一般用的就是哈希算法，存进去的位置标记为1

候选者：标记为1的位置表示存在，标记为0的位置标示不存在

候选者：布隆过滤器是可以以较低的空间占用来判断元素是否存在进而用于去重，但是它也有对应的缺点

候选者：只要使用哈希算法离不开「哈希冲突」，导致有存在「误判」的情况

候选者：在布隆过滤器中，如果元素判定为存在，那该元素「未必」真实存在。如果元素判定为不存在，那就肯定是不存在

候选者：这应该不用我多解释了吧？（结合「哈希算法」和「标记为1的位置表示存在，标记为0的位置标示不存在」这两者就能得出上面结论）

候选者：布隆过滤器也不能「删除」元素（也是哈希算法的局限性，在布隆过滤器中是不能准确定位一个元素的）

候选者：如果要用的话，布隆过滤器的实现可以直接上Guava已经实现好的，不过这个是单机的

候选者：而分布式下的布隆过滤器，一般现在会用Redis，但也不是没个公司都会部署布隆过滤器的Redis版（还是有局限，像我以前公司就没有）

候选者：所以，目前我负责的项目都是没有用布隆过滤器的（：

候选者：如果「去重」开销比较大，可以考虑建立「多层过滤」的逻辑

候选者：比如，先看看『本地缓存』能不能过滤一部分，剩下「强校验」交由『远程存储』（常见的Redis或者DB）进行二次过滤

面试官：嗯，那我就想起你上一次回答Kafka的时候了

面试官：当时你说在处理订单时实现了at least one + 幂等

面试官：幂等处理时：前置过滤使用的是Redis，强一致校验时使用的是DB唯一索引，也是为了提高性能，对吧？

面试官：唯一Key 好像就是 「订单编号 + 订单状态」

候选者：面试官你记性真的好！

候选者：一般我们需要对数据强一致性校验，就直接上MySQL（DB），毕竟有事务的支持

候选者：「本地缓存」如果业务适合，那可以作为一个「前置」判断

候选者：Redis高性能读写，前置判断和后置均可（：

候选者：而HBase则一般用于庞大数据量的场景下（Redis内存太贵，DB不够灵活也不适合单表存大量数据）

候选者：至于幂等，一般的存储还是「Redis」和「数据库」

候选者：最最最最常见的就是数据库「唯一索引」来实现幂等（我所负责的好几个项目都是用这个）

候选者：构建「唯一Key」是业务相关的事了（：一般是用自己的业务ID进行拼接，生成一个”有意义”的唯一Key

候选者：当然，也有用「Redis」和「MySQL」实现分布式锁来实现幂等的（：

候选者：但Redis分布式锁是不能完全保证安全的，而MySQL实现分布式锁（乐观锁和悲观锁还是看业务吧，我是没用到过的）

候选者：网上有很多实现「幂等」的方案，本质上都是围绕着「存储」和「唯一Key」做了些变种，然后取了个名字…

候选者：总的来说，换汤不换药（：

面试官：嗯…了解了

欢迎关注我的微信公众号【Java3y】来聊聊Java面试，对线面试官系列持续更新中！

【对线面试官-移动端】系列 一周两篇持续更新中！

【对线面试官-电脑端】系列 一周两篇持续更新中！

原创不易！！求三连！！

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

发表于

这是我参与11月更文挑战的第16天，活动详情查看：2021最后一次更文挑战。

在 Web 应用中，有时需要在响应请求前或者响应请求后做一些处理，为了让每个视图函数避免编写重复功能的代码，Flask 提供了请求钩子，它们可以用来注册在请求处理的不同阶段执行的处理函数，我们就可以轻易的对请求进行预处理和后处理。

Flask 常用请求钩子如下：

  • before_first_request：在处理第一个请求之前运行
  • before_request：在每次请求之前运行，如果没有未处理的异常抛出，会在每个请求结束后运行
  • after_request：如果没有未处理的异常抛出，在每次请求结束后运行
  • teardown_request：即使有未处理的异常抛出，也会在每个请求结束后运行

这些请求钩子是使用装饰器方式实现，用法也非常简单，使用起来和app.route()装饰器基本相同。下面使用这些请求钩子装饰一些函数，用于在每次请求前后做一些处理，为了方便理解，只是单纯打印一句话。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
python复制代码@app.before_first_request
def before_first_request():
    print('before_first_request')


@app.before_request
def before_request():
    print('before_request')


@app.after_request
def after_request(response):
    print('after_request')
    return response


@app.teardown_request
def teardown_request(e):
    print('teardown_request')


@app.route('/test')
def test():
    return 'test'

第一次请求控制台输出：

image.png

第二次请求控制台输出：

image.png

下面是请求钩子的一些常见应用场景：

  • before_first_request：第一个请求之前运行，可以进行一些 Web 程序的初始化操作
  • before_request：每次请求之前运行，可以进行数据库连接的创建操作、用户的权限校验操作等
  • after_request：我们经常在视图函数中进行数据库操作，比如更新、插入，之后需要将更改提交到数据库中，提交更改的代码就可以放到 after_request 钩子注册的函数中
  • teardown_request：可以接收视图函数的异常，一般用来记录错误日志

注意：
每个请求钩子可以注册任意多个处理函数，函数名也并不是必须和钩子名称相同。如果有多个 before_request，执行顺序从上往下；after_request 接收一个响应对象，并且返回同一个或者更新后的响应对象，多个 after_request 执行顺序是从下往上。

原创不易，如果小伙伴们觉得有帮助，麻烦点个赞再走呗~

最后，感谢女朋友在工作和生活中的包容、理解与支持 ！

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

发表于

欢迎访问我的GitHub

github.com/zq2599/blog…

内容：所有原创文章分类汇总及配套源码，涉及Java、Docker、Kubernetes、DevOPS等；

本篇概览

  • 本文是《Spring Cloud Gateway实战》系列的第三篇，前文介绍了多种路由配置方式，它们存在一个共同问题：路由配置变更后必须重启Gateway应用才能生效，聪明的您一下就看出了问题关键：这样不适合生产环境！
  • 如何让变动后的路由立即生效，而无需重启应用呢？这就是今天的主题：动态路由

设计思路

  • 这里提前将设计思路捋清楚，总的来说就是将配置放在nacos上，写个监听器监听nacos上配置的变化，将变化后的配置更新到Gateway应用的进程内：
  • 上述思路体现在代码中就是下面三个类：
  1. 将操作路由的代码封装到名为RouteOperator的类中，用此类来删除和增加进程内的路由
  2. 做一个配置类RouteOperatorConfig，可以将RouteOperator作为bean注册在spring环境中
  3. 监听nacos上的路由配置文件，一旦有变化就取得最新配置，然后调用RouteOperator的方法更新进程内的路由，这些监听nacos配置和调用RouteOperator的代码都放RouteConfigListener类中
  • 在本次实战中，一共涉及三个配置文件，其中bootstrap.yml + gateway-dynamic-by-nacos是大家熟悉的经典配置，bootstrap.yml 在本地，里面是nacos的配置，gateway-dynamic-by-nacos在naocs上，里面是整个应用所需的配置（例如服务端口号、数据库等），还有一个配置文件在nacos上，名为gateway-json-routes，是JSON格式的，里面是路由配置，之所以选择JSON格式，是因为JSON比yml格式更易于解析和处理；
  • 最终，整个微服务架构如下图所示：

在这里插入图片描述

  • 思路已清晰，开始编码

源码下载

  • 本篇实战中的完整源码可在GitHub下载到，地址和链接信息如下表所示(github.com/zq2599/blog…%EF%BC%9A)
名称 链接 备注
项目主页 github.com/zq2599/blog… 该项目在GitHub上的主页
git仓库地址(https) github.com/zq2599/blog… 该项目源码的仓库地址，https协议
git仓库地址(ssh) git@github.com:zq2599/blog_demos.git 该项目源码的仓库地址，ssh协议
  • 这个git项目中有多个文件夹，本篇的源码在spring-cloud-tutorials文件夹下，如下图红框所示：

在这里插入图片描述

  • spring-cloud-tutorials是父工程，下属多个子工程，今天的实战的代码是gateway-dynamic-by-nacos，如下图所示：

在这里插入图片描述

编码

  • 新增名为gateway-dynamic-by-nacos的工程，其pom.xml内容如下，注意中文注释的说明：
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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
xml复制代码<?xml version="1.0" encoding="UTF-8"?>
<project xmlns="http://maven.apache.org/POM/4.0.0"
         xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
         xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd">
    <parent>
        <artifactId>spring-cloud-tutorials</artifactId>
        <groupId>com.bolingcavalry</groupId>
        <version>1.0-SNAPSHOT</version>
    </parent>
    <modelVersion>4.0.0</modelVersion>

    <artifactId>gateway-dynamic-by-nacos</artifactId>

    <dependencies>
        <dependency>
            <groupId>com.bolingcavalry</groupId>
            <artifactId>common</artifactId>
            <version>${project.version}</version>
        </dependency>

        <dependency>
            <groupId>org.springframework.cloud</groupId>
            <artifactId>spring-cloud-starter-gateway</artifactId>
        </dependency>

        <dependency>
            <groupId>io.projectreactor</groupId>
            <artifactId>reactor-test</artifactId>
            <scope>test</scope>
        </dependency>

        <dependency>
            <groupId>org.springframework.boot</groupId>
            <artifactId>spring-boot-starter-test</artifactId>
            <scope>test</scope>
        </dependency>

        <!-- 把springboot内容断点暴露出去 -->
        <dependency>
            <groupId>org.springframework.boot</groupId>
            <artifactId>spring-boot-starter-actuator</artifactId>
        </dependency>

        <!-- 使用bootstrap.yml的时候，这个依赖一定要有 -->
        <dependency>
            <groupId>org.springframework.cloud</groupId>
            <artifactId>spring-cloud-starter-bootstrap</artifactId>
        </dependency>

        <!-- 路由策略使用lb的方式是，这个依赖一定要有 -->
        <dependency>
            <groupId>org.springframework.cloud</groupId>
            <artifactId>spring-cloud-starter-loadbalancer</artifactId>
        </dependency>

        <!--nacos:配置中心-->
        <dependency>
            <groupId>com.alibaba.cloud</groupId>
            <artifactId>spring-cloud-starter-alibaba-nacos-config</artifactId>
        </dependency>

        <!--nacos:注册中心-->
        <dependency>
            <groupId>com.alibaba.cloud</groupId>
            <artifactId>spring-cloud-starter-alibaba-nacos-discovery</artifactId>
        </dependency>
    </dependencies>

    <build>
        <plugins>
            <!-- 如果父工程不是springboot，就要用以下方式使用插件，才能生成正常的jar -->
            <plugin>
                <groupId>org.springframework.boot</groupId>
                <artifactId>spring-boot-maven-plugin</artifactId>
                <configuration>
                    <mainClass>com.bolingcavalry.gateway.GatewayApplication</mainClass>
                </configuration>
                <executions>
                    <execution>
                        <goals>
                            <goal>repackage</goal>
                        </goals>
                    </execution>
                </executions>
            </plugin>
        </plugins>
    </build>
</project>
  • 配置文件bootstrap.yml，上面只有nacos，可见其他配置信息还是来自naocs：
1
2
3
4
5
6
7
8
9
yml复制代码spring:
  application:
    name: gateway-dynamic-by-nacos
  cloud:
    nacos:
      config:
        server-addr: 127.0.0.1:8848
        file-extension: yml
        group: DEFAULT_GROUP
  • 负责处理进程内路由配置的类是RouteOperator，如下所示，可见整个配置是字符串类型的，用了Jackson的ObjectMapper进行反序列化（注意，前面的实战中配置文件都是yml格式，但本例中是JSON，稍后在nacos上配置要用JSON格式），然后路由配置的处理主要是RouteDefinitionWriter类型的bean完成的，为了让配置立即生效，还要用applicationEventPublisher发布进程内消息：
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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
java复制代码package com.bolingcavalry.gateway.service;

import com.fasterxml.jackson.core.JsonProcessingException;
import com.fasterxml.jackson.core.type.TypeReference;
import com.fasterxml.jackson.databind.ObjectMapper;
import lombok.extern.slf4j.Slf4j;
import org.springframework.cloud.gateway.event.RefreshRoutesEvent;
import org.springframework.cloud.gateway.route.RouteDefinition;
import org.springframework.cloud.gateway.route.RouteDefinitionWriter;
import org.springframework.context.ApplicationEventPublisher;
import org.springframework.util.StringUtils;
import reactor.core.publisher.Mono;
import java.util.ArrayList;
import java.util.List;

@Slf4j
public class RouteOperator {
    private ObjectMapper objectMapper;

    private RouteDefinitionWriter routeDefinitionWriter;

    private ApplicationEventPublisher applicationEventPublisher;

    private static final List<String> routeList = new ArrayList<>();

    public RouteOperator(ObjectMapper objectMapper, RouteDefinitionWriter routeDefinitionWriter, ApplicationEventPublisher applicationEventPublisher) {
        this.objectMapper = objectMapper;
        this.routeDefinitionWriter = routeDefinitionWriter;
        this.applicationEventPublisher = applicationEventPublisher;
    }

    /**
     * 清理集合中的所有路由，并清空集合
     */
    private void clear() {
        // 全部调用API清理掉
        routeList.stream().forEach(id -> routeDefinitionWriter.delete(Mono.just(id)).subscribe());
        // 清空集合
        routeList.clear();
    }

    /**
     * 新增路由
     * @param routeDefinitions
     */
    private void add(List<RouteDefinition> routeDefinitions) {

        try {
            routeDefinitions.stream().forEach(routeDefinition -> {
                routeDefinitionWriter.save(Mono.just(routeDefinition)).subscribe();
                routeList.add(routeDefinition.getId());
            });
        } catch (Exception exception) {
            exception.printStackTrace();
        }
    }

    /**
     * 发布进程内通知，更新路由
     */
    private void publish() {
        applicationEventPublisher.publishEvent(new RefreshRoutesEvent(routeDefinitionWriter));
    }

    /**
     * 更新所有路由信息
     * @param configStr
     */
    public void refreshAll(String configStr) {
        log.info("start refreshAll : {}", configStr);
        // 无效字符串不处理
        if (!StringUtils.hasText(configStr)) {
            log.error("invalid string for route config");
            return;
        }

        // 用Jackson反序列化
        List<RouteDefinition> routeDefinitions = null;

        try {
            routeDefinitions = objectMapper.readValue(configStr, new TypeReference<List<RouteDefinition>>(){});
        } catch (JsonProcessingException e) {
            log.error("get route definition from nacos string error", e);
        }

        // 如果等于null，表示反序列化失败，立即返回
        if (null==routeDefinitions) {
            return;
        }

        // 清理掉当前所有路由
        clear();

        // 添加最新路由
        add(routeDefinitions);

        // 通过应用内消息的方式发布
        publish();

        log.info("finish refreshAll");
    }
}
  • 做一个配置类RouteOperatorConfig.java，将实例化后的RouteOperator注册到spring环境中：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
java复制代码package com.bolingcavalry.gateway.config;

import com.bolingcavalry.gateway.service.RouteOperator;
import com.fasterxml.jackson.databind.ObjectMapper;
import org.springframework.cloud.gateway.route.RouteDefinitionWriter;
import org.springframework.context.ApplicationEventPublisher;
import org.springframework.context.annotation.Bean;
import org.springframework.context.annotation.Configuration;

@Configuration
public class RouteOperatorConfig {
    @Bean
    public RouteOperator routeOperator(ObjectMapper objectMapper,
                                       RouteDefinitionWriter routeDefinitionWriter,
                                       ApplicationEventPublisher applicationEventPublisher) {

        return new RouteOperator(objectMapper,
                routeDefinitionWriter,
                applicationEventPublisher);
    }
}
  • 最后是nacos的监听类RouteConfigListener，可见关键技术点是ConfigService.addListener，用于添加监听，里面就是配置发生变化后更新路由的逻辑，另外还有很重要的一步：立即调用getConfig方法取得当前配置，刷新当前进程的路由配置：
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
java复制代码package com.bolingcavalry.gateway.service;

import com.alibaba.nacos.api.NacosFactory;
import com.alibaba.nacos.api.config.ConfigService;
import com.alibaba.nacos.api.config.listener.Listener;
import com.alibaba.nacos.api.exception.NacosException;
import lombok.extern.slf4j.Slf4j;
import org.springframework.beans.factory.annotation.Autowired;
import org.springframework.beans.factory.annotation.Value;
import org.springframework.stereotype.Component;
import javax.annotation.PostConstruct;
import java.util.concurrent.Executor;

@Component
@Slf4j
public class RouteConfigListener {

    private String dataId = "gateway-json-routes";

    private String group = "DEFAULT_GROUP";

    @Value("${spring.cloud.nacos.config.server-addr}")
    private String serverAddr;

    @Autowired
    RouteOperator routeOperator;

    @PostConstruct
    public void dynamicRouteByNacosListener() throws NacosException {

        ConfigService configService = NacosFactory.createConfigService(serverAddr);

        // 添加监听，nacos上的配置变更后会执行
        configService.addListener(dataId, group, new Listener() {

            public void receiveConfigInfo(String configInfo) {
                // 解析和处理都交给RouteOperator完成
                routeOperator.refreshAll(configInfo);
            }

            public Executor getExecutor() {
                return null;
            }
        });

        // 获取当前的配置
        String initConfig = configService.getConfig(dataId, group, 5000);

        // 立即更新
        routeOperator.refreshAll(initConfig);
    }
}
  • RouteConfigListener.java中还有一处要记下来，那就是dataId变量的值gateway-json-routes，这是nacos上配置文件的名字，稍后咱们在nacos上配置的时候会用到
  • 最后是平淡无奇的启动类：
1
2
3
4
5
6
7
8
9
10
11
java复制代码package com.bolingcavalry.gateway;

import org.springframework.boot.SpringApplication;
import org.springframework.boot.autoconfigure.SpringBootApplication;

@SpringBootApplication
public class GatewayApplication {
    public static void main(String[] args) {
        SpringApplication.run(GatewayApplication.class,args);
    }
}
  • 编码完成了，接下来在nacos上增加两个配置；
  • 第一个配置名为gateway-dynamic-by-nacos，内容如下：
1
2
3
4
5
6
7
8
9
10
11
12
yml复制代码server:
  port: 8086

# 暴露端点
management:
  endpoints:
    web:
      exposure:
        include: '*'
  endpoint:
    health:
      show-details: always
  • 第二个配置名为gateway-json-routes，格式要选择JSON，可见只有一个路由（IP+端口那个），另一个用服务名作为URL的路由先不配上去，稍后用来验证动态增加能不能立即生效：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
json复制代码[
    {
        "id": "path_route_addr",
        "uri": "http://127.0.0.1:8082",
        "predicates":[
            {
                "name": "Path",
                "args": {
                    "pattern": "/hello/**"
                }
            }
        ]
    }
]
  • 至此，咱们已经完成了开发工作，接下来验证动态路由是否能达到预期效果，我这里用的客户端工具是postman

验证

  • 确保nacos、provider-hello、gateway-dynamic-by-nacos等服务全部启动：

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

  • 在nacos上修改配置项gateway-json-routes的内容，增加名为path_route_lb的路由配置，修改后完整的配置如下：
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
json复制代码[
    {
        "id": "path_route_addr",
        "uri": "http://127.0.0.1:8082",
        "predicates":[
            {
                "name": "Path",
                "args": {
                    "pattern": "/hello/**"
                }
            }
        ]
    }
    ,
    {
        "id": "path_route_lb",
        "uri": "lb://provider-hello",
        "predicates":[
            {
                "name": "Path",
                "args": {
                    "pattern": "/lbtest/**"
                }
            }
        ]
    }
]
  • 点击右下角的发布按钮后，gateway-dynamic-by-nacos应用的控制台立即输出了以下内容，可见监听已经生效：
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
shell复制代码2021-08-15 19:39:45.883  INFO 18736 --- [-127.0.0.1_8848] c.a.n.client.config.impl.ClientWorker    : [fixed-127.0.0.1_8848] [polling-resp] config changed. dataId=gateway-json-routes, group=DEFAULT_GROUP
2021-08-15 19:39:45.883  INFO 18736 --- [-127.0.0.1_8848] c.a.n.client.config.impl.ClientWorker    : get changedGroupKeys:[gateway-json-routes+DEFAULT_GROUP]
2021-08-15 19:39:45.890  INFO 18736 --- [-127.0.0.1_8848] c.a.n.client.config.impl.ClientWorker    : [fixed-127.0.0.1_8848] [data-received] dataId=gateway-json-routes, group=DEFAULT_GROUP, tenant=null, md5=54fb76dcad838917818d0160ce2bd72f, content=[
    {
        "id": "path_route_addr",
        "uri": "http://127.0.0.1:8082",
        "predicates..., type=json
2021-08-15 19:39:45.891  INFO 18736 --- [-127.0.0.1_8848] c.b.gateway.service.RouteOperator        : start refreshAll : [
    {
        "id": "path_route_addr",
        "uri": "http://127.0.0.1:8082",
        "predicates":[
            {
                "name": "Path",
                "args": {
                    "pattern": "/hello/**"
                }
            }
        ]
    }
    ,
    {
        "id": "path_route_lb",
        "uri": "lb://provider-hello",
        "predicates":[
            {
                "name": "Path",
                "args": {
                    "pattern": "/lbtest/**"
                }
            }
        ]
    }
]
2021-08-15 19:39:45.894  INFO 18736 --- [-127.0.0.1_8848] c.b.gateway.service.RouteOperator        : finish refreshAll
2021-08-15 19:39:45.894  INFO 18736 --- [-127.0.0.1_8848] c.a.nacos.client.config.impl.CacheData   : [fixed-127.0.0.1_8848] [notify-ok] dataId=gateway-json-routes, group=DEFAULT_GROUP, md5=54fb76dcad838917818d0160ce2bd72f, listener=com.bolingcavalry.gateway.service.RouteConfigListener$1@123ae1f6 
2021-08-15 19:39:45.894  INFO 18736 --- [-127.0.0.1_8848] c.a.nacos.client.config.impl.CacheData   : [fixed-127.0.0.1_8848] [notify-listener] time cost=3ms in ClientWorker, dataId=gateway-json-routes, group=DEFAULT_GROUP, md5=54fb76dcad838917818d0160ce2bd72f, listener=com.bolingcavalry.gateway.service.RouteConfigListener$1@123ae1f6
  • 再用postman发同样请求，这次终于成功了，可见动态路由已经成功：

在这里插入图片描述

  • 由于依赖了spring-boot-starter-actuator库，并且配置文件中也添加了相关配置，我们还可以查看SpringBoot应用内部的配置情况，用浏览器访问http://localhost:8086/actuator/gateway/routes，可见最新的配置情况，如下图：

在这里插入图片描述

  • 至此，动态路由的开发和验证已完成，希望这个实用的功能可以给您一些参考，开发出更加灵活实用的网关服务；

你不孤单，欣宸原创一路相伴

  1. Java系列
  2. Spring系列
  3. Docker系列
  4. kubernetes系列
  5. 数据库+中间件系列
  6. DevOps系列

欢迎关注公众号：程序员欣宸

微信搜索「程序员欣宸」，我是欣宸，期待与您一同畅游Java世界…
github.com/zq2599/blog…

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

发表于

「这是我参与11月更文挑战的第16天，活动详情查看：2021最后一次更文挑战」

KMP

- KMP算法的时间复杂度是O(m+n),主要优点是：主串不回溯

一.示例图

#二.经典例题

剖析上面的例题

1
arduino复制代码p作为模式串'aabaac'      s作为主串'aabaabaabaac'

1. 首先我们先求解next数组

2. 主串一直往前走，模式串进行比较

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
css复制代码①
a a b a a  b a a b a a c
a a b a a 'c'                
此时可以看到位于模式串的第'六位'字母c 与主串发生不匹配，这时去找next数组第六位，'next[6]=3'
那么此时回退到第三位根据公式'j=next[j]'

②
a a b a a b a a b a a c
      a a b a a'c' 
此时可以看到又是第六位字母'c'发生不匹配,仍然回退到'j=next[j]'-->相当于回退三位

③
a a b a a b a a b a a c
            a a b a a c
此时终于 '全部匹配'

上面的例题的方法二

例1图

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
css复制代码1. 首先我们先将模式串的前后缀的部分匹配值求出，如'例1图'
2. 这时我们进行模拟匹配的时候，就可以使用公式 '右移位数 = 已匹配的字符数-对应的部分匹配值'    
 ①
a a b a a  b a a b a a c
a a b a a 'c'  
此时第六位不匹配，那么我们看到第五位'a'匹配值是'2',已经匹配的是'5'所以使用公式
'5-2=3'   此时我们将模式串向后移动三位得到②

②
a a b a a b a a b a a c
      a a b a a'c' 
同理与上面思路相同，仍然是'5-2=3' 将模式串向后移动三位得到③

③
a a b a a b a a b a a c
            a a b a a c

彩蛋

  • 到了这里，大家重新看例1图，我们要求的next数组其实就是将例1图中的
  • 匹配值整体向右一位，是不是很神奇！

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

发表于

「这是我参与11月更文挑战的第15天，活动详情查看：2021最后一次更文挑战」

💦 二叉树的概念

1
2
3
复制代码一棵二叉树是节点的一个有限集合，该集合：
1、或者为空
2、由一个根节点加上两棵别称为左子树和右子树的二叉树组成

在这里插入图片描述

1️⃣ 二叉树不存在度大于 2 的结点

2️⃣ 二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树

⚠ 注意：对于任意的二叉树都是由以下几种情况复合而成的：

在这里插入图片描述
❓ 现实中的存在这种二叉树吗 ❔

   在人为的干涉的情况下一定是存在的，因为没有什么是一电锯解决不了的事
在这里插入图片描述
当然也不乏有大自然的鬼斧神工，注意区分普通的树
在这里插入图片描述

💦 特殊的二叉树

1️⃣ 满二叉树：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为 K，且结点总数是 2^k - 1，则它就是满二叉树。

2️⃣ 完全二叉树：完全二叉树的前 k - 1 层都满的，第 k 层不一定满 (这就意味着满二叉树是完全二叉树，但完全二叉树不一定是满二叉树)，但是从最后一层从左到右必须是连续的，也就是说完全二叉树中度为 1 的节点最少 0 个，最多 1 个。完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为 K 的，有 n 个结点的二叉树，且每个结点都与深度为 K 的满二叉树中编号从 1 至 n 的结点 一一 对应称之为完全二叉树。要注意的是满二叉树是一种特殊的完全二叉树。

在这里插入图片描述

▶ 满二叉树的节点个数就是等比求和
在这里插入图片描述
2^0^ + 2^1^ + 2^2^ + … 2^(k-1)^

利用公式所以满二叉树的节点个数就是 2^k^ - 1

▶ 完全二叉树的节点个数

最多：2^k - 1  这是满二叉树

最少：2^(k-1)^ - 1 + 1  ->  2^(k-1)^

   2^(k-1)^ - 1 这是前 k-1 层节点的个数，+1 则是第 k 层至少一个

💦 二叉树的性质

1️⃣ 若规定根节点的层数为 1，则一棵非空二叉树的第 i 层上最多有 2^(i-1) 个结点

在这里插入图片描述

2️⃣ 若规定根节点的层数为 1，则深度为 h 的二叉树的最大结点数是 2^h - 1

在这里插入图片描述

3️⃣ 对任何一棵二叉树, 如果度为 0 其叶结点个数为 n₀, 度为 2 的分支结点个数为 n₂,则有 n₀＝ n₂＋1

在这里插入图片描述

4️⃣ 若规定根节点的层数为 1，具有 n 个结点的满二叉树的深度为 h = log₂(n+1)  ps：log₂(n+1)是 log 以 2 为底， n+1 的对数

在这里插入图片描述

5️⃣ 对于具有 n 个结点的完全二叉树，如果按照从上至下从左至右的数组顺序对所有节点从 0 开始编号，则对于序号为 i 的结点有：

  ▶ 若 i>0，i 位置节点的双亲序号：(i-1)/2；i=0，i 为根节点编号，无双亲节点

  ▶ 若 2i+1<n，左孩子序号：2i+1，2i+1>=n 否则无左孩子

  ▶ 若 2i+2<n，右孩子序号：2i+2，2i+2>=n 否则无右孩子

💦 二叉树的概念选择题

1、某二叉树共有 399 个结点，其中有 199 个度为 2 的节点，则该二叉树中的叶子节点数为（ ）

A. 不存在这样的二叉树

B. 200

C. 198

D. 199

📝 分析：这里的叶子节点就是度为 0 的节点，已知二叉树中度为 2 的节点为 199 个，则度为 0 的节点等于度为 2 的节点 +1，所以选择 B 选项

2、下列数据结构中，不适合采用顺序存储结构的是（ ）注意此题可以先了解下面的二叉树的存储结构在来做

A. 非完全二叉树

B. 堆

C. 队列

D. 栈

📝 分析：顺序结构存储就是使用数组来存储，它只适合表示完全二叉树，因为不是完全二叉树会有空间的浪费。数组只适合存储完全二叉树或者满二叉树。

所以选择 A 选项

3、在具有 2n 个节点的完全二叉树中，叶子节点个数为（ ）

A. n

B. n+1

C. n-1

D. n/2

📝 分析：

假设度为 0 的个数是 x0，度为 2 的个数是 x2，度为 1 的个数是 x1，那么：

▶ x0 + x1 + x2 = 2n

▶ x0 = x2 + 1

由 x0 = x2 + 1 得到 x2 = x0 - 1

所以 x0 + x1 + x2 = 2n 同 x0 + x1 + x0 - 1 = 2n 同 2x0 + x1 - 1 = 2n

这时再回过头想想完全二叉树中度为 1 的节点最少 0 个，最多就只有 1 个，

所以 x1 = 0 or 1

所以 2x0 + x1 - 1 = 2n 就有 2 种情况：

▶ 2x0 + 0 - 1 = 2n

▶ 2x0 + 1 - 1 = 2n

所以结果一目了然，当 x1 = 0 时，x0为小数，显然不可能；当 x1 = 1 时满足，所以选择 A 选项

4、一棵完全二叉树的节点数为 531 个，那么这棵树的高度为（ ）

A. 11

B. 10

C. 8

D. 12

📝 分析：

假设完全二叉树的高度是 h，那么：最多有 2^h-1 个节点；最少有 2^(h-1) 个节点

▶ h = 11 时：最多 2047；最少 2014，所以不合理

▶ h = 10 时：最多 1023；最少 512，所以合情合理

▶ h = 8 时：最多 255；最少 128，所以不合理

▶ h = 12 时：最多 4095；最少 2048，所以不合理

所以选择 B 选项

5、一个具有 767 个节点的完全二叉树，其叶子节点个数为 ( )

A. 383

B. 384

C. 385

D. 386

📝 分析：此题类似于第 3 题

假设度为 0 的个数是 x0，度为 2 的个数是 x2，度为 1 的个数是 x1，那么：

▶ x0 + x1 + x2 = 767

▶ x0 = x2 + 1

由 x0 = x2 + 1 得到 x2 = x0 - 1

所以 x0 + x1 + x2 = 767 同 x0 + x1 + x0 - 1 = 767 同 2x0 + x1 - 1 = 767

这时再回过头想想完全二叉树中度为 1 的节点最少 0 个，最多就只有 1 个，

所以 x1 = 0 or 1

所以 2x0 + x1 - 1 = 767 就有 2 种情况：

▶ 2x0 + 0 - 1 = 767

▶ 2x0 + 1 - 1 = 767

所以结果一目了然，当 x1 = 0 时，满足条件；当 x1 = 1 时，不满足条件，所以选择 B 选项

💦 二叉树的存储结构

二叉树一般可以使用两种结构存储，一种顺序结构，一种链式结构：。

  1️⃣ 顺序存储：顺序结构存储就是使用数组来存储，它只适合表示完全二叉树，因为不是完全二叉树会有空间的浪费。而现实使用中只有堆才会使用数组来存储，二叉树顺序存储在物理上是一个数组，在逻辑上是一颗二叉树。如下图所见，数组只适合存储完全二叉树或者满二叉树。

  ❓ 怎么表示下标和树的关系 ❔

     下标表示树中父子关系的公式：

     左孩子和右孩子

       leftchild = parent * 2 + 1

       rightchild = parent * 2 + 2

     父亲 (这里无论是左孩子还是右孩子都适用于以下公式)

       parent = (child - 1) / 2

在这里插入图片描述

  2️⃣ 链式存储：二叉树的链式存储结构是指用链表来表示一棵二叉树，即用链表来指示元素的逻辑关系。通常的方法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所在的链的存储地址。链式结构又分为二叉链和三叉链，现阶段本篇文章我们只了解二叉链，在以后的文章内写到高阶数据结构时，如红黑树等才会用到三叉链。
在这里插入图片描述

  ❓ 如何定义二叉链和三叉链 ❔

    二叉链只能通过父亲找孩子，类似于单向链表；而三叉链不仅能通过父亲找孩子，还能通过孩子找父亲，类似于双向链表。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
c复制代码typedef int BTDataType;
//二叉链
struct BinaryTreeNode
{
	struct BinaryTreeNode* _pLeft; //指向当前节点的左孩子
	struct BinaryTreeNode* _pRight; //指向当前节点的右孩子	
	BTDataType _data; //当前节点的值域 
}

//三叉链
struct BinaryTreeNode
{
	struct BinaryTreeNode* _pParent; //指向当前节点的父亲
	struct BinaryTreeNode* _pLeft; //指向当前节点的左孩子
	struct BinaryTreeNode* _pRight; //指向当前节点的右孩子
	BTDataType _data; //当前节点的值域
}

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

发表于

「这是我参与11月更文挑战的第16天，活动详情查看：2021最后一次更文挑战」

一、爬虫的合法性问题

目前还处于不明确的蛮荒阶段，“允许哪些行为”这种基本秩序还处于建设中。

至少目前来看，如果抓取的数据为个人所用，则不存在问题；如果数据用于转载，那么

抓取数据的类型就很重要了：一般来说，当抓取的数据是实现生活中的真实数据（比如，营业地址，电话清单）时，是允许转载的，但是，如果是原创数据（比如，意见或评论），通常就会受到版权限制，而不能转载。

讨论：百度爬虫抓取数据行为的合法性问题。

****** 注意：不管怎么样，作为一个访客，应当约束自己的抓取行为，这就是说要求下载请求的速度需要限定在一个合理值之内，并且还需要设定一个专属的用户代理来标识自己。

二、爬虫的准备工作：网站的背景调研

网站的背景调研对聚焦的网络爬虫而言至关重要，正所谓：知己知彼，百战不殆。

1 、robots 协议

Robots 协议（也称为爬虫协议、机器人协议等）的全称是“网络爬虫排除标准”（Robots Exclusion Protocol ），网站通过Robots 协议告诉搜索引擎哪些页面可以抓取，哪些页面不能抓取。

****比如：

淘宝网：www.taobao.com/robots.txt

****再比如：

www.douban.com/robots.txt

搜索引擎和DNS 解析服务商( 如DNSPod 等）合作，新网站域名将被迅速抓取。但是搜索引擎蜘蛛的爬行是被输入了一定的规则的，它需要遵从一些命令或文件的内容，如标注为nofollow 的链接，或者是Robots 协议。另外一种则是，通过网站的站长主动对搜索引擎提交网站的网址，搜索引擎则会在接下来派出“蜘蛛”，对该网站进行爬取。

2、网站地图sitemap

sitemap 是一个网站所有链接的容器。很多网站的连接层次比较深，蜘蛛很难抓取到，网站地图可以方便搜索引擎蜘蛛抓取网站页面，通过抓取网站页面，清晰了解网站的架构，网站地图一般存放在根目录下并命名为sitemap ，为搜索引擎蜘蛛指路，增加网站重要内容页面的收录。网站地图就是根据网站的结构、框架、内容，生成的导航网页文件。大多数人都知道网站地图对于提高用户体验有好处：它们为网站访问者指明方向，并帮助迷失的访问者找到他们想看的页面。

网站地图sitemap 有两种形式：

A.HTML ：称为HTML 版本的网站地图，英文是sitemap, 特质HTML 版网站地图，这个版本的网站地图就是用户可以在网站上看到的，列出网站上所有主要页面的链接的页面。对小网站来说，甚至可以列出整个网站的所有页面，对于具有规模的网站来说，一个网站地图不可能罗列所有的页面链接，可以采取两种办法，一种办法是网站地图只列出网站最主要的链接，如一级分类，二级分类，第二种办法是将网站地图分成几个文件，主网站地图列出通往次级网站的链接，次级网站地图在列出一部分页面链接。

B.XML ：XML 版本的网站地图是由Google 首先提出的，怎么区分了，上面所说的HTML 版本的s 是小写的，而XML 版本的S 则是大写的，XML 版本的网站地图是由XML 标签组成的，文件本身必须是utf8 编码，网站地图文件实际上就是列出网站需要被收录的页面的URL ，最简单的网站地图可以是一个纯文本件，文件只要列出页面的URL ，一行列一个URL ，搜索引擎就能抓取并理解文件内容。

可以使用这个网站工具来生成某网站的sitemap ： www.sitemap-xml.org

3、 估算网站的大小

可以使用搜索引擎来做，比如在百度中使用site:

)​

说明：这里只是通过百度搜索引擎大致来估算网站的大小，受到网站本身对搜索引擎爬虫的限制，及搜索引擎本身爬取数据技术的限制，所以这只是一个经验值，可以作为估算网站体量量级的一个经验值。

4、 识别网站用了何种技术

为了更好的了解网站，抓取该网站的信息，我们可以先了解一下该网站大致所使用的技术架构。

安装builtwith :

Windows ： pip install bulitwith

Linux: sudo pip install builtwith

使用：在Python 交互环境下，输入：

1
2
3
arduino复制代码import builtwith

builtwith.parse("http://www.sina.com.cn")

5、 寻找网站的所有者

有时候，我们需要知道网站的所有者是谁，这里在技术上有个简单的方法可以参考。

安装python-whois :

Windows ： pip install python-whois

使用：在Python 交互环境下，输入：

1
2
3
arduino复制代码import whois

whois.whois("http://www.sina.com.cn")

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

发表于

「这是我参与11月更文挑战的第16天，活动详情查看：2021最后一次更文挑战」

前言：

本讲义为高级爬虫课程的一部分。通过对各种爬虫的主流技术进行研究得出了关于目前网络爬虫所遇到的问题与解决方案进行了较为详细的阐述。在实例中，选用了对国内主流的豆瓣，猫眼电影，今日头条等进行实际的数据抓取，但是随着时间流逝，目标网站的更新，可能有部分代码无法正常运行，望周知。

一、爬虫的简单定义

网络爬虫（又被称为网页蜘蛛，网络机器人，在FOAF社区中间，更经常的称为网页追逐者），是一种按照一定的规则，自动地抓取万维网信息的程序或者脚本。另外一些不常使用的名字还有蚂蚁、自动索引、模拟程序或者蠕虫。

简单来说：使用事先写好的程序去抓取网络上所需要的数据，这样的程序就叫网络爬虫。

爬虫的分类

网络爬虫可以分为通用网络爬虫(如搜索引擎的爬虫，根据几个URL的种子不断的去抓取数据)和聚焦网络爬虫(有选择性的抓取预先定义好的主题和相关页面的网络爬虫)。

A.通用网络爬虫：

搜索引擎中第一步就是爬虫。但是搜索引擎中的爬虫是一种广泛获取各种网页的信息的程序；除了HTML文件外，搜索引擎通常还会抓取和索引文字为基础的多种文件类型，如TXT，WORD，PDF等； 但是对于图片，视频，等非文字的内容则一般不会处理；但是对于脚本和一些网页中的程序是不会处理的；

)​

B.聚焦网络爬虫：

针对某一特定领域的数据进行抓取的程序。比如旅游网站，金融网站，招聘网站等等；特定领域的聚集爬虫会使用各种技术去处理我们需要的信息，所以对于网站中动态的一些程序，脚本仍会执行，以保证确定能抓取到网站中的数据；

二、为什么需要爬虫

爬虫的用途

A.解决冷启动问题：对于很多社交类的网站，冷启动是很困难的。对于新注册的用户而言，要留住他们，需要先注入一批假用户，已构造社区的氛围。一般这些假的用户可以通过网络爬虫从微博或其他APP中抓取而来；今日头条等互联网媒体最早也就是使用了爬虫+网页排序的技术，所以它们解决冷启动的方式也是需要爬虫；

)​

B.搜索引擎的根基：做搜索引擎少不了爬虫程序；

C.建立起知识图谱，帮助建立机器学习的训练集：

)​

D.可以制作各种商品的比价，趋势分析等：

)​

E.其他：比如分析淘宝上竞争对手的数据；分析微博的数据传递影响力，政府的舆情分析，分析人与人之间的关系等等；

)​

总之一句话：在当今的大数据时代，做任何价值分析的前提是数据，而爬虫则是获得这个前提的一个低成本高收益手段；而对同学们而言，另一个重要的价值是解决就业问题。

三、怎么做爬虫

用Python做爬虫非常的简单，在交互式环境中简单的两行代码即可

)​

做一个爬虫如此简单吗？

当然不是。让我们来看下要做一个爬虫工程师需要哪些知识和技能：

******** 爬虫工程师的晋级之路，网络爬虫涉及哪些技术：

初级爬虫工程师：

  1. Web前端的知识：HTML, CSS, JavaScript, DOM, DHTML, Ajax, jQuery,json等；
  2. 正则表达式，能提取正常一般网页中想要的信息，比如某些特殊的文字，链接信息，知道什么是懒惰，什么是贪婪型的正则；
  3. 会使用re, BeautifulSoup，XPath等获取一些DOM结构中的节点信息；
  4. 知道什么是深度优先，广度优先的抓取算法，及实践中的使用规则；
  5. 能分析简单网站的结构，会使用urllib或requests库进行简单的数据抓取；

中级爬虫工程师：

  1. 了解什么是Hash，会使用简单的MD5,SHA1等算法对数据进行Hash以便存储；
  2. 熟悉HTTP,HTTPS协议的基础知识,了解GET，POST方法,了解HTTP头中的信息，包括返回状态码，编码，user-agent，cookie，session等；
  3. 能设置User-Agent进行数据爬取，设置代理等；
  4. 知道什么是Request，什么是Response，会使用Fiddler, Wireshark等工具抓取及分析简单的网络数据包；对于动态爬虫，要学会分析Ajax请求，模拟制造Post数据包请求，抓取客户端session等信息，对于一些简单的网站，能够通过模拟数据包进行自动登录；
  5. 对于比较难搞定的网站，学会使用phatomjs+selenium抓取一些动态网页信息；
  6. 并发下载，通过并行下载加速数据抓取；多线程的使用；

高级爬虫工程师：

  1. 能使用Tesseract，各种图像处理技术，CNN，百度AI等库进行验证码识别；
  2. 能使用数据挖掘的技术，分类算法等避免死链等；
  3. 会使用常用的数据库进行数据存储，查询，如Mongodb，Redis(大数据量的缓存)等；下载缓存，学习如何通过缓存避免重复下载的问题；Bloom Filter的使用；
  4. 能使用机器学习的技术动态调整爬虫的爬取策略，从而避免被禁IP封号等；
  5. 能使用一些开源框架Scrapy等分布式爬虫，能部署掌控分布式爬虫进行大规模的数据抓取。

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%