粗俗地速记一点对“事件驱动”的新理解

最近在给公司写一个高性能代理,成品在不久的将来会以GPL协议开源。关于这个项目我会写一组博客,目前已经有了一个草稿,详细内容有待填充。

这两天一直在思考如何重构代理的工作线程部分,以及需要的话应该如何实现多路复用(multiplexing)。昨晚看了一个Boost.asio的思路,早上又读了读HAProxy是如何抽象epoll的。asio应用起来思路非常清晰,但抽象层次略高于我需要的Proxy;HAProxy的抽象层次合适、思路干净,但对于我的Proxy的应用范围来说又过于复杂。晚上散步继续琢磨如何将两者的优点整理进手头的项目时,突然体会到一点程序模块间分工的“第一原理”。思路从“事件驱动”(Event-Driven)而来,有点类似“单一责任原则”,但又稍微更泛泛一些。粗俗地说:

事儿来了,会干的部分干明白;不会干的部分交给会干的干。

似乎有点显然,我稍微展开一点。

艰苦朴素

所谓代理,要做的事情不过就是读取A的消息,转发给B;读取B的消息,转发给A。一个最简单的代理逻辑如下:

所谓(edge-triggered-)epoll,不过就是当文件提示符(file descriptor)的状态发生变化的时候产生一个事件,并在事件里包含该文件提示符现在的状态,如是否有新消息可以读,是否有空间可以写等等。但这里存在一个小问题——如果epoll产生事件告知程序”这个fd有数据可以读,而现有的read buffer空间不足以读完全部内容时,epoll将不会产生另外一个事件(因为“读”状态一直都是准备就绪的,也就没有状态变化来引发另外一个事件)。所以每次有一端将内容传递给下一段发送后,程序一定要手动调用handle_*_read来检查一个fd是否还有残留的数据,所以这里我们加一个逻辑:

在早期版本中,这段代码(其中一个函数)长这个样子:proxy-a-bit-messy-imo (github.com)

可以看到tunnel的成员函数既需要关心buffer的状态,又需要明白epoll的关键字(EAGAIN/EWOULDBLOCK),并且还要记得在适当的地方重试(最后一行)。主观上这个复杂程度(对于目标应用来讲)算不算高暂且不论,它几乎没有任何抽象,需要理解每一个层面的问题才能正确工作。另外它直接依赖epoll的关键字,使得代码较难重构。

重构

这个重构吸收了一点HAProxy的设计,大概长这个样子:proxy-a-bit-less-messy-imo · GitHub

在写这段代码时我的思路是这样的(如上文的“第一原则”所言):

  • 我真的想不清楚当我收到EPOLLIN和EPOLLOUT(事件中的参数)的时候应该做什么,但是至少我可以对它们进行解释。
    • EPOLLIN是说哪里有一些数据可以读了
    • EPOLLOUT是说哪里有一些空间可以写了
    • 所以我先抽象这个“哪里”出来,按成规起名叫Channel;然后仅仅用事件中的参数更新自己的状态
    • 更新完状态之后做什么?我不知道,但有人应该知道,所以啥都不做
  • 有一位兄台,它不懂、甚至不想知道什么是EPOLLIN和EPOLLOUT。但它知道如何做双向转发,随便起个名叫Pipe。
    • 不管我需要做什么行动,在此之前肯定至少有一个事件抵达,所以不需要额外的事件触发器(需要一点分析,请随意跳过)
      • 如果我需要读,之前一定至少有一个EPOLLIN(没准备好读什么?)
      • 如果我需要写,之前要么有一个EPOLLIN(不读数据写什么?),要么有一个EPOLLOUT(腾出空间写了)
      • 如果我的fd一直没读完(因为此端的读buffer满了),那么此间彼端一定EWOULDBLOCK在写(否则彼端的写buffer应该是空的,可以转移此端读buffer的内容并重置状态),所以此后一定有一个EPOLLOUT
    • 如果A能读,让A读
    • 如果A有数据,B能写,把A的数据给B写
    • 对B也一样
  • 那么让它们俩都实现一个事件处理器(EventHandler)接口
    • handle方法负责“干明白会干的事儿”
    • next方法负责“对于不会干的事儿,找一个会干的人”
    • propagate方法负责把消息传递出去

几个优点:

  1. 主观体验好了一些(less cognitive load)
  2. 可以将系统IO换成poll/select/kqueue甚至io_uring,不会影响上层的代码逻辑(lower change amplification)
  3. 更模块化一些,例如可以在不替换Pipe逻辑的情况下,将Channel更换为支持多路复用的MuxChannel(lower change amplification)

综上,根据《软件设计哲学》(A Philosophy of Software Design (John Ousterhout))所述(详情),这个重构降低了系统的复杂程度,是一个改进。

另外:

  1. 两个gist都不是最终代码,仅供演示参考
  2. 为啥要用epoll这么底层的东西写?主要是想学造轮子(我闲的);其次是我们确实需要一个支持AF_VSOCK的高性能代理——扩展现有的成熟框架(wangle, asio, etc)的话要么难度也不小,要么是框架本身太重。
  3. 似乎已经不是“速记”了啊…写了蛮久,还学了学怎么用Inkscape画图。

AWS Enclave & KMS

AWS Enclave is a type of VM whose host machine cannot access its memory. The host machine can only use certain APIs that’s provided by an enclave via vsock. This secure feature is provided by AWS Nitro System, therefore an enclave has to run on a Nitro-based EC2 instance. Also, an enclave image is built upon a docker image with aws nitro-cli.

Other than secure from host machine, a running enclave instance can generate attestation document that can somehow (I’m planning to dig deep in later posts) be verified by AWS services like its key management service (AWS KMS), so an enclave can use kms:decrypt without exposing any encryption/decryption details to host machine.

Think about the following scenario: you have a web service and wants to distribute a client library, and you need to make sure your web service only communicate to the client you distribute to. Or, only your client can understand the response.

If you haven’t seen the difficulties in this problem, hint: how can you prevent the host intercepting your http (even https) to get the messages and poke the memory of your client to get the secret, then make a fake (probably malicious) client to cheat?

AWS Enclave provides a solution like this:

  • use a secret to encrypt all messages
  • store the secret inside your client, so your client can decrypt the messages
  • distribute your feature inside a enclave image, so your user cannot access the secret from memory
  • decrypt with a service that can check the validity of enclave attestation document
    1. you may decrypt with kms:decrypt and setup key policy to automate attestation
    2. you may implement your own attestation and let the client load the key on start

Next part is my following the code to find corresponding APIs in the sample enclave-kms project. May be too detailed and not so interesting. If you are ready click ‘Page 2’ (WordPress never failed to surprise me).

Understanding Position-Based Dynamics

This post will be my notes on PDB study and will only include points I feel note-worthy. It is by no means a well-rounded tutorial. Btw I learned the principals from this online course: https://www.youtube.com/watch?v=fH3VW9SaQ_c (kudos)

Along with the note I’ll implement the distance constraint to illustrate how it works.

Reminders

  • PBD does not even try to simulate actual physics. It only looks good. All physics ‘references’ (for example, so-called momentum conservation) are attempts to make the scene look real.
  • PDB algorithm is a constraint solver. The algorithm introduced in the course is one-constraint-a-time, Gauss-Seidel method.

Math Review

  • Gauss-Seidel updates proposed values during iteration
  • Jacobi updates values only after each iteration (symmetrical?)

PBD Loop

before mainloop, all vertices should be assigned an initial position x_i, velocity v_i and invert-mass w_i (1/m_i).

  1. for each vert i, update proposed velocity v_i = v_i + t * w_i * external_force_i
  2. damp velocities. a simple way is times 0.99
  3. for each vert i, update proposed position p_i = x_i + t * v_i
  4. for each vert i, detect collection and generate collision constraints x_i -> p_i
  5. solve constraints – it’s numerical solver, so here will be an inner loop
  6. for each vert i, finalize velocity v_i to be actual velocity (p_i – x_i) / t
  7. for each vert i, finalize position x_i to be p_i

Cheatsheet

Distance constraint
C(p_i, p_j) = |p_i, p_j| - d
(look carefully you will notice it is not Hooke's law)

For constraint C(p1, p2), with invert mass of w1, w2 respectively,
Gradient of p1: (p1-p2)/|p1-p2|
Gradient of p2: (p2-p1)/|p2-p1|
Update of p1: -w1/(w1+w2)*(|p1-p2|-d)*(p1-p2)/|p1-p2|
Update of p2: +w2/(w1+w2)*(|p1-p2|-d)*(p1-p2)/|p1-p2|

Code

GitHub Gist: https://gist.github.com/stormouse/90a8d22582ad4e9bc6c91c4a5f80e842

https://editor.p5js.org/stormouse/present/lbMzg3OsY