Google BBR 拥塞控制算法简单介绍

最近在网上看了一些 BBR 的资料,简单玩了一下,这里做一个记录。

简单的介绍

BBR 是一种拥塞控制算法。拥塞控制算法的目的简单来说就避免将过多的包发到网络上,造成网络堵车。假如现在网络上比较拥堵,那么 TCP 就使用拥塞控制算法来让发送端发的慢一些。如何在不造成网络拥堵的情况下,又能利用带宽快速发送数据,就是拥塞控制算法要解决的问题了。

这篇文章介绍了常见的拥塞控制算法。一般的拥塞控制算法是通过丢包来认为网络中是否发生拥塞的,这样的问题是,网络是存在一定的概率因为错误而丢包,就会导致无法充分利用带宽;另外一个问题是网络有可能会有 buffer 存在,导致发送端认为的网络容量因为没考虑到 buffer 比实际的要高。

那么 BBR 是怎么解决问题的呢?1)不再将丢包认为是一个网络拥堵的现象;2)分别估计带宽和延迟。

以下是启用的实验。(略水)

新开一个一台 Fedora32 发行版的机器,可以看到默认的拥塞控制算法是 cubic :

升级 Kernel

Kernel 的拥塞控制算法是可插拔的,这意味着我们不需要重新编译 Kernel 就可以更换拥塞控制算法。但是 BBR 要求最低是 4.9.0 才能使用。

但是 Fedora32 的内核已经是 5.x 的了,所以我就不用升级了。

Enable BBR

使用下面的命令可以启用 BBR:

接下来是验证。首先确认 bbr 在可用算法中。下面这个输出应该包含 bbr (顺序不重要):

在验证当前生效的算法应该是 bbr:

最后验证 Kernel 模块已经正确加载:

输出如下:

bbr 的开启就完成了。

Benchmark

对比一下相比于默认使用的 cubic,有没有速度的提升。先安装 httpd,生成一个随机的文件,供下载测试。

然后再开一台旧金山的机器,从开启 bbr 的机器上下载文件测试速度。使用下面这个命令来下载刚刚生成的这个 100MB 的文件。

测试了当前服务器上可用的几种算法,结果如下:

  1. cubic: 8.047663181818182(s)
  2. bbr: 8.084801727272726(s)
  3. reno: 8.060761727272727(s)

bbr 竟然是最慢的一个,-_-||

 

参考资料:

  1. Implementing SCTP Pluggable Congestion Control for Linux
  2. 中科大 李博杰写的科普
 

JavaBean, POJO, DTO, VO, 傻傻分不清楚?

关于这些概念,网上有很多解释,大多数都是胡说八道。我在 Stack Overflow 上看到了一个版本,认为这个理解是比较合理的。

太长不看版:

DTO 和 VO 用途是一样的,大多数语境下都可以互相替换。JavaBean 是一个惯例,DTO 和 VO 都遵循了这个惯例,所以他们都是 JavaBean. DTO, VO 和 JavaBean 都是 POJO.

JavaBean

Sun 推出了一个 JavaBean 的惯例,遵循了这个惯例的 Java 对象都是 JavaBean. 所以首先要理解的是,JavaBean 并不是一个实现,也不是接口,只是一个惯例。

这些惯例包括:

  • 可以使用一个没有参数的构造器初始化出来这个 Bean;
  • 可以通过 getter/setter 读写 Bean 的属性;
  • 可以序列化这个 Bean;
  • …… (详细的定义请参考 Sun 的说明)

Java语言欠缺属性、事件、多重继承功能。所以,如果要在Java程序中实现一些面向对象编程的常见需求,只能手写大量胶水代码。Java Bean正是编写这套胶水代码的惯用模式或约定。这些约定包括getXxx、setXxx、isXxx、addXxxListener、XxxEvent等。遵守上述约定的类可以用于若干工具或库。

——来源:杨博

有了这个概念(惯例),Spring, Hibernate 这些框架交流、实现起来,都大量使用 Bean 这个概念。比如“注入一个 Bean“,“声明一个 Bean”,你就知道这里的这个 Bean 必须要有无参数的构造函数,必须要有 setter/getter 等等。这些框架在使用的时候,会采用初始化出来 Bean 然后 setXX() 这种方式,构造出来最终的 Bean.

JavaBean 并不是一个接口,更像是为了交流方便的一个名词。

POJO

POJO 的全称是 Plain Old Java Object, 简单又老的 Java 对象。这里的简单是相对来讲的。 EJB 2.x 的 Entity Beans 比较重量,需要实现 javax.ejb 的一些接口。而 POJO 就比较轻量,就是一个 Java 对象,不需要实现任何的接口。

这个术语由 Martin Fowler, Rebecca Parsons 和 Josh MacKenzie 在 2020 年提出:

我们想,为什么人们不愿意使用一个普通的对象,大概是因为普通的对象没有一个 fancy 的名字,所以我们给它们取了一个。

所以 POJO 本质上也是可以方便沟通的术语。PO 在那个年代也不是一个新词:

  • 电话制造行业的 POTS, Plain Old Telephone Service
  • PODS, Plain Old Data Structures, 表示在 C++ 定义数据结构,但是只使用 C 语言里面的 Feature
  • POD, Plain Old Documentation, Perl 语言中的概念

有了 POJO 这个名字,相比框架里面各种的对象概念,就容易理解多了,所以这个概念被很广地使用开来。可以用 POJO 来解释 JavaBean: JavaBean 就是可以序列化的 POJO, 并且有无参构造器,可以使用 getter/setter 来读写属性。

VO

Value Object, 是保存了值的对象。比如 java.lang.Integer. Martin Fowler 对 Value Object 的描述是:

Value Object 是指像 Money 或者 Date Range Object 这样的小对象。对它们来说,值的语义比 id 的语义更加重要。比较它们相等的时候,只要它们的值相等就可以认为是相等,而不需要在意是不是一定是同一个对象。

一个比较好理解的视角是,Value Object 应该是不可变的。如果你要改变一个 Value Object, 你应该创建一个新的然后替换掉原来的,而不应该改变原来的对象的属性。

我认为这个上面这个对 Value Object 的理解是比较合理的,但是早期的 J2EE 教材将 Value Object 描述为一个完全不同的理解,在这个理解中 VO 完全等价于 Data Transfer Object.

DTO

Data Transfer Object. Data Transfer Object 是一个 EJB 中引入的(反)设计模式。思想是将很多数据组装在一个 Value Object 中,然后通过网络传输。而不是在 EJB 中进行很多次远程调用。

DTO 和业务对象的区别是:DTO 除了保存数据,没有其他的行为(方法)。

传统中的 EJB 引入 DTO 主要是为了解决两个问题:

  1. EJB 的 Entity Beans 无法序列化,DTO 解决这个序列化的问题;
  2. DTO 的使用,含蓄的引入了一个组装数据的过程,将所有的数据组装好再返回;

总结一下,对于大多数的情况, DTO 和 VO 是一个东西(Martin Fowler 理解的 VO 不是),并且它们遵守了 JavaBean 的约定。所有的这些东西都是 POJO.

我觉得本质上讲,这些概念也是类似一种“设计模式”的东西,之所以提出来这些概念,还是解决 Java 表达能力的不足,需要用一种通用的做法在 Java 程序员中形成共识,来解决这个问题。比如在 RPC 调用中,我定义了这么一个方法:

然后被同事说不能这么用,这样“没有扩展性”,假如将来要添加一个新的字段 address ,那么你这个接口扩展了一个字段,就不能向后兼容了。

应该这么定义:

这样,这个接口就有扩展性了。实际上,这也是 JavaBean 的一个用法吧。

但是在 Python 中,我们的函数的变量的形式有:

处理起来“兼容”问题就简单多了。

但是 Java 不行,Java 必须将参数封装成对象,然后生成一堆 setter/getter,原本一行代码能搞定的事情,就要写成几十行。

相关参考:

  1. 阿里巴巴Java开发手册中的DO、DTO、BO、AO、VO、POJO定义
  2. https://stackoverflow.com/a/1612671/6931919
 

幻读

数据库的事务应该保证隔离性,这就是说,两个用户(连接)在操作数据库的时候,它们之间的操作应该互相不受影响的。比如用户 A 在修改了 foo 这个变量,但是还没有提交,那么 B 不应该看到这个修改。

但是隔离性的时间不是一件简单的时间,隔离性保证的越高,要么实现的技术手段越复杂,要么性能很低。因为很显然,避免多个事务之间互相影响,就必然要通过加锁来同步操作。如果想要更高的性能,就必须要加更加细粒度的锁,或者使用无锁(更加复杂)的技术来实现。

隔离性一般有这几个问题:

  1. 读到了未提交的数据。这个比较好理解,也比较好解决。一般加锁就行。
  2. 在同一个事务中,两次读到的数据不一样。比如用户 A 开始了一个事务,查询了 foo,这时候用户 B 修改了 foo 并且提交了,然后 A 在事务中又查询了 foo,发现和上一次查询不一样。这也违反了“隔离性”,但是读到的数据却的确是已经提交的数据。这就是“不可重复读”问题。现在用 MVCC 的方式解决,大体意思就是一个事务开始的时候记一个版本(时间戳)v1,其他人所有的操作都会带上新的版本(时间戳),那么在这个事务中,所看到的所有的数据都是先于 v1 的,所有在 v1 之后提交的数据都看不到。MVCC 有一些 tricky 的地方,比如要删除数据的时候,不能直接删除,因为删除了的话,对于所有的事务(即使是在删除操作 commit 之前开始的事务)来说都看不到了。为了解决这个问题,需要在要删除的对象上标记一个新的版本,记为删除。这样之前的事务看到这个数据的时候,发现删除操作是在自己的事务版本之后的,就仍然可以读到这个对象。这样,就可以解决了同一个事务中读到的数据不一样的问题。(但这样其实会带来新的问题,比如数据标记新的版本了,那么索引要不要标记呢?索引怎么做隔离?比如 PostgresSQL 的 COUNT 其实不是一个 O(1) 的操作,而是要遍历每一行数据,检查数据对当前的事务是否是可见的
  3. 幻读。上面说这么多,主要是给这个问题做铺垫,我觉得这个问题最有意思了。本文下面会主要讲讲幻读。

假设这么一种情况:一家医院规定必须至少有 1 名医生在值班,某天值班医生 A 和 B 感到不舒服想请假,按照系统的要求,不能让 A 和 B 同事请假成功的。如果我们使用的数据库没有解决了幻读的问题,那么即使解决了“重复读”问题,也是不正确的。考虑下面这种情况:

这样两人都会同时请假成功。

这个问题并不是“不可重复读”问题,因为两个事务看到的正是事务开头的数据。这个竞争条件产生的根本原因是,这两个事务互相依赖了别的对象,但是别的对象又被更改了。

在这种情况中,我们可以锁住所有的对象,强制他们只能一个接一个的执行。

再举一个幻读的例子:抢占会议室。

抢占程序是这样的,先检查会议室 R 在 某一天 12:00 有没有被抢占,如果没有的话,就可以抢占。那么假如两个事务同时发起的话,就同时看到这个会议室并没有被抢占,就会错误地被抢占两次。被抢占两次的 SQL 过程如下:

这个问题我们也可以通过加锁来解决:将不存在的锁转换成已经存在的。比如,只允许抢占 7 天内的会议室,并且以小时为单位进行抢占。然后就可以将 7 天内的每一个小时作为一个锁,要抢占这个会议室就必须先获得锁。

另外有一些问题不容易实例化不存在的锁。比如注册系统,不允许同一个用户名字被注册两次。但是这种情况可以用数据库的 unique 约束来解决。

不太好解决的问题,防止双重开支。支付系统要保证用户支付的钱不能大于自己的余额,不然公司要倒闭了。那么付款的事务中,我们先检查一下余额是否足够,然后在发起支付,这样可以吗?如果用户同时用电脑付款,也用手机付款,会不会在同一个事务中提交两次呢?

这些问题都有一种共同的模式:

  1. 执行一个 select 查询;
  2. 根据 1 的查询结果,判断当前的操作是否能够继续;
  3. 如果能,就继续,但是这个操作会改变 1 的结果;

因为事务进入的时候 2 都是检查通过的,但是都执行了 3,会影响彼此的 1 的结果,导致出现竞争条件。这就是幻读。

除了“强行加锁”,即上文中提到的方法以外。最靠谱的是使用串行化的隔离级别,即对于程序员来说,数据库好像在串行地一个一个执行事务,这样永远不会有竞争条件。但是因为性能问题,串行化很少使用。

 

注:本文内容大多数都阅读 DDIA 第七章的笔记。

 

Redis 的命令设计

很多人都知道,Redis 对代码上简单有一种极致的追求,比如坚持命令处理单线程。我在很多用户层面的配置和命令中,也看到了这种简单而优雅。比如 SAVE 的参数,save 900 1 表示 900 秒内有一次写,就执行备份,这样可以配置多条配置,就可以达到即可以根据时间配置备份频率,又可以根据写入次数配置频率。

又比如 ACL 的设计,虽然不能说设计的特别简单,但是功能非常丰富,即可以根据 key 来设置权限,又可以根据命令来设置权限,并且既可以设置白名单,又可以设置黑名单。单单来说白名单与黑名单,我见过很多系统,只要涉及这两个概念,就会让用户一头雾水了。如果我有一个A是在黑名单中,然后A里面的X在白名单中,那么X到底会不会生效呢?然后你就必须去看它的实现才知道是怎么样一个逻辑。(比如 poetry 对文件的 include 和 exclude 配置,就是一个反例)但是 Redis 的 ACL 设计,用了类似 DSL 的方式,一点歧义都没有。

但是 KeyDB 中说,Antirez 对代码库的简单要求的太过分了,以至于将很多复杂留给了用户。在 Redis 命令设计方面,我有类似的感受。甚至对于有一些命令的设计上,我认为并没有设计的取舍,纯粹是不知道为啥就设计成了这个样子。

这篇文档就来说说我对 Redis 中那些理解不能的设计。首先声明,这都是我个人无法理解,也可能它有它的道理,只是我不知道,如果你知道这个设计的道理,麻烦在评论中告诉我。

第一个想到的就是,为什么命令会允许有空格?

在 RESP 协议中,是用首位标志指示后面的 String 的,假如我用 RESP 将 set foo bar 打包发出去,那么我实际上发出去的就是(以下输出用这个脚本抓到的):

这里 => 表示发出去的内容,<= 表示收到的内容,这是抓包脚本添加的。*3 表示后面会发送 3 个 token,$3 表示接下来的字符串长度是 3.

假如命令中可以允许空的话,那么对于 client list 这个命令,实际发出去的就是:

可以看到,redis-cli 是将 clientlist 分开作为两个 token 发送出去的,根本无法知道第一个“变量”一个命令,还是第一个变量+第二个变量是一个命令啊!对于一些要解析发送内容的场景来说很是头疼。

这个问题仔细想想,如果你用 Redis Module 来扩展 Redis 的功能的话,也会遇到的。比如你要实现一个 HELLOWORD RAND 命令怎么办?你没办法告诉 Redis说 “嘿! 兄弟我实现的这个命令,你收到的时候要拿前两个参数作为命令名字,后面的参数才是命令参数,不要搞混了哦~”,因为 Redis Module 总不能连 Redis 去解析命令那部分代码也干涉吧(我不确定做不做得到,没有去看 Redis 这一部分的源代码,读者知道的话请赐教),我写个 Redis Module 就是想做个简单的功能,你不要对我要求太多!

所以怎么办呢?Redis 文档里面说,哥们你得这么写 HELLOWORLD.RAND. 你看这不就没空格了吗?我解析的时候总是拿第一个参数来解析就可以了。

我靠,凭什么只能你官方的命令防火,不能我 Module 的命令点个灯啊!

第二个问题,人格分裂。

在 Redis 中,有一些命令是需要接受 pair 的。比如 HSET,你可以同时设置多个键值对(since 4.0):HSET foo bar hello world. 所以 HSET 的语法是 HSET key field value [field value ...] 。So far so good, no problem at all.

But,XREADGROUP 这个命令的语法是什么鬼???

为什么会有 key key ... id id ... 这种设计??

假如我想写一个自动补全的客户端,在 key 这个 token 的时候,我没有任何办法知道,应该根据 key 来补全,还是要根据 id 来补全啊! T T

第三个问题,一些命令的向后兼容。

这里说的是 AUTH,在 Redis5 之前,AUTH 的用法是 AUTH PASSWORD。但是自动 Redis6 增加了 ACL 开始,AUTH 支持两种用法:AUTH USERNAME PASSWORD 或者 AUTH PASSWORD.

我的痛苦非常简单,也非常痛。

我有一个超屌的功能,就是能在命令行中将一部分输入替换成 * (屌吧,至少我没见过任何一个命令行能够这么做,sudo 让你输密码的时候,你根本不知道输入了几位,如果不小心输错,只能按下 N 次 Delete)

但是现在,第一个参数可能是 USERNAME ,可能是 PASSWORD,我到底是隐藏呢?还是不隐藏呢?(好吧其实这个痛点对于大部分用户来说不痛,向后兼容了嘛,还挺好的!只有我哭晕在厕所)

 

PS: IRedis 即将支持 Redis 6~ 欢迎尝试

 

Use the Index, Luke! 笔记6:增删改的索引

前面我们讨论的都是查询语言,但是 SQL 不仅仅是查询,还需要修改数据。索引是完全冗余的数据,是用空间换时间的一种形式。对于修改数据来说,这就意味着不仅要修改表中的数据,还要修改索引中的数据,索引对修改数据来说会带来负面的性能影响。

Insert

Insert 语句几乎是唯一无法从索引获益的语句,因为 insert 没有 where 条件。

索引越多,insert 执行的就越慢。

在表中添加一条记录的过程如下:首先,在数据库中找一个地方放这条记录。在一般的 heap table 中,没有对 row 的顺序的要求,所以随便找一个空闲的 table block 放就可以了。基本上都是顺序写,速度很快。

但是如果有索引的话,必须要保证在索引中能找到这条数据,所以也要在索引中添加这条数据。

索引中的数据都是有顺序的,并且还要保证索引的 BTree 添加了这条记录之后还是平衡的。这个操作就慢很多。虽然数据库的索引本身可以帮助这个过程快速的找到这个记录所在的 block 位置,但是依然要查几(1-4)个block。

找到这个 block 之后,数据库需要确认这个 block 现在是否有足够的空间放这个记录,如果没有的话,就要将叶子节点分裂,将当前 block 的记录平均分在新老的叶子节点中,保持树的平衡。最糟糕的情况下,如果父节点这个时候也同时满了,就需要再来一次分裂。

下图是没有索引到有5个索引的情况下,插入的性能:

可以看到,在第一个索引出现的时候,性能相比没有索引下降了上千倍。随着索引的增加,性能在不断的下降。所以尽可能的复用索引也很重要。

那么什么索引都不建的情况下不是插入很快吗?但是没有是索引的话,这些数据几乎没办法使用,也就没什么价值了。即使 write-only log 表也有一个主键索引。

但是有一种情况,就是从其他的 SQL 系统 load 大量的数据的时候,暂时 drop 掉索引是一个加速数据加载的好方法。数据仓库里面这样操作比较常见。

Delete

Delete 可以受益于索引了,因为 delete 可以有 where 语句。所以我们在前文中讨论过的使用索引的场景,同样适用于 delete。(基本上就是索引可以用于 select 的地方都可以用于 delete)

找到了要删除的数据之后,就可以从 table 中删除这条数据,同 insert 一样,在 table 中删除之后,还要在 BTree 索引中执行删除。这一步操作和 insert 是一样的,在索引中删除之后可能要设计叶子节点的合并,是比较耗时的。所以随着索引越多,性能下降的跟上面 insert 那个图差不多。

Update

Update 操作同样需要更新索引,所以跟上 insert delete 差不多。

有一点不同的是,update 可能更多多列,可能更新一列,更新的列数更多,涉及需要更新的索引就越多。

显然,如果一列数据没有变,那我们就最好不要更新它。

这句话看起来是废话,但是很多 ORM 的 save() 操作,每次都会更新所有的属性的。比如 Hibernate,只有显示地关闭 dynamicUpdate 才不会每次都去更新。这一点格外重要。

一个保险的办法是在开发的时候打开 ORM 的真正执行的 SQL 日志,进行审计。