原论文

Dean, Jeffrey, and Sanjay Ghemawat. “MapReduce: simplified data processing on large clusters.” Communications of the ACM 51.1 (2008): 107-113.

前言

Google 三驾马车之一，MIT 6.824 first day 的 preparation task。

Abstract

MapReduce is a programming model and an associated implementation for processing and generating large data sets. Users specify a map function that processes a key/value pair to generate a set of intermediate key/value pairs, and a reduce function that merges all intermediate values associated with the same intermediate key.

MapReduce 通过 Map 函数对一个基于 k-v 对的数据集进行处理，生成对应的中间数据集，再通过 Reduce 函数对这些中间数据集中具有相同的 key 的 value 进行合并。

关注点

The run-time system takes care of the details of partitioning the input data, scheduling the program’s execution across a set of machines, handling machine failures, and managing the required inter-machine communication.

• 如何分割输入数据。
• 分布式集群的调度。
• 机器的错误处理。
• 集群机器间的通信。

解决问题

The input data is usually large and the computations have to be distributed across hundreds or thousands of machines in order to finish in a reasonable amount of time. The issues of how to parallelize the computation, distribute the data, and handlefailures conspire to obscure the original simple computation with large amounts of complex code to deal with these issues.

输入的数据量巨大，难以在单机下完成，如果想在可接受的时间内完成，需要将计算分给成百上千的机器上。

前言

Java 中的 synchronized 有偏向锁、轻量级锁、重量级锁三种形式，分别对应了锁只被一个线程持有、不同线程交替持有锁、多线程竞争锁三种情况，锁会按偏向锁 -> 轻量级锁 -> 重量级锁的顺序升级。

synchronized 代码块

对于被 synchronized 关键字修饰的代码块而言，在编译成字节码时会生成对应的 monitorenter 和 monitorexit 指令分别对应synchronized 同步块的进入和退出。

1
2
3
4
5
6
7
8
9
10
11

public void syncBlock();
    descriptor: ()V
    flags: ACC_PUBLIC
    Code:
      stack=2, locals=3, args_size=1
         1: monitorenter  //进入synchronized方法
         //...省略  
         10: monitorexit   //退出synchronized方法
         //...省略
         20: monitorexit //退出synchronized方法
         22: return

有两个 monitorexit 指令的原因是为了保证抛出异常下也能释放锁，所以 javac 为同步代码块添加了一个隐式的 try-finally，在 finally 中会调用 monitorexit 命令释放锁。

synchronized 方法

从以下字节码中可以看出，synchronized 方法并没有 monitorenter 和 monitorexit 指令，而是一个 ACC_SYNCHRONIZED 标识，该标识指明了该方法是一个同步方法，JVM通过该 ACC_SYNCHRONIZED 标识来辨别一个方法是否为同步方法，从而执行相应的获取锁操作。

1
2
3
4
5
6
7
8
9
10

public synchronized void syncMethod();
    descriptor: ()V
    // 方法标识ACC_PUBLIC代表public修饰，ACC_SYNCHRONIZED指明该方法为同步方法
    flags: ACC_PUBLIC, ACC_SYNCHRONIZED
    Code:
      stack=2, locals=1, args_size=1
         0: getstatic     #2                  // Field java/lang/System.out:Ljava/io/PrintStream;
         3: ldc           #5                  // String hello method
         5: invokevirtual #4                  // Method java/io/PrintStream.println:(Ljava/lang/String;)V
         8: return

在 Java 6 之前，monitor 的实现完全是依靠操作系统内部的互斥锁 Mutex Lock，因为需要进行用户态到内核态的切换，所以同步操作是一个无差别的重量级操作，性能也很低。但在 Java 6 开始，提供了三种不同的 monitor 实现：偏向锁、轻量级锁和重量级锁，大大改进了其性能。

1. 打包为 jar 包

1

mvn -DskipTests=true clean package

2. 编写 Dockerfile

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

FROM java:8
VOLUME /tmp
ADD airnet-api-service-0.0.1-SNAPSHOT.jar app.jar
EXPOSE 8085
ENV JAVA_OPTS="\
-server \
# 初始堆内存大小
-Xms128m \
# 堆内存最大值
-Xmx256m \
# 年轻代大小
-Xmn64m \
# 年轻的和老年代的内存比例为 1:4
-XX:NewRatio=4 \
# 新生代 Eden 和 Survivor 比例为 8:2
-XX:SurvivorRatio=8 \
# 打印GC详细信息
-XX:+PrintGCDetails"
ENTRYPOINT java ${JAVA_OPTS} -jar /app.jar

关键词

数据类型、范式与反范式、B-Tree索引、Hash索引。

Scheme 与数据类型优化

在 MySQL 中，Scheme 与 Database 是等价的，可视为表的集合。

选择优化的数据类型

选择数据类型的原则：

• 更小的通常更好：使用可以正确使用存储数据的最小数据类型。
• 简单就好：简单数据类型的操作意味着更少的 CPU 开销，例如整形和字符操作代价更低。这里的例子是一使用 MySQL 自建的类型而不是字符串来存储日期和时间，二是用整形存储 IP 地址。
• 尽量避免NULL：可为 NULL 的列使得索引、索引统计和值比较都更复杂，且会使用更多的存储空间。当可为 NULL 的列被索引时，每个索引记录需要一个额外的字节。

例如，DATETIME 和 TIMESTAMP 都可以存储日期和时间，精确到秒，然而 TIMESTAMP 只使用 DATETIME 一半的存储空间，且会根据时区自动变化。另一方面，TIMESTAMP 允许的时间范围要更小，且时区自动更新有时反而会成为障碍。

整数类型

整数类型包括：TINYINT（8位），SMALLINT（16位），MEDIUMINT（24位），INT（32位），BIGINT（64位）。它们可以存储从$-2^{N-1}$ 到 $2^{N-1}-1$ 范围的整数，其中 $N$ 为位数。

整数类型有可选的属性 UNSIGNED，表示不允许负值，可以使正数的表示范围提高一倍，例如 TINYINT.UNSIGNED 可以存储 0~255，而 TINYINT 是 -128~127。

虽然 MySQL 可以为整数类型指定宽度，但实际并不会限制值得合法范围，只是规定了一些 GUI 的显示位数。对于存储和计算来说，INT(1) 和 INT(10) 是相同的。

前言

最近把 AirNet 中的空气质量排行换成了用 Zset 实现，这篇笔记就来深入了解下 Zset 的底层实现原理。

Zset 编码的选择

在通过 ZADD 命令添加第一个元素到空 key 时， Redis 会通过检查输入的第一个元素来决定使用何种编码。

如果第一个元素符合以下条件的话， 就创建一个 REDIS_ENCODING_ZIPLIST 编码的 Zset：

• 服务器属性 server.zset_max_ziplist_entries 的值大于 0 （默认为 128 ）。
• 元素的 member 长度小于服务器属性 server.zset_max_ziplist_value 的值（默认为 64 ）。

否则，创建一个 REDIS_ENCODING_SKIPLIST 编码的 Zset。

对于一个 REDIS_ENCODING_ZIPLIST 编码的 Zset， 只要满足以下任一条件， 则会被转换为 REDIS_ENCODING_SKIPLIST 编码：

• ziplist 所保存的元素数量超过服务器属性 server.zset_max_ziplist_entries 的值（默认值为 128 ）
• 新添加元素的 member 的长度大于服务器属性 server.zset_max_ziplist_value 的值（默认值为 64 ）

前言

在毕设的 API 模块中，考虑到分布式环境下采用 UUID 直接生成 Key 可能会导致 Key 重复的问题，最终的 Key 生成策略采用 Twitter Snowflake 算法生成唯一 ID， 再使用 HmacMD5 算法对 ID 加密生成 API Key。

其他常见的分布式唯一 ID 生成策略还有：

• 数据库自增字段

• UUID

• Mongdb objectID

• Redis 原子命令 INCR

• ZooKeeper 的 ZNode 数据版本生成序列号，可以生成 32 位和 64 位的数据版本号

• 美团的 Leaf 系统 (类似 Twitter Snowflake 但通过 ZooKeeper 解决了时钟回拨问题)

Twitter Snowflake 算法

Snowflake 是 Twitter 开源的分布式 ID 生成算法，目的是在分布式系统中生成全局唯一且趋势递增的 ID，属于划分命名空间并行生成的一种算法，其生成结果为 64bit 的 long 型 ID。Snowflake 算法可以保证每秒至少生成约 409.6万个不重复的 ID，具有极高的性能。

其中：

• 符号位：占 1 位，其值始终是 0，无实际作用。
• 时间表示位：占 41 位，用来记录时间戳（毫秒），可以表示 $0$ 至 $2^{41}-1​$ 毫秒约等于 69 年的时间。
• 数据中心位：占 5 位，可表示 $0$ 至 $2^{5}-1$ 共 32 个数据中心。
• 机器编号位：占 5 位，每个数据中心内可表示 $0$ 至 $2^{5}-1$ 共 32 个机器。
• 序列编号位：占 12 位，用来记录同毫秒内产生的不同 ID，可表示 $0$ 至 $2^{12}-1$ 共 4096 个序列号。

前言

毕设的 API 模块中使用了 Guava RateLimter 进行 QPS 限流，顺便了解下常见的限流算法，主要包括令牌桶、漏桶、计数器。

漏桶算法(Leaky Bucket)

漏桶算法（Leaky Bucket）是计算机网络中流量整形（Traffic Shaping）或速率限制（Rate Limiting）时经常使用的一种算法，主要目的是控制数据注入到网络的速率，平滑网络上的突发流量。

漏桶算法描述如下：

• 一个固定容量的漏桶，按照常量固定速率流出水滴（请求）
• 如果桶是空的，则不需流出水滴
• 可以以任意速率流入水滴到
• 如果流入水滴超出了桶的容量，则流入的水滴溢出了（被丢弃），而漏桶容量是不变的。

前言

一次由于间隙锁导致的 Lock wait timeout，记录一下解决过程。

异常描述

前端反映端口返回 504 Gateway Timeout，到服务器上查看对应的服务实例日志发现了以下异常：

1
2
3
4
5
6

### Cause: com.mysql.cj.jdbc.exceptions.MySQLTransactionRollbackException: Lock wait timeout exceeded; try restarting transaction
; Lock wait timeout exceeded; try restarting transaction; nested exception is com.mysql.cj.jdbc.exceptions.MySQLTransactionRollbackException: Lock wait timeout exceeded; try restarting transaction] with root cause

com.mysql.cj.jdbc.exceptions.MySQLTransactionRollbackException: Lock wait timeout exceeded; try restarting transaction
...
...

关键词

MySQL 逻辑架构、读写锁与锁粒度、死锁、2PL两阶段锁定协议、ACID、四种隔离级别、脏读、不可重复读和幻读、MVCC、InnoDB与MyISAM。

MySQL 逻辑架构

• 第一层：不是 MySQL 独有，包括连接处理、授权认证、安全等。
• 第二层：大多数 MySQL 的核心服务功能都在该层，包括查询解析、分析、优化、缓存以及所有的内置函数，以及所有的跨存储引擎功能（存储过程、触发器、视图等）。
• 第三层：包含存储引擎，存储数据，提供读写接口。

读写锁与锁粒度

读写锁

读锁：也称共享锁，多个用户可以在同一时刻读取同个资源。

写锁：也称排他锁，写锁会阻塞其他写锁与读锁，保证只有同一时刻只有一个用户能执行写入。

锁粒度

表锁：锁定整张表。

行级锁：行级锁只在存储引擎层实现，MySQL 服务器层没有实现，InnoDB 中锁粒度默认为行锁。

事务

ACID

ACID 表示原子性（Atomicity）、一致性（Consistency）、隔离性（Isolation）、持久性（Durability），是事务必须要满足的四个特性。

• 原子性：一个事务是一个不可分割的最小工作单元，整个事务要么全部完成，要么全部失败回滚，不可能只执行其中的一部分操作。

• 一致性：开启事务前后数据的完整性必须保持一致。

• 隔离性：一个事务所做的修改在最终提交以前，对其他事务是不可见的。

• 持久性：一旦事务提交，则其所做的修改就会永久保存至数据库中，此时即使数据库崩溃，修改的数据也不会丢失。

隔离级别

• READ UNCOMMITTED 读未提交：事务的修改即使没有被提交，对其他事务也是课件的。其他事务可能会读取到未提交的数据，如果此时该事务失败回滚，其他事务读到的数据就是回滚前的脏数据，也被称为脏读。

• READ COMMITTED 读已提交：这是大多数数据库默认的隔离级别，但 MySQL 不是。一个事务从开始直到提交前，所做的任何修改对其他的事务都是不可见的，也叫不可重复读，一个事务范围内两个相同的查询，可能会得到不同的结果。

• REPEATABLE READ 可重复读：MySQL 默认的隔离级别，存在幻读问题：当某个事务在读取某个范围内的记录时，另一个事务在此范围内插入新的记录，此时之前的事务再次读取该范围内的记录时，就会产生幻影行。InnoDB 与 XtraDB 通过 MVCC 解决了该问题。

• SERIALIZABLE 可串行化：最高隔离级别，强制事务串行执行，避免了幻读问题，会在读取的每一行数据都加上锁。

MySQL 中可以通过SET TRANSACTION ISOLATION LEVEL来设置隔离级别，新的隔离级别会在下一个事务开始时生效，或者在配置文件中设置整个数据库的隔离级别。

第1章 整洁代码

What is clean code

Ron Jeffries 对 Clean Code 的排序：

1. 能通过所有测试
2. 没有重复代码
3. 体现系统中的全部设计理念
4. 包括尽量少的实体，比如类、方法、函数等

We are the author

Javadoc 中的 @author 字段告诉了我们是什么人，我们是作者，写代码时，应记得自己作为一个作者，要为评判你工作的的读者写代码。使代码易读，自然也会使之易写。

第2章 有意义的命名

• 名副其实：变量、函数和类的名称应该表达了所有的大问题，如果名称还需要注释来补充，那就不算名副其实。
• 避免误导：避免使用系统的专用名称，避免在名称中带入注入List关键字等待有特殊意义的词(即使容器是个List，最好也不要直接写出类型名)，避免使用十分类似的名称（如XYZControllerForHandingOfStrings和XYZControllerForStorageOfStrings），避免使用误导性名称（如Ol和01）。
• 做有意义的区分：像a1，a2，an的区分等同于废话，诸如getUser()、getUserInfo()、getUserData()的方法，如果没有明确的约定，也是很难一言看出区别的。要区别名称，必须要让以读者有鉴别不同之处的方式来区分。
• 使用读得出来的名称：比如生成时间戳，不要用genymdhms这样的生造词，用genTimestamp会更像人话。
• 使用可搜索的名称：单字母和数字常量是很难被一下搜出来的，单字母名称仅可用在短方法中的本地变量，名称的长短应与其作用域大小相对应。
• 避免使用编码：不必使用成员前缀，对于接口和实现，不推荐使用“I”开头修饰，不如在实现类中直接添加后缀“Imp”。
• 避免思维映射：专业的程序员和聪明的程序员之间的区别在于，专业的程序员知道，明确是王道，他们写的是其他人能理解的代码（过于”聪明“的程序员写的代码只有自己能看懂）。
• 类名：类名和对象名应该是名词或名词短语，类名不应当是动词
• 方法名：方法名应当是动词或动词短语，访问、修改和断言应该加上前缀”get”、”set”、”is”。
• 每个概念对应一个词：给每个抽象概念（fetch、retrieve、get这些相近词就很糟糕）选一个词，并一以贯之。
• 添加有意义的语境，但不要添加没用的语境，精确才是命名的要点。