Making *MaNy* threads
on RubyKoichi Sasada
Cookpad Inc.
ko1@cookpad.com
RubyKaigi 20221

Today’s talk

MaNy Project❗ The name “MaNy” is invented by @nobu• Goal: Make MANY threads (> 100K)• Support massive network concurrent connections• HTTP/2, WebSocket, GRPC, …
• Like Go, Erlang, …

• Lightweight Ractor creation• Many actors like Erlang• Technique: M:N threads• M native threads (M is about nproc) and N (> 100K) Ruby threads• Current: 1:1 model (N Ruby threads on N native threads)• Great reference to Go's implementation• Two-level scheduling• Ractor level M:N scheduling• Thread level 1:N scheduling2

About Koichi Sasada🏇• Ruby interpreter developer employed by
Cookpad Inc. (2017~) with @mame• YARV (Ruby 1.9~)• Generational/Incremental GC (Ruby 2.1~)• Ractor (Ruby 3.0~)• debug.gem (Ruby 3.1~)•…

• Ruby Association Director (2012~)• 2022 Call for Grant Proposals (~ Oct 3, 2022)3

Motivation
Highly concurrent language Ruby
• Support to make a highly concurrent applications by*scripting* in Ruby
• Make MANY threads (> 100K)• Support massive network concurrent connections• HTTP/2, WebSocket, GRPC, …
• Like Go, Erlang, …

•Lightweight Ractors• Actor programming with many actors like Erlang• To encourage casual concurrent / parallel programming with
Ractor on Ruby
4📗 Study in computer science/OS area
📌NT: Native thread or kernel thread

Background
Thread system implementation techniques
How to handle N=3 Ruby threads (RTs) on 2 CPU cores?

1:N (Ruby ~1.8)

M:N(M = 2)

1:1 (Ruby 1.9~)

User
RT

RT

OS/Lib

NT

H/W

CPU
Core

RT

CPU
Core

RT

RT

RT

NT

NT

NT

NT

NT

CPU
Core

CPU
Core

CPU
Core

CPU
Core

RT

RT

RT

🏇

1:N model
Green threads, user level threads, …
• Only 1 native thread (NT) run multiple threads• Ruby ~1.8
• 😀 Completely controllable• 😀 Lightweight (in theory)• 😨 Can not run in parallel• 😨 Difficult to handle blocking operations
T1

T2

time
T3

T1

NT1
NT2
❗ Only NT1 is used!
6🏇

1:1 model
Most simplified technique• 1 native thread per Ruby thread• Ruby 1.9~ (has GVL limitation. This page eliminates it)• 😀 Simple, easy to handle blocking operations (system does)• 😀 Can run in parallel on multi-core systems• 😨 More overhead (compare with 1:N, in theory)• 😨 Less controllable (only native thread system schedules)
T1
NT1
Create T2

NT2

T2
Create T3

NT3

T3
🚫

7

🏇

M:N threads
Best performance (in theory) and complicated• Mixed with pros. (and cons.) of 1:N and 1:1• 😀 Controllable (in theory)• 😀 Lightweight (in theory)• 😀 Can run in parallel• 😨 Difficult to handle blocking operations• 😨 Complex
T1{Create T3}

NT1

T3

{Time slice}
Create T2
T1

T2
NT2
sample: M = 2 (only NT1 and NT2)

{I/O blocking}❗T1 runs on NT1 and NT2

8

M:N threads
Existing implementations• Operating systems• Solaris, FreeBSD, … (now they use 1:1 threads)• Language native• Go’s goroutines• Erlang’s (Elixir’s) processes• Extensions• Java’s virtual threads (JEP 425: Virtual Threads)• Rust’s tokio, …

9

Ruby’s case• Threads run in concurrently, not in parallel• Concurrent❗ GVL had stood for “Global VM
Lock” because it is only 1 lockper VM (only 1 thread has GVL
can run on a Ruby VM).
However, GVLs are available per
a ractor. In this talk we continue
to use the word GVL and we cansay Great Valuable Lock oranything you like.

• Context switch by time slice (100ms)• Switch on blocking operations like blocking I/O• Not in parallel: A giant lock (GVL) keeps running 1 thread on a Ractor.

• Ractors can run in parallel• A Ractor has at least 1 thread• Threads on different ractors can run in parallel• 1:1 threads can not make 100K threads/ractors because ofsome limitations• Creation overhead and OS resource limitations• M:N technique is used by recent “concurrent” languages and how about
on Ruby like Go language without changing anything …?

MaNy projectIntroduce M:N scheduler into Ruby

11

Two-level scheduling• Ractor level scheduling• Run ractors on M native threads (M:N model)• Global ready queue (GRQ) manages runnable Ractors• Thread level scheduling• Run threads on 1 native thread (1:N model)• Thread ready queue (TRQ) manages runnable Ruby threads in a Ractor• Use multiple native threads to handle unmanaged blocking ops.
• Support 1:1 model mode for compatibility• Misc• Both FIFO scheduler (no priority queue(s))• Re-introduce a timer thread to manage context switch (Go’s sysmon)
12

M:N Ractor level scheduling (M=2)
GRQ: []
R1

GRQ: [R1]R3

NT1
R1 creates R3
GRQ: [R3]

Switch to R3 by time slice

R1 creates R2 and run on NT2
GRQ: []
R2

Switch to R1 GRQ: []R1

NT2{I/O blocking}→ No ready threads on R2

📌 Ractor R1, R2, R3 have 1 thread, respectively.
💪 R1 runs on NT1 and NT2 (M:N scheduler)

1:N Thread level scheduling in a Ractor
NT1

TRQ: []

TRQ: [RT3, RT1]

TRQ: [RT1, RT2]

TRQ: [RT2, RT3]

RT1

RT2

RT3

RT1

time slice
notification

time slice
notification

time slice
notification

RT1 creates RT2
TRQ[RT2]
RT1 creates RT3
TRQ[RT2, RT3]

Timer Thread

100ms

14

Handle blocking operations• We need to handle “Blocking operations” for user level scheduling,otherwise all threads stops• Blocking operations• Managed blocking operations• I/O (most of read/write)• manage by I/O multiplexing API (select, poll, epoll, kqueue, IOCP, io_uring, …)• Sleeping• Synchronization (Mutex, Queue, …)• Unmanaged blocking operations• All other blocking operations not listed above, written in C
• Huge number calculation like Bignum#*• DNS lookup• I/O (can not detect block-able or not)• open on FIFO, close on NFS, …
• …
15

Handle blocking operations
on existing Ruby versions🏇• Ruby ~1.8 on 1:N model• Only handle managed blocking operations.
• Can not handle unmanaged blocking operations… (stop all threads).
• ex) system’s DNS resolver can stop all threads, but resolve.rb does not stop.

• 😨 Difficult to handle blocking operations (only the interpreter can do it)• Ruby 1.9~ on 1:1 model (2007~, 15 years)• Can handle all blocking operations by releasing GVL• “rb_thread_call_without_gvl(func)” API ← 💛 Easy to use• Other threads can run.

• Not handled blocking operations can stop all threads, but after 15 years,
most of critical operations are handled with the API 💚
16Handle blocking operations
on MaNy• Managed blocking operations• Blocking I/O, sleep, synchronizations are managed by a scheduler• Timer thread observe I/O events and schedule• epoll, kqueue, IOCP (now only epoll is supported)• Unmanaged blocking operations• Run a blocking operations on a native threads marked by dedicated• DNT (Dedicated native thread) pinned down to a Ruby thread🏇• Add a new native thread to run other threads if blocking operations
consume a time
• Timer thread observes native threads count for scheduling17

Handle managed blocking operations

🏇{blocking read}
TRQ: [RT2, RT3]

RT1

TRQ: [RT2]

TRQ: [RT2, RT3]

RT3

RT1

NT1

(1) Register RT1 iswaiting for IO

Continue with IO result

RT2

RT2

TRQ: [RT3]

TRQ: [RT3, RT1]

(2) Switch to RT2

Timer Threadtime slice
notification

time slice
notification

time slice
notification{IO is ready}Start status:
Ruby threads RT1, RT2, RT3 are there
TRQ (Thread Ready Queue) is [RT2, RT2]

(3) Add RT1 to ready queue→ TRQ: [RT2, RT1]

❓ RT1 can be scheduled early18

Handle unmanaged blocking operations (M=1)
TRQ: [RT2, RT3]

{finish blocking op}

RT1 {start blocking op}
NT1

mark NT1
dedicated (DNT)NT2

🚫

Remove NT1 because
NT2 is already used
(M=1 < NT num=2)

TRQ: [RT3]

TRQ: [RT2]

TRQ: [RT1, RT3]

TRQ: [R

RT2

RT3

RT2

RT1

Make RT1 ready
TRQ: [RT2, RT1]

Add new NT2 and resumes RT2

Timer Thread

Detect no NT for thread scheduling
Start status:
Ruby threads RT1, RT2, RT3 are there
TRQ (Thread Ready Queue) is [RT2, RT2]

❗ There are many DNT (≦RT num）
19

Compatibility issue• C-extensions can rely on 1:1 model• Doesn’t work if it relies on NT’s Thread-Local-Storage (TLS)• ... other cases? depends on native thread ID?

→ Compatibility mode
• Bind dedicated native thread (DNT) → Force 1:1 model mode
• Go’s runtime.LockOSThread()• ex) Thread.bind_dedicated_native_thread = true

• Default?
• Bind DNT if user specifies (Go’s approach, because Go hadn’t compat. issue)• Bind DNT only with the main thread (← Current choice)• Bind DNT with threads on the main ractor (safer choice)• Support scheduling with normal NT and DNT (complex)
20

Bound threads for compatibility
1:1 model🏇

Thread.bind_dedicated_native_thread = true # not fixed name

RT1
NT1
Create RT2
NT2

RT2
Create RT3

NT3

RT3
🚫

21

21

Advantages of M:N• Lightweight threading (and ractor system)• Remove impedance mismatch between NT scheduler and Ruby’sscheduler especially with GVL• No synchronization is needed to control within a Ractor• (Slightly) lightweight creation• pthread_create() is fantastic fast on recent systems, so not big impact

22

Disadvantage of M:N• Compatibility issue (already discussed)• Complication• Overhead• (Slightly) overhead for I/O by checking blockable operation or not• (Slightly) introducing a timer native thread for management• Change visibility outside from Ruby process• Metrics tools like ps, top, …
• gdb (debugger)• hard to debug native threads without not running RTs• rb_bug() prints huge lines of memory maps (thread count * 2)23

Compare with fiber scheduler (Ruby 3.0~)• Similar motivation (to support huge number of connections)• Good for fiber scheduler• Ruby user can write a scheduler• Can mark best score with the well-tuned scheduler for the application• Non-MRI implementations can use the scheduler written in Ruby

• Good for MaNy Project• Ruby users don’t need to care about a scheduler• Can mark better score without changing threaded apps
• (Hopefully) no hungs on unmanaged blocking operations (like current threads)• Timeslice is provided (auto-context switch)• Integration with Ractor system → parallel computation
24

Other interesting topics🏇• O(n…) traps• Deadlock detection code can iterate all threads• Works well for small number of threads, but superslow for many threads (O(nm))• Thread.list uses alloca(thead_num) and it causes stack overflow• rb_notify_fd_close() iterates all waiting fds (O(n^2))• …

• Implementation• Two level scheduling with dedicated native threads (1:1)• Signal handling• Context management (stack management, context switching, …)• Time slice provider• Debug techniques (logging system)• Scheduler functions (naming)• Others• Mysterious OS limitations for native threads• top (linux /proc) sometimes shows strange values• …

25Evaluation

26

Evaluations environment🏇• Machine• Intel(R) Core(TM) i7-6700 CPU, 4 cores, 8 HW threads, 64GB mem• Linux 5.4.0-125-generic (Ubuntu 20.04)• ulimit -n `ulimit -Hn` (to increase open files for sockets)• vm.max_map_count = 2,000,000 (a thread consumes 2 maps)• Base ruby: ruby 3.2.0dev (2022-07-26T07:03:44Z master 9a8f6e392f)[x86_64-linux]• RUBY_THREAD_VM_STACK_SIZE=32768 (32KB, default: 1MB) because master
speed decreases in proportion to the VM stack size (will be solved)• Client machine• AMD Ryzen 9 5900HX , 8 cores, 16 HW threads, 16GB mem• Code• MaNy branch: https://github.com/ko1/ruby/tree/many• Examples: https://github.com/ko1/many_examples
27

Thread creation# make x threads and stop them
# restart them# join all and GC.start

MaNy Ruby

master (~170K threads)
50

Time (sec)40
30
Many/Thread Total

20

Master/Thread Total

100
0200,000

400,000

600,000

800,000

1,000,000

1,200,000

Concurrent threads
28

# GC.disable# make x threads and stop them
# restart them# join all and GC.startThread creation
GC overhead
MaNy Ruby (create)

MaNy Ruby/GC.disable (create)50

1M creat. → 40 sec
1 creat. → 40 usec

Time (sec)40

1M creat. → 7 sec
1 creat. → 7 usec

30
20

join & GC.start

10

0
0

200,000

400,000

600,000

800,000

1,000,000

1,200,000

Concurrent threads
Many/Thread create

Many/Thread join/GC

Many/Thread/GC.disablee create

Many/Thread/GC.disablee join/GC
29

🏇

Ractor creation❗

Time (sec)

1500
1000
500

0
0

10,00020,00030,00040,00050,00060,00070,00080,000Concurrent threads/ractors
Thread/MaNy Total

Master/Thread Total

Ractor/MaNy Total

Ractor/MaNy/GC.disable Total
30

🏇

Ractor creation❗ Synchronization issue…?
60

Time (sec)

50

😨

40
30
20
10
0
0

10,00020,00030,00040,00050,00060,00070,00080,000Concurrent threads/ractors

Thread/MaNy Total

Master/Thread Total

Ractor/MaNy/GC.disable Total
31

Ring example• Prepare n threads ordered sequentially• Pass a message to the next Ruby thread with Queue
RT0
msg
RT1

RTn

… many threads …

RT2
32

Ring example❗ Kernel/Ruby scheduler’s impedance mismatch(GVL handling)
Loop on MaNy

Loop on master
250

Time (sec)

200
150
100
50
0
0

200,000

400,000

600,000

800,000

1,000,000

1,200,000

Concurrent threadsloop(med)loop(med)/master(med: median value of 3 trials)

33

🏇

Ring example

Loop on MaNy

1.2
1M pass. → 1 sec
1 pass. → 1 usec

Time (sec)

1
0.8
0.6
0.4
0.2
0
0

200,000

400,000

600,000

800,000

1,000,000

1,200,000

Concurrent threadsloop(med)(med: median value of 3 trials)

34

Ring example
Compare with Go/Loop time🏇
Loop on MaNy

1.2
1M pass. → 1 sec
1 pass. → 1 usec

1
0.8

The overhead is from interaction with the timer thread…?

0.6

Loop on Go

0.4

1M pass. → 0.35 sec
1 pass. → 0.35 usec

0.2

0
0

200,000

400,000

600,000

loop(med)

800,000

1,000,000

1,200,000loop(med)/go
Go 1.19
35

50

40

30

1,000
34,00067,000100,000
133,000
166,000
199,000
232,000
265,000
298,000
331,000
364,000
397,000
430,000
463,000
496,000
529,000
562,000
595,000
628,000
661,000
694,000
727,000
760,000
793,000
826,000
859,000
892,000
925,000
958,000
991,000

Ring example
Compare with Go/Creation time

10

setup/many🏇The overhead may be from• GC
• The first time memory setup• System calls (mmap, mprotect)• Physical page allocation by OS

20

❓❓

0

setup/go36

Chat server example“hello”
client1

Server“hello”
client2“hello”• A client sends a message, andthe server sends a received
message to all connected clients.
• A blocked client should not block
other clients• The server and clients areconnected with TCP/IP

client3“hello”

37Chat server example: Queue version

🏇client1
ServerR1

W1

client2
W2

R2

W3

R3

client3🔑Array of writers

Readers and writers are connected with
Queues (green lines)• Prepare a reader thread and a writer thread for eachconnection. → 2*n threads for n connections• Readers and writers should be separated because
38
writing to the socket can block.

Chat server example: Broker version

🏇client1
ServerR1

W1

client2
W2

W3

BrokerR2

R3

Readers and writers are connected with
Queues (green lines)

client3• Add a broker thread• Readers send message to the broker, and it
broadcast to writers. No Mutex🔑!

39

Chat server example
RTT x 100

# from clients
100.times{
socks[n/2] << “msg”
socks.each{|s| s.gets} }200

MasterTime (sec)

150

100

MaNy
50

IO.select without
any threads

0
0

10,00020,00030,00040,00050,00060,000Concurrent connections
Many/Broker 100*(post+get*n)Many/Queue 100*(post+get*n)

Master/broker 100*(post+get*n)

Master/queue 100*(post+get*n)

Master/select 100*(post+get*n)40Chat server example
Connection time🏇

IO.select without
any threads200

poll(2)’s overhead

Time (sec)

150

100

50

0
0

10,00020,00030,00040,00050,00060,000Concurrent connections
Many/Broker Create

Many/Queue Create

Master/broker Create

Master/queue Create

Master/select Create

41

Future work
• MaNy project• Complete implementations• Ractor support• Increase supported platforms (Mac, Windows, …. Now Linux only)• Merge into master (3.2…?)• Ractor local GC (working with a GSoC student)• Feasible debugger for massive concurrent application→ Make Ruby as a casual concurrent language
42

Acknowledgements• Matz, mame and other reviewers of our design• Yuki Torii helps me a lot to attend RubyKaigi 202243

Today’s talk

MaNy Project• Goal: Make MANY threads (> 100K)• Support massive network concurrent connections• HTTP/2, WebSocket, GRPC, …
• Like Go, Erlang, …

• Lightweight Ractor creation• Many actors like Erlang• Technique: M:N threads• M native threads (M is about nproc) and N (> 100K) Ruby threads• Current: 1:1 model (N Ruby threads on N native threads)• Great reference to Go's implementation• Two-level scheduling• Ractor level M:N scheduling• Thread level 1:N scheduling44