字节面试总结

# 使用 Redis 快速实现分布式锁

Tags: Redis, 分布式

Published: 2024年6月23日

# 分布式锁的需求


![Untitled.png](https://cdn.jsdelivr.net/gh/Gypsophila1006/img/img/082816759ad050cd9afc3d4aec3d7796.Untitled.webp)

一般来说，生产环境可用的分布式锁需要满足以下几点：

- **互斥性**，互斥是锁的基本特征，同一时刻只能有一个线程持有锁，执行临界操作；
- **超时释放**，超时释放是锁的另一个必备特性，可以对比 MySQL InnoDB 引擎中的 innodb_lock_wait_timeout 配置，通过超时释放，防止不必要的线程等待和资源浪费；
- **可重入性**，在分布式环境下，同一个节点上的同一个线程如果获取了锁之后，再次请求还是可以成功；
- **高性能和高可用**，加锁和解锁的开销要尽可能的小，同时也需要保证高可用，防止分布式锁失效；
- **支持阻塞和非阻塞性**，这个一般是在业务代码中实现，比如在获取锁时通过 while(true) 或者轮询来实现阻塞操作。

# Redis实现分布式锁的方法

## **使用 setnx 实现分布式锁**

Redis 支持 setnx 指令，只在 key 不存在的情况下，将 key 的值设置为 value，若 key 已经存在，则 setnx 命令不做任何动作。如果 setnx 返回 1，则说明该进程获得锁；如果 setnx 返回 0，则说明其他进程已经获得了锁，进程不能进入临界区；如果需要阻塞当前进程，可以在一个循环中不断尝试 setnx 操作。

对比一下上面说的分布式锁特性，使用这种方式实现分布式锁的问题很明显：不支持超时释放锁，如果进程在加锁后宕机，则会导致锁无法删除，其他进程无法获得锁。

## **使用 setnx 和 expire 实现**

在分布式锁的实现中，依赖业务线程进行锁的释放，如果进程宕机，那么就会出现死锁。Redis 在设置一个 key 时，支持设置过期时间，利用这一点，可以在缓存中实现锁的超时释放，解决死锁问题。

在使用 setnx 获取锁之后，通过 expire 给锁加一个过期时间，利用 Redis 的缓存失效策略，进行锁的超时清除。

通过设置过期时间，避免了占锁到释放锁的过程发生异常而导致锁无法释放的问题，但是在 Redis 中，**setnx 和 expire 这两条命令不具备原子性**。如果一个线程在执行完 setnx 之后突然崩溃，导致锁没有设置过期时间，那么这个锁就会一直存在，无法被其他线程获取。

## **使用 set 扩展命令实现**

为了解决这个问题，在 Redis 2.8 版本中，扩展了 set 命令，支持 set 和 expire 指令组合的原子操作，解决了加锁过程中失败的问题。

```abap
redis> SET key value expireTime nx
```

nx 表示仅在键不存在时设置，这样可以在同一时间内完成设置值和设置过期时间这两个操作，防止设置过期时间异常导致的死锁。那么这种方式还存在问题吗？

使用 setex 方式看起来解决了锁超时的问题，但在实际业务中，如果对超时时间设置不合理，存在这样一种可能：在加锁和释放锁之间的业务逻辑执行的太长，以至于超出了锁的超时限制，缓存将对应 key 删除，其他线程可以获取锁，出现对加锁资源的并发操作。

**如何避免这个问题呢？**

- 首先，基于 Redis 的分布式锁一般是用于耗时比较短的瞬时性任务，业务上超时的可能性较小
- 其次，在获取锁时，可以设置 value 为一个随机数，在释放锁时进行读取和对比，确保释放的是当前线程持有的锁，一般是通过 Redis 结合 Lua 脚本的方案实现；
- 最后，需要添加完备的日志，记录上下游数据链路，当出现超时，则需要检查对应的问题数据，并且进行人工修复。

# **分布式锁的高可用**

上面分布式锁的实现方案中，都是针对单节点 Redis 而言的，在生产环境中，为了保证高可用，避免单点故障，通常会使用 Redis 集群。

## **集群下分布式锁存在哪些问题**

集群环境下，Redis 通过主从复制来实现数据同步，Redis 的主从复制（Replication）是异步的，所以单节点下可用的方案在集群的环境中可能会出现问题，在故障转移（Failover） 过程中丧失锁的安全性。

由于 Redis 集群数据同步是异步的，假设 Master 节点获取到锁后在未完成数据同步的情况下，发生节点崩溃，此时在其他节点依然可以获取到锁，出现多个客户端同时获取到锁的情况。

我们模拟下这个场景，按照下面的顺序执行：

- 客户端 A 从 Master 节点获取锁；
- Master 节点宕机，主从复制过程中，对应锁的 key 还没有同步到 Slave 节点上；
- Slave 升级为 Master 节点，于是集群丢失了锁数据；
- 其他客户端请求新的 Master 节点，获取到了对应同一个资源的锁；
- 出现多个客户端同时持有同一个资源的锁，不满足锁的互斥性。

关于在集群中如何实现分布式锁，可以使用Redlock算法

## **Redlock 算法**

**Redlock 算法**是在单 Redis 节点基础上引入的**高可用模式**，Redlock 基于 N 个完全独立的 Redis 节点，一般是**大于 3 的奇数个**（通常情况下 N 可以设置为 5），可以基本保证集群内各个节点不会同时宕机。

假设当前集群有 5 个节点，运行 Redlock 算法的客户端依次执行下面各个步骤，来完成获取锁的操作：

- 客户端记录当前系统时间，以毫秒为单位；
- 依次尝试从 5 个 Redis 实例中，使用相同的 key 获取锁，当向 Redis 请求获取锁时，客户端应该设置一个网络连接和响应超时时间，超时时间应该小于锁的失效时间，避免因为网络故障出现的问题；
- 客户端使用当前时间减去开始获取锁时间就得到了获取锁使用的时间，当且仅当从半数以上的 Redis 节点获取到锁，并且当使用的时间小于锁失效时间时，锁才算获取成功；
- 如果获取到了锁，key 的真正有效时间等于有效时间减去获取锁所使用的时间，减少超时的几率；
- 如果获取锁失败，客户端应该在所有的 Redis 实例上进行解锁，即使是上一步操作请求失败的节点，防止因为服务端响应消息丢失，但是实际数据添加成功导致的不一致。

> 分布式系统设计是实现复杂性和收益的平衡，考虑到集群环境下的一致性问题，也要避免过度设计。在实际业务中，一般使用基于单点的 Redis 实现分布式锁就可以，出现数据不一致，通过人工手段去回补。
>

使用 Redis 快速实现分布式锁

# Go排序

Tags: Golang


![Untitled.png](https://cdn.jsdelivr.net/gh/Gypsophila1006/img/img/84469885cb1c2f6ac4a42fbc608877d9.Untitled.webp)

# 选择排序

每次找未排序部分最小的，放到前面

```go
func selectSort(arr []int) []int {
	for i := 0; i < len(arr); i++ {
		min := i
		for j := i + 1; j < len(arr); j++ {
			if arr[j] < arr[min] {
				min = j
			}
		}
		arr[i], arr[min] = arr[min], arr[i]
	}
	return arr
}
```

# 冒泡排序

比较相邻元素，如果逆序则交换

```go
func bubbleSort(arr []int) []int {
	swapped := true
	for swapped {
		swapped = false
		for i := 0; i < len(arr)-1; i++ {
			if arr[i] > arr[i+1] {
				arr[i], arr[i+1] = arr[i+1], arr[i]
				swapped = true
			}
		}
	}
	return arr
}
```

# 插入排序

将未排序的部分，逐个插入到已排序部分

```go
func insertSort(arr []int) []int {
	for i := 1; i < len(arr); i++ {
		tmp := arr[i]
		j := i - 1
		for ; j >= 0 && arr[j] > tmp; j-- {
			arr[j+1] = arr[j]
		}
		arr[j+1] = tmp
	}
	return arr
}
```

# 希尔排序

把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至 1 时，整个文件恰被分成一组，算法便终止。

```go
func shellSort(arr []int) []int {
	for d := len(arr) / 2; d > 0; d /= 2 {
		for i := d; i < len(arr); i++ {
			for j := i; j >= d && arr[j] < arr[j-d]; j -= d {
				arr[j], arr[j-d] = arr[j-d], arr[j]
			}
		}
	}
	return arr
}
```

# 归并排序

分治思想，不断将已排序的数组合并

```go
func merge(left, right []int) []int {
	res := make([]int, 0, len(left)+len(right))
	i, j := 0, 0
	for i < len(left) && j < len(right) {
		if left[i] <= right[j] {
			res = append(res, left[i])
			i++
		} else {
			res = append(res, right[j])
			j++
		}
	}
	for i < len(left) {
		res = append(res, left[i])
		i++
	}
	for j < len(right) {
		res = append(res, right[j])
		j++
	}
	return res
}

func mergesort(arr []int) []int {
	if len(arr) < 2 {
		return arr
	}
	mid := len(arr) / 2
	left := mergesort(arr[:mid])
	right := mergesort(arr[mid:])
	return merge(left, right)
}
```

# 快速排序

选出一个基准（pivot），将比它小的放在前面，大的放在后面。再递归的处理前后的数组

```go
func partition(list []int, low, high int) int {
	pivot := list[low]
	for low < high {
		for low < high && list[high] >= pivot {
			high--
		}
		list[low] = list[high]
		for low < high && list[low] <= pivot {
			low++
		}
		list[high] = list[low]
	}
	list[low] = pivot
	return low
}

func quickSort(list []int, low, high int) {
	if high > low {
		pivot := partition(list, low, high)
		quickSort(list, low, pivot-1)
		quickSort(list, pivot+1, high)
	}
}
```

Go排序

# 读写分离

Tags: Mysql, 分布式

Published: 2024年6月23日

# 什么时候需要读写分离

互联网大部分业务场景都是读多写少的，对于电商等典型业务，读和写的请求对比可能差了不止一个数量级。为了不让数据库的读成为业务瓶颈，同时也为了保证写库的成功率，一般会采用读写分离的技术来保证。

读写分离顾名思义，就是分离读库和写库操作，从 CRUD 的角度，主数据库处理新增、修改、删除等事务性操作，而从数据库处理 SELECT 查询操作。具体的实现上，可以有一主一从，一个主库配置一个从库；也可以一主多从，也就是一个主库，但是配置多个从库，读操作通过多个从库进行，支撑更高的读并发压力。

读写分离的实现是把访问的压力从主库转移到从库，特别在单机数据库无法支撑并发读写，并且业务请求大部分为读操作的情况下。如果业务特点是写多读少，比如一些需要动态更新的业务场景，应用读写分离就不合适了，由于 MySQL InnoDB 等关系型数据库对事务的支持，使得写性能不会太高，一般会选择更高性能的 NoSQL 等存储来实现。

# Mysql主从复制

读写分离是基于主从复制架构实现的，下面介绍一下 MySQL 中的主从复制技术。

## **binlog 日志**

MySQL InnoDB 引擎的主从复制，是通过二进制日志 binlog 来实现。除了数据查询语句 select 以外，binlog 日志记录了其他各类数据写入操作，包括 DDL 和 DML 语句。

binlog 有三种格式：Statement、Row 及 Mixed。

- Statement 格式，基于 SQL 语句的复制

在 Statement 格式中，binlog 会记录每一条修改数据的 SQL 操作，从库拿到后在本地进行回放就可以了。

- Row 格式，基于行信息复制

Row 格式以行为维度，记录每一行数据修改的细节，不记录执行 SQL 语句的上下文相关的信息，仅记录行数据的修改。假设有一个批量更新操作，会以行记录的形式来保存二进制文件，这样可能会产生大量的日志内容。

- Mixed 格式，混合模式复制

Mixed 格式，就是 Statement 与 Row 的结合，在这种方式下，不同的 SQL 操作会区别对待。比如一般的数据操作使用 row 格式保存，有些表结构的变更语句，使用 statement 来记录。

## **主从复制过程**

MySQL 主从复制过程如下图所示：

![](https://learn.lianglianglee.com/%e4%b8%93%e6%a0%8f/%e5%88%86%e5%b8%83%e5%bc%8f%e6%8a%80%e6%9c%af%e5%8e%9f%e7%90%86%e4%b8%8e%e5%ae%9e%e6%88%9845%e8%ae%b2-%e5%ae%8c/assets/CgqCHl7h4UKAHeKQAAGxgG2nPaQ910.png)

- 主库将变更写入 binlog 日志，从库连接到主库之后，主库会创建一个log dump 线程，用于发送 bin log 的内容。
- 从库开启同步以后，会创建一个 IO 线程用来连接主库，请求主库中更新的 bin log，I/O 线程接收到主库 binlog dump 进程发来的更新之后，保存在本地 relay 日志中。
- 接着从库中有一个 SQL 线程负责读取 relay log 中的内容，同步到数据库存储中，也就是在自己本地进行回放，最终保证主从数据的一致性。

## **读写分离要注意的问题**

分布式系统通过主从复制实现读写分离，解决了读和写操作的性能瓶颈问题，但同时也增加了整体的复杂性。我们看一下引入主从复制后，额外需要注意哪些问题。

### **主从复制下的延时问题**

由于主库和从库是两个不同的数据源，主从复制过程会存在一个延时，当主库有数据写入之后，同时写入 binlog 日志文件中，然后从库通过 binlog 文件同步数据，由于需要额外执行日志同步和写入操作，这期间会有一定时间的延迟。特别是在高并发场景下，刚写入主库的数据是不能马上在从库读取的，要等待几十毫秒或者上百毫秒以后才可以。

在某些对一致性要求较高的业务场景中，这种主从导致的延迟会引起一些业务问题，比如订单支付，付款已经完成，主库数据更新了，从库还没有，这时候去从库读数据，会出现订单未支付的情况，在业务中是不能接受的。

为了解决主从同步延迟的问题，通常有以下几个方法。

- 敏感业务强制读主库

在开发中有部分业务需要写库后实时读数据，这一类操作通常可以通过强制读主库来解决。

- 关键业务不进行读写分离

对一致性不敏感的业务，比如电商中的订单评论、个人信息等可以进行读写分离，对一致性要求比较高的业务，比如金融支付，不进行读写分离，避免延迟导致的问题。

### **主从复制如何避免丢数据**

假设在数据库主从同步时，主库宕机，并且数据还没有同步到从库，就会出现数据丢失和不一致的情况，虽然这是一个极端场景，一般不会发生，但是 MySQL 在设计时还是考虑到了。

MySQL 数据库主从复制有异步复制、半同步复制和全同步复制的方式。

- 异步复制

异步复制模式下，主库在接受并处理客户端的写入请求时，直接返回执行结果，不关心从库同步是否成功，这样就会存在上面说的问题，主库崩溃以后，可能有部分操作没有同步到从库，出现数据丢失问题。

- 半同步复制

在半同步复制模式下，主库需要等待至少一个从库完成同步之后，才完成写操作。主库在执行完客户端提交的事务后，从库将日志写入自己本地的 relay log 之后，会返回一个响应结果给主库，主库确认从库已经同步完成，才会结束本次写操作。相对于异步复制，半同步复制提高了数据的安全性，避免了主库崩溃出现的数据丢失，但是同时也增加了主库写操作的耗时。

- 全同步复制

全同步复制指的是在多从库的情况下，当主库执行完一个事务，需要等待所有的从库都同步完成以后，才完成本次写操作。全同步复制需要等待所有从库执行完对应的事务，所以整体性能是最差的。

读写分离

# 关于golang中不同方式遍历字符串的反思

Tags: Golang

Published: 2024年6月19日

概要: This blog reflects on the different ways of iterating over strings in Golang, highlighting common mistakes and explaining the differences between Unicode and UTF-8 encoding.




起初学习时，并没有关注string的存储方式以及unicode和utf-8编码的区别，故出现了很滑稽的问题，在处理字符串时，使用错误的方法，导致得到的类型不正确，在继续追究错误原因时，发现一些帖子写的并不是很清晰。

## **最最低级的错误**

首先介绍一个最低级的错误：

```go
s := "abc你好"
for v := range s{
    fmt.Println(v)
}
```

起初我以为这样遍历得到的v会是每个字符（新手狠狠拍脑子！），然而这样得到的v是每个字符位置的下标：0、1、2、3、6。

## **Unicode和UTF-8**

接下来应该主要讨论另外两种方式，但是在此之前先介绍一下`unicode`和`utf-8`的区别。此处引用([Unicode和UTF-8有什么区别 • Worktile社区](https://worktile.com/kb/ask/45850.html))的内容。

- 基本概念不同。Unicode是一种字符集，而UTF-8是Unicode的一种实现方式。此外，Unicode定义了每个字符的编号和名称，而UTF-8则是一种用于在计算机上存储和传输Unicode字符的编码方式。
- 编码方式不同。Unicode使用的是固定长度的编码方式，即每个字符占用相同的字节数；而UTF-8则采用可变长度的编码方式，不同字符所占用的字节数不同，根据字符的Unicode编号来确定字节数。
- 字符范围不同。Unicode能够表示的字符范围比UTF-8更广泛，包括世界上所有语言中的字符以及许多特殊字符和符号。而UTF-8只是Unicode的一种编码方式，它只能够表示Unicode字符集中的一部分。
- 存储空间不同。在存储和传输数据时，UTF-8通常比Unicode更节省空间。因为UTF-8采用可变长度的编码方式，对于ASCII字符，只需要一个字节即可表示，而Unicode则需要两个字节。对于非ASCII字符，UTF-8的存储空间通常也比Unicode要小。

在了解上面内容之后，还需要知道Go语言的默认编码是**UTF-8**。 在Go语言中，字符串的默认编码就是UTF-8，这也是Go语言内部使用的字符编码格式。 Go语言的源代码也默认使用UTF-8编码格式。这也是后面出现问题的原因所在。

## **言归正传**

先看for range的这个方法。`i`与`v`分别是s的每个字符的下标和他的`unicode`码点（后面解释）。

```go
s := "abc你好"
for i,v := range s{
    fmt.Printf("index:%d, value: %d\n", i, v)
}
/*
index:0, value: 97
index:1, value: 98
index:2, value: 99
index:3, value: 20320
index:6, value: 22909
*/
```

观察以上输出，我们会发现对于前三个字符，即英文字符，index分别为0、1、2，但是到了后面中文部分出现了变化，index变为了3、6。上面介绍了**UTF-8**编码是不定长的，即一个字符可能需要不同字节的空间存储。结合index的值，可以猜测，此处index的值为字符串的每个字符的第一个字节相对于字符串首地址的索引。出现上面这样的结果说明对于`abc`字符各只占用一个字节，而后面的中文占用了3个字节。

换一种方式打印：

```go
s := "abc你好"
for i, v := range s {
    fmt.Printf("index:%d, value: %c\n", i, v)
}
/*
index:0, value: a
index:1, value: b
index:2, value: c
index:3, value: 你
index:6, value: 好
*/
```

使用`%c`打印的是对应的 Unicode 码点表示的字符。因此可以得到结论，上面的value值为字符所对应的unicode码点的值。

那么在讨论清楚上面的内容之后，我们再看另外一个方式。

```go
s := "abc你好"
for i := 0; i < len(s); i++ {
    fmt.Printf("index:%d, value: %d\n", i, s[i])
}
/*
index:0, value: 97
index:1, value: 98
index:2, value: 99
index:3, value: 228
index:4, value: 189
index:5, value: 160
index:6, value: 229
index:7, value: 165
index:8, value: 189
*/
```

我们发现index一直从0打印到8,很奇怪的现象，但是结合for range打印的结果分析来看，恰好字符串s的字节数为9，`abc`各占一个字节，而`你好`各占用三个字节。因此，很容易想到此处value的值为UTF-8编码中，每个字节的值。

换用`%c`打印：

```go
s := "abc你好"
for i := 0; i < len(s); i++ {
    fmt.Printf("index:%d, value: %c\n", i, s[i])
}
/*
index:0, value: a
index:1, value: b
index:2, value: c
index:3, value: ä
index:4, value: ½
index:5, value:
index:6, value: å
index:7, value: ¥
index:8, value: ½
*/
```

果然从c之后，出现了6个奇怪的结果，因为将`你好`的UTF-8编码转化为了6个编码，再分别将他们在unicode字符集中代表的字符打印出来，出现这些结果。

## **总结**

简单总结一下：

- 第一种，遍历字符串的每一个字符的起始位置相对于字符串首地址的索引。
- 第二个，index同第一种的结果相同，而v为每个字符对应的unicode码点。这种方式遍历得到的v的类型可以认为是`rune`（是可以认为，起码这样比较类型是正确的，处理中文字符串时这样使用）。
- 第三个，i会遍历字符串的每一个**字节**的下标，对，是每个字节。而s[i]表示的每个字节的值。这种方式不会以字符为单位遍历，因此对于不止需要一个字节空间表示的字符不能正确表示出来。这种方式遍历得到的s[i]的类型可以认为是`byte`。

至此，遇到的问题解释清楚。写的很啰嗦，因为自己之前基础很差，很少深究过代码出现错误的底层原因，所以借此次机会写的详细一些，希望能够对看到此文的人有所帮助。

关于golang中不同方式遍历字符串的反思

在这里，我记录学习后端技术、实习经验和个人思考，也会随性分享一些生活琐事和吐槽。如果你和我有相似的兴趣或经历，欢迎随时交流！