性能测试:ArrayBlockingQueue vs. Go channel

测试方案:

  1. 主线程将一个 Integer 对象发到 Channel 0
  2. 线程 i 将对象从 Channel i 不断搬运到 Channel i+1
  3. 最后一个线程从 Channel N-1 中拿到对象,做加和

为了保证公平,Go 中自行封装一个 Integer 而不是用 int 型;考虑到实际中大多数情况下 channel 里走的都是对象而非基本类型,这样是合理的。

发现二者完成时间基本都在 3.8s ~ 4.0s 之间,可以说没有差异。ArrayBlockingQueue 的性能看来还是很高的。

PS. 尝试了容量不限的 ListBlockingQueue,时间在 5s 左右,也还可以接受。

测试代码在这里

获得了 AWS Solution Architect 证书

Solutions-Architect-Associate

可惜这个博客并不是在 AWS 上。

分享一下用到的学习资料:

个人学习笔记(整理自 ACloudGuru 课程每章总结)

译:Varnish 架构师笔记

找到这篇文章是在阅读 Kafka 文档时,一个名为 “Don't fear the filesystem!”的段落中提到的。文档指出,我们总是思维定势地以为磁盘很慢,内存很快。然而今天的计算机体系结构中,并非这么简单:

  • 因为操作系统 PageCache 的存在,磁盘操作可能很快
  • 虽然磁盘 IOPS 难以提高,但吞吐量在不断上升;换句话说,顺序读写磁盘非常快
  • CPU Cache 常常被忽略了,了解 CPU Cache 对提升内存读写性能至关重要

原文链接

当你开始深入 Varnish 的源代码后,应该会发觉它与你日常所见的一般应用软件有着明显不同,而这绝非偶然。

多年以来我的绝大部分时间花费在 FreeBSD 的内核开发上,而每每涉足用户空间编程,却总是毫无例外地发现那里的人们还在以1975年的方式工作。

所以 Varnish 这个项目一开始并没能激起我很大的兴趣。但我渐渐意识到 Varnish 虽然是一个用户态应用,但却也是一个能充分发挥我长久以来积累的关于硬件和内核的经验知识的理想场所。目前 Varnish 的开发已经进展到alpha版本的阶段,而我觉得应当承认自己相当享受这一段历程。

1975的编程方式到底出了什么问题?

简而言之:计算机系统再也不应该被看作是由两个存储层次构成的了。

首先是主存:从水银延迟线,磁芯存储器,到现在可供随机访问的RAM。

然后是辅存:从纸带,磁带,到磁盘。最早的磁盘有一屋子大,然后缩小到洗衣机的尺寸,到今天硬盘可以被放进随身携带的 MP3 播放器中。

于是大家就按照这样的划分,在内存中分配变量,在磁盘中存取数据,以这样的方式进行编程工作。

还是拿 Squid 这个1975年风格的系统为例:你事先配置它的内存和硬盘用量,然后它会花费大把时间来追踪哪些HTTP对象驻留内存中,哪些存放在硬盘上,并且根据不同情况来调整它们的放置策略。

然而实际上呢,现今的计算机应被视为只使用一种统一的存储系统,这个系统完全基于硬盘(磁盘,固态硬盘或者其他什么东西),而传统的内存呢,在操作系统内核和虚拟内存硬件机制的帮助下可以被看作是硬盘的缓存。

回过头来看 Squid 的策略,它精心设计的存储管理机制实际上却陷入了与操作系统内核同样精巧的管理策略的激烈冲突。而就像所有内战一样,这样的冲突必然一事无成。

我们可以尝试从细节角度来看整个流程:一开始 Squid 会请求内存用来创建了一个 HTTP 对象,它往往会在创建之初被频繁访问多次,然后闲置一段时间。而后当内核接收到其他内存分配请求时,会将这些它认为闲置的内存数据放到硬盘交换分区去,而把这些回收的内存页用于更活跃的任务。在Squid下一次访问这一对象时,操作系统又会把暂存在交换分区的数据取回来供它使用。 这些内核对于内存的操作对于 Squid 是透明的,在它看来这个 HTTP 对象就像从没离开过内存一样,而实际上物理内存页得到了更有效的使用。

这就是虚拟内存机制。

如果事情到此为止的话就好了,但接下来1975年式的编程风格就出现了。

一段时间之后,Squid 也和内核一样注意到了这个对象闲置了,于是打算把它放到硬盘上去,省出一些内存来给更频繁访问的数据使用。所以它打开一个文件把这个对象写了进去。

打开慢镜头来看这个写入的过程:

Squid 通过系统调用 write 将 HTTP 对象的虚拟内存地址传递给内核。
由于物理页已经被内核交换出去,这个内存访问将引发一个缺页中断。 为了重新载入这个内存页,内核不得不交换出另一个正在使用的内存页(很可能包含另一 Squid 的对象),修复页表,然后继续执行系统调用。 Squid 对这些一无所知,它自以为只是进行了一次再普通不过的访存操作而已。

接下来 Squid 可以终于拿这块内存放别的数据了。而当这个对象再次被访问到时,Squid 又不得不把它从硬盘中取回来。首先它需要空闲的内存来存放这个对象,于是它根据某种淘汰算法选中另一个最近不常用的对象,把它写到硬盘上去(上面那些步骤重演了一遍)。然后打开文件读出这次所需的那个对象,最后通过网络套接字发送出去。

这一切显然充满了各种无用功。

让我们看看 Varnish 是怎么做的

Varnish 会直接请求大块虚拟内存,并由操作系统将这个内存空间映射到一个硬盘文件。当需要访问某个 HTTP 对象时,只需要正确索引这个对象相应的虚拟内存地址,剩下的交给操作系统就好了。当内核需要回收一些内存页时,它会自行决定将一些 Varnish 的内存数据写回到映射的文件中。而当 Varnish 再次访问这一块虚拟内存时,内核自然会腾出内存页来将文件中的数据读回使用。

仅此而已。

Varnish 不去尝试控制哪些数据应该被缓存在内存中,哪些应该放到硬盘上去。内核代码和硬件会处理这些事情,而且处理得很漂亮。

此外,与 Squid 不同的是 Varnish 只需要一个文件而不是为每个 HTTP 对象创建单独的文件。没有任何理由需要在 HTTP 对象和文件系统对象间建立一一对应的关系,也没有理由把时间浪费在文件系统的命名空间处理上。Varnish 需要处理的只是虚拟内存的指针和所需对象的长度值而已。

虚拟内存的出现为数据大于物理内存的场景提供了一种便利的机制,但人们似乎并没有领悟这一点。

更多的缓存

CPU 的时钟频率目前看来基本止步于4GHz了。即便如此,为了避免内存读写的瓶颈,硬件工程师们不得不使用使用一级,二级,有时候甚至是三级 CPU cache(现在我们可以认为 RAM 是第四级缓存了),此外还有写缓冲,流水线,页模式读取等各种技术,而这些都是为了加快访存来匹配CPU的处理速度。

虽然时钟频率方面受限,但硅工艺的进步缩小了器件尺寸,集成了更多的晶体管。所以多核 CPU 的设计逐渐成为主流,但这从编程模型角度看来实在是很糟糕的一件事。

虽然多核系统存在已久,但编写能够利用上多个 CPU 的代码依然是一件棘手的事。而要在多核系统上写出高性能的程序就更是如此了。

比如我们有两个计数器:

unsigned n_foo;  
unsigned n_bar;  

在一个 CPU 上执行了 n_foo++ 的操作会使得CPU读取 n_foo 的值然后写回。

读取一个内存位置首先会检查它是否在 CPU L1 cache 中命中,这挺难的除非它刚刚被使用过。接下来是 L2 cache,我们不妨假设依然没有命中吧。

如果是在一个单核系统上,CPU 会去内存读取数据然后就完事。但在多核系统中,我们必须去检查其他CPU核心是否缓存并修改了 n_foo 的数值。我们会发起一个特殊的总线事务做这种检查,如果其他 CPU 答复说它确实持有这样一份拷贝,它就需要将它写回到内存中。如果硬件设计良好,我们可能可以通过总线监听获得这份新数据,不然的话就需要去内存里读取它。

我们终于可以修改 n_foo 的值了,但其实修改完了之后一般不会直接将它写回到内存中。为了之后操作的快速存取,很可能我们会把它缓存起来。

现在假设另一个 CPU 需要执行 n_bar++ 的操作,它能够直接进行吗?答案是否定的。因为缓存的单位并不是字节而是 cache-line(典型值是 8-128 个字节)。所以当第一个 CPU 忙着处理 n_foo 时,第二个 CPU 必须等待,因为虽然它想获取的是另一个变量,但却不幸落在了同一个 cache-line 中。

明白了吧?没错,这有点丑。

我们该怎么办

尽一切可能,减少内存操作。

下面是 Varnish 的一些做法。

当需要处理一个 HTTP 请求或响应时,我们会持有一组指针和一个内存工作区。我们并不需要在处理每个 HTTP 报头时都调用 malloc,而是一次性分配整个工作区的内存,然后按需从中获取所需空间。而当我们一次性释放全部报头时,只要将指针重置到工作区的起始位置即可。

当需要将 HTTP 报头从一个请求拷贝到另一个请求(或从从一个响应复制到另一个响应)时,并不需要进行字符串拷贝,而只要拷贝指针。如果源报头在这个过程中不会被不释放或改写,这样做是非常安全的。比如从客户端请求到后台请求的拷贝就是这样一个例子。

但在一些新构建的报头生命周期长于源报头的场景中,就需要另外分配内存了。例如当我们会缓存新 HTTP 对象时,首先就计算整个报头所需空间,然后通过一次 malloc 调用来获取内存。

另外我们会尽可能重用那些正被缓存的内存数据。

比如 Varnish 的 worker 线程是以最近最忙的方式调度的,也即是说一个 worker 线程空闲后会被放回到队列的最前端,使得它更有机会马上去处理下一个新请求,这样它的数据,栈空间和变量等很可能可以在 CPU 缓存中被重用,而不是再次从RAM中读取。

同时对于 worker 线程经常使用的数据,我们会把它们分配在每个线程的栈变量中,并且确保它们占据完整的内存页。这样我们就可以尽可能避免 cache-line 的竞争。

如果对你来说这些听起来都很陌生,我可以告诉你它们是确实有效的:Varnish 处理一个命中缓存的请求最多只需18个系统调用,而且其中不少只是为了获得时间戳来满足统计的需要。

这些技术并不新鲜,我们已经在内核开发中使用了10多年,现在该轮到你们来学习了:-)

如此,欢迎进入 Varnish,一个 2006风格架构的程序。

HackerRank: Spanning Tree Fraction 题解

题目:https://www.hackerrank.com/contests/w31/challenges/spanning-tree-fraction 一张连通图G=(V,E)上,每条边有a和b两个整数,求一个生成树使得Sum(a) / Sum(b) 最大,输出这个最大值的分数形式 p/q

设 $\frac{\sum{a_i}}{\sum{b_i}} \ge c$ ,经过变换可得,$\sum{(a_i - b_i c)} \ge 0$,这种形式下 ai - bi * c 就退化为一条边的 cost,能方便得用 Prim 或 Kruskal 算法求出 cost 最大的生成树。

因为我们知道 c 的取值是受限制的——显然不能任意大。根据题意,我们要求 c 的最大可能值 max(c),借助二分查找:如果 c 取值 (L+R)/2 时找不到生成树满足 sum cost >= 0,说明 max(c) 在右半边;反之,如果 c 的取值 (L+R)/2 时可行,说明在左半边(因为 C 是实数,这里说的都是闭区间)。 

Prim 和 Kruskal 算法的实现也是一个难点。本题中 Kruskal 算法更简单,从小到大取所有的边,利用并查集可以快速判断这条边是否已经被连通了,若还为连通就要选取此边。

最后的 p/q 怎么求呢?显然从实数 c 变回 p/q 是不可能的。假如循环 N 次,最后一次循环可以认为已经收敛了,最后一次计算中途的 $\sum{a_i}$ 和 $\sum{b_i}$ 就是最优 case 下的取值,将 $\frac{\sum{a_i}}{\sum{b_i}}$ 化简、消除公约数即可。

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <numeric>
using namespace std;

int n, m;  
const int N = 100002;  
int u[N], v[N], a[N], b[N];

double w[N];  
int p[N];

int set[N];

int find_set(int x) {  
    if (set[x] == x) return x;
    return set[x] = find_set(set[x]);
}

bool union_set(int a, int b) {  
    a = find_set(a);
    b = find_set(b);
    if (a == b) return false;
    set[a] = b;
    return true;
}

int A, B;

bool check(double c) {  
    for (int i = 0; i < m; i++) w[i] = a[i] - b[i] * c;
    sort(p, p + m, [](int i, int j){ return w[i] > w[j]; });
    iota(set, set + n, 0);
    A = B = 0;
    for (int i = 0; i < m; i++) {
        const int e = p[i];
        if (union_set(u[e], v[e])) {
            A += a[e];
            B += b[e];
        }
    }
    return A >= B * c;
}

int gcd(int a, int b) {  
    while (a && b) {
        if (a > b) a %= b;
        else b %= a;
    }
    return a | b;
}

int main() {  
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        scanf("%d %d %d %d", &u[i], &v[i], &a[i], &b[i]);
    }
    iota(p, p + m, 0);
    double lo = 0, hi = 1e5;
    for (int t = 0; t < 100; t++) {
        double c = (hi + lo) * 0.5;
        if (check(c)) lo = c;
        else hi = c;
    }
    int g = gcd(A, B);
    printf("%d/%d\n", A/g, B/g);
    return 0;
}

AWS 学习笔记之 SQS/SWF/SNS 等

SQS - Simple Queue Service

SQS 是 AWS 的消息队列服务,用于暂存消息并等待接收者处理。

  • 不保证 FIFO,可能乱序到达
  • Visibility Timeout 最长 12 小时
  • 保证每条消息至少被传递一次(At least once),这意味着某些情况下可能传递多次,所以你写程序的时候要注意处理重复的消息
  • 每条消息最大 256 KB
    • 然而,依据 64 KB 的 Chunk 数量计费
    • 所以一个 256 KB 的消息可能产生 4 次费用:4 * 64 KB chunks
  • SQS 的消息没有优先级;如果你需要优先级,最佳实践是创建多个 SQS 队列

SWF - Simple Workflow service

SWF 提供 Workflow 服务,比如 Amazon 用它来处理客户订单的流程——下单、支付、配货、发货……

  • 一个 Workflow 可以长达 1 年,而 SQS 的消息最多保留 14 天
  • SWF 的 API 面向 task,而 SQS 的 API 面向 message
  • SWF 保证一个 task 只会分配一次、不会重复;SQS 不保证这一点
  • SWF 会跟踪每个 task 和 event 的处理;SQS 没有这个功能

SWF 有以下 3 种 Actors:

  • Workflow Starter - 启动 workflow 的程序,比如电商网站的下单操作
  • Decider - 控制 task 的执行流程,如果某个步骤完成/失败,decider 决定下一步做什么
  • Activity Worker - 执行任务,可以是人类

SNS - Simple Notification Service

SNS 提供消息通知服务,例如当 CloudTrail 发出警告时给用户发 Email 通知。

SNS 的订阅者可以是以下这些:

  • HTTP / HTTPS
  • Email / Email (JSON)
  • SQS
  • Lambda
  • Application

SNS vs SQS:

  • 相同点:都是消息服务
  • 不同点:SNS 是 Push,而 SQS 是 Pull (Poll)

API Gateway

  • API Gateway 很便宜,并能自动伸缩
  • API Gateway 可以通过 cache 提升性能,减轻后端服务器的负载
  • API Gateway 可以 throttle 流量从而防止被攻击
  • 可以把所有的访问记到 CloudWatch
  • 如果你用到了跨域 AJAX,记得开启 CORS (Cross-Origin Resource Sharing)

Elastic Transcoder

提供云转码服务,将原始视频格式转换到不同的格式,从而方便在电脑、平板或手机上播放。AWS 提供了很多预设的格式,你不用自己调参数,直接选择对应的设备就可以了。

根据转码的时间以及分辨率收费。

AWS 学习笔记之 VPC

VPC

  • 把 VPC 想象成一个逻辑上的数据中心
  • 包含一个 IGW (Internet Gateway)或者 Virtual Private Gateway,Route Tables,Network ACLs,Subnets,Security Groups
  • 1 个 Subnet = 1 个可用区
  • Security Group 是有状态的,Network ACL 是无状态的
  • VPC 可以连接(peer)起来,甚至可以连接不同 AWS 账号的 VPC
  • 不能 transitive peer!如果 A 和 B 相连,B 和 C 相连,A 和 C 是联通的,必须手动连接 A 和 C

NAT Instance

  • 创建 NAT instance 的时候要关掉 Source/Destination Check
  • NAT instance 必须放在 public subnet 里
  • 必须有一个 Elastic IP
  • 必须有一个从 private subnet 到 NAT instance 的路由
  • NAT instance 支持的流量取决于 instance size,如果不够用只能增加 instance size
  • 如果要 HA,可以利用 Autoscaling Group 为不同 AZ 的 subnet 创建 NAT instance

NAT Gateway

  • 很新,很可能不出现在考试中
  • 可以自动伸缩,最大支持 10Gbps
  • 不用管补丁
  • 不用管 security group
  • 不用手工禁用 Source/Destination Check
  • 自动分配 IP 地址
  • 记得要更新 Route table

Network ACLs

  • VPC 创建的时候会自动创建一个 default network ACL,允许所有 outbound 和 inbount 流量
  • 你可以创建自定义的 network ACL,默认情况下,新创建的 network ACL 阻止所有连接(为了安全考虑)
  • VPC 里的每个 subnet 必须要指定一个 network ACL,如果你没有显式的指定 network ACL,那就是用 default network ACL
  • 一个 subnet 只能指定一个 network ACL;但 network ACL 可以被指定给多个 subnet。注意,当你把一个 network ACL 指定给某个 subnet 的时候,subnet 之前设定的 network ACL 就被挤掉了,不能共存(以上两点和 Route table 很相似)
  • Network ACL 的每条 rule 都有一个序号,序号决定了 rule 执行的循序
  • Network ACL 包含两张表:inbound rules 和 outbound rules,每个 rule 可以是 allow 或者 deny
  • Network ACL 是无状态的。也就是说,对允许进入的流量也可能会被拒绝出去,反之亦然(区别于 security group)
  • 可以用 Network ACL 来 block 某些 IP 地址(段),security group 则不行

NAT vs Bastions

  • NAT 用来给 private subnet 里的机器提供 internet 访问
  • Bastion 用来安全地管理 private subnet 里的机器,也可以称为跳板机

容灾架构

  • 如果你想保证容灾性,至少保证 2 个 public subnets 和 2 个 private subnets,保证它们不在一个可用区
  • 保证 ELB 横跨你的多个可用区
  • 对于 Bastion instance,把它放在 autoscaling group 里,保证至少有 2 个节点工作,用 Route53 来做 fail over
  • NAT instance 就比较麻烦了,每个 public subnet 里需要放一个,各自分配一个 IP 地址,而且你要写一个脚本来做 fail over。如果可能的话,用 NAT gateway 来代替

VPC Flow Logs

用来监控 VPC 里的网络流量。