BYT0723的博客

Record Programming

0%

发表于 更新于 分类于 Valine：

waiting to learn

1. 字符串匹配算法（KMP）

2. LIS（最长递增子序列）

3. LCS（最长公共子序列）

4. LCP（最长公共前缀）

5. LPS（最长回文子序列）

6. ED（最小编辑距离）

发表于 更新于 分类于 Valine：

1. 同步和异步，阻塞和非阻塞

2. 线程状态

3. 什么是上下文切换

4. 文件系统格式

  1. 类 Unix
    ext
  • ext
  • ext2
  • ext3
  • ext4
  1. DOM
  • FAT32

传统的 windows 平台文件系统格式，兼容性强。
但 FAT32 不支持 4GB 以上的文件，并且没有日志，也就是断电后容易出现文件丢失的情况

  • NTFS

发表于 更新于 分类于 Valine：

1. SQL 语句的执行流程

1.1 逻辑剖析

sql 语句 > 查询缓存 > 解释器 > 优化器 > 执行器

2. 如何在生产环境中为表格增加字段

3.事务

3.1 ACID

  • Atomicity，原子操作
  • Consistency，一致性
  • Isolation，隔离性
  • Durability，持久性

解释如下可能会用到 2~3 个事务，这里简称 ABC。

  • 脏写

    1. A 先将数据从 NULL 更新为 1
    2. 在 A 未提交时，B 将数据从 1 更新为 2
    3. A 在执行过程中发生错误并回滚，将数据回滚为 NULL
    4. B 提交后发现数据并不是 2，并且自己的事务并没有执行失败

    B 写失败了

  • 脏读

    1. A 先将数据从 NULL 更新为 1
    2. 在 A 未提交时，B 读取数据为 1
    3. A 在执行过程中发生错误并回滚，将数据回滚为 NULL
    4. B 再次读取数据发现是 NULL

    B 在 step 2 时读取了脏数据

脏写和脏读类似，都是对未提交事务修改的数据进行操作，在该事务发生错误回滚后，就会导致脏写和脏读发生

  • 不可重复读（update）
    A 在执行过程中多次读取数据，但在执行过程中，B 和 C 修改并提交了数据，导致 A 多次读取读取到了不同的值

  • 幻读（insert,delete）
    A 在执行过程中多次查询数据，但在执行过程中，B 和 C 插入并提交新的数据，导致 A 多次查询，查到了不同条数的结果

阅读全文 »

发表于 更新于 分类于 Valine：

1. 互斥锁和自旋锁

区别：

  • 互斥锁：在加锁失败后，线程会释放 CPU，给其他线程；
    互斥锁在加锁失败时，会从用户态陷入到内核态，让内核帮我们切换线程，这样就会造成一定的性能开销。
    线程在两次状态的切换中，会有两次线程上下文切换。

    线程的上下文切换的是什么？当两个线程是属于同一个进程，因为虚拟内存是共享的，所以在切换时，虚拟内存这些资源就保持不动，只需要切换线程的私有数据、寄存器等不共享的数据。

    1. 加锁失败时，将 CPU 让给其他线程
    2. 锁被释放时，线程会转换为[就绪]状态，内核会在合适时间将 CPU 切换回该线程

    有大佬统计过，大概在几十纳秒到几微秒之间。如果你能确定被锁住的代码执行时间很短，就应该选用自旋锁，否则使用互斥锁。

  • 自旋锁：在加锁失败后，线程会忙等待，直到它拿到锁；
    自旋锁是通过 CAS（Compare And Swap）函数，在用户态完成加锁和解锁，所以不会上下文切换的开销，相对于互斥锁更快，开销更小。

阅读全文 »

发表于 更新于 分类于 Valine：

1. atomic.AddInt64在 32 位操作系统上内存对齐的问题

1.1 问题

在32位机器上使用int64可能会出现panic: unaligned 64-bit atomic operation

1.2 触发代码

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

import (
	"sync/atomic"
)

type Foo struct {
	a int64
	b int32
	c int64
}

func main() {
	var f Foo
	atomic.AddInt64(&f.a, 1) // 这里不会崩溃
	atomic.AddInt64(&f.c, 1) // 这里会崩溃
}
阅读全文 »

发表于 更新于 分类于 Valine：

1. etcd 是什么

etcd 是一个分布式键值对存储，设计用来可靠而快速的保存关键数据并提供访问。
通过分布式锁，leader 选举和写屏障(write barriers)来实现可靠的分布式协作。
etcd 集群是为高可用，持久性数据存储和检索而准备。

1.1 etcd 的应用场景:

  • 服务发现
  • 消息发布和订阅
  • 负载均衡
  • 分布式锁、分布式队列
  • 集群监控和 leader 竞选

2. etcd 的基本操作

  • 通过 http 进行通信
  • 通过 etcdctl 连接进行操作
阅读全文 »

发表于 更新于 分类于 Valine：

1. redis 简介

redis 是内存型 NoSQL 数据库，因其使用内存存储，性能优越，其读写速度远超其他类型的数据库。

1.1 redis 的应用场景

  • 缓存：使用 redis 存储一些常用的主要数据可以提升响应速度（redis 和数据库的数据一致性）
  • 高速读写场合：在高频次读写操作时，数据库的响应就会显著降低。而这时，使用 redis 进行高速读写，在读写结束时，异步将数据写入数据库中

2.redis 的数据类型和基本操作

2.1 redis 的数据类型

  • String(二进制安全，可以存储任何数据，例如 jpg 或其他序列化字节，最大存储 512MB)
1
2
3
4
5
# update or (create if not exist)
set [key] [value]

# search key
get [key]
  • Hash
1
2
3
4
5
# update or (create if not exist) field
hset [key] [field1] [value1] […] […]

# search field of hset key
hget [key] [field1]
阅读全文 »

发表于 更新于 分类于 Valine：

1. Slice 扩容机制

  • 当 newLen >= 2 * cap, 则 newCap = newLen

  • 当 newLen < 2 * cap

    • 如果 cap < 256, 则 newCap = 2 * cap
    • 如果 cap >= 256, 则 newCap = cap + (cap + 3 * threshold) / 4, 即 1.25 倍容量+ 0.75 倍阈值的平滑因子, 平滑因子在各个阈值阶段也会不同
      starting cap growth factor
      256 2.0
      512 1.63
      1024 1.44
      2048 1.35
      4096 1.30
阅读全文 »

发表于 更新于 分类于 Valine：

1. MYSQL 优化的几个原则

  • 减少数据访问：设置合理的字段类型，启用压缩，通过索引访问等减少磁盘 IO
  • 返回更少的数据：只返回需要的字段和数据分页处理，减少磁盘和网络 IO
  • 减少交互次数：批量 DML 操作，函数存储等减少数据连接次数
  • 利用更多资源：使用表分区，并增加并行操作，更大限度利用 CPU 资源

总结一下

  • 最大化利用索引
  • 尽可能避免全表扫描
  • 减少无效数据的查询

2. 优化策略

声明：以下 SQL 优化策略适用于数据量较大的场景下，如果数据量较小，没必要以此为准，以免画蛇添足。

2.1 避免不走索引的场景

  1. 尽量避免在字段开头模糊查询，会导致数据库引擎放弃索引，进行全表扫描
1
2
3
4
# bad
SELECT * FROM t WHERE username LIKE '%王%'
# good
SELECT * FROM t WHERE username LIKE '王%'

如果需要在前面使用模糊查询，提供几个解决思路：

  • 使用 MySQL 内置函数INSTR(str, substr)来匹配
  • 使用 FullText 全文索引，用 match against 检索
  • 数据量较大的情况，建议引入 ElasticSearch、solr，亿级数据量检索速度秒级
  • 当表数据量较少（几千条左右），直接like '%xx%'
阅读全文 »