davidyanxw

davidyanxw 查看完整档案

填写现居城市  |  填写毕业院校  |  填写所在公司/组织填写个人主网站
编辑
_ | |__ _ _ __ _ | '_ \| | | |/ _` | | |_) | |_| | (_| | |_.__/ \__,_|\__, | |___/ 个人简介什么都没有

个人动态

davidyanxw 关注了用户 · 4月14日

煎鱼 @eddycjy

我的公众号:脑子进煎鱼了
博客地址:https://eddycjy.com/
喝口热水,写写代码。

关注 1984

davidyanxw 收藏了文章 · 3月1日

Go - 代码生成工具

分享两个常用的代码生成工具:

  • gormgen
  • handlergen

gormgen

基于 MySQL 数据表结构进行生成 3 个文件:

  1. 生成表的 struct 结构体
  2. 生成表的 Markdown 文档
  3. 生成表的 CURD 方法

场景

在进行业务需求开发时,创建完数据表后,执行代码生成工具,常用的 CURD 操作全部生成完毕,使用的时候只需要 . 后面的方法即可,这样大大提高了业务开发效率。

示例

表结构:

CREATE TABLE `user_demo` (
  `id` int(11) unsigned NOT NULL AUTO_INCREMENT COMMENT '主键',
  `user_name` varchar(32) NOT NULL DEFAULT '' COMMENT '用户名',
  `nick_name` varchar(100) NOT NULL DEFAULT '' COMMENT '昵称',
  `mobile` varchar(20) NOT NULL DEFAULT '' COMMENT '手机号',
  `is_deleted` tinyint(1) NOT NULL DEFAULT '-1' COMMENT '是否删除 1:是  -1:否',
  `created_at` timestamp NOT NULL DEFAULT CURRENT_TIMESTAMP COMMENT '创建时间',
  `updated_at` timestamp NOT NULL DEFAULT CURRENT_TIMESTAMP ON UPDATE CURRENT_TIMESTAMP COMMENT '更新时间',
  PRIMARY KEY (`id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4 COMMENT='用户Demo表';

1、在 config 中设置需要自动生成的表,参数为 cmd.genTables,如果设置为空,表示生成当前数据库中的所有的表,如果设置多张表还可以用 “,” 分割。

[cmd]
genTables = 'user_demo'

2、在根目录下执行脚本

./scripts/gormgen.sh

执行完毕后,会在 /internal/api/repository/db_repo 中生成 user_demo_repo 目录,同时也会生成 3 个文件:

  • gen_model.go
  • gen_table.md
  • gen_user_demo.go

gen_model.go 内容如下:

package user_demo_repo

import "time"

// 用户Demo表
//go:generate gormgen -structs UserDemo -input .
type UserDemo struct {
    Id        int32     // 主键
    UserName  string    // 用户名
    NickName  string    // 昵称
    Mobile    string    // 手机号
    IsDeleted int32     // 是否删除 1:是  -1:否
    CreatedAt time.Time `gorm:"time"` // 创建时间
    UpdatedAt time.Time `gorm:"time"` // 更新时间
}

gen_table.md Markdown 内容如下:

image.png

gen_user_demo.go 内容如下:

func NewModel() *UserDemo {...}

func NewQueryBuilder() *userDemoRepoQueryBuilder {...}

func (t *UserDemo) Create(db *gorm.DB) (id int32, err error) {...}

func (t *UserDemo) Delete(db *gorm.DB) (err error) {...}

func (t *UserDemo) Updates(db *gorm.DB, m map[string]interface{}) (err error) {...}

type userDemoRepoQueryBuilder struct {...}

func (qb *userDemoRepoQueryBuilder) buildQuery(db *gorm.DB) *gorm.DB {...}

func (qb *userDemoRepoQueryBuilder) Count(db *gorm.DB) (int64, error) {...}

func (qb *userDemoRepoQueryBuilder) First(db *gorm.DB) (*UserDemo, error) {...}

func (qb *userDemoRepoQueryBuilder) QueryOne(db *gorm.DB) (*UserDemo, error) {...}

func (qb *userDemoRepoQueryBuilder) QueryAll(db *gorm.DB) ([]*UserDemo, error) {...}

func (qb *userDemoRepoQueryBuilder) Limit(limit int) *userDemoRepoQueryBuilder {...}

func (qb *userDemoRepoQueryBuilder) Offset(offset int) *userDemoRepoQueryBuilder {...}

func (qb *userDemoRepoQueryBuilder) WhereId(p db_repo.Predicate, value int32) *userDemoRepoQueryBuilder {...}

func (qb *userDemoRepoQueryBuilder) OrderById(asc bool) *userDemoRepoQueryBuilder {...}

func (qb *userDemoRepoQueryBuilder) WhereUserName(p db_repo.Predicate, value string) *userDemoRepoQueryBuilder {...}

func (qb *userDemoRepoQueryBuilder) OrderByUserName(asc bool) *userDemoRepoQueryBuilder {...}

func (qb *userDemoRepoQueryBuilder) WhereNickName(p db_repo.Predicate, value string) *userDemoRepoQueryBuilder {...}

func (qb *userDemoRepoQueryBuilder) OrderByNickName(asc bool) *userDemoRepoQueryBuilder {...}

func (qb *userDemoRepoQueryBuilder) WhereMobile(p db_repo.Predicate, value string) *userDemoRepoQueryBuilder {...}

func (qb *userDemoRepoQueryBuilder) OrderByMobile(asc bool) *userDemoRepoQueryBuilder {...}

func (qb *userDemoRepoQueryBuilder) WhereIsDeleted(p db_repo.Predicate, value int32) *userDemoRepoQueryBuilder {...}

func (qb *userDemoRepoQueryBuilder) OrderByIsDeleted(asc bool) *userDemoRepoQueryBuilder {...}

func (qb *userDemoRepoQueryBuilder) WhereCreatedAt(p db_repo.Predicate, value time.Time) *userDemoRepoQueryBuilder {...}

func (qb *userDemoRepoQueryBuilder) OrderByCreatedAt(asc bool) *userDemoRepoQueryBuilder {...}

func (qb *userDemoRepoQueryBuilder) WhereUpdatedAt(p db_repo.Predicate, value time.Time) *userDemoRepoQueryBuilder {...}

func (qb *userDemoRepoQueryBuilder) OrderByUpdatedAt(asc bool) *userDemoRepoQueryBuilder {...}

使用

这样使用生成后的方法:

// 查询示例:
user_demo_repo.NewQueryBuilder().
    WhereUserName(db_repo.EqualPredicate, "tom").
    OrderById(true).
    QueryOne(u.db.GetDbR().WithContext(ctx.RequestContext()))

handlergen

基于定义的 Handler 文件中 type interface 中接口方法,进行生成文件。

场景

本次需求的研发负责人通过定义 type interface 的方式,定义出需要开发的方法,执行代码生成工具,每个方法的空实现都会生成在一个单独的文件中,开发人员只需去实现各自方法即可,便于进行分工和代码管理。

示例

比如 test_handler 中定义的 type interface 如下:

var _ Handler = (*handler)(nil)

type Handler interface {
    // i 为了避免被其他包实现
    i()
    // Create 创建用户
    Create() core.HandlerFunc
    // Update 编辑用户
    Update() core.HandlerFunc
    // Delete 删除用户
    Delete() core.HandlerFunc
    // Detail 用户详情
    Detail() core.HandlerFunc
}

type handler struct {
    logger      *zap.Logger
    cache       cache.Repo
    userService user_service.UserService
}

func New(logger *zap.Logger, db db.Repo, cache cache.Repo) Handler {
    return &handler{
        logger:      logger,
        cache:       cache,
        userService: user_service.NewUserService(db, cache),
    }
}

func (h *handler) i() {}

在根目录下执行脚本:

./scripts/handlergen.sh test_handler

// test_handler 为需要生成 handler 的包名

执行完毕后,会在 /internal/api/controller/test_handler 中生成 4 个文件:

  • func_create.go
  • func_update.go
  • func_detail.go
  • func_delete.go

func_create.go 内容如下:

type createRequest struct{}

type createResponse struct{}

func (h *handler) Create() core.HandlerFunc {
    return func(c core.Context) {

    }
}

其中 createRequest 为入参结构体,createResponse 为出参结构体。

func_update.go 内容如下:

type updateRequest struct{}

type updateResponse struct{}

func (h *handler) Update() core.HandlerFunc {
    return func(c core.Context) {

    }
}

func_detail.go 内容如下:

type detailRequest struct{}

type detailResponse struct{}

func (h *handler) Detail() core.HandlerFunc {
    return func(c core.Context) {

    }
}

func_delete.go 内容如下:

type deleteRequest struct{}

type deleteResponse struct{}

func (h *handler) Delete() core.HandlerFunc {
    return func(c core.Context) {

    }
}
以上代码都在 go-gin-api 项目中,地址:https://github.com/xinliangno...
查看原文

davidyanxw 收藏了文章 · 2月20日

从 Go 的二进制文件中获取其依赖的模块信息

大家好,我是张晋涛。

我们用 Go 构建的二进制文件中默认包含了很多有用的信息。例如,可以获取构建用的 Go 版本:

(这里我使用我一直参与的一个开源项目 KIND 为例)

➜  kind git:(master) ✗ go version ./bin/kind 
./bin/kind: go1.16

或者也可以获取该二进制所依赖的模块信息:

➜  kind git:(master) ✗ go version -m ./bin/kind
./bin/kind: go1.16
        path    sigs.k8s.io/kind
        mod     sigs.k8s.io/kind        (devel)
        dep     github.com/BurntSushi/toml      v0.3.1
        dep     github.com/alessio/shellescape  v1.4.1
        dep     github.com/evanphx/json-patch/v5        v5.2.0
        dep     github.com/mattn/go-isatty      v0.0.12
        dep     github.com/pelletier/go-toml    v1.8.1  h1:1Nf83orprkJyknT6h7zbuEGUEjcyVlCxSUGTENmNCRM=
        dep     github.com/pkg/errors   v0.9.1
        dep     github.com/spf13/cobra  v1.1.1
        dep     github.com/spf13/pflag  v1.0.5
        dep     golang.org/x/sys        v0.0.0-20210124154548-22da62e12c0c      h1:VwygUrnw9jn88c4u8GD3rZQbqrP/tgas88tPUbBxQrk=
        dep     gopkg.in/yaml.v2        v2.2.8
        dep     gopkg.in/yaml.v3        v3.0.0-20210107192922-496545a6307b      h1:h8qDotaEPuJATrMmW04NCwg7v22aHH28wwpauUhK9Oo=
        dep     k8s.io/apimachinery     v0.20.2
        dep     sigs.k8s.io/yaml        v1.2.0

查看 KIND 代码仓库中的 go.mod文件,都包含在内了。

其实 Linux 系统中二进制文件包含额外的信息并非 Go 所特有的,下面我将具体介绍其内部原理和实现。当然,用 Go 构建的二进制文件仍是本文的主角。

Linux ELF 格式

ELF 是 Executable and Linkable Format 的缩写,是一种用于可执行文件、目标文件、共享库和核心转储(core dump)的标准文件格式。ELF 文件 通常 是编译器之类的输出,并且是二进制格式。以 Go 编译出的可执行文件为例,我们使用 file 命令即可看到其具体类型 ELF 64-bit LSB executable

➜  kind git:(master) ✗ file ./bin/kind 
./bin/kind: ELF 64-bit LSB executable, x86-64, version 1 (SYSV), statically linked, not stripped

本文中我们来具体看看 64 位可执行文件使用的 ELF 文件格式的结构和 Linux 内核源码中对它的定义。

使用 ELF 文件格式的可执行文件是由 ELF 头(ELF Header) 开始,后跟 程序头(Program Header)节头(Section Header) 或两者均有组成的。

ELF 头

ELF 头始终位于文件的零偏移(zero offset)处(即:起点位置),同时在 ELF 头中还定义了程序头和节头的偏移量。

我们可以通过 readelf 命令查看可执行文件的 ELF 头,如下:

➜  kind git:(master) ✗ readelf -h ./bin/kind 
ELF Header:
  Magic:   7f 45 4c 46 02 01 01 00 00 00 00 00 00 00 00 00 
  Class:                             ELF64
  Data:                              2's complement, little endian
  Version:                           1 (current)
  OS/ABI:                            UNIX - System V
  ABI Version:                       0
  Type:                              EXEC (Executable file)
  Machine:                           Advanced Micro Devices X86-64
  Version:                           0x1
  Entry point address:               0x46c460
  Start of program headers:          64 (bytes into file)
  Start of section headers:          400 (bytes into file)
  Flags:                             0x0
  Size of this header:               64 (bytes)
  Size of program headers:           56 (bytes)
  Number of program headers:         6
  Size of section headers:           64 (bytes)
  Number of section headers:         15
  Section header string table index: 3

从上面的输出我们可以看到,ELF 头是以某个 Magic 开始的,此 Magic 标识了有关文件的信息,即:前四个 16 进制数,表示这是一个 ELF 文件。具体来说,将它们换算成其对应的 ASCII 码即可:

45 = E

4c = L

46 = F

7f 是其前缀,当然,也可以直接在 Linux 内核源码中拿到此处的具体定义:

// include/uapi/linux/elf.h#L340-L343
#define    ELFMAG0        0x7f        /* EI_MAG */
#define    ELFMAG1        'E'
#define    ELFMAG2        'L'
#define    ELFMAG3        'F'

接下来的数 02 是与 Class 字段相对应的,表示其体系结构,它可以是 32 位(=01) 或是 64 位(=02)的,此处显示 02 表示是 64 位的,再有 readelf 将其转换为 ELF64 进行展示。这里的取值同样可以在 Linux 内核源码中找到:

// include/uapi/linux/elf.h#L347-L349
#define    ELFCLASSNONE    0        /* EI_CLASS */
#define    ELFCLASS32    1
#define    ELFCLASS64    2

再后面的两个 01 01 则是与 Data 字段和 Version 字段相对应的,Data 有两个取值分别是 LSB(01)和 MSB(02),这里倒没什么必要展开。另外就是 Version 当前只有一个取值,即 01 。

// include/uapi/linux/elf.h#L352-L358
#define ELFDATANONE    0        /* e_ident[EI_DATA] */
#define ELFDATA2LSB    1
#define ELFDATA2MSB    2

#define EV_NONE        0        /* e_version, EI_VERSION */
#define EV_CURRENT    1
#define EV_NUM        2

接下来需要注意的就是我前面提到的关于偏移量的内容,即输出中的以下内容:

  Start of program headers:          64 (bytes into file)
  Start of section headers:          400 (bytes into file)
  Flags:                             0x0
  Size of this header:               64 (bytes)
  Size of program headers:           56 (bytes)
  Number of program headers:         6
  Size of section headers:           64 (bytes)
  Number of section headers:         15

ELF 头总是在起点,在此例中接下来是程序头(Program Header),随后是节头(Section Header),这里的输出显示程序头是从 64 开始的,所以节头的位置就是:

64 + 56 * 6 = 400

与上述输出符合,同理,节头的结束位置是:

400 + 15 * 64 = 1360

下一节内容中将用到这部分知识。

程序头

通过 readelf -l 可以看到其程序头,包含了若干段(Segment),内核看到这些段时,将调用 mmap syscall 来使用它们映射到虚拟地址空间。这部分不是本文的重点,我们暂且跳过有个印象即可。

➜  kind git:(master) ✗ readelf -l ./bin/kind 

Elf file type is EXEC (Executable file)
Entry point 0x46c460
There are 6 program headers, starting at offset 64

Program Headers:
  Type           Offset             VirtAddr           PhysAddr
                 FileSiz            MemSiz              Flags  Align
  PHDR           0x0000000000000040 0x0000000000400040 0x0000000000400040
                 0x0000000000000150 0x0000000000000150  R      0x1000
  LOAD           0x0000000000000000 0x0000000000400000 0x0000000000400000
                 0x0000000000333a75 0x0000000000333a75  R E    0x1000
  LOAD           0x0000000000334000 0x0000000000734000 0x0000000000734000
                 0x00000000002b3be8 0x00000000002b3be8  R      0x1000
  LOAD           0x00000000005e8000 0x00000000009e8000 0x00000000009e8000
                 0x0000000000020ac0 0x00000000000552d0  RW     0x1000
  GNU_STACK      0x0000000000000000 0x0000000000000000 0x0000000000000000
                 0x0000000000000000 0x0000000000000000  RW     0x8
  LOOS+0x5041580 0x0000000000000000 0x0000000000000000 0x0000000000000000
                 0x0000000000000000 0x0000000000000000         0x8

 Section to Segment mapping:
  Segment Sections...
   00     
   01     .text 
   02     .rodata .typelink .itablink .gosymtab .gopclntab 
   03     .go.buildinfo .noptrdata .data .bss .noptrbss 
   04     
   05     

节头

使用 readelf -S 即可查看其节头,其结构如下:

// include/uapi/linux/elf.h#L317-L328
typedef struct elf64_shdr {
  Elf64_Word sh_name;        /* Section name, index in string tbl */
  Elf64_Word sh_type;        /* Type of section */
  Elf64_Xword sh_flags;        /* Miscellaneous section attributes */
  Elf64_Addr sh_addr;        /* Section virtual addr at execution */
  Elf64_Off sh_offset;        /* Section file offset */
  Elf64_Xword sh_size;        /* Size of section in bytes */
  Elf64_Word sh_link;        /* Index of another section */
  Elf64_Word sh_info;        /* Additional section information */
  Elf64_Xword sh_addralign;    /* Section alignment */
  Elf64_Xword sh_entsize;    /* Entry size if section holds table */
} Elf64_Shdr;

对照实际的命令输出,含义就很明显了。

➜  kind git:(master) ✗ readelf -S ./bin/kind 
There are 15 section headers, starting at offset 0x190:

Section Headers:
  [Nr] Name              Type             Address           Offset
       Size              EntSize          Flags  Link  Info  Align
  [ 0]                   NULL             0000000000000000  00000000
       0000000000000000  0000000000000000           0     0     0
  [ 1] .text             PROGBITS         0000000000401000  00001000
       0000000000332a75  0000000000000000  AX       0     0     32
  [ 2] .rodata           PROGBITS         0000000000734000  00334000
       000000000011f157  0000000000000000   A       0     0     32
  [ 3] .shstrtab         STRTAB           0000000000000000  00453160
       00000000000000a4  0000000000000000           0     0     1
  [ 4] .typelink         PROGBITS         0000000000853220  00453220
       00000000000022a0  0000000000000000   A       0     0     32
  [ 5] .itablink         PROGBITS         00000000008554c0  004554c0
       0000000000000978  0000000000000000   A       0     0     32
  [ 6] .gosymtab         PROGBITS         0000000000855e38  00455e38
       0000000000000000  0000000000000000   A       0     0     1
  [ 7] .gopclntab        PROGBITS         0000000000855e40  00455e40
       0000000000191da8  0000000000000000   A       0     0     32
  [ 8] .go.buildinfo     PROGBITS         00000000009e8000  005e8000
       0000000000000020  0000000000000000  WA       0     0     16
  [ 9] .noptrdata        PROGBITS         00000000009e8020  005e8020
       0000000000017240  0000000000000000  WA       0     0     32
  [10] .data             PROGBITS         00000000009ff260  005ff260
       0000000000009850  0000000000000000  WA       0     0     32
  [11] .bss              NOBITS           0000000000a08ac0  00608ac0
       000000000002f170  0000000000000000  WA       0     0     32
  [12] .noptrbss         NOBITS           0000000000a37c40  00637c40
       0000000000005690  0000000000000000  WA       0     0     32
  [13] .symtab           SYMTAB           0000000000000000  00609000
       0000000000030a20  0000000000000018          14   208     8
  [14] .strtab           STRTAB           0000000000000000  00639a20
       000000000004178d  0000000000000000           0     0     1
Key to Flags:
  W (write), A (alloc), X (execute), M (merge), S (strings), I (info),
  L (link order), O (extra OS processing required), G (group), T (TLS),
  C (compressed), x (unknown), o (OS specific), E (exclude),
  l (large), p (processor specific)

Go 二进制文件探秘

本文中,我们重点关注名为 .go.buildinfo 的部分。 使用 objdump 查看其具体内容:

➜  kind git:(master) ✗ objdump -s -j .go.buildinfo ./bin/kind

./bin/kind:     file format elf64-x86-64

Contents of section .go.buildinfo:
 9e8000 ff20476f 20627569 6c64696e 663a0800  . Go buildinf:..
 9e8010 a0fc9f00 00000000 e0fc9f00 00000000  ................

这里我们按顺序来,先看到第一行的 16 个字节。

image

  • 前 14 个字节是魔术字节,必须为 \xff Go buildinf:
  • 第 15 字节表示其指针大小,这里的值为 0x08,表示 8 个字节;
  • 第 16 字节用于判断字节序是大端模式还是小端模式,非 0 为大端模式,0 为小端模式。

我们继续看第 17 字节开始的内容。

Go 版本信息

前面我们也看到了当前使用的字节序是小端模式,这里的地址应该是 0x009ffca0

我们来取出 16 字节的内容:

➜  kind git:(master) ✗ objdump -s --start-address 0x009ffca0 --stop-address 0x009ffcb0 ./bin/kind   

./bin/kind:     file format elf64-x86-64

Contents of section .data:
 9ffca0 f5027d00 00000000 06000000 00000000  ..}.............

这里前面的 8 个字节是 Go 版本的信息,后 8 个字节是版本所占的大小(这里表示占 6 个字节)。

➜  kind git:(master) ✗ objdump -s --start-address  0x007d02f5 --stop-address 0x007d02fb ./bin/kind

./bin/kind:     file format elf64-x86-64

Contents of section .rodata:
 7d02f5 676f31 2e3136                        go1.16

所以,如上所示,我们拿到了构建此二进制文件所用的 Go 版本的信息,是用 Go 1.16 进行构建的。

Go Module 信息

前面我们使用了 17~24 字节的信息,这次我们继续往后使用。

➜  kind git:(master) ✗ objdump -s --start-address  0x009ffce0 --stop-address 0x009ffcf0 ./bin/kind       

./bin/kind:     file format elf64-x86-64

Contents of section .data:
 9ffce0 5a567e00 00000000 e6020000 00000000  ZV~.............

与前面获取 Go 版本信息时相同,前 8 个字节是指针,后 8 个字节是其大小。也就是说从 0x007e565a 开始,大小为 0x000002e6 ,所以我们可以拿到以下内容:

➜  kind git:(master) ✗ objdump -s --start-address  0x007e565a --stop-address 0x7e5940 ./bin/kind

./bin/kind:     file format elf64-x86-64

Contents of section .rodata:
 7e565a 3077 af0c9274 080241e1 c107e6d6 18e6 0w...t..A.......
 7e566a 7061 74680973 6967732e 6b38732e 696f path.sigs.k8s.io
 7e567a 2f6b 696e640a 6d6f6409 73696773 2e6b /kind.mod.sigs.k
 7e568a 3873 2e696f2f 6b696e64 09286465 7665 8s.io/kind.(deve
 7e569a 6c29 090a6465 70096769 74687562 2e63 l)..dep.github.c
 7e56aa 6f6d 2f427572 6e745375 7368692f 746f om/BurntSushi/to
 7e56ba 6d6c 0976302e 332e3109 0a646570 0967 ml.v0.3.1..dep.g
 7e56ca 6974 6875622e 636f6d2f 616c6573 7369 ithub.com/alessi
 7e56da 6f2f 7368656c 6c657363 61706509 7631 o/shellescape.v1
 7e56ea 2e34 2e31090a 64657009 67697468 7562 .4.1..dep.github
 7e56fa 2e63 6f6d2f65 76616e70 68782f6a 736f .com/evanphx/jso
 7e570a 6e2d 70617463 682f7635 0976352e 322e n-patch/v5.v5.2.
 7e571a 3009 0a646570 09676974 6875622e 636f 0..dep.github.co
 7e572a 6d2f 6d617474 6e2f676f 2d697361 7474 m/mattn/go-isatt
 7e573a 7909 76302e30 2e313209 0a646570 0967 y.v0.0.12..dep.g
 7e574a 6974 6875622e 636f6d2f 70656c6c 6574 ithub.com/pellet
 7e575a 6965 722f676f 2d746f6d 6c097631 2e38 ier/go-toml.v1.8
 7e576a 2e31 0968313a 314e6638 336f7270 726b .1.h1:1Nf83orprk
 7e577a 4a79 6b6e5436 68377a62 75454755 456a JyknT6h7zbuEGUEj
 7e578a 6379 566c4378 53554754 454e6d4e 4352 cyVlCxSUGTENmNCR
 7e579a 4d3d 0a646570 09676974 6875622e 636f M=.dep.github.co
 7e57aa 6d2f 706b672f 6572726f 72730976 302e m/pkg/errors.v0.
 7e57ba 392e 31090a64 65700967 69746875 622e 9.1..dep.github.
 7e57ca 636f 6d2f7370 6631332f 636f6272 6109 com/spf13/cobra.
 7e57da 7631 2e312e31 090a6465 70096769 7468 v1.1.1..dep.gith
 7e57ea 7562 2e636f6d 2f737066 31332f70 666c ub.com/spf13/pfl
 7e57fa 6167 0976312e 302e3509 0a646570 0967 ag.v1.0.5..dep.g
 7e580a 6f6c 616e672e 6f72672f 782f7379 7309 olang.org/x/sys.
 7e581a 7630 2e302e30 2d323032 31303132 3431 v0.0.0-202101241
 7e582a 3534 3534382d 32326461 36326531 3263 54548-22da62e12c
 7e583a 3063 0968313a 56777967 55726e77 396a 0c.h1:VwygUrnw9j
 7e584a 6e38 38633475 38474433 725a5162 7172 n88c4u8GD3rZQbqr
 7e585a 502f 74676173 38387450 55624278 5172 P/tgas88tPUbBxQr
 7e586a 6b3d 0a646570 09676f70 6b672e69 6e2f k=.dep.gopkg.in/
 7e587a 7961 6d6c2e76 32097632 2e322e38 090a yaml.v2.v2.2.8..
 7e588a 6465 7009676f 706b672e 696e2f79 616d dep.gopkg.in/yam
 7e589a 6c2e 76330976 332e302e 302d3230 3231 l.v3.v3.0.0-2021
 7e58aa 3031 30373139 32393232 2d343936 3534 0107192922-49654
 7e58ba 3561 36333037 62096831 3a683871 446f 5a6307b.h1:h8qDo
 7e58ca 7461 4550754a 4154724d 6d573034 4e43 taEPuJATrMmW04NC
 7e58da 7767 37763232 61484832 38777770 6175 wg7v22aHH28wwpau
 7e58ea 5568 4b394f6f 3d0a6465 70096b38 732e UhK9Oo=.dep.k8s.
 7e58fa 696f 2f617069 6d616368 696e6572 7909 io/apimachinery.
 7e590a 7630 2e32302e 32090a64 65700973 6967 v0.20.2..dep.sig
 7e591a 732e 6b38732e 696f2f79 616d6c09 7631 s.k8s.io/yaml.v1
 7e592a 2e32 2e30090a f9324331 86182072 0082 .2.0...2C1.. r..
 7e593a 4210 4116d8f2                        B.A...          

我们成功的拿到了其所依赖的 Modules 相关的信息,
这与我们在文章开头执行 go version -m ./bin/kind 是可以匹配上的,只不过这里的内容相当于是做了序列化。

具体实现

在前面的内容中,关于如何使用 readelf 和 objdump 命令获取二进制文件的的 Go 版本和 Module 信息就已经涉及到了其具体的原理。这里我来介绍下 Go 代码的实现。

节头的名称是硬编码在代码中的

//src/cmd/go/internal/version/exe.go#L106-L110
    for _, s := range x.f.Sections {
        if s.Name == ".go.buildinfo" {
            return s.Addr
        }
    }

同时,魔术字节也是通过如下定义:

var buildInfoMagic = []byte("\xff Go buildinf:")

获取 Version 和 Module 相关信息的逻辑如下,在前面的内容中也已经基本介绍过了,这里需要注意的也就是字节序相关的部分了。

    ptrSize := int(data[14])
    bigEndian := data[15] != 0
    var bo binary.ByteOrder
    if bigEndian {
        bo = binary.BigEndian
    } else {
        bo = binary.LittleEndian
    }
    var readPtr func([]byte) uint64
    if ptrSize == 4 {
        readPtr = func(b []byte) uint64 { return uint64(bo.Uint32(b)) }
    } else {
        readPtr = bo.Uint64
    }
    vers = readString(x, ptrSize, readPtr, readPtr(data[16:]))
    if vers == "" {
        return
    }
    mod = readString(x, ptrSize, readPtr, readPtr(data[16+ptrSize:]))
    if len(mod) >= 33 && mod[len(mod)-17] == '\n' {
        // Strip module framing.
        mod = mod[16 : len(mod)-16]
    } else {
        mod = ""
    }

总结

我在这篇文章中分享了如何从 Go 的二进制文件中获取构建它时所用的 Go 版本及它依赖的模块信息。如果对原理不感兴趣的话,直接通过 go version -m 二进制文件 即可获取相关的信息。

具体实现还是依赖于 ELF 文件格式中的相关信息,同时也介绍了 readelf 和 objdump 工具的基本使用,ELF 格式除了本文介绍的这种场景外,还有很多有趣的场景可用,比如为了安全进行逆向之类的。

另外,你可能会好奇从 Go 的二进制文件获取这些信息有什么作用。最直接的来说,可以用于安全漏洞扫描,比如检查其依赖项是否有安全漏洞;或是可以对依赖进行分析(主要指:接触不到源代码的场景下)会比较有用。


欢迎订阅我的文章公众号【MoeLove】

TheMoeLove

查看原文

davidyanxw 赞了文章 · 1月13日

面试:Redis为什么快呢?查询为何会变慢呢?

越努力,越幸运,
本文已收藏在GitHub中JavaCommunity, 里面有面试分享、源码分析系列文章,欢迎收藏,点赞
https://github.com/Ccww-lx/Ja...

在实际开发,Redis使用会频繁,那么在使用过程中我们该如何正确抉择数据类型呢?哪些场景下适用哪些数据类型。而且在面试中也很常会被面试官问到Redis数据结构方面的问题:

  • Redis为什么快呢?
  • 为什么查询操作会变慢了?
  • Redis Hash rehash过程
  • 为什么使用哈希表作为Redis的索引

当我们分析理解了Redis数据结构,可以为了我们在使用Redis的时候,正确抉择数据类型使用,提升系统性能。

Redis底层数据结构

Redis 是一个内存键值key-value 数据库,且键值对数据保存在内存中,因此Redis基于内存的数据操作,其效率高,速度快;

其中,KeyString类型,Redis 支持的 value 类型包括了 StringListHashSetSorted SetBitMap等。Redis 能够之所以能够广泛地适用众多的业务场景,基于其多样化类型的value

RedisValue的数据类型是基于为Redis自定义的对象系统redisObject实现的,

typedef struct redisObject{
    //类型
    unsigned type:4;
    //编码
    unsigned encoding:4;
    //指向底层实现数据结构的指针
    void *ptr;
    ….. 
} 

redisObject除了记录实际数据,还需要额外的内存空间记录数据长度、空间使用等元数据信息,其中包含了 8 字节的元数据和一个 8 字节指针,指针指向具体数据类型的实际数据所在位置:

image.png

其中,指针指向的就是基于Redis的底层数据结构存储数据的位置,Redis的底层数据结构:SDS,双向链表、跳表,哈希表,压缩列表、整数集合实现的。

那么Redis底层数据结构是怎么实现的呢?

Redis底层数据结构实现

我们先来看看Redis比较简单的SDS,双向链表,整数集合

SDS、双向链表和整数集合

SDS,使用len字段记录已使用的字节数,将获取字符串长度复杂度降低为O(1),而且SDS惰性释放空间的,你free了空间,系统把数据记录下来下次想用时候可直接使用。不用新申请空间。
image.png
整数集合,在内存中分配一块地址连续的空间,数据元素会挨着存放,不需要额外指针带来空间开销,其特点为内存紧凑节省内存空间,查询复杂度为O(1)效率高,其他操作复杂度为O(N);

双向链表, 在内存上可以为非连续、非顺序空间,通过额外的指针开销前驱/后驱指针串联元素之间的顺序。

其特点为节插入/更新数据复杂度为O(1)效率高,查询复杂度为O(N);

Hash哈希表

哈希表,其实类似是一个数组,数组的每个元素称为一个哈希桶,每个哈希桶中保存了键值对数据,且哈希桶中的元素使用dictEntry结构,
image.png

因此,哈希桶元素保存的并不是键值对值本身,而是指向具体值的指针,所以在保存每个键值对的时候会额外空间开销,至少有增加24个字节,特别是ValueString的键值对,每一个键值对就需要额外开销24个字节空间。当保存数据小,额外开销比数据还大时,这时为了节省空间,考虑换数据结构。

那来看看全局哈希表全图:
image.png
虽然哈希表操作很快,但Redis数据变大后,就会出现一个潜在的风险:哈希表的冲突问题和 rehash开销问题这可以解释为什么哈希表操作变慢了?

当往哈希表中写入更多数据时,哈希冲突是不可避免的问题 , Redis 解决哈希冲突的方式,就是链式哈希,同一个哈希桶中的多个元素用一个链表来保存,它们之间依次用指针连接,如图所示:
image.png

当哈希冲突也会越来越多,这就会导致某些哈希冲突链过长,进而导致这个链上的元素查找耗时长,效率降低。

为了解决哈希冲突带了的链过长的问题,进行rehash操作,增加现有的哈希桶数量,分散单桶元素数量。那么rehash过程怎么样执行的呢?

Rehash

为了使rehash 操作更高效,使用两个全局哈希表:哈希表 1 和哈希表 2,具体如下:

  • 将哈希表 2 分配更大的空间,
  • 把哈希表 1 中的数据重新映射并拷贝到哈希表 2 中;
  • 释放哈希表 1 的空间

但由于表1和表2在重新映射复制时数据大,如果一次性把哈希表 1 中的数据都迁移完,会造成 Redis 线程阻塞,无法服务其他请求。

为了避免这个问题,保证Redis能正常处理客户端请求,Redis 采用了渐进式 rehash

每处理一个请求时,从哈希表 1 中依次将索引位置上的所有 entries 拷贝到哈希表 2 中,把一次性大量拷贝的开销,分摊到了多次处理请求的过程中,避免了耗时操作,保证了数据的快速访问。

img

在理解完Hash哈希表相关知识点后,看看不常见的压缩列表和跳表。

压缩列表与跳表

压缩列表,在数组基础上,在压缩列表在表头有三个字段 zlbytes、zltail 和 zllen,分别表示列表长度、列表尾的偏移量和列表中的 entry 个数;压缩列表在表尾还有一个 zlend,表示列表结束。
image.png

优点:内存紧凑节省内存空间,内存中分配一块地址连续的空间,数据元素会挨着存放,不需要额外指针带来空间开销;查找定位第一个元素和最后一个元素,可以通过表头三个字段的长度直接定位,复杂度是 O(1)。

跳表 ,在链表的基础上,增加了多级索引,通过索引位置的几个跳转,实现数据的快速定位,如下图所示:

比如查询33

img

特点:当数据量很大时,跳表的查找复杂度为O(logN)。

综上所述,可以得知底层数据结构的时间复杂度:

数据结构类型时间复杂度
哈希表O(1)
整数数组O(N)
双向链表O(N)
压缩列表O(N)
跳表O(logN)

Redis自定义的对象系统类型即为RedisValue的数据类型,Redis的数据类型是基于底层数据结构实现的,那数据类型有哪些呢?

Redis数据类型

StringListHashSorted SetSet比较常见的类型,其与底层数据结构对应关系如下:

数据类型数据结构
StringSDS(简单动态字符串)
List双向链表
压缩列表
Hash压缩列表<br/>哈希表
Sorted Set压缩列表<br/>跳表
Set哈希表<br/>整数数组

数据类型对应特点跟其实现的底层数据结构差不多,性质也是一样的,且

String,基于SDS实现,适用于简单key-value存储、setnx key value实现分布式锁、计数器(原子性)、分布式全局唯一ID。

List, 按照元素进入List 的顺序进行排序的,遵循FIFO(先进先出)规则,一般使用在 排序统计以及简单的消息队列。

Hash, 是字符串key和字符串value之间的映射,十分适合用来表示一个对象信息 ,特点添加和删除操作复杂度都是O(1)。

Set,是String 类型元素的无序集合,集合成员是唯一的,这就意味着集合中不能出现重复的数据。 基于哈希表实现的,所以添加,删除,查找的复杂度都是 O(1)。

Sorted Set, 是Set的类型的升级, 不同的是每个元素都会关联一个 double 类型的分数,通过分数排序,可以范围查询。

那我们再来看看这些数据类型,Redis GeoHyperLogLogBitMap

Redis Geo, 将地球看作为近似为球体,基于GeoHash 将二维的经纬度转换成字符串,来实现位置的划分跟指定距离的查询。特点一般使用在跟位置有关的应用。

HyperLogLog, 是一种概率数据结构,它使用概率算法来统计集合的近似基数 , 错误率大概在0.81%。 当集合元素数量非常多时,它计算基数所需的空间总是固定的,而且还很小,适合使用做 UV 统计。

BitMap ,用一个比特位来映射某个元素的状态, 只有 0 和 1 两种状态,非常典型的二值状态,且其本身是用 String 类型作为底层数据结构实现的一种统计二值状态的数据类型 ,优势大量节省内存空间,可是使用在二值统计场景。

在理解上述知识后,我们接下来讨论一下根据哪些策略选择相对应的应用场景下的Redis数据类型?

选择合适的Redis数据类型策略

在实际开发应用中,Redis可以适用于众多的业务场景,但我们需要怎么选择数据类型存储呢?

主要依据就是时间/空间复杂度,在实际的开发中可以考虑以下几个点:

  • 数据量,数据本身大小
  • 集合类型统计模式
  • 支持单点查询/范围查询
  • 特殊使用场景

数据量,数据本身大小

当数据量比较大,数据本身比较小,使用String就会使用额外的空间大大增加,因为使用哈希表保存键值对,使用dictEntry结构保存,会导致保存每个键值对时额外保存dictEntry的三个指针的开销,这样就会导致数据本身小于额外空间开销,最终会导致存储空间数据大小远大于原本数据存储大小。

可以使用基于整数数组压缩列表实现了 ListHashSorted Set ,因为整数数组压缩列表在内存中都是分配一块地址连续的空间,然后把集合中的元素一个接一个地放在这块空间内,非常紧凑,不用再通过额外的指针把元素串接起来,这就避免了额外指针带来的空间开销。而且采用集合类型时,一个 key 就对应一个集合的数据,能保存的数据多了很多,但也只用了一个 dictEntry,这样就节省了内存。

集合类型统计模式

Redis集合类型统计模式常见的有:

  • 聚合统计( 交集、差集、并集统计 ): 对多个集合进行聚合计算时,可以选择Set
  • 排序统计(要求集合类型能对元素保序): RedisListSorted Set是有序集合,List是按照元素进入 List 的顺序进行排序的,Sorted Set 可以根据元素的权重来排序;
  • 二值状态统计( 集合元素的取值就只有 0 和 1 两种 ):Bitmap 本身是用 String 类型作为底层数据结构实现的一种统计二值状态的数据类型 , Bitmap通过 BITOP 按位 与、或、异或的操作后使用 BITCOUNT 统计 1 的个数。
  • 基数统计( 统计一个集合中不重复的元素的个数 ):HyperLogLog 是一种用于统计基数的数据集合类型 ,统计结果是有一定误差的,标准误算率是 0.81% 。需要精确统计结果的话,用 Set 或 Hash 类型。

img

Set类型,适用统计用户/好友/关注/粉丝/感兴趣的人集合聚合操作,比如

  • 统计手机APP每天的新增用户数
  • 两个用户的共同好友

RedisListSorted Set是有序集合,使用应对集合元素排序需求 ,比如

  • 最新评论列表
  • 排行榜

Bitmap二值状态统计,适用数据量大,且可以使用二值状态表示的统计,比如:

  • 签到打卡,当天用户签到数
  • 用户周活跃
  • 用户在线状态

HyperLogLog 是一种用于统计基数的数据集合类型, 统计一个集合中不重复的元素个数 ,比如

  • 统计网页的 UV , 一个用户一天内的多次访问只能算作一次

支持单点查询/范围查询

RedisListSorted Set是有序集合支持范围查询,但是Hash是不支持范围查询的

特殊使用场景

消息队列,使用Redis作为消息队列的实现,要消息的基本要求消息保序处理重复的消息保证消息可靠性,方案有如下:

  • 基于 List 的消息队列解决方案
  • 基于 Streams 的消息队列解决方案
基于List基于Strems
消息保序使用LPUSH/RPOP使用XADD/XREAD
阻塞读取使用BRPOP使用XREAD block
重复消息处理生产者自行实现全局唯一IDStreams自动生成全局唯一ID
消息可靠性使用BRPOPLPUSH使用PENDING List自动留存消息
适用场景消息总量小消息总量大,需要消费组形式读取数据

基于位置 LBS 服务,使用Redis的特定GEO数据类型实现,GEO 可以记录经纬度形式的地理位置信息,被广泛地应用在 LBS 服务中。 比如:打车软件是怎么基于位置提供服务的。

总结

Redis之所以那么快,是因为其基于内存的数据操作和使用Hash哈希表作为索引,其效率高,速度快,而且得益于其底层数据多样化使得其可以适用于众多场景,不同场景中选择合适的数据类型可以提升其查询性能。

谢谢各位点赞,没点赞的点个赞支持支持
最后,微信搜《Ccww技术博客》观看更多文章,也欢迎关注一波。
查看原文

赞 16 收藏 6 评论 0

davidyanxw 收藏了文章 · 1月13日

面试:Redis为什么快呢?查询为何会变慢呢?

越努力,越幸运,
本文已收藏在GitHub中JavaCommunity, 里面有面试分享、源码分析系列文章,欢迎收藏,点赞
https://github.com/Ccww-lx/Ja...

在实际开发,Redis使用会频繁,那么在使用过程中我们该如何正确抉择数据类型呢?哪些场景下适用哪些数据类型。而且在面试中也很常会被面试官问到Redis数据结构方面的问题:

  • Redis为什么快呢?
  • 为什么查询操作会变慢了?
  • Redis Hash rehash过程
  • 为什么使用哈希表作为Redis的索引

当我们分析理解了Redis数据结构,可以为了我们在使用Redis的时候,正确抉择数据类型使用,提升系统性能。

Redis底层数据结构

Redis 是一个内存键值key-value 数据库,且键值对数据保存在内存中,因此Redis基于内存的数据操作,其效率高,速度快;

其中,KeyString类型,Redis 支持的 value 类型包括了 StringListHashSetSorted SetBitMap等。Redis 能够之所以能够广泛地适用众多的业务场景,基于其多样化类型的value

RedisValue的数据类型是基于为Redis自定义的对象系统redisObject实现的,

typedef struct redisObject{
    //类型
    unsigned type:4;
    //编码
    unsigned encoding:4;
    //指向底层实现数据结构的指针
    void *ptr;
    ….. 
} 

redisObject除了记录实际数据,还需要额外的内存空间记录数据长度、空间使用等元数据信息,其中包含了 8 字节的元数据和一个 8 字节指针,指针指向具体数据类型的实际数据所在位置:

image.png

其中,指针指向的就是基于Redis的底层数据结构存储数据的位置,Redis的底层数据结构:SDS,双向链表、跳表,哈希表,压缩列表、整数集合实现的。

那么Redis底层数据结构是怎么实现的呢?

Redis底层数据结构实现

我们先来看看Redis比较简单的SDS,双向链表,整数集合

SDS、双向链表和整数集合

SDS,使用len字段记录已使用的字节数,将获取字符串长度复杂度降低为O(1),而且SDS惰性释放空间的,你free了空间,系统把数据记录下来下次想用时候可直接使用。不用新申请空间。
image.png
整数集合,在内存中分配一块地址连续的空间,数据元素会挨着存放,不需要额外指针带来空间开销,其特点为内存紧凑节省内存空间,查询复杂度为O(1)效率高,其他操作复杂度为O(N);

双向链表, 在内存上可以为非连续、非顺序空间,通过额外的指针开销前驱/后驱指针串联元素之间的顺序。

其特点为节插入/更新数据复杂度为O(1)效率高,查询复杂度为O(N);

Hash哈希表

哈希表,其实类似是一个数组,数组的每个元素称为一个哈希桶,每个哈希桶中保存了键值对数据,且哈希桶中的元素使用dictEntry结构,
image.png

因此,哈希桶元素保存的并不是键值对值本身,而是指向具体值的指针,所以在保存每个键值对的时候会额外空间开销,至少有增加24个字节,特别是ValueString的键值对,每一个键值对就需要额外开销24个字节空间。当保存数据小,额外开销比数据还大时,这时为了节省空间,考虑换数据结构。

那来看看全局哈希表全图:
image.png
虽然哈希表操作很快,但Redis数据变大后,就会出现一个潜在的风险:哈希表的冲突问题和 rehash开销问题这可以解释为什么哈希表操作变慢了?

当往哈希表中写入更多数据时,哈希冲突是不可避免的问题 , Redis 解决哈希冲突的方式,就是链式哈希,同一个哈希桶中的多个元素用一个链表来保存,它们之间依次用指针连接,如图所示:
image.png

当哈希冲突也会越来越多,这就会导致某些哈希冲突链过长,进而导致这个链上的元素查找耗时长,效率降低。

为了解决哈希冲突带了的链过长的问题,进行rehash操作,增加现有的哈希桶数量,分散单桶元素数量。那么rehash过程怎么样执行的呢?

Rehash

为了使rehash 操作更高效,使用两个全局哈希表:哈希表 1 和哈希表 2,具体如下:

  • 将哈希表 2 分配更大的空间,
  • 把哈希表 1 中的数据重新映射并拷贝到哈希表 2 中;
  • 释放哈希表 1 的空间

但由于表1和表2在重新映射复制时数据大,如果一次性把哈希表 1 中的数据都迁移完,会造成 Redis 线程阻塞,无法服务其他请求。

为了避免这个问题,保证Redis能正常处理客户端请求,Redis 采用了渐进式 rehash

每处理一个请求时,从哈希表 1 中依次将索引位置上的所有 entries 拷贝到哈希表 2 中,把一次性大量拷贝的开销,分摊到了多次处理请求的过程中,避免了耗时操作,保证了数据的快速访问。

img

在理解完Hash哈希表相关知识点后,看看不常见的压缩列表和跳表。

压缩列表与跳表

压缩列表,在数组基础上,在压缩列表在表头有三个字段 zlbytes、zltail 和 zllen,分别表示列表长度、列表尾的偏移量和列表中的 entry 个数;压缩列表在表尾还有一个 zlend,表示列表结束。
image.png

优点:内存紧凑节省内存空间,内存中分配一块地址连续的空间,数据元素会挨着存放,不需要额外指针带来空间开销;查找定位第一个元素和最后一个元素,可以通过表头三个字段的长度直接定位,复杂度是 O(1)。

跳表 ,在链表的基础上,增加了多级索引,通过索引位置的几个跳转,实现数据的快速定位,如下图所示:

比如查询33

img

特点:当数据量很大时,跳表的查找复杂度为O(logN)。

综上所述,可以得知底层数据结构的时间复杂度:

数据结构类型时间复杂度
哈希表O(1)
整数数组O(N)
双向链表O(N)
压缩列表O(N)
跳表O(logN)

Redis自定义的对象系统类型即为RedisValue的数据类型,Redis的数据类型是基于底层数据结构实现的,那数据类型有哪些呢?

Redis数据类型

StringListHashSorted SetSet比较常见的类型,其与底层数据结构对应关系如下:

数据类型数据结构
StringSDS(简单动态字符串)
List双向链表
压缩列表
Hash压缩列表<br/>哈希表
Sorted Set压缩列表<br/>跳表
Set哈希表<br/>整数数组

数据类型对应特点跟其实现的底层数据结构差不多,性质也是一样的,且

String,基于SDS实现,适用于简单key-value存储、setnx key value实现分布式锁、计数器(原子性)、分布式全局唯一ID。

List, 按照元素进入List 的顺序进行排序的,遵循FIFO(先进先出)规则,一般使用在 排序统计以及简单的消息队列。

Hash, 是字符串key和字符串value之间的映射,十分适合用来表示一个对象信息 ,特点添加和删除操作复杂度都是O(1)。

Set,是String 类型元素的无序集合,集合成员是唯一的,这就意味着集合中不能出现重复的数据。 基于哈希表实现的,所以添加,删除,查找的复杂度都是 O(1)。

Sorted Set, 是Set的类型的升级, 不同的是每个元素都会关联一个 double 类型的分数,通过分数排序,可以范围查询。

那我们再来看看这些数据类型,Redis GeoHyperLogLogBitMap

Redis Geo, 将地球看作为近似为球体,基于GeoHash 将二维的经纬度转换成字符串,来实现位置的划分跟指定距离的查询。特点一般使用在跟位置有关的应用。

HyperLogLog, 是一种概率数据结构,它使用概率算法来统计集合的近似基数 , 错误率大概在0.81%。 当集合元素数量非常多时,它计算基数所需的空间总是固定的,而且还很小,适合使用做 UV 统计。

BitMap ,用一个比特位来映射某个元素的状态, 只有 0 和 1 两种状态,非常典型的二值状态,且其本身是用 String 类型作为底层数据结构实现的一种统计二值状态的数据类型 ,优势大量节省内存空间,可是使用在二值统计场景。

在理解上述知识后,我们接下来讨论一下根据哪些策略选择相对应的应用场景下的Redis数据类型?

选择合适的Redis数据类型策略

在实际开发应用中,Redis可以适用于众多的业务场景,但我们需要怎么选择数据类型存储呢?

主要依据就是时间/空间复杂度,在实际的开发中可以考虑以下几个点:

  • 数据量,数据本身大小
  • 集合类型统计模式
  • 支持单点查询/范围查询
  • 特殊使用场景

数据量,数据本身大小

当数据量比较大,数据本身比较小,使用String就会使用额外的空间大大增加,因为使用哈希表保存键值对,使用dictEntry结构保存,会导致保存每个键值对时额外保存dictEntry的三个指针的开销,这样就会导致数据本身小于额外空间开销,最终会导致存储空间数据大小远大于原本数据存储大小。

可以使用基于整数数组压缩列表实现了 ListHashSorted Set ,因为整数数组压缩列表在内存中都是分配一块地址连续的空间,然后把集合中的元素一个接一个地放在这块空间内,非常紧凑,不用再通过额外的指针把元素串接起来,这就避免了额外指针带来的空间开销。而且采用集合类型时,一个 key 就对应一个集合的数据,能保存的数据多了很多,但也只用了一个 dictEntry,这样就节省了内存。

集合类型统计模式

Redis集合类型统计模式常见的有:

  • 聚合统计( 交集、差集、并集统计 ): 对多个集合进行聚合计算时,可以选择Set
  • 排序统计(要求集合类型能对元素保序): RedisListSorted Set是有序集合,List是按照元素进入 List 的顺序进行排序的,Sorted Set 可以根据元素的权重来排序;
  • 二值状态统计( 集合元素的取值就只有 0 和 1 两种 ):Bitmap 本身是用 String 类型作为底层数据结构实现的一种统计二值状态的数据类型 , Bitmap通过 BITOP 按位 与、或、异或的操作后使用 BITCOUNT 统计 1 的个数。
  • 基数统计( 统计一个集合中不重复的元素的个数 ):HyperLogLog 是一种用于统计基数的数据集合类型 ,统计结果是有一定误差的,标准误算率是 0.81% 。需要精确统计结果的话,用 Set 或 Hash 类型。

img

Set类型,适用统计用户/好友/关注/粉丝/感兴趣的人集合聚合操作,比如

  • 统计手机APP每天的新增用户数
  • 两个用户的共同好友

RedisListSorted Set是有序集合,使用应对集合元素排序需求 ,比如

  • 最新评论列表
  • 排行榜

Bitmap二值状态统计,适用数据量大,且可以使用二值状态表示的统计,比如:

  • 签到打卡,当天用户签到数
  • 用户周活跃
  • 用户在线状态

HyperLogLog 是一种用于统计基数的数据集合类型, 统计一个集合中不重复的元素个数 ,比如

  • 统计网页的 UV , 一个用户一天内的多次访问只能算作一次

支持单点查询/范围查询

RedisListSorted Set是有序集合支持范围查询,但是Hash是不支持范围查询的

特殊使用场景

消息队列,使用Redis作为消息队列的实现,要消息的基本要求消息保序处理重复的消息保证消息可靠性,方案有如下:

  • 基于 List 的消息队列解决方案
  • 基于 Streams 的消息队列解决方案
基于List基于Strems
消息保序使用LPUSH/RPOP使用XADD/XREAD
阻塞读取使用BRPOP使用XREAD block
重复消息处理生产者自行实现全局唯一IDStreams自动生成全局唯一ID
消息可靠性使用BRPOPLPUSH使用PENDING List自动留存消息
适用场景消息总量小消息总量大,需要消费组形式读取数据

基于位置 LBS 服务,使用Redis的特定GEO数据类型实现,GEO 可以记录经纬度形式的地理位置信息,被广泛地应用在 LBS 服务中。 比如:打车软件是怎么基于位置提供服务的。

总结

Redis之所以那么快,是因为其基于内存的数据操作和使用Hash哈希表作为索引,其效率高,速度快,而且得益于其底层数据多样化使得其可以适用于众多场景,不同场景中选择合适的数据类型可以提升其查询性能。

谢谢各位点赞,没点赞的点个赞支持支持
最后,微信搜《Ccww技术博客》观看更多文章,也欢迎关注一波。
查看原文

davidyanxw 收藏了文章 · 1月13日

[深入理解Redis]读取RDB文件

最近在做一个解析rdb文件的功能,途中遇到了一些问题,也解决了一些问题。具体为什么要做这件事情之后再详谈,本次主要想聊聊遇到的开始处理文件时遇到的第一个难题:理解RDB文件的协议、如何读取二进制文件。

RDB文件

[Redis源码阅读]redis持久化
文章介绍过,Redis的持久化是通过RDB和AOF实现的。Redis的RDB文件是二进制格式的文件,从这个方面再次体现了Redis是基于内存的缓存数据库,不管对于存储到硬盘还是恢复数据都十分快捷。Redis有多种数据类型:string、list、hash、set、zset,不同数据类型占用的内存大小是不一样的,解析出自然语言可以识别的数据就需要使用不同的方法,保存到文件的时候也需要一些协议或者规则。这有点类似于编程语言里面的数据类型,不同的数据类型占用的字节大小不一致,但是保存到计算机都是二进制的编码,就看是读取多少个字节,以怎样的方式解读。

举个例子,redis的对象类型是特定的几个字符表示,0代表字符串,读取到字符串类型后,紧接着就是字符串的长度,保存着接下来需要读取的字节大小,读取到的字节最终构成完整字符串对象的值。对于保存了"name" => "hoohack"键值对的字符串对象保存到内存可以用下图表示:

redis字符串存储

当然,除了字符串,redis还有列表,集合,哈希等各种对象,针对这些类型,在RDB文件里面都有不同的规则定义,只需要按照RDB文件格式的协议来解读文件,就能完整无误地把文件解读成自然语言能描述的字符。

仔细对比,可以发现跟计算机的操作方式是类似的,数据保存在计算机都是二进制的,具体的值应该看需要多少个字节,以什么类型解析,读取不同的字节解析到的值是不一样的,同样的字节大小,但是使用不同类型保存,只要做适当的转换,也是正确的。比如在C语言中的void *指针是4个字节,int也是4个字节,定义一个int整数,将它保存到void *也是没问题的,读取的时候只需要做一次类型转换就可以了。

因此,解读RDB文件最关键的就是理解RDB文件的协议,只要理解完RDB文件格式的协议,根据定义好的协议来解析各种数据类型的数据。更详细的RDB文件协议可以参考RDB文件格式的定义文档:RDB file format

查看RDB文件

先清空redis数据库,保存一个键值对,然后执行save命令将当前数据库的数据保存的rdb文件,得到文件dump.rdb。

127.0.0.1:6379> flushall
OK
127.0.0.1:6379> set name hoohack
OK
127.0.0.1:6379> save
OK

cat查看文件:

cat-rdb-file

可以看到是一个包含乱码的文件,因为文件是以二进制的格式保存,要想打印出人类能看出的语言,可以通过linux的od命令查看。od命令用于输出文件的八进制、十六进制或其他格式编码的字节,通常用于输出文件中不能直接显示在终端的字符,注意输出的是字节,分隔符之间的字符都是保存在一个字节的。

od命令输出文件八进制、十六进制等格式

通过man手册可以看到,打印出16进制格式的参数是x,字符是c,将字符与十六进制的对应关系打印出来:od -A x -t x1c -v dump.rdb

打印得出结果如下:

linux-od

从上图看到,文件打印出来的都是一些十六进制的数字,转换成十进制再去ASCII码表就能查找到对应的字符。比如第一个字符,52=516+21=82='R’。
在这里说一句,个人觉得这od命令非常有用,在解析数据出现疑惑的时候,就是通过这个命令排查遇到的问题。把文件内容打印出来,找到当前读取的字符,对比RDB文件协议,看看究竟要解析的是什么数据,再对比代码中的解析逻辑,看看是否有问题,然后再修正代码。
如果觉得敲命令麻烦,可以把文件上传然后在线查看:https://www.onlinehexeditor.com

数据的二进制保存和读取

我们知道,计算机的所有数据都是以二进制的格式保存的,我们看到的字符是通过读取二进制然后解析出来的数据,程序根据不同数据类型做相应的转换,然后展示出来的就是我们看到的字符。
计算机允许多种数据类型,比如有:32位整数、64位整数、字符串、浮点数、布尔值等等,不同的数据类型是通过读取不同大小的字节,根据类型指定的读取方式读取出来,就是想要的数据了。

解析数据的第一步,就是读取数据。在计算机里面,大家所知道的数据都是逐个字节地读取数据。因此,首先要实现的就是按照字节去读取文件。

本次采用实现的解析RDB文件功能的语言是Golang,在Golang的文件操作的API里,提供了按字节读取的函数File.ReadAt

函数原型如下:


func (f *File) ReadAt(b []byte, off int64) (n int, err error)

函数从File指针的指向的位置off开始,读取len(b)个字节的数据,并保存到b中。
根据对API的理解,自己实现了一个按照字节读取文件数据的函数,函数接收长度值,代表需要读取的字节长度。具体实现代码如下:

type Rdb struct {
    fp *os.File
    ... // other field
}

func (r *Rdb) ReadBuf(length int64) ([]byte, error) {
    // 初始化一个大小为length的字节数组
    buf := make([]byte, length)

    // 从curIndex开始读取length个字节
    size, err := r.fp.ReadAt(buf[:length], r.curIndex)

    checkErr(err)

    if size < 0 {
        fmt.Fprintf(os.Stderr, "cat: error reading: %s\n", err.Error())
        return []byte{}, err
    } else {
        // 读取成功,更新文件操作的偏移量
        r.curIndex += length
        return buf, nil
    }
}

Golang的数据转换

上面实现的函数返回的是字节数组,当函数返回读取到的数据后,如果需要保存在不同的数据类型就需要做转换,Golang也提供了比较强大的api。以下是我在解析数据时遇到的数据类型转换的解决方案,希望对大家有帮助。
字符串


str := string(buf)

int整数,先转为二进制的值,然后再用int32类型格式化


intVal := int(binary.BigEndian.Uint32(buf))

int64整数,先转为二进制的值,然后再用int64类型格式化


int64Val := int64(int16(binary.LittleEndian.Uint16(valBuf)))

浮点数


floatVal, err := strconv.ParseFloat(string(floatBuf), 64)

float64浮点数,先转为二进制的值,再调用math库的Float64frombits函数转换二进制的值为float64类型


floatBit := binary.LittleEndian.Uint64(buf)
floatVal := math.Float64frombits(floatBit)

总结

理论上的理解和实践上的应用是不一样的,虽然大家都知道数据是二进制的,就是怎么怎么解析,但是真正实现起来还是不少问题。通过操作二进制文件的一次实践,收获了以下几点:

1、更深刻地理解到数据在计算机中的保存方式,一切都是0和1的二进制内容,只是看你要怎么用而已,适当的类似转换也可以得到你想要的内容

2、在某个系统下操作就要遵循已定义好的协议,不然得到的都是乱套或者乱码的东西,比如数据的字节序不同也会使数据的解析结果不一致

原创文章,文笔有限,才疏学浅,文中若有不正之处,万望告知。

如果本文对你有帮助,请点个赞吧,谢谢^_^

更多精彩内容,请关注个人公众号。

查看原文

davidyanxw 收藏了文章 · 1月11日

服务端高并发分布式架构演进之路

1. 概述

本文以淘宝作为例子,介绍从一百个到千万级并发情况下服务端的架构的演进过程,同时列举出每个演进阶段会遇到的相关技术,让大家对架构的演进有一个整体的认知,文章最后汇总了一些架构设计的原则。

特别说明:本文以淘宝为例仅仅是为了便于说明演进过程可能遇到的问题,并非是淘宝真正的技术演进路径

2. 基本概念

在介绍架构之前,为了避免部分读者对架构设计中的一些概念不了解,下面对几个最基础的概念进行介绍:

  • 分布式
    系统中的多个模块在不同服务器上部署,即可称为分布式系统,如Tomcat和数据库分别部署在不同的服务器上,或两个相同功能的Tomcat分别部署在不同服务器上
  • 高可用
    系统中部分节点失效时,其他节点能够接替它继续提供服务,则可认为系统具有高可用性
  • 集群
    一个特定领域的软件部署在多台服务器上并作为一个整体提供一类服务,这个整体称为集群。如Zookeeper中的Master和Slave分别部署在多台服务器上,共同组成一个整体提供集中配置服务。在常见的集群中,客户端往往能够连接任意一个节点获得服务,并且当集群中一个节点掉线时,其他节点往往能够自动的接替它继续提供服务,这时候说明集群具有高可用性
  • 负载均衡
    请求发送到系统时,通过某些方式把请求均匀分发到多个节点上,使系统中每个节点能够均匀的处理请求负载,则可认为系统是负载均衡的
  • 正向代理和反向代理
    系统内部要访问外部网络时,统一通过一个代理服务器把请求转发出去,在外部网络看来就是代理服务器发起的访问,此时代理服务器实现的是正向代理;当外部请求进入系统时,代理服务器把该请求转发到系统中的某台服务器上,对外部请求来说,与之交互的只有代理服务器,此时代理服务器实现的是反向代理。简单来说,正向代理是代理服务器代替系统内部来访问外部网络的过程,反向代理是外部请求访问系统时通过代理服务器转发到内部服务器的过程。

3. 架构演进

3.1 单机架构

clipboard.png

以淘宝作为例子。在网站最初时,应用数量与用户数都较少,可以把Tomcat和数据库部署在同一台服务器上。浏览器往www.taobao.com发起请求时,首先经过DNS服务器(域名系统)把域名转换为实际IP地址10.102.4.1,浏览器转而访问该IP对应的Tomcat。

随着用户数的增长,Tomcat和数据库之间竞争资源,单机性能不足以支撑业务

3.2 第一次演进:Tomcat与数据库分开部署

clipboard.png

Tomcat和数据库分别独占服务器资源,显著提高两者各自性能。

随着用户数的增长,并发读写数据库成为瓶颈

3.3 第二次演进:引入本地缓存和分布式缓存

clipboard.png

在Tomcat同服务器上或同JVM中增加本地缓存,并在外部增加分布式缓存,缓存热门商品信息或热门商品的html页面等。通过缓存能把绝大多数请求在读写数据库前拦截掉,大大降低数据库压力。其中涉及的技术包括:使用memcached作为本地缓存,使用Redis作为分布式缓存,还会涉及缓存一致性、缓存穿透/击穿、缓存雪崩、热点数据集中失效等问题。

缓存抗住了大部分的访问请求,随着用户数的增长,并发压力主要落在单机的Tomcat上,响应逐渐变慢

3.4 第三次演进:引入反向代理实现负载均衡

clipboard.png

在多台服务器上分别部署Tomcat,使用反向代理软件(Nginx)把请求均匀分发到每个Tomcat中。此处假设Tomcat最多支持100个并发,Nginx最多支持50000个并发,那么理论上Nginx把请求分发到500个Tomcat上,就能抗住50000个并发。其中涉及的技术包括:Nginx、HAProxy,两者都是工作在网络第七层的反向代理软件,主要支持http协议,还会涉及session共享、文件上传下载的问题。

反向代理使应用服务器可支持的并发量大大增加,但并发量的增长也意味着更多请求穿透到数据库,单机的数据库最终成为瓶颈

3.5 第四次演进:数据库读写分离

clipboard.png

把数据库划分为读库和写库,读库可以有多个,通过同步机制把写库的数据同步到读库,对于需要查询最新写入数据场景,可通过在缓存中多写一份,通过缓存获得最新数据。其中涉及的技术包括:Mycat,它是数据库中间件,可通过它来组织数据库的分离读写和分库分表,客户端通过它来访问下层数据库,还会涉及数据同步,数据一致性的问题。

业务逐渐变多,不同业务之间的访问量差距较大,不同业务直接竞争数据库,相互影响性能

3.6 第五次演进:数据库按业务分库

clipboard.png

把不同业务的数据保存到不同的数据库中,使业务之间的资源竞争降低,对于访问量大的业务,可以部署更多的服务器来支撑。这样同时导致跨业务的表无法直接做关联分析,需要通过其他途径来解决,但这不是本文讨论的重点,有兴趣的可以自行搜索解决方案。

随着用户数的增长,单机的写库会逐渐会达到性能瓶颈

3.7 第六次演进:把大表拆分为小表

clipboard.png

比如针对评论数据,可按照商品ID进行hash,路由到对应的表中存储;针对支付记录,可按照小时创建表,每个小时表继续拆分为小表,使用用户ID或记录编号来路由数据。只要实时操作的表数据量足够小,请求能够足够均匀的分发到多台服务器上的小表,那数据库就能通过水平扩展的方式来提高性能。其中前面提到的Mycat也支持在大表拆分为小表情况下的访问控制。

这种做法显著的增加了数据库运维的难度,对DBA的要求较高。数据库设计到这种结构时,已经可以称为分布式数据库,但是这只是一个逻辑的数据库整体,数据库里不同的组成部分是由不同的组件单独来实现的,如分库分表的管理和请求分发,由Mycat实现,SQL的解析由单机的数据库实现,读写分离可能由网关和消息队列来实现,查询结果的汇总可能由数据库接口层来实现等等,这种架构其实是MPP(大规模并行处理)架构的一类实现。

目前开源和商用都已经有不少MPP数据库,开源中比较流行的有Greenplum、TiDB、Postgresql XC、HAWQ等,商用的如南大通用的GBase、睿帆科技的雪球DB、华为的LibrA等等,不同的MPP数据库的侧重点也不一样,如TiDB更侧重于分布式OLTP场景,Greenplum更侧重于分布式OLAP场景,这些MPP数据库基本都提供了类似Postgresql、Oracle、MySQL那样的SQL标准支持能力,能把一个查询解析为分布式的执行计划分发到每台机器上并行执行,最终由数据库本身汇总数据进行返回,也提供了诸如权限管理、分库分表、事务、数据副本等能力,并且大多能够支持100个节点以上的集群,大大降低了数据库运维的成本,并且使数据库也能够实现水平扩展。

数据库和Tomcat都能够水平扩展,可支撑的并发大幅提高,随着用户数的增长,最终单机的Nginx会成为瓶颈

3.8 第七次演进:使用LVS或F5来使多个Nginx负载均衡

clipboard.png

由于瓶颈在Nginx,因此无法通过两层的Nginx来实现多个Nginx的负载均衡。图中的LVS和F5是工作在网络第四层的负载均衡解决方案,其中LVS是软件,运行在操作系统内核态,可对TCP请求或更高层级的网络协议进行转发,因此支持的协议更丰富,并且性能也远高于Nginx,可假设单机的LVS可支持几十万个并发的请求转发;F5是一种负载均衡硬件,与LVS提供的能力类似,性能比LVS更高,但价格昂贵。由于LVS是单机版的软件,若LVS所在服务器宕机则会导致整个后端系统都无法访问,因此需要有备用节点。可使用keepalived软件模拟出虚拟IP,然后把虚拟IP绑定到多台LVS服务器上,浏览器访问虚拟IP时,会被路由器重定向到真实的LVS服务器,当主LVS服务器宕机时,keepalived软件会自动更新路由器中的路由表,把虚拟IP重定向到另外一台正常的LVS服务器,从而达到LVS服务器高可用的效果。

此处需要注意的是,上图中从Nginx层到Tomcat层这样画并不代表全部Nginx都转发请求到全部的Tomcat,在实际使用时,可能会是几个Nginx下面接一部分的Tomcat,这些Nginx之间通过keepalived实现高可用,其他的Nginx接另外的Tomcat,这样可接入的Tomcat数量就能成倍的增加。

由于LVS也是单机的,随着并发数增长到几十万时,LVS服务器最终会达到瓶颈,此时用户数达到千万甚至上亿级别,用户分布在不同的地区,与服务器机房距离不同,导致了访问的延迟会明显不同

3.9 第八次演进:通过DNS轮询实现机房间的负载均衡

clipboard.png

在DNS服务器中可配置一个域名对应多个IP地址,每个IP地址对应到不同的机房里的虚拟IP。当用户访问www.taobao.com时,DNS服务器会使用轮询策略或其他策略,来选择某个IP供用户访问。此方式能实现机房间的负载均衡,至此,系统可做到机房级别的水平扩展,千万级到亿级的并发量都可通过增加机房来解决,系统入口处的请求并发量不再是问题。

随着数据的丰富程度和业务的发展,检索、分析等需求越来越丰富,单单依靠数据库无法解决如此丰富的需求

3.10 第九次演进:引入NoSQL数据库和搜索引擎等技术

clipboard.png

当数据库中的数据多到一定规模时,数据库就不适用于复杂的查询了,往往只能满足普通查询的场景。对于统计报表场景,在数据量大时不一定能跑出结果,而且在跑复杂查询时会导致其他查询变慢,对于全文检索、可变数据结构等场景,数据库天生不适用。因此需要针对特定的场景,引入合适的解决方案。如对于海量文件存储,可通过分布式文件系统HDFS解决,对于key value类型的数据,可通过HBase和Redis等方案解决,对于全文检索场景,可通过搜索引擎如ElasticSearch解决,对于多维分析场景,可通过Kylin或Druid等方案解决。

当然,引入更多组件同时会提高系统的复杂度,不同的组件保存的数据需要同步,需要考虑一致性的问题,需要有更多的运维手段来管理这些组件等。

引入更多组件解决了丰富的需求,业务维度能够极大扩充,随之而来的是一个应用中包含了太多的业务代码,业务的升级迭代变得困难

3.11 第十次演进:大应用拆分为小应用

clipboard.png

按照业务板块来划分应用代码,使单个应用的职责更清晰,相互之间可以做到独立升级迭代。这时候应用之间可能会涉及到一些公共配置,可以通过分布式配置中心Zookeeper来解决。

不同应用之间存在共用的模块,由应用单独管理会导致相同代码存在多份,导致公共功能升级时全部应用代码都要跟着升级

3.12 第十一次演进:复用的功能抽离成微服务

clipboard.png

如用户管理、订单、支付、鉴权等功能在多个应用中都存在,那么可以把这些功能的代码单独抽取出来形成一个单独的服务来管理,这样的服务就是所谓的微服务,应用和服务之间通过HTTP、TCP或RPC请求等多种方式来访问公共服务,每个单独的服务都可以由单独的团队来管理。此外,可以通过Dubbo、SpringCloud等框架实现服务治理、限流、熔断、降级等功能,提高服务的稳定性和可用性。

不同服务的接口访问方式不同,应用代码需要适配多种访问方式才能使用服务,此外,应用访问服务,服务之间也可能相互访问,调用链将会变得非常复杂,逻辑变得混乱

3.13 第十二次演进:引入企业服务总线ESB屏蔽服务接口的访问差异

clipboard.png

通过ESB统一进行访问协议转换,应用统一通过ESB来访问后端服务,服务与服务之间也通过ESB来相互调用,以此降低系统的耦合程度。这种单个应用拆分为多个应用,公共服务单独抽取出来来管理,并使用企业消息总线来解除服务之间耦合问题的架构,就是所谓的SOA(面向服务)架构,这种架构与微服务架构容易混淆,因为表现形式十分相似。个人理解,微服务架构更多是指把系统里的公共服务抽取出来单独运维管理的思想,而SOA架构则是指一种拆分服务并使服务接口访问变得统一的架构思想,SOA架构中包含了微服务的思想。

业务不断发展,应用和服务都会不断变多,应用和服务的部署变得复杂,同一台服务器上部署多个服务还要解决运行环境冲突的问题,此外,对于如大促这类需要动态扩缩容的场景,需要水平扩展服务的性能,就需要在新增的服务上准备运行环境,部署服务等,运维将变得十分困难

3.14 第十三次演进:引入容器化技术实现运行环境隔离与动态服务管理

clipboard.png

目前最流行的容器化技术是Docker,最流行的容器管理服务是Kubernetes(K8S),应用/服务可以打包为Docker镜像,通过K8S来动态分发和部署镜像。Docker镜像可理解为一个能运行你的应用/服务的最小的操作系统,里面放着应用/服务的运行代码,运行环境根据实际的需要设置好。把整个“操作系统”打包为一个镜像后,就可以分发到需要部署相关服务的机器上,直接启动Docker镜像就可以把服务起起来,使服务的部署和运维变得简单。

在大促的之前,可以在现有的机器集群上划分出服务器来启动Docker镜像,增强服务的性能,大促过后就可以关闭镜像,对机器上的其他服务不造成影响(在3.14节之前,服务运行在新增机器上需要修改系统配置来适配服务,这会导致机器上其他服务需要的运行环境被破坏)。

使用容器化技术后服务动态扩缩容问题得以解决,但是机器还是需要公司自身来管理,在非大促的时候,还是需要闲置着大量的机器资源来应对大促,机器自身成本和运维成本都极高,资源利用率低

3.15 第十四次演进:以云平台承载系统

clipboard.png

系统可部署到公有云上,利用公有云的海量机器资源,解决动态硬件资源的问题,在大促的时间段里,在云平台中临时申请更多的资源,结合Docker和K8S来快速部署服务,在大促结束后释放资源,真正做到按需付费,资源利用率大大提高,同时大大降低了运维成本。

所谓的云平台,就是把海量机器资源,通过统一的资源管理,抽象为一个资源整体,在之上可按需动态申请硬件资源(如CPU、内存、网络等),并且之上提供通用的操作系统,提供常用的技术组件(如Hadoop技术栈,MPP数据库等)供用户使用,甚至提供开发好的应用,用户不需要关系应用内部使用了什么技术,就能够解决需求(如音视频转码服务、邮件服务、个人博客等)。在云平台中会涉及如下几个概念:

  • IaaS:基础设施即服务。对应于上面所说的机器资源统一为资源整体,可动态申请硬件资源的层面;
  • PaaS:平台即服务。对应于上面所说的提供常用的技术组件方便系统的开发和维护;
  • SaaS:软件即服务。对应于上面所说的提供开发好的应用或服务,按功能或性能要求付费。
至此,以上所提到的从高并发访问问题,到服务的架构和系统实施的层面都有了各自的解决方案,但同时也应该意识到,在上面的介绍中,其实是有意忽略了诸如跨机房数据同步、分布式事务实现等等的实际问题,这些问题以后有机会再拿出来单独讨论

4. 架构设计总结

  • 架构的调整是否必须按照上述演变路径进行?
    不是的,以上所说的架构演变顺序只是针对某个侧面进行单独的改进,在实际场景中,可能同一时间会有几个问题需要解决,或者可能先达到瓶颈的是另外的方面,这时候就应该按照实际问题实际解决。如在政府类的并发量可能不大,但业务可能很丰富的场景,高并发就不是重点解决的问题,此时优先需要的可能会是丰富需求的解决方案。
  • 对于将要实施的系统,架构应该设计到什么程度?
    对于单次实施并且性能指标明确的系统,架构设计到能够支持系统的性能指标要求就足够了,但要留有扩展架构的接口以便不备之需。对于不断发展的系统,如电商平台,应设计到能满足下一阶段用户量和性能指标要求的程度,并根据业务的增长不断的迭代升级架构,以支持更高的并发和更丰富的业务。
  • 服务端架构和大数据架构有什么区别?
    所谓的“大数据”其实是海量数据采集清洗转换、数据存储、数据分析、数据服务等场景解决方案的一个统称,在每一个场景都包含了多种可选的技术,如数据采集有Flume、Sqoop、Kettle等,数据存储有分布式文件系统HDFS、FastDFS,NoSQL数据库HBase、MongoDB等,数据分析有Spark技术栈、机器学习算法等。总的来说大数据架构就是根据业务的需求,整合各种大数据组件组合而成的架构,一般会提供分布式存储、分布式计算、多维分析、数据仓库、机器学习算法等能力。而服务端架构更多指的是应用组织层面的架构,底层能力往往是由大数据架构来提供。
  • 有没有一些架构设计的原则?

    • N+1设计。系统中的每个组件都应做到没有单点故障;
    • 回滚设计。确保系统可以向前兼容,在系统升级时应能有办法回滚版本;
    • 禁用设计。应该提供控制具体功能是否可用的配置,在系统出现故障时能够快速下线功能;
    • 监控设计。在设计阶段就要考虑监控的手段;
    • 多活数据中心设计。若系统需要极高的高可用,应考虑在多地实施数据中心进行多活,至少在一个机房断电的情况下系统依然可用;
    • 采用成熟的技术。刚开发的或开源的技术往往存在很多隐藏的bug,出了问题没有商业支持可能会是一个灾难;
    • 资源隔离设计。应避免单一业务占用全部资源;
    • 架构应能水平扩展。系统只有做到能水平扩展,才能有效避免瓶颈问题;
    • 非核心则购买。非核心功能若需要占用大量的研发资源才能解决,则考虑购买成熟的产品;
    • 使用商用硬件。商用硬件能有效降低硬件故障的机率;
    • 快速迭代。系统应该快速开发小功能模块,尽快上线进行验证,早日发现问题大大降低系统交付的风险;
    • 无状态设计。服务接口应该做成无状态的,当前接口的访问不依赖于接口上次访问的状态。
查看原文

davidyanxw 收藏了文章 · 2020-12-30

缓存原理与微服务缓存自动管理

抛开业务谈技术都是在耍流氓。—— Kevin Wan

为什么需要缓存?

先从一个老生常谈的问题开始谈起:我们的程序是如何运行起来的?

  1. 程序存储在 disk
  2. 程序是运行在 RAM 之中,也就是我们所说的 main memory
  3. 程序的计算逻辑在 CPU 中执行

来看一个最简单的例子:a = a + 1

  1. load x:
  2. x0 = x0 + 1
  3. load x0 -> RAM

上面提到了3种存储介质。我们都知道,三类的读写速度和成本成反比,所以我们在克服速度问题上需要引入一个 中间层。这个中间层,需要高速存取的速度,但是成本可接受。于是乎,Cache 被引入

而在计算机系统中,有两种默认缓存:

  • CPU 里面的末级缓存,即 LLC。缓存内存中的数据
  • 内存中的高速页缓存,即 page cache。缓存磁盘中的数据

缓存读写策略

引入 Cache 之后,我们继续来看看操作缓存会发生什么。因为存在存取速度的差异「而且差异很大」,从而在操作数据时,延迟或程序失败等都会导致缓存和实际存储层数据不一致。

我们就以标准的 Cache+DB 来看看经典读写策略和应用场景。

Cache Aside

先来考虑一种最简单的业务场景,比如用户表:userId:用户id, phone:用户电话token,avtoar:用户头像url,缓存中我们用 phone 作为key存储用户头像。当用户修改头像url该如何做?

  1. 更新DB数据,再更新Cache 数据
  2. 更新 DB 数据,再删除 Cache 数据

首先 变更数据库变更缓存 是两个独立的操作,而我们并没有对操作做任何的并发控制。那么当两个线程并发更新它们的时候,就会因为写入顺序的不同造成数据不一致。

所以更好的方案是 2

  • 更新数据时不更新缓存,而是直接删除缓存
  • 后续的请求发现缓存缺失,回去查询 DB ,并将结果 load cache

这个策略就是我们使用缓存最常见的策略:Cache Aside。这个策略数据以数据库中的数据为准,缓存中的数据是按需加载的,分为读策略和写策略。

但是可见的问题也就出现了:频繁的读写操作会导致 Cache 反复地替换,缓存命中率降低。当然如果在业务中对命中率有监控报警时,可以考虑以下方案:

  1. 更新数据时同时更新缓存,但是在更新缓存前加一个 分布式锁。这样同一时间只有一个线程操作缓存,解决了并发问题。同时在后续读请求中时读到最新的缓存,解决了不一致的问题。
  2. 更新数据时同时更新缓存,但是给缓存一个较短的 TTL

当然除了这个策略,在计算机体系还有其他几种经典的缓存策略,它们也有各自适用的使用场景。

Write Through

先查询写入数据key是否击中缓存,如果在 -> 更新缓存,同时缓存组件同步数据至DB;不存在,则触发 Write Miss

而一般 Write Miss 有两种方式:

  • Write Allocate:写时直接分配 Cache line
  • No-write allocate:写时不写入缓存,直接写入DB,return

Write Through 中,一般采取 No-write allocate 。因为其实无论哪种,最终数据都会持久化到DB中,省去一步缓存的写入,提升写性能。而缓存由 Read Through 写入缓存。

这个策略的核心原则:用户只与缓存打交道,由缓存组件和DB通信,写入或者读取数据。在一些本地进程缓存组件可以考虑这种策略。

Write Back

相信你也看出上述方案的缺陷:写数据时缓存和数据库同步,但是我们知道这两块存储介质的速度差几个数量级,对写入性能是有很大影响。那我们是否异步更新数据库?

Write back 就是在写数据时只更新该 Cache Line 对应的数据,并把该行标记为 Dirty。在读数据时或是在缓存满时换出「缓存替换策略」时,将 Dirty 写入存储。

需要注意的是:在 Write Miss 情况下,采取的是 Write Allocate,即写入存储同时写入缓存,这样我们在之后的写请求只需要更新缓存。

async purge 此类概念其实存在计算机体系中。Mysql 中刷脏页,本质都是尽可能防止随机写,统一写磁盘时机。

Redis

Redis是一个独立的系统软件,和我们写的业务程序是两个软件。当我们部署了Redis 实例后,它只会被动地等待客户端发送请求,然后再进行处理。所以,如果应用程序想要使用 Redis 缓存,我们就要在程序中增加相应的缓存操作代码。所以我们也把 Redis 称为 旁路缓存,也就是说:读取缓存、读取数据库和更新缓存的操作都需要在应用程序中来完成。

而作为缓存的 Redis,同样需要面临常见的问题:

  • 缓存的容量终究有限
  • 上游并发请求冲击
  • 缓存与后端存储数据一致性

替换策略

一般来说,缓存对于选定的被淘汰数据,会根据其是干净数据还是脏数据,选择直接删除还是写回数据库。但是,在 Redis 中,被淘汰数据无论干净与否都会被删除,所以,这是我们在使用 Redis 缓存时要特别注意的:当数据修改成为脏数据时,需要在数据库中也把数据修改过来。

所以不管替换策略是什么,脏数据有可能在换入换出中丢失。那我们在产生脏数据就应该删除缓存,而不是更新缓存,一切数据应该以数据库为准。这也很好理解,缓存写入应该交给读请求来完成;写请求尽可能保证数据一致性。

至于替换策略有哪些,网上已经有很多文章归纳之间的优劣,这里就不再赘述。

ShardCalls

并发场景下,可能会有多个线程(协程)同时请求同一份资源,如果每个请求都要走一遍资源的请求过程,除了比较低效之外,还会对资源服务造成并发的压力。

go-zero 中的 ShardCalls 可以使得同时多个请求只需要发起一次拿结果的调用,其他请求"坐享其成",这种设计有效减少了资源服务的并发压力,可以有效防止缓存击穿。

对于防止暴增的接口请求对下游服务造成瞬时高负载,可以在你的函数包裹:

fn = func() (interface{}, error) {
  // 业务查询
}
data, err = g.Do(apiKey, fn)
// 就获得到data,之后的方法或者逻辑就可以使用这个data

其实原理也很简单:

func (g *sharedGroup) Do(key string, fn func() (interface{}, error)) (interface{}, error) {
  // done: false,才会去执行下面的业务逻辑;为 true,直接返回之前获取的data
  c, done := g.createCall(key)
  if done {
    return c.val, c.err
  }
  
  // 执行调用者传入的业务逻辑
  g.makeCall(c, key, fn)
  return c.val, c.err
}

func (g *sharedGroup) createCall(key string) (c *call, done bool) {
  // 只让一个请求进来进行操作
  g.lock.Lock()
  // 如果携带标示一系列请求的key在 calls 这个map中已经存在,
  // 则解锁并同时等待之前请求获取数据,返回
  if c, ok := g.calls[key]; ok {
    g.lock.Unlock()
    c.wg.Wait()
    return c, true
  }
  
  // 说明本次请求是首次请求
  c = new(call)
  c.wg.Add(1)
  // 标注请求,因为持有锁,不用担心并发问题
  g.calls[key] = c
  g.lock.Unlock()

  return c, false
}

这种 map+lock 存储并限制请求操作,和groupcache中的 singleflight 类似,都是防止缓存击穿的利器

源码地址:sharedcalls.go

缓存和存储更新顺序

这是开发中常见纠结问题:到底是先删除缓存还是先更新存储?

情况一:先删除缓存,再更新存储;

  • A 删除缓存,更新存储时网络延迟
  • B 读请求,发现缓存缺失,读存储 -> 此时读到旧数据

这样会产生两个问题:

  • B 读取旧值
  • B 同时读请求会把旧值写入缓存,导致后续读请求读到旧值

既然是缓存可能是旧值,那就不管删除。有一个并不优雅的解决方案:在写请求更新完存储值以后,sleep() 一小段时间,再进行一次缓存删除操作

sleep 是为了确保读请求结束,写请求可以删除读请求造成的缓存脏数据,当然也要考虑到 redis 主从同步的耗时。不过还是要根据实际业务而定。

这个方案会在第一次删除缓存值后,延迟一段时间再次进行删除,被称为:延迟双删

情况二:先更新数据库值,再删除缓存值:

  • A 删除存储值,但是删除缓存网络延迟
  • B 读请求时,缓存击中,就直接返回旧值

这种情况对业务的影响较小,而绝大多数缓存组件都是采取此种更新顺序,满足最终一致性要求。

情况三:新用户注册,直接写入数据库,同时缓存中肯定没有。如果程序此时读从库,由于主从延迟,导致读取不到用户数据。

这种情况就需要针对 Insert 这种操作:插入新数据入数据库同时写缓存。使得后续读请求可以直接读缓存,同时因为是刚插入的新数据,在一段时间修改的可能性不大。

以上方案在复杂的情况或多或少都有潜在问题,需要贴合业务做具体的修改

如何设计好用的缓存操作层?

上面说了这么多,回到我们开发角度,如果我们需要考虑这么多问题,显然太麻烦了。所以如何把这些缓存策略和替换策略封装起来,简化开发过程?

明确几点:

  • 将业务逻辑和缓存操作分离,留给开发这一个写入逻辑的点
  • 缓存操作需要考虑流量冲击,缓存策略等问题。。。

我们从读和写两个角度去聊聊 go-zero 是如何封装。

QueryRow

// res: query result
// cacheKey: redis key
err := m.QueryRow(&res, cacheKey, func(conn sqlx.SqlConn, v interface{}) error {
  querySQL := `select * from your_table where campus_id = ? and student_id = ?`
  return conn.QueryRow(v, querySQL, campusId, studentId)
})

我们将开发查询业务逻辑用 func(conn sqlx.SqlConn, v interface{}) 封装。用户无需考虑缓存写入,只需要传入需要写入的 cacheKey。同时把查询结果 res 返回。

那缓存操作是如何被封装在内部呢?来看看函数内部:

func (c cacheNode) QueryRow(v interface{}, key string, query func(conn sqlx.SqlConn, v interface{}) error) error {
 cacheVal := func(v interface{}) error {
  return c.SetCache(key, v)
 }
 // 1. cache hit -> return
  // 2. cache miss -> err
 if err := c.doGetCache(key, v); err != nil {
    // 2.1 err defalut val {*}
  if err == errPlaceholder {
   return c.errNotFound
  } else if err != c.errNotFound {
   return err
  }
  // 2.2 cache miss -> query db
    // 2.2.1 query db return err {NotFound} -> return err defalut val「see 2.1」
  if err = query(c.db, v); err == c.errNotFound {
   if err = c.setCacheWithNotFound(key); err != nil {
    logx.Error(err)
   }

   return c.errNotFound
  } else if err != nil {
   c.stat.IncrementDbFails()
   return err
  }
  // 2.3 query db success -> set val to cache
  if err = cacheVal(v); err != nil {
   logx.Error(err)
   return err
  }
 }
 // 1.1 cache hit -> IncrementHit
 c.stat.IncrementHit()

 return nil
}

从流程上恰好对应缓存策略中的:Read Through

源码地址:cachedsql.go

Exec

而写请求,使用的就是之前缓存策略中的 Cache Aside -> 先写数据库,再删除缓存。

_, err := m.Exec(func(conn sqlx.SqlConn) (result sql.Result, err error) {
  execSQL := fmt.Sprintf("update your_table set %s where 1=1", m.table, AuthRows)
  return conn.Exec(execSQL, data.RangeId, data.AuthContentId)
}, keys...)

func (cc CachedConn) Exec(exec ExecFn, keys ...string) (sql.Result, error) {
 res, err := exec(cc.db)
 if err != nil {
  return nil, err
 }

 if err := cc.DelCache(keys...); err != nil {
  return nil, err
 }

 return res, nil
}

QueryRow 一样,调用者只需要负责业务逻辑,缓存写入和删除对调用透明。

源码地址:cachedsql.go

线上的缓存

开篇第一句话:脱离业务将技术都是耍流氓。以上都是在对缓存模式分析,但是实际业务中缓存是否起到应有的加速作用?最直观就是缓存击中率,而如何观测到服务的缓存击中?这就涉及到监控。

下图是我们线上环境的某个服务的缓存记录情况:

还记得上面 QueryRow 中:查询缓存击中,会调用 c.stat.IncrementHit()。其中的 stat 就是作为监控指标,不断在计算击中率和失败率。

源码地址:cachestat.go

在其他的业务场景中:比如首页信息浏览业务中,大量请求不可避免。所以缓存首页的信息在用户体验上尤其重要。但是又不像之前提到的一些单一的key,这里可能涉及大量消息,这个时候就需要其他缓存类型加入:

  1. 拆分缓存:可以分 消息id -> 由 消息id 查询消息,并缓存插入消息list中。
  2. 消息过期:设置消息过期时间,做到不占用过长时间缓存。

这里也就是涉及缓存的最佳实践:

  • 不允许不过期的缓存「尤为重要」
  • 分布式缓存,易伸缩
  • 自动生成,自带统计

总结

本文从缓存的引入,常见缓存读写策略,如何保证数据的最终一致性,如何封装一个好用的缓存操作层,也展示了线上缓存的情况以及监控。所有上面谈到的这些缓存细节都可以参考 go-zero 源码实现,见 go-zero 源码的 core/stores

项目地址

https://github.com/tal-tech/go-zero

欢迎使用 go-zero 并 star 鼓励我们!👏🏻

项目地址:
https://github.com/tal-tech/go-zero
查看原文

davidyanxw 收藏了文章 · 2020-12-29

DP 就是暴力,暴力就是艺术

题目地址(面试题 17.23. 最大黑方阵)

https://leetcode-cn.com/probl...

题目描述

给定一个方阵,其中每个单元(像素)非黑即白。设计一个算法,找出 4 条边皆为黑色像素的最大子方阵。

返回一个数组 [r, c, size] ,其中 r, c 分别代表子方阵左上角的行号和列号,size 是子方阵的边长。若有多个满足条件的子方阵,返回 r 最小的,若 r 相同,返回 c 最小的子方阵。若无满足条件的子方阵,返回空数组。

示例 1:

输入:
[
   [1,0,1],
   [0,0,1],
   [0,0,1]
]
输出: [1,0,2]
解释: 输入中 0 代表黑色,1 代表白色,标粗的元素即为满足条件的最大子方阵
示例 2:

输入:
[
   [0,1,1],
   [1,0,1],
   [1,1,0]
]
输出: [0,0,1]
提示:

matrix.length == matrix[0].length <= 200

前置知识

公司

  • 暂无

思路

看了下数据范围,矩阵大小不超过 $200 \times 200$,因此答案应该就是暴力,这个数据范围差不多 N 的三次方的复杂度都可以通过,其中 N 为矩阵的边长。原因我也在之前的文章来和大家聊聊我是如何刷题的(第三弹)中讲过了,那就是 $200^3$ 刚好是是 800 万,再多就很容易超过 1000 万了。

乍一看,这道题和 221. 最大正方形,实则不然。 这道题是可以空心的,只要边长是部分都是 0 即可,这就完全不同了。

如下图,红色部分就是答案。只需要保证边全部是 0 就好了,所以里面有一个 1 无所谓的。

我们不妨从局部入手,看能不能打开思路。

这是一种常用的技巧,当你面对难题无从下手的时候可以画个图,从特殊情况和局部情况开始,帮助我们打开思路。

比如我想计算以如下图红色格子为右下角的最大黑方阵。我们可以从当前点向上向左扩展直到非 0。

在上面的例子中,不难看出其最大黑方阵不会超过 min(4, 5)。

那答案直接就是 4 么? 对于这种情况是的, 但是也存在其他情况。比如:

因此解空间上界虽然是 4,但是下界仍然可能为 1。

下界为 1 是因为我们只对值为 0 的格子感兴趣,如果格子为 0 ,最差最大方阵就是自身。

上面我已经将算法锁定为暴力求解了。对于解空间的暴力求解怎么做?无非就是枚举所有解空间,最多减减枝

直白一点来说就是:

  • 1 可以么?
  • 2 可以么?
  • 3 可以么?
  • 4 可以么?

这叫做特殊。

如果你已经搞懂了这个特殊情况, 那么一般情况也就不难了。

算法描述:

  1. 从左到右从上到下扫描一次矩阵。
  2. 如果格子值是 0,则分别向上和向左扫描直到第一个不是 0 的格子,那么最大方阵的上界就是 min(向左延伸的长度, 向上延伸的长度)。
  3. 逐步尝试[1, 上界] 直到无法形成方阵,最后可行的方阵就是以当前点能 形成的最大方阵。
  4. 扫描过程维护最大值,最后返回最大值以及顶点信息即可。

现在的难点只剩下第三点部分如何逐步尝试[1, 上界]。实际上这个也不难,只需要:

  • 在向左延伸的同时向上探测
  • 在向上延伸的同时向左探测

看一下图或许好理解一点。

如上图就是尝试 2 是否可行,如果可行,我们继续得寸进尺,直到不可行或者到上界。

接下来,分析一下算法的时间复杂度。

  • 由于每一个为 0 的点都需要向左向上探测,那么最坏就是 O(N),其中 N 为边长。
  • 向左向上的同时需要继续探测,这个复杂度最坏的情况也是 O(N)。

由于我们需要对最多$O(N^2)$个点执行上面的逻辑,因此总的时间复杂度就是 $$O(N^4)$$

而实际上每一个格子都是一个独立的子问题, 因此可以使用一个 memo(比如哈希表)将每个格子的扩展结果保存起来,这样可以将复杂度优化到 $O(N^3)$。

比如上面提到的向上向左探测的过程,如果上面和左面格子的扩展结果已经计算出来了,那么直接用就行了,这部分延伸的复杂度可以降低到 $O(1)$。因此不难看出, 当前格子的计算依赖于左侧和上方格子,因此使用从左到右从上到下扫描矩阵 是正确的选择,因为我们需要在遍历当当前格子的时候左侧和上方格子的结果已经被计算出来了

  1. (4,5) 找到上方相邻的格子,如果是 1 直接返回。
  2. 如果上方格子值是 0 ,去 memo 中查询。
  3. memo 返回 结果,我们只需要将这个结果 + 1 就是可以向上延伸的最大长度了。

比如现在要计算以坐标(4,5) 为右下角的最大方阵的边长。第一步要向上探测到 (3,5),到达(3,5) 之后无需继续往上延伸而是从 memo 中获取。(4,5) 上方的 0 的格子就是(3,5) 上方的格子个数 + 1。

最后一个问题。什么数据结构可以实现上面查询过程 $O(1)$ 时间呢?hashmap 可以,数组也可以。

  • 使用哈希 map 的好处是无非事先开辟空间。缺点是如果数据量太大,可能会因为哈希表的冲突处理导致超时。比如石子游戏使用哈希表存就很容易超时。
  • 使用数组好处和坏处几乎和哈希表是相反的。数组需要实现指定大小, 但是数组是不会冲突的,也不需要计算哈希键,因此在很多情况下性能更好。进一步使用数组这种内存连续的数据结构对 CPU 友好,因此同样复杂度会更快。 而哈希表使用了链表或者树,因此对 CPU 缓存就没那么友好了。

综上,我推荐大家使用数组来存储。

这道题差不多就是这样了。实际上,这就是动态规划优化,其实也没什么神奇嘛,很多时候都是暴力枚举 + 记忆化而已。

代码

代码支持:Java,Python

Java Code:

class Solution {
    public int[] findSquare(int[][] matrix) {
        int [] res = new int [0];
        int [][][] dp = new int [2][matrix.length+1][matrix[0].length+1];
        int max = 0
        for(int i=1;i<=matrix.length;i++){
            for(int j=1;j<=matrix[0].length;j++){
                if(matrix[i-1][j-1]==0){
                    dp[0][i][j] = dp[0][i-1][j]+1;
                    dp[1][i][j] = dp[1][i][j-1]+1;
                    int bound = Math.min(dp[0][i][j], dp[1][i][j]);
                    for(int k=0;k<bound;k++){
                        if(dp[1][i-k][j]>=k+1&&dp[0][i][j-k]>=k+1){
                            if(k+1>max){
                                res = new int [3];
                                max = k+1;
                                res[0] = i-k-1;
                                res[1] = j-k-1;
                                res[2] = max;
                            }
                        }
                    }
                }
            }
        }
        return res;
    }
}

Python Code:

class Solution:
    def findSquare(self, matrix: List[List[int]]) -> List[int]:
        n = len(matrix)
        dp = [[[0, 0] for _ in range(n + 1)] for _ in range(n + 1)]
        ans = []
        for i in range(1, n + 1):
            for j in range(1, n + 1):
                if matrix[i - 1][j - 1] == 0:
                    dp[i][j][0] = dp[i-1][j][0] + 1
                    dp[i][j][1] = dp[i][j-1][1] + 1
                    upper = min(dp[i][j][0], dp[i][j][1])
                    for k in range(upper):
                        if min(dp[i-k][j][1], dp[i][j-k][0]) >= k + 1:
                            if not ans or k + 1 > ans[2]:
                                ans = [i-k-1, j-k-1, k + 1]

        return ans

复杂度分析

  • 时间复杂度:$O(N^3)$,其中 N 为矩阵边长。
  • 空间复杂度:空间的瓶颈在于 memo,而 memo 的大小为矩阵的大小,因此空间复杂度为 $O(N^2)$,其中 N 为矩阵边长。

以上就是本文的全部内容了。大家对此有何看法,欢迎给我留言,我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库:https://github.com/azl3979858... 。 目前已经 38K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。

查看原文

davidyanxw 收藏了文章 · 2020-12-29

跳表 | 会跳的链表真的非常diao

原创公众号「bigsai
文章已收录在 我的Github bigsai-algorithm

前言

跳表是面试常问的一种数据结构,它在很多中间件和语言中得到应用,我们熟知的就有Redis跳表。并且在面试的很多场景可能会问到,偶尔还会让你手写试一试(跳表可能会让手写,红黑树是不可能的),这不,给大伙复原一个场景:

image-20201225113330615

但你别慌,遇到蘑菇头这种面试官也别怕,因为你看到这篇文章了(得意😏),不用像熊猫那样窘迫。

对于一个数据结构或算法,人群数量从听过名称、了解基本原理、清楚执行流程、能够手写 呈抖降的趋势。因为很多数据结构与算法其核心原理可能简单,但清楚其执行流程就需要动脑子去思考想明白,但是如果能够把它写出来,那就要自己一步步去设计和实现。可能要花很久才能真正写出来,并且还可能要查阅大量的资料。

而本文在前面进行介绍跳表,后面部分详细介绍跳表的设计和实现,搞懂跳表,这一篇真的就够了。

快速了解跳表

跳跃表(简称跳表)由美国计算机科学家William Pugh发明于1989年。他在论文《Skip lists: a probabilistic alternative to balanced trees》中详细介绍了跳表的数据结构和插入删除等操作。

跳表(SkipList,全称跳跃表)是用于有序元素序列快速搜索查找的一个数据结构,跳表是一个随机化的数据结构,实质就是一种可以进行二分查找的有序链表。跳表在原有的有序链表上面增加了多级索引,通过索引来实现快速查找。跳表不仅能提高搜索性能,同时也可以提高插入和删除操作的性能。它在性能上和红黑树,AVL树不相上下,但是跳表的原理非常简单,实现也比红黑树简单很多。

在这里你可以看到一些关键词:链表(有序链表)、索引、二分查找。想必你的脑海中已经有了一个初略的印象,不过你可能还是不清楚这个"会跳的链表"有多diao,甚至还可能会产生一点疑虑:跟随机化有什么关系?你在下文中很快就能得到答案!

回顾链表,我们知道链表和顺序表(数组)通常都是相爱相杀,成对出现,各有优劣。而链表的优势就是更高效的插入、删除。痛点就是查询很慢很慢!每次查询都是一种O(n)复杂度的操作,链表估计自己都气的想哭了😢。

image-20201224155243423

这是一个带头结点的链表(头结点相当于一个固定的入口,不存储有意义的值),每次查找都需要一个个枚举,相当的慢,我们能不能稍微优化一下,让它稍微跳一跳呢?答案是可以的,我们知道很多算法和数据结构以空间换时间,我们在上面加一层索引,让部分节点在上层能够直接定位到,这样链表的查询时间近乎减少一半,链表自己虽然没有开心起来,但收起了它想哭的脸。

image-20201224160740034

这样,在查询某个节点的时候,首先会从上一层快速定位节点所在的一个范围,如果找到具体范围向下然后查找代价很小,当然在表的结构设计上会增加一个向下的索引(指针)用来查找确定底层节点。平均查找速度平均为O(n/2)。但是当节点数量很大的时候,它依旧很慢很慢。我们都知道二分查找是每次都能折半的去压缩查找范围,要是有序链表也能这么跳起来那就太完美了。没错跳表就能让链表拥有近乎的接近二分查找的效率的一种数据结构,其原理依然是给上面加若干层索引,优化查找速度。

image-20201224175922421

通过上图你可以看到,通过这样的一个数据结构对有序链表进行查找都能近乎二分的性能。就是在上面维护那么多层的索引,首先在最高级索引上查找最后一个小于当前查找元素的位置,然后再跳到次高级索引继续查找,直到跳到最底层为止,这时候以及十分接近要查找的元素的位置了(如果查找元素存在的话)。由于根据索引可以一次跳过多个元素,所以跳查找的查找速度也就变快了。

对于理想的跳表,每向上一层索引节点数量都是下一层的1/2.那么如果n个节点增加的节点数量(1/2+1/4+…)<n。并且层数较低,对查找效果影响不大。但是对于这么一个结构,你可能会疑惑,这样完美的结构真的存在吗?大概率不存在的,因为作为一个链表,少不了增删该查的一些操作。而删除和插入可能会改变整个结构,所以上面的这些都是理想的结构,在插入的时候是否添加上层索引是个概率问题(1/2的概率),在后面会具体讲解。

跳表的增删改查

上面稍微了解了跳表是个啥,那么在这里就给大家谈谈跳表的增删改查过程。在实现本跳表的过程为了便于操作,我们将跳表的头结点(head)的key设为int的最小值(一定满足左小右大方便比较)。

对于每个节点的设置,设置成SkipNode类,为了防止初学者将next向下还是向右搞混,直接设置right,down两个指针。

class SkipNode<T>
{
    int key;
    T value;
    SkipNode right,down;//右下个方向的指针
    public SkipNode (int key,T value) {
        this.key=key;
        this.value=value;
    }
}

跳表的结构和初始化也很重要,其主要参数和初始化方法为:

public class SkipList <T> {
    
    SkipNode headNode;//头节点,入口
    int highLevel;//当前跳表索引层数
    Random random;// 用于投掷硬币
    final int MAX_LEVEL = 32;//最大的层

    SkipList(){
        random=new Random();
        headNode=new SkipNode(Integer.MIN_VALUE,null);
        highLevel=0;
    }
    //其他方法
}

查询操作

很多时候链表也可能这样相连仅仅是某个元素或者key作为有序的标准。所以有可能链表内部存在一些value。不过修改和查询其实都是一个操作,找到关键数字(key)。并且查找的流程也很简单,设置一个临时节点team=head。当team不为null其流程大致如下:

(1) 从team节点出发,如果当前节点的key与查询的key相等,那么返回当前节点(如果是修改操作那么一直向下进行修改值即可)。

(2) 如果key不相等,且右侧为null,那么证明只能向下(结果可能出现在下右方向),此时team=team.down

(3) 如果key不相等,且右侧不为null,且右侧节点key小于待查询的key。那么说明同级还可向右,此时team=team.right

(4)(否则的情况)如果key不相等,且右侧不为null,且右侧节点key大于待查询的key 。那么说明如果有结果的话就在这个索引和下个索引之间,此时team=team.down。

最终将按照这个步骤返回正确的节点或者null(说明没查到)。

image-20201224210130178

例如上图查询12节点,首先第一步从head出发发现右侧不为空,且7<12,向右;第二步右侧为null向下;第三步节点7的右侧10<12继续向右;第四步10右侧为null向下;第五步右侧12小于等于向右。第六步起始发现相等返回节点结束。

而这块的代码也非常容易:

public SkipNode search(int key) {
    SkipNode team=headNode;
    while (team!=null) {
        if(team.key==key)
        {
            return  team;
        }
        else if(team.right==null)//右侧没有了,只能下降
        {
            team=team.down;
        }
        else if(team.right.key>key)//需要下降去寻找
        {
            team=team.down;
        }
        else //右侧比较小向右
        {
            team=team.right;
        }
    }
    return null;
}

删除操作

删除操作比起查询稍微复杂一丢丢,但是比插入简单。删除需要改变链表结构所以需要处理好节点之间的联系。对于删除操作你需要谨记以下几点:

(1)删除当前节点和这个节点的前后节点都有关系

(2)删除当前层节点之后,下一层该key的节点也要删除,一直删除到最底层

根据这两点分析一下:如果找到当前节点了,它的前面一个节点怎么查找呢?这个总不能在遍历一遍吧!有的使用四个方向的指针(上下左右)用来找到左侧节点。是可以的,但是这里可以特殊处理一下 ,不直接判断和操作节点,先找到待删除节点的左侧节点。通过这个节点即可完成删除,然后这个节点直接向下去找下一层待删除的左侧节点。设置一个临时节点team=head,当team不为null具体循环流程为:

(1)如果team右侧为null,那么team=team.down(之所以敢直接这么判断是因为左侧有头结点在左侧,不用担心特殊情况)

(2)如果team右侧不 为null,并且右侧的key等于待删除的key,那么先删除节点,再team向下team=team.down为了删除下层节点。

(3)如果team右侧不 为null,并且右侧key小于待删除的key,那么team向右team=team.right。

(4)如果team右侧不 为null,并且右侧key大于待删除的key,那么team向下team=team.down,在下层继续查找删除节点。

image-20201225002518856

例如上图删除10节点,首先team=head从team出发,7<10向右(team=team.right后面省略);第二步右侧为null只能向下;第三部右侧为10在当前层删除10节点然后向下继续查找下一层10节点;第四步8<10向右;第五步右侧为10删除该节点并且team向下。team为null说明删除完毕退出循环。

删除操作实现的代码如下:

public void delete(int key)//删除不需要考虑层数
{
    SkipNode team=headNode;
    while (team!=null) {
        if (team.right == null) {//右侧没有了,说明这一层找到,没有只能下降
            team=team.down;
        }
        else if(team.right.key==key)//找到节点,右侧即为待删除节点
        {
            team.right=team.right.right;//删除右侧节点
            team=team.down;//向下继续查找删除
        }
        else if(team.right.key>key)//右侧已经不可能了,向下
        {
            team=team.down;
        }
        else { //节点还在右侧
            team=team.right;
        }
    }
}

插入操作

插入操作在实现起来是最麻烦的,需要的考虑的东西最多。回顾查询,不需要动索引;回顾删除,每层索引如果有删除就是了。但是插入不一样了,插入需要考虑是否插入索引,插入几层等问题。由于需要插入删除所以我们肯定无法维护一个完全理想的索引结构,因为它耗费的代价太高。但我们使用随机化的方法去判断是否向上层插入索引。即产生一个[0-1]的随机数如果小于0.5就向上插入索引,插入完毕后再次使用随机数判断是否向上插入索引。运气好这个值可能是多层索引,运气不好只插入最底层(这是100%插入的)。但是索引也不能不限制高度,我们一般会设置索引最高值如果大于这个值就不往上继续添加索引了。

我们一步步剖析该怎么做,其流程为

(1)首先通过上面查找的方式,找到待插入的左节点。插入的话最底层肯定是需要插入的,所以通过链表插入节点(需要考虑是否为末尾节点)

(2)插入完这一层,需要考虑上一层是否插入,首先判断当前索引层级,如果大于最大值那么就停止(比如已经到最高索引层了)。否则设置一个随机数1/2的概率向上插入一层索引(因为理想状态下的就是每2个向上建一个索引节点)。

(3)继续(2)的操作,直到概率退出或者索引层数大于最大索引层。

具体向上插入的时候,实质上还有非常重要的细节需要考虑。首先如何找到上层的待插入节点

这个各个实现方法可能不同,如果有左、上指向的指针那么可以向左向上找到上层需要插入的节点,但是如果只有右指向和下指向的我们也可以巧妙的借助查询过程中记录下降的节点。因为曾经下降的节点倒序就是需要插入的节点,最底层也不例外(因为没有匹配值会下降为null结束循环)。在这里我使用这个数据结构进行存储,当然使用List也可以。下图就是给了一个插入示意图。

image-20201225100031207

其次如果该层是目前的最高层索引,需要继续向上建立索引应该怎么办?

首先跳表最初肯定是没索引的,然后慢慢添加节点才有一层、二层索引,但是如果这个节点添加的索引突破当前最高层,该怎么办呢?

这时候需要注意了,跳表的head需要改变了,新建一个ListNode节点作为新的head,将它的down指向老head,将这个head节点加入栈中(也就是这个节点作为下次后面要插入的节点),就比如上面的9节点如果运气够好在往上建立一层节点,会是这样的。

image-20201225100432978

插入上层的时候注意所有节点要新建(拷贝),除了right的指向down的指向也不能忘记,down指向上一个节点可以用一个临时节点作为前驱节点。如果层数突破当前最高层,头head节点(入口)需要改变。

这部分更多的细节在代码中注释解释了,详细代码为:

public void add(SkipNode node)
{

    int key=node.key;
    SkipNode findNode=search(key);
    if(findNode!=null)//如果存在这个key的节点
    {
        findNode.value=node.value;
        return;
    }
    Stack<SkipNode>stack=new Stack<SkipNode>();//存储向下的节点,这些节点可能在右侧插入节点
    SkipNode team=headNode;//查找待插入的节点   找到最底层的哪个节点。
    while (team!=null) {//进行查找操作 
        if(team.right==null)//右侧没有了,只能下降
        {
            stack.add(team);//将曾经向下的节点记录一下
            team=team.down;
        }
        else if(team.right.key>key)//需要下降去寻找
        {
            stack.add(team);//将曾经向下的节点记录一下
            team=team.down;
        }
        else //向右
        {
            team=team.right;
        }
    }
    int level=1;//当前层数,从第一层添加(第一层必须添加,先添加再判断)
    SkipNode downNode=null;//保持前驱节点(即down的指向,初始为null)
    while (!stack.isEmpty()) {
        //在该层插入node
        team=stack.pop();//抛出待插入的左侧节点
        SkipNode nodeTeam=new SkipNode(node.key, node.value);//节点需要重新创建
        nodeTeam.down=downNode;//处理竖方向
        downNode=nodeTeam;//标记新的节点下次使用
        if(team.right==null) {//右侧为null 说明插入在末尾
            team.right=nodeTeam;
        }
        //水平方向处理
        else {//右侧还有节点,插入在两者之间
            nodeTeam.right=team.right;
            team.right=nodeTeam;
        }
        //考虑是否需要向上
        if(level>MAX_LEVEL)//已经到达最高级的节点啦
            break;
        double num=random.nextDouble();//[0-1]随机数
        if(num>0.5)//运气不好结束
            break;
        level++;
        if(level>highLevel)//比当前最大高度要高但是依然在允许范围内 需要改变head节点
        {
            highLevel=level;
            //需要创建一个新的节点
            SkipNode highHeadNode=new SkipNode(Integer.MIN_VALUE, null);
            highHeadNode.down=headNode;
            headNode=highHeadNode;//改变head
            stack.add(headNode);//下次抛出head
        }
    }
}

总结

对于上面,跳表完整分析就结束啦,当然,你可能看到不同品种跳表的实现,还有的用数组方式表示上下层的关系这样也可以,但本文只定义right和down两个方向的链表更纯正化的讲解跳表。

对于跳表以及跳表的同类竞争产品:红黑树,为啥Redis的有序集合(zset) 使用跳表呢?因为跳表除了查找插入维护和红黑树有着差不多的效率,它是个链表,能确定范围区间,而区间问题在树上可能就没那么方便查询啦。而JDK中跳跃表ConcurrentSkipListSet和ConcurrentSkipListMap。 有兴趣的也可以查阅一下源码。

对于学习,完整的代码是非常重要的,这里我把完整代码贴出来,需要的自取。

import java.util.Random;
import java.util.Stack;
class SkipNode<T>
{
    int key;
    T value;
    SkipNode right,down;//左右上下四个方向的指针
    public SkipNode (int key,T value) {
        this.key=key;
        this.value=value;
    }

}
public class SkipList <T> {

    SkipNode headNode;//头节点,入口
    int highLevel;//层数
    Random random;// 用于投掷硬币
    final int MAX_LEVEL = 32;//最大的层
    SkipList(){
        random=new Random();
        headNode=new SkipNode(Integer.MIN_VALUE,null);
        highLevel=0;
    }
    public SkipNode search(int key) {
        SkipNode team=headNode;
        while (team!=null) {
            if(team.key==key)
            {
                return  team;
            }
            else if(team.right==null)//右侧没有了,只能下降
            {
                team=team.down;
            }
            else if(team.right.key>key)//需要下降去寻找
            {
                team=team.down;
            }
            else //右侧比较小向右
            {
                team=team.right;
            }
        }
        return null;
    }

    public void delete(int key)//删除不需要考虑层数
    {
        SkipNode team=headNode;
        while (team!=null) {
            if (team.right == null) {//右侧没有了,说明这一层找到,没有只能下降
                team=team.down;
            }
            else if(team.right.key==key)//找到节点,右侧即为待删除节点
            {
                team.right=team.right.right;//删除右侧节点
                team=team.down;//向下继续查找删除
            }
            else if(team.right.key>key)//右侧已经不可能了,向下
            {
                team=team.down;
            }
            else { //节点还在右侧
                team=team.right;
            }
        }
    }
    public void add(SkipNode node)
    {
    
        int key=node.key;
        SkipNode findNode=search(key);
        if(findNode!=null)//如果存在这个key的节点
        {
            findNode.value=node.value;
            return;
        }

        Stack<SkipNode>stack=new Stack<SkipNode>();//存储向下的节点,这些节点可能在右侧插入节点
        SkipNode team=headNode;//查找待插入的节点   找到最底层的哪个节点。
        while (team!=null) {//进行查找操作
            if(team.right==null)//右侧没有了,只能下降
            {
                stack.add(team);//将曾经向下的节点记录一下
                team=team.down;
            }
            else if(team.right.key>key)//需要下降去寻找
            {
                stack.add(team);//将曾经向下的节点记录一下
                team=team.down;
            }
            else //向右
            {
                team=team.right;
            }
        }

        int level=1;//当前层数,从第一层添加(第一层必须添加,先添加再判断)
        SkipNode downNode=null;//保持前驱节点(即down的指向,初始为null)
        while (!stack.isEmpty()) {
            //在该层插入node
            team=stack.pop();//抛出待插入的左侧节点
            SkipNode nodeTeam=new SkipNode(node.key, node.value);//节点需要重新创建
            nodeTeam.down=downNode;//处理竖方向
            downNode=nodeTeam;//标记新的节点下次使用
            if(team.right==null) {//右侧为null 说明插入在末尾
                team.right=nodeTeam;
            }
            //水平方向处理
            else {//右侧还有节点,插入在两者之间
                nodeTeam.right=team.right;
                team.right=nodeTeam;
            }
            //考虑是否需要向上
            if(level>MAX_LEVEL)//已经到达最高级的节点啦
                break;
            double num=random.nextDouble();//[0-1]随机数
            if(num>0.5)//运气不好结束
                break;
            level++;
            if(level>highLevel)//比当前最大高度要高但是依然在允许范围内 需要改变head节点
            {
                highLevel=level;
                //需要创建一个新的节点
                SkipNode highHeadNode=new SkipNode(Integer.MIN_VALUE, null);
                highHeadNode.down=headNode;
                headNode=highHeadNode;//改变head
                stack.add(headNode);//下次抛出head
            }
        }

    }
    public void printList() {
        SkipNode teamNode=headNode;
        int index=1;
        SkipNode last=teamNode;
        while (last.down!=null){
            last=last.down;
        }
        while (teamNode!=null) {
            SkipNode enumNode=teamNode.right;
            SkipNode enumLast=last.right;
            System.out.printf("%-8s","head->");
            while (enumLast!=null&&enumNode!=null) {
                if(enumLast.key==enumNode.key)
                {
                    System.out.printf("%-5s",enumLast.key+"->");
                    enumLast=enumLast.right;
                    enumNode=enumNode.right;
                }
                else{
                    enumLast=enumLast.right;
                    System.out.printf("%-5s","");
                }

            }
            teamNode=teamNode.down;
            index++;
            System.out.println();
        }
    }
    public static void main(String[] args) {
        SkipList<Integer>list=new SkipList<Integer>();
        for(int i=1;i<20;i++)
        {
            list.add(new SkipNode(i,666));
        }
        list.printList();
        list.delete(4);
        list.delete(8);
        list.printList();
    }
}

进行测试一下可以发现跳表还是挺完美的(自夸一下)。
image-20201225105810595

原创不易,bigsai请思否的朋友们帮两件事帮忙一下:

  1. 点赞、收藏、关注支持一下, 您的肯定是我创作的源源动力。
  2. 微信搜索「bigsai」,关注我的原创技术公众号,前进道路上不迷路!

咱们下次再见!

查看原文

认证与成就

  • 获得 21 次点赞
  • 获得 16 枚徽章 获得 1 枚金徽章, 获得 4 枚银徽章, 获得 11 枚铜徽章

擅长技能
编辑

(゚∀゚ )
暂时没有

开源项目 & 著作
编辑

(゚∀゚ )
暂时没有

注册于 2012-06-01
个人主页被 1.1k 人浏览