本篇是论文 Spanner: Google’s Globally-Distributed Database 的中文翻译，尽量保持原文的章节顺序与表述。

拓扑排序（Topological Sorting）是一个有向无环图（DAG, Directed Acyclic Graph）的所有顶点的线性序列。且该序列必须满足下面两个条件：

1. 每个顶点出现且只出现一次。
2. 若存在一条从顶点 A 到顶点 B 的路径，那么在序列中顶点 A 出现在顶点 B 的前面。

graph TD
id1((1)) --> id2((2))
id1((1)) --> id4((4))
id2((2)) --> id4((4))
id4((4)) --> id3((3))
id2((2)) --> id3((3))
id4((4)) --> id5((5))
id3((3)) --> id5((5))

有向无环图（DAG）才有拓扑排序，非DAG图没有拓扑排序一说。

shell 脚本选项参数解析通常有 3 种方法。

• 解析参数数组
• 基于getopts
• 基于getopt

概念介绍

布尔基础:

• 逻辑表达式: 由逻辑变量和与 $\land$ ,或 $\lor$ ,非 $\neg$ 3种运算符连接所构成的表达式。

• 析取式: 表达式之间都通过逻辑或连接的复合表达式。

• 合取式: 表达式之间都通过逻辑与连接的复合表达式。

• 合取范式 (Conjunctive Normal Form)2 是命题公式的一个标准型，它由一系列析取子句 用合取操作连接而来。如 $(a) \land (a \lor \neg c) \land (b \lor c)$

• 与之相反，析取范式 (Disjunctive Normal Form) 是命题公式的另一个标准型，它由一系列 合取子句 用 析取操作 连接而来。如 $(a) \lor (a \land \neg c) \lor (b \land c)$

表达式化简:

• 表达式相等: 两个表达式具有同样的变量，且对于变量的任意一组取值，表达式的值均相等，这两个表达式是相等的
• 最小项: 如果某个表达式的某个乘积(与)项包含了表达式的全部变量，其中每个表达式都以原变量或是反变量的形式出现。n个变量可以有2^n个最小项。
• 主析取式: 可以将表达式化简为全部由最小项组成的唯一表达式，也被称为主析取式(符合析取范式).

JMH 是openJDK项目下的JVM工具，用于构建，运行和分析用Java和其他语言编写的针对JVM的nano/micro/milli/macro微基准测试。

随着多核芯片的广泛使用，线程是提升性能的首选方案。适当提升一点线程数会很好;事实上，拥有太多线程可能会使程序陷入困境。过多的线程主要对两个方面有影响:

• 首先，在太多线程之间划分固定数量的工作会使每个线程分到的工作太少，以至于启动和终止线程的开销会影响有用的工作。
• 其次，运行太多线程会因为共享有限硬件资源，从而导致产生过多的开销。

split命令可以将一个大文件分割成很多个小文件，有时需要将文件分割成更小的片段，比如为提高可读性，生成日志等。

本文是学习flink源码前的准备工作。在开始之前，先做好准备工作：

• 安装JDK8+，Flink 依赖 Java 8 或更新的版本来进行构建。
  • 自flink1.15 开始需要Java 11(如无必要不使用更高版本的JDk去build)
• 安装Maven 3 ( Maven 3.3.x 可以构建 Flink，但是不能正确地屏蔽掉指定的依赖。Maven 3.2.5 可以正确地构建库文件)
• 安装Scala 2.11或2.12
  • 自flink1.15 开始需要Scala 2.12

版本格式：主版本号.次版本号.修订号，版本号递增规则如下：

• 主版本号：当你做了不兼容的 API 修改，
• 次版本号：当你做了向下兼容的功能性新增，
• 修订号：当你做了向下兼容的问题修正。

先行版本号及版本编译元数据可以加到主版本号.次版本号.修订号 的后面，作为延伸。

生命游戏是英国数学家约翰·何顿·康威在1970年发明的细胞自动机。

java 的 nio包提供了对文件系统的监控服务，主要使用系统原生文件服务，同时在没有原生服务的时候，使用轮询来监控。下面是一个代码示例:

    String path = "/tmp";
    // 获取当前OS平台下的文件系统监控器
    WatchService watcher = FileSystems.getDefault().newWatchService();
    //将监控器注册给指定的文件节点,该方法会让监控器线程就绪并运行，调用完后监控器就开始监控

    /* 文件变化枚举类型
     * ENTRY_CREATE：创建
     * ENTRY_DELETE：删除
     * ENTRY_MODIFY：修改
     */
    Paths.get(path).register(watcher,
        StandardWatchEventKinds.ENTRY_CREATE,
        StandardWatchEventKinds.ENTRY_DELETE,
        StandardWatchEventKinds.ENTRY_MODIFY);

    while (true) {
        WatchKey key = watcher.take();
        // 获得WatchKey（监控池）中的具体监控信息,
        // !!! 一个文件变化动作可能会引发一系列的事件，因此WatchKey中保存着一个事件列表List<WatchEvent<?>> list
        for (WatchEvent<?> event: key.pollEvents()) {

            System.out.println(event.context() + " comes to " + event.kind());
        }
        // 完成一次监控就需要重置监控器一次.
        boolean valid = key.reset(); 
        if (!valid) {
            break;
        }
    }
// ---------- output --------------
// tmp.log comes to ENTRY_DELETE

AOP Alliance 项目是许多对Aop和java有浓厚兴趣的软件开发人员联合成立的开源项目，旨在确定Aop的标准。面向切面编程是设计和开发应用程序的一个好方案，AOP 提供了一种通用方法来构建关注点(横切关注点)，并将它们灵活地作为模块插入应用。但是，也带来了问题： 不同的AOP实现并不能适配所有环境。

大多数人不相信完美系统，我们认为一个系统总是能处理给定的一个问题和环境(不需要适配其他)。现在已经有了很多的AOP实现或AOP相关的技术，例如，通用代理，拦截器或字节码翻译工具。具体如下:

• AspectJ: 面向切面的源码级和字节码级别的织入器。
• AspectWerkz: 一个面向切面框架(字节码动态织入,支持XML配置)。
• BCEL: 一个字节码翻译器
• JAC: 一个面向切面框架(字节码动态织入，可配置切面)
• Javassist: 字节码翻译器，有高级API。
• JBoss-AOP: 拦截和基于元数据的AOP框架(支持独立运行和在JBoss应用服务器种运行)
• JMangler: 一个字节码翻译器，支持兼容翻译
• Nanning: 一个面向切面织入器框架
• Prose: 一个面向切面动态字节码织入框架

对我们而言，这些实现没有好与坏的区别，都适合于某些问题或环境。AOP Alliance的目的不是提出新的AOP模型，也不是提供一个更好的AOP实现来解决所有场景的问题。其目的在于提炼所有AOP实现的共同核心能力:

• 避免重复造轮子，尽量重用
• 简化某个环境下现有AOP组件的适配
• 简化开发工具集成AOP能力的工作

一些常用的shell 脚本和snippets。

Shell 脚本（shell script），是一种为 shell 编写的脚本程序。Linux 的 Shell 种类众多，常见的有：

1. Bourne Shell（/usr/bin/sh或/bin/sh）
2. Bourne Again Shell（/bin/bash）
3. C Shell（/usr/bin/csh）
4. K Shell（/usr/bin/ksh）
5. Shell for Root（/sbin/sh）
6. Z Shell /usr/bin/zsh)

由于易用和免费，Bash 在日常工作中被广泛使用。同时，Bash 也是大多数Linux 系统默认的 Shell。

之前有听说过 java 8 的 lambda 实现不再是java 1.5的匿名内部类语法糖。今天刚好有时间看看:

public class App {

    @FunctionalInterface
    public interface LambdaDemo{
        public void runLambda();
    }
    public static void doSomething(LambdaDemo demo){
        demo.runLambda();
    }

    public static void main(String[] args) {
        doSomething(()->System.out.println("hello world!"));
    }
}

在 Java 编程中，我们偶尔能看到“时钟回拨”的现象:

//now() returns 2019-01-13T22:34:05.681Z
order.setCreationTime(Instant.now());

//... 执行一些其他工作

//now() returns 2019-01-13T22:34:03.123Z
//发现时间比创建时间提前了，仿佛时间被回拨
order.setCancelationTime(Instant.now());

为什么需要 Cuckoo Hash

哈希表最理想的状态是：一个 key 经过哈希函数计算后，直接落到一个确定的槽位。但不同 key 可能算出同一个位置，线性探测、链地址法等方法会引入探测链或桶内扫描，查询时间也就不再稳定。

Cuckoo Hash（布谷鸟哈希）最早由 Rasmus Pagh 和 Flemming Friche Rodler 提出。它给每个 key 安排两个候选位置：只要其中一个为空，就能直接放入；如果两个都被占用，就把已经占据位置的旧 key 踢到它的另一个候选位置。这个过程像布谷鸟把别的鸟蛋挤出鸟巢，因此得名。

它的最大特点是查询路径非常确定：计算两个哈希值，检查两个固定位置即可。不需要在冲突链上逐个比较，也不需要探测一段连续区间，因此删除也可以用同样简单的方式完成。

先来看个最简 DEMO(双向通信):

// server端
public class SocketServer {
  public static void main(String[] args) throws Exception {
    ServerSocket server = new ServerSocket(8080);
    
    // 阻塞等待连接
    Socket socket = server.accept();

    // 从socket中获取输入流，并建立缓冲区进行读取
    InputStream inputStream = socket.getInputStream();
    byte[] bytes = new byte[1024];
    int len;
    StringBuilder sb = new StringBuilder();
    while ((len = inputStream.read(bytes)) != -1) {
      sb.append(new String(bytes, 0, len,"UTF-8"));
    }
    System.out.println("Received: " + sb);
    OutputStream outputStream = socket.getOutputStream();
    outputStream.write("hello client".getBytes("UTF-8"));
    outputStream.flush();

    // 关闭流&连接
    inputStream.close();
    outputStream.close();
    socket.close();
    server.close();
  }
}
// client 端
public class SocketClient {
  public static void main(String args[]) throws Exception {
    Socket socket = new Socket("127.0.0.1", 8080);
    // 建立连接后获得输出流
    OutputStream outputStream = socket.getOutputStream();
    String message="hello server";
    outputStream.write(message.getBytes("UTF-8"));
    //通知server消息发送完成
    socket.shutdownOutput();
    
    // 读取消息
    InputStream inputStream = socket.getInputStream();
    byte[] bytes = new byte[1024];
    int len;
    StringBuilder sb = new StringBuilder();
    while ((len = inputStream.read(bytes)) != -1) {
      sb.append(new String(bytes, 0, len,"UTF-8"));
    }
    System.out.println("Received: " + sb);

    // 关闭流&连接
    inputStream.close();
    outputStream.close();
    socket.close();
  }
}

每个服务器资源都有一个自己的名字，服务器资源名被称为统一资源标识符(URI)，用于唯一标识标识并定位资源。URI 是一个通用的概念，由两个主要的子集 URL 和 URN 组成。 URL是通过描述资源的位置来标识资源的，而 URN 是通过名字来标识资源。

http规范将更通用的 URI 作为资源标识符，但在http应用程序实际使用中，更常见的是处理URL。

对象的创建和销毁在一定程度上会消耗系统的资源，虽然jvm的性能在近几年已经得到了很大的提高，对于多数对象来说，没有必要利用对象池技术来进行对象的创建和管理。但是对于有些对象来说，其创建的代价还是比较昂贵的，比如线程、tcp连接、数据库连接等对象。对于那些创建耗时较长，或者资源占用较多的对象，比如网络连接，线程之类的资源，通常使用池化来管理这些对象，从而达到提高性能的目的。

apache-common-pool提供了一个通用的对象池技术的实现。可以很方便的基于它来实现自己的对象池。比如DBCP和Jedis他们的内部对象池的实现就是依赖于apache-common-pool(本文分析的是apache common pool2)。