我们先从问题出发,看看 Erlang 为了解决并发问题做了哪些努力。
任务可以先简单的划分为 CPU 和 IO 两种操作,相比之下,IO 操作速度非常慢。如果在进行 IO 操作的同时, CPU 忙等,效率会非常低。
系统为了解决这个问题,提供了线程。在进行 IO 操作的时候,线程会被挂起,直到 I/O 操作成功,才有可能被唤醒。
由于并发要做到在逻辑上同时执行,那么一个线程执行一段时间,就需要让其他线程执行。所以系统线程实现了抢占式调度。
系统的调度是指令级的,比如 A = A + 1
需要多个指令,如果两个线程同时这行 A = A + 1
,由于读取值和存入值的顺序不同,会造成 A 的值不同。也就是所说的线程安全。
我们看到,系统线程解决了两个问题,傻等 IO 和线程间基于时间的公平调度,但带来了线程安全问题。
JavaScript 使用 callback 避免了 CPU 的忙等。并发能力也不错。实质上是,在进行 IO 操作的时候,只发起 IO 操作的 request,而不等 IO 操作结束,直接返回,当 IO 操作结束的时候,再执行对应的 callback。
而 callback 一旦嵌套,就很难维护。可以在语言层面解决这个问题,比如 ActionCable 使用单独的线程同时监听多个 file descriptor(event loop),有 IO ready 的时候执行相应的 callback。并把这些细节完全的隐藏在框架之下。而 rust 的 Tokio 在提供全局的 event loop 同时,提供了 reactor 模型来避免 callback 嵌套的问题。
callback 是语言级别的,保证了操作的原子性,也就不会有线程安全之类的问题。
我们再来看公平调度这个问题,callback 模式,可以抽象为,CPU 计算,异步 I/O 请求,I/O ready 后执行 callback。
我们假设这样一个场景, 1 秒有 1000 个请求打到服务器,刚好第一个请求需要计算 1s,而 callback 模式需要先完成这 1s 的运算, 才能让 CPU 处理其他请求,也就是说,其他请求的延迟至少有 1s。这样显然是不公平的。更好的做法是,第一个请求执行一小段时间,让 CPU 去处理其他请求。
所以 callback 模式解决 IO 忙等,避免了并发安全,但没有解决公平调度。
首先 Erlang 使用 Reactor 模型,避免了线程安全之类的问题。使用单独的的线程调度 IO 任务,解决了 IO 忙等。
公平调度本质上是执行任务一段时间,再执行另一个任务的能力。如果像系统一样按照时间分片来调度话,同样会破坏操作的原子性。所以 Erlang 使用 reduction 来做调度。
简单来说,可以把 reduction 理解为一次 Erlang 方法的执行。Erlang 给每个 process 分配 4000(当前版本,以前是 2000,这块就不细说)个 reductions,如果 4000 个 reductions 执行完了,就执行另外一个 process。
使用方法作为调度的好处是,保证了原子性,而函数的调用次数也可以较好的反应执行时间。Erlang 给 IO 请求和 bif、nif 分配了不同的 reduction,这样就可以更好的保证公平性。
Erlang 的 reduction 实际计算比较复杂,比如 ets:lookup 是 ets table 里 item 数量 * 2,也就是执行完一次 ets:lookup,必然会有一次调度。
%% 1k
Foo = fun() ->
receive
start ->
ets:lookup(test_1k,1),
receive
stop ->
stop
end
end
end.
ets:new(test_1k, [named_table, bag, public, {read_concurrency, true}]).
lists:map(fun(I) -> ets:insert(test_1k, {I, I}) end, lists:seq(1, 1000)).
Pid = spawn(Foo).
process_info(Pid).
;; 2000 reductions
Pid ! start.
process_info(Pid).
;; 4000 reductions
目前,CPU 大多是多个核心,也就是同一时间,在物理上可以执行多个指令。系统线程可以利用多核。而 JavaScript 是单线程,只有靠多个进程来利用多核资源。
假设 CPU 是双核的,物理核数是 2,我们起两个 JavaScript 节点,这样看起来就可以很好的利用多核 CPU 资源。
但如果请求是随机的,就有可能现两个节点中,一个有任务,另一个节点空闲的情况。当然在两个节点前可以加个 load balance 来缓解,但依然没有办法完全解决。
Erlang 使用多个 scheduler,每个 scheduler 在一个系统 thread 里运行。scheduler 的 thread 会和 CPU 动态绑定(两个 scheduler 在一个 cpu 就无法利用多核了),
如果一个 scheduler 空了的话,就会去偷(恩,源代码中写的就是偷)其他 scheduler 的 process。每隔一定的 reduction,还会做一次迁移。
如果一个 scheduler 闲太久了,就会让它去睡觉,可以省资源,也同时避免了无用的调度。去睡觉前还会 spin 一段时间,等待别人给他任务,因为唤醒一个 scheduler 比较耗时。
调度、并发安全、Reactor 模型仅仅是 Erlang 一部分,Erlang 的 OTP 为并发这个问题提供了一套完善的解决方案。
比如知乎在使用 go 重写的时候,发现 goroutine 没有父子 goroutine 的概念,很坑。而 Erlang 有 supervisor、link、monitor,做这件事非常自然。
再如 let it crash 哲学,如果 process 出问题了,直接让他死掉,再重启 process,这样就解决了软件工程 90% 的问题。
而这些只是 Erlang 的冰山一角。Erlang 不仅仅提供了并发能力,并且提供了一套完善的并发机制。
唠叨了这么多,有点跑题,下面来看下源码。
这块写出来后,感觉这块有点枯燥。。。
一种是 dirty 的,比如 nif、I/O 操作,这些都不会再执行中 yield,会阻塞 scheduler,所以 Erlang 使用单独的 thread 处理这些 process。 一种是 normal,就是由 Erlang 代码实现的,这种可以随时在执行完一个方法后 yield,不会阻塞 scheduler。
Erlang 会分别创建两种线程来处理相应的任务。
normal 的 thread 数目,默认是由 logical processor(cpu core or hardware thread) 决定的,Erlang 实现了 Erlang process,所以系统线程数目大于 logical processor 的数目,一般并不会带来更好的性能。
Erlang 根据需要,创建完系统线程后,erts_schedule 在 process_main 和 erts_dirty_process_main 里被调用。也就是说,erts_schedule 会同时处理 dirty 和 normal 两种调度。
erts_schedule 大体分为三个部分:
internal_sched_out_proc 会处理 process 调出后的操作。
check_activities_to_run,检查是否有需要执行的活动,包括 reblance scheduler,检查 timer 等。
pick_next_process 则是选择一个合适的 process 来执行。
internal_sched_out_proc 首先计算、设置 reductions,之后会调用 schedule_out_process。
在 schedule_out_process 会选择需要将 process 移入对应的 run queue,如果是 dirty 的,就会被移入 diry scheduler 的 run queue 里,如果不是 dirty 的话,会先检查是否需要 migration,之后再移入。
而在 pick_next_process 里,发现选出的 process 是 dirty 相关的话,会直接跳到 internal_sched_out_proc 这个 tag,
也就是说,一个 process 如果是 dirty 的话,会从 normal scheduler migrate 到 dirty scheduler。一个 normal process 执行完之后,可能会被 migrate 到其他 normal scheduler 里。
执行完 internal_sched_out_proc 后会执行 check_activities_to_run,check_activities_to_run 大体包括:
首先是检查 timer,esdp->last_monotonic_time >= erts_next_timeout_time(esdp->next_tmo_ref)
,
scheduler 的最后一次的时间,如果大于下次 timeout 的时间,则 erts_bump_timers
,由此可以看出 Erlang timeout 是软实时的,是由 esdp(ErtsSchedulerData) 记录一个 timer 的引用,每次调用 erts_schedule 才会被处理。
所谓的软实时是指,是指如果设置 10 秒的 timeout,这个 timeout 不会在 10 秒之前被触发,但无法保证一定在 10s 执行。
check_balance 的触发条件是,check_balance_reds < 0,而 check_balance_reds 的定义是
#define ERTS_RUNQ_CHECK_BALANCE_REDS_PER_SCHED (2000*CONTEXT_REDS)
#define ERTS_RUNQ_CALL_CHECK_BALANCE_REDS \
(ERTS_RUNQ_CHECK_BALANCE_REDS_PER_SCHED/2)
CONTEXT_REDS 是 4000,也就是大约 2000 * 2000 个 reductions 之后会执行一次 check_balance。
在进入 check_balance 的时候,发现有 scheduler 在执行 check_balance,则将自身 check_balance_reds 设置为 INT_MAX,来避免同时执行。
check_balance 根据之前的情况,预测一个 scheduler 的执行能力,设置迁移路径。如果一个 scheduler 负载过低,则将其设置为 inactive。
inactive 的 scheduler run queue 会被清空,并进入 sleep 状态,而 Erlang node 负载高的时候,再被再次唤醒。
check_balance 之后,会根据路径做 immigrate。
对于 dirty scheduler,且没有 process 可执行,会被挂起。
erlang 默认会根据 logical processors(logical processors 指的是 CPU 核数或者硬件线程)数目来创建 scheduler thread(系统线程)。这样就可以利用多核的能力。
所以当 thread 被分配给错误的 CPU core 的时候,使用 check_cpu_bind 来纠正这种情况。
auxiliary(辅助) work,在这里会处理一些诸如 cancel_timer 的工作。
在 check_balance 里,会把一个 scheduler 设置为 inactive,empty_runq 用来清空 run queue。
如果没有任务执行时 (! runq_got_work_to_execute),会调用 try_steal_task。
try_steal_task 先给自己上了一把锁,防止别人这个时候偷自己的,然后先偷 inactive run queue,之后偷 active queue(偷的方法名很也有趣 check_possible_steal_victim,可以翻译成找个倒霉蛋)。
ERTS_LC_CHK_RUNQ_LOCK(rq, rq_locked);
get_no_runqs(&active_rqs, &blnc_rqs);
偷的时候,就是从其他 run queue 拿 process 的过程。
根据 run queue 的当前的最高 (ErtsRunQueue 有多个 priority queue) 的优先级,挑选一个存在的、且不在执行中的 process,如果不存在这样的 process,则再次跳到 pick_next_process 这个 tag。
如果当前 process 是 dirty 的,则 unlock 这个 process(erts_proc_unlock(p, ERTS_PROC_LOCK_STATUS)),并跳转到 sched_out_proc, 之后跳到 internal_sched_out_proc,就如之前所说,dirty process 会被丢到 dirty scheduler 里。
如果不是 dirty 的,除了会计算 reds 之外,还会做一些 gc 之类的操作。
可以说 Erlang 提供了优秀的并发能力和一套完善的并发机制。