Mysql存储树结构

通常在mysql中存储树形结构的方案，是通过在子节点上存储父节点编号的方案来实现的。这种方案可以很直观的体现各个节点之间的关系，通常可以满足大多数需求。

但是当数据量变大和层级关系变深后，对于部分需求(例如，判断节点是否其他节点的子节点)这样的存储方式很难满足要求。这类需求实质上需要在内存中构建一棵树，通过遍历树来给出答案。如果还是使用parent_id这种存储模型，显然需要按照树的层级关系递归向下搜索。

例如，以mysql数据库样例Employees表为例。

1
2
3
4
5
6
7
8
9
10
11
12

+----------------+
| employees      |
+----------------+
| employeeNumber |
| lastName       |
| firstName      |
| extension      |
| email          |
| officeCode     |
| reportsTo      |
| jobTitle       |
+----------------+

employees表有reportsTo字段引用employeeNumber字段。描述employee之间的层级关系。

上述的存储方式，获取树的流程为:

1
2
3
4
5
6
7
8
9
10

List<Employee> employees;
List<Employee> records;
List<String> reportsTos;
do {
    // getEmployeesByReportsTos 每次调用都要连接数据库，查询数据库
    // select * from employees where reportsTo in ${reportsTos};
    employee= getEmployeesByReportsTos(reportsTos);
    reportsTos = getReportsTos(employee);
    records.addAll(employees);
}while(employees.isNotEmpty())

上述操作是递归方式查询，查询效率仍会随着树层级深度的提高而变差。

Presto: SQL on EveryThing

本篇是论文的中文简单翻译

摘要

Presto是一个开源分布式查询引擎，支撑了Facebook内部大部分的SQL分析工作。Presto的设计目标是具有适应性、灵活性和可扩展性。它支持具有不同特征的各种各样的用例。这些用例的范围从要求亚秒级延迟的面向用户的报表应用到花费数小时的聚合或关联数TB数据的ETL任务。Presto的连接器API允许以插件的方式为数十个数据源提供高性能I/O接口，包括Hadoop数据仓库、RDBMS数据库、NoSQL系统和流处理系统。在本论文中，我们概述了Presto在Facebook内部支撑的一系列用例。然后，我们描述了它的架构和实现，并阐述了使其能够支持这些用例的功能和性能优化。最后，我们展示了性能结果，从而论证了我们主要的设计决策的影响。

关键词: SQL，查询引擎，大数据，数据仓库

Diff算法-Myers算法

diff算法用于比较文本间的差异，通常用于版本控制系统，例如 git( $git diff)。

什么是diff

diff算法的目的是计算出文本间的差异，那么首先介绍下什么是文本差异。文本差异就是目标文本和源文本之间的区别，也就是将源文本变成目标文本所需要的操作。这里的操作包括插入(insert)和 删除(delete)。

假设我们要计算下面两个字符串之间的差异：

• a: ABCABBA
• b: CBABAC

一种可能的结果是删除a中的全部字符，然后再插入b中的全部字符。

1
2
3
4
5
6
7
8
9
10
11
12
13

- A
- B
- C
- A
- B
- B
- A
+ C
+ B
+ A
+ B
+ A
+ C

上面的差异是有效的，但是并不是较好的差异。差异中的更改数量应该尽可能少。例如:

1
2
3
4
5
6
7
8
9

1.  - A       2.  - A       3.  + C
    - B           + C           - A
      C             B             B
    - A           - C           - C
      B             A             A
    + A             B             B
      B           - B           - B
      A             A             A
    + C           + C           + C

上面的3种差异都是拥有最小更改数量的方案。但是第二种和第三种没有第一种看起来“直观”。“直观”有两个特点。

1. 删除后新增，比新增后删除要好。例如上面的例子 2 比例子 3 看起来要直观
2. 当修改一块代码时，整块的删除然后新增，比删除新增交叉在一起要好，例如:

1
2
3
4
5
6

Good: - one            Bad: - one
      - two                 + four
      - three               - two
      + four                + five
      + five                + six
      + six                 - three

3. 新增或删除的内容应该和代码结构相呼应，例如下面的例子，左边我们可以很直观地看出新增了一个inspect 方法。

1
2
3
4
5
6
7
8
9

Good: class Foo                   Bad:    class Foo
        def initialize(name)                def initialize(name)
          @name = name                        @name = name
        end                             +   end
    +                                   +
    +   def inspect                     +   def inspect
    +     @name                         +     @name
    +   end                                 end
      end                                 end

DBLog:一款通用的变化数据捕获框架

本篇是论文的中文简单翻译

应⽤程序使⽤多个异构数据库是⼀种常⻅的模式，其中每个数据库都⽤于满⾜特定需求，例如存储规范形式的数据或提供⾼级搜索功能。因此，对于应⽤程序来说，需要保持多个数据库同步。我们观察到了⼀系列试图解决这个问题的不同模式，例如双写和分布式事务。然⽽，这些⽅法在可行性、稳健性和维护⽅⾯存在局限性。最近出现的另⼀种⽅法是利⽤变更数据捕获 (CDC) 从数据库的事务⽇志中捕获更改的行，并最终以低延迟将它们传递到下游。为了解决数据同步问题，还需要复制数据库的完整状态，⽽事务⽇志通常不包含完整的更改历史记录。同时，有些⽤例需要事务⽇志事件的⾼可⽤性，以便数据库尽可能保持同步。

为了应对上述挑战，我们开发了⼀种新颖的 CDC数据库框架，即 DBLog。 DBLog 利⽤基于⽔印的⽅法，允许我们将事务⽇志事件与我们直接从表中选择的行交错以捕获完整状态。我们的解决⽅案允许⽇志事件继续进行，⽽不会在处理选择时停⽌。可以随时在所有表、特定表或表的特定主键上触发选择。 DBLog 以块的形式执行选择并跟踪进度，允许它们暂停和恢复。⽔印⽅法不使⽤锁，对源的影响最⼩。 DBLog⽬前被 Netflix 的数⼗个微服务⽤于⽣产。

关键字:

• databases
• replication
• change-data-capture

Scalable IO in Java

本文是 Doug Lea 的 “Scalable IO in Java” 读书笔记

可扩展的网络服务

在一般的网络或分布式服务等应用程序中，大都具备一些相同的处理流程，例如：

1. 读取请求数据;
2. 对请求数据进行解码;
3. 对数据进行处理;
4. 对回复数据进行编码;
5. 发送回复;

当然在实际应用中每一步的运行效率都是不同的，例如其中可能涉及到xml解析、文件传输、web页面的加载、计算服务等不同功能。

算法之MD5

MD5 即Message-Digest Algorithm 5 (信息-摘要算法5)。MD5 使用little-endian(小端模式)，输入任意不定长度信息，以 512-bit 进行分组，生成四个32-bit 数据，最后联合输出固定 128-bit 的信息摘要。

MD5 不是足够安全的。Hans Dobbertin在1996年找到了两个不同的512-bit 块,它们 在MD5 计算下产生相同的hash 值。至今还没有真正找到两个不同的消息，它们的MD5 的hash 值相等。

log 性能优化

日志是服务中一个重要组成部分，当优化性能的时候，也要思考对日志的性能优化。

分布式追踪系统

随着微服务和云原生开发的兴起，越来越多应用基于分布式进行开发，大型应用拆分为微服务后，服务之间的依赖和调用变得越来越复杂。微服务提供了一个强大的体系结构，但也有面临了一些挑战，例如：

• 如何调试和观察跨复杂网络的分布式调用？
• 如何分析服务链路的瓶颈并对其进行调优？
• 如何快速进行服务链路的故障发现？
• …

为了更好地维护这些服务，软件领域出现了 Observability 思想。

Dapper,大规模分布式系统的跟踪系统

本篇是论文的中文简单翻译

概述

当代的互联网的服务，通常都是用复杂的、大规模分布式集群来实现的。互联网应用构建在不同的软件模块集上，这些软件模块，有可能是由不同的团队开发、可能使用不同的编程语言来实现、有可能布在了几千台服务器，横跨多个不同的数据中心。因此，就需要一些可以帮助理解系统行为、用于分析性能问题的工具。

Dapper–Google生产环境下的分布式跟踪系统，应运而生。那么我们就来介绍一个大规模集群的跟踪系统，它是如何满足一个低损耗、应用透明的、大范围部署这三个需求的。当然Dapper设计之初，参考了一些其他分布式系统的理念，尤其是Magpie³和X-Trace¹²，但是我们之所以能成功应用在生产环境上，还需要一些画龙点睛之笔，例如采样率的使用以及把代码植入限制在一小部分公共库的改造上。

自从Dapper发展成为一流的监控系统之后，给其他应用的开发者和运维团队帮了大忙，所以我们今天才发表这篇论文，来汇报一下这两年来，Dapper是怎么构建和部署的。Dapper最初只是作为一个自给自足的监控工具起步的，但最终进化成一个监控平台，这个监控平台促生出多种多样的监控工具，有些甚至已经不是由Dapper团队开发的了。下面我们会介绍一些使用Dapper搭建的分析工具，分享一下这些工具在google内部使用的统计数据，展现一些使用场景，最后会讨论一下我们迄今为止从Dapper收获了些什么。

时间格式字符串-年底的惊喜

这一个常在元旦附近出没的Bug，主要原因是Java 日期格式FormatString 中的yyyy 被写成了YYYY。
要注意的是，对于年份来说，大写的Y和小写的y其意义是不同的。y 是Year, Y 表示的是Week year

经过试验，得出的结果如下：Week year 意思是当天所在的周属于的年份，一周从周日开始，周六结束，只要本周跨年，那么这周就算入下一年。

注意上面的Week year 指format时的结果，对于YYYY格式使用parse, 会得到意想不到的结果。

1
2
3
4
5
6
7
8

SimpleDateFormat upperFormater = new SimpleDateFormat("YYYY-MM-dd HH:mm:ss");
SimpleDateFormat lowerFormater = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
System.out.println(lowerFormater.parse("2021-12-30 09:00:00"));
String lower = lowerFormater.format(lowerFormater.parse("2021-12-30 09:00:00"));
System.out.println(lower);
String upper = upperFormater.format(lowerFormater.parse("2021-12-30 09:00:00"));
System.out.println(upper);
System.out.println(upperFormater.parse("2021-12-30 09:00:00"));