chengzhycn's blog

KAIST-CS431: Nondeterminisms of Shared-memory Concurrency

2025-08-27

Nondeterminism

thread interleaving

interleaving semantics： 将多线程的指令交替组合成好像是单线程执行一样。

不同线程间的Load/store指令是穿插执行的，导致最终的行为有多种多样的可能。

static COUNTER = AtomicUsize::new(0);
// thread A & B
let c = COUNTER.load();
COUNTER.store(c + 1);

如上示例，两个线程A和B同时对COUNTER进行+1操作，预期结果当然是2。但是由于线程调度的不确定性可能出现如下的执行顺序：

[COUNTER=0] A load, B load, A store, B store [COUNTER=1]

导致结果不符合预期。

解决方案

使用原子的reading & writing，禁止掉这种不符预期的执行顺序。

// thread A & B
let c = COUNTER.fetch_and_add(1);

“Read-modify-write”, e.g. swap, compare-and-swap, fetch-and-add

reordering

同一个线程中的指令会因为硬件和编译器的优化发生指令重排。

DATA = 42;       ||   if FLAG.load() {
FLAG.store(1);   ||       assert(DATA == 42);
                 ||   }

如上图示例，预期是当FLAG.load()为1时，DATA == 42。但是因为指令重排，左边线程中，FLAG.store(1)可能发生在赋值语句前面；右边线程中assert语句也可能发生在if语句前面。

[Read more]

KAIST-CS431: Lock Based API

2025-08-27

#Rust #Concurrency #KAIST-CS431

标准库中的并发API

Rust 标准库中基于锁的 API 主要围绕几个核心原语构建，这些原语提供了不同级别的并发控制和用途。它们都包含在 std::sync 模块中。以下是一些最常用的基于锁的 API：

std::sync::Mutex<T> (互斥锁)
- 用途： 最常见的互斥锁，用于保护共享数据，确保一次只有一个线程可以访问该数据。
- 特点：
  - 当线程尝试获取已被锁定的 Mutex 时，它会阻塞直到锁被释放。
  - 提供内部可变性（&T -> &mut T）通过 RAII (Resource Acquisition Is Initialization) 机制，即 MutexGuard。当 MutexGuard 离开作用域时，锁会自动释放。
  - 是“poisoning”感知的：如果持有锁的线程在锁被释放前发生 panic，Mutex 会被标记为 poisoned。后续尝试获取锁的线程会得到一个 PoisonError，其中包含原始的 MutexGuard，允许它们决定如何处理被中断的数据。
- 何时使用： 当你需要独占访问某个共享资源时，例如全局计数器、数据结构或配置设置。
std::sync::RwLock<T> (读写锁)
- 用途： 允许多个读取者同时访问共享数据，但只允许一个写入者独占访问数据。
- 特点：
  - 读取者（read()）： 允许多个线程并行获取读锁。只要没有写入者持有锁，所有读锁请求都会成功。
  - 写入者（write()）： 只允许一个线程获取写锁。当有写入者持有锁时，所有读锁和写锁请求都会阻塞。
  - 也提供 RAII 机制，通过 RwLockReadGuard 和 RwLockWriteGuard。
  - 同样是“poisoning”感知的。
- 何时使用： 当你的数据被频繁读取但很少写入时，RwLock 可以提供比 Mutex 更好的并发性能。例如，一个缓存系统或一个配置对象。
std::sync::Once (只运行一次)
- 用途： 确保某个代码块（一个初始化函数）在程序生命周期中只被执行一次，即使有多个线程同时尝试触发它。
- 特点：
  - call_once() 方法会执行一个闭包。第一次调用会实际执行闭包，后续的调用会等待第一次调用完成，但不会再次执行闭包。
  - 通常用于惰性初始化全局数据或单例模式。
- 何时使用： 初始化全局静态变量（例如日志系统、配置加载器）或实现单例模式。通常与 lazy_static crate (在稳定版 Rust 中) 或 std::sync::OnceLock (在 1.70+ 版本中，见下文) 结合使用。
std::sync::Barrier (屏障)
- 用途： 用于同步一组线程，确保所有线程都到达某个预定义点后才能继续执行。
- 特点：
  - 通过 wait() 方法实现等待。当调用 wait() 的线程数量达到预设值时，所有等待的线程都会同时被释放。
  - wait() 返回一个 BarrierWaitResult，指示当前线程是否是最后一个到达屏障的。
- 何时使用： 需要协调多个并行任务的执行，例如在某个阶段结束后开始下一阶段，或者在所有子任务完成后进行汇总。

Rust 1.70+ 中引入的更现代的基于锁的 API：

[Read more]

Wasm Internals - Overview

2025-08-26

#Wasm

Wasm 的历史发展

早期（Wasm MVP - 2017）

诞生背景： Wasm 的设计目标是为了替代 asm.js，提供更小、更快、更安全的 Web 二进制格式。
核心模块的初步定义： MVP（Minimum Viable Product）阶段定义了 Wasm Core Module 的基本结构：函数、内存、表、导入、导出、全局变量等。
主要用例： 游戏引擎、音视频编解码、计算密集型任务等。
限制：
- 没有模块化系统： 模块之间没有标准的链接机制，只能通过宿主环境（如 JavaScript）进行协调。
- 缺乏垃圾回收（GC）： 需要手动内存管理或使用语言自带的 GC 机制（如 Emscripten 的 mimalloc）。
- 没有线程： 无法直接利用多核 CPU。
- 没有宿主 API 标准化： 模块与宿主环境的交互方式高度依赖宿主（如浏览器），没有统一的接口定义。
- 没有组件模型： 模块重用和组合非常困难。

中期（MVP 之后 - 持续演进）

Wasm 社区和工作组认识到 MVP 的局限性，并开始着手扩展 Wasm 的能力，这直接影响了 Core Module 的能力：

多值（Multiple Returns & Parameters）： 允许函数返回多个值，接收多个参数，提高表达能力。
引用类型（Reference Types）： 引入了 externref 和 funcref，允许 Wasm 直接引用宿主对象和函数，而无需通过数字 ID 传递，为未来的 GC 和组件模型打下基础。
固定大小的 SIMD（Fixed-width SIMD）： 引入了新的指令集，允许在 Wasm 中进行向量化操作，进一步提升某些计算密集型任务的性能。
线程（Threads）： 引入了共享内存和原子操作，允许 Wasm 模块在多线程环境下运行，极大地提升了并行计算能力。
内存增长和限制（Memory Growth and Limits）： 提供了更灵活的内存管理机制。
Tail Calls（尾调用）： 优化了函数调用的性能。

近期和未来（Wasm Component Model）

这是 Wasm 发展中最重要的方向之一，旨在解决 Core Module 在模块化和互操作性方面的根本性问题：

[Read more]

Wasm Internals: Stack Machine

2025-08-20

#wasm

Wasm 中的“栈机”（Stack Machine），这正是其核心执行模型之一。Wasm 是一种基于栈的虚拟机，这意味着它的所有操作都通过从一个操作数栈中弹出值、执行操作并将结果压回栈中来完成。它没有传统的“寄存器”概念。

什么是栈机？

在计算机科学中，栈机是一种计算模型，其中指令操作数被隐含地从一个被称为“操作数栈”的内存区域中获取，并且结果被隐含地压回这个栈。这种模型与基于寄存器或基于累加器的模型形成对比。

Wasm 栈机的工作原理

Wasm 模块中的函数是由一系列指令组成的。这些指令会操作一个中央的操作数栈。

操作数栈（Operand Stack）：
- 这是 Wasm 执行函数时最核心的数据结构。
- 所有的操作数（如整数、浮点数）和操作结果都临时存储在这个栈上。
- 指令不会像在注册机中那样直接指定操作数的位置（如“将 R1 的值加到 R2”）。相反，它们会假定操作数已经在栈的顶部。
局部变量（Local Variables）：
- 除了操作数栈，每个函数调用还有一个独立的“局部变量”区域。
- 局部变量是命名的存储位置，可以在函数的整个执行过程中被访问和修改。
- 虽然局部变量不是栈的一部分，但有很多指令允许你将局部变量的值压入栈中，或者将栈顶部的值存储到局部变量中。
参数（Parameters）：
- 函数的参数在函数被调用时，会被初始化为局部变量的一部分（通常是前几个局部变量）。
- 它们也可以被认为是函数执行上下文的一部分。
指令的操作：
- 压栈（Push）：很多指令会将值压入栈中。例如：
  - i32.const 42：将整数常量 42 压入栈。
  - local.get <idx>：获取索引为 <idx> 的局部变量的值并压入栈。
- 弹栈（Pop）：大多数操作指令会从栈顶弹出所需数量的操作数。例如：
  - i32.add：弹出栈顶的两个 i32 整数，将它们相加，然后将结果压回栈。
  - if/else/loop 等控制流指令的条件值也会从栈中弹出。
- 复合操作：一些指令可能弹出一个值，执行一些副作用（如内存写入），而不压入任何新值。例如：
  - i32.store：弹出内存地址和要存储的值，将值写入内存。

栈机模型的优势与特点

紧凑性（Compactness）：
- 指令更短，因为它们不需要编码操作数的位置。例如，一个加法操作，在寄存器机中可能需要指定两个源寄存器和一个目标寄存器；在栈机中，它只是一个简单的 add 指令。
- 这有助于生成更小的二进制代码，对于 Web 环境中的快速下载和解析非常有利。
简化编译器后端（Simplified Compiler Backends）：
- IR（中间表示）到指令的映射通常更直接。许多高级语言的语义本身就可以很容易地映射到栈操作。
- 这使得将 C/C++/Rust 等语言编译到 Wasm 变得相对容易。
易于验证（Easy to Validate）：
- Wasm 在加载时会进行严格的类型检查和结构验证。栈机模型使得验证其类型安全变得相对容易。例如，当检查 i32.add 指令时，验证器只需确保栈顶有两个 i32 类型的值。
- 这对于沙盒环境中的安全性至关重要。
独立于目标架构（Architecture-Independent）：

[Read more]

Kubernetes CSI 简介

2025-06-24

#kubernetes #csi

K8s CSI 是 Kubernetes 中非常重要的一个组件，它解决了存储与计算分离的复杂性，并为容器化应用提供了持久化存储的能力。

1. 基本概念

CSI (Container Storage Interface) 译为 容器存储接口。它是由 Kubernetes 社区与存储厂商共同制定的一套标准接口规范。

在 CSI 出现之前，Kubernetes 存储插件的开发和管理存在以下痛点：

紧耦合问题： Kubernetes 内部集成了大量的存储驱动（In-tree 存储插件），例如 AWS EBS、GCE PD、Azure Disk、Ceph RBD 等。这意味着每当存储厂商需要支持 Kubernetes 时，他们都必须将其存储驱动代码提交到 Kubernetes 的核心代码库中。这种方式导致了：
- Kubernetes 代码库臃肿： 集成了大量存储逻辑，增加了核心代码的复杂性和维护难度。
- 发布周期长： 存储驱动的更新需要跟随 Kubernetes 的发布周期，新功能和 bug 修复不能及时推送到用户。
- 存储厂商开发受限： 每次更新都需要与 Kubernetes 社区协调，开发和测试流程繁琐。
兼容性问题： 不同存储厂商的存储系统差异巨大，缺乏统一的接口规范，导致存储系统与 Kubernetes 之间的集成困难。

CSI 的目标就是解决这些问题，实现存储系统与 Kubernetes 的解耦。 它定义了一套通用的接口，允许任何存储厂商开发自己的 CSI 驱动，然后通过这些驱动来与 Kubernetes 进行交互，从而为容器提供存储服务。

1.1. 资源定义

1.1.1. Volumes

Volumes 是 Kubernetes 中 Pod 通过文件系统访问和共享数据的抽象。它主要提供了如下功能：

通过 ConfigMap 或者 Secret 共享配置；
跨容器、跨 Pod 甚至跨 Node 共享数据；
数据持久化。在 Pod 销毁之后仍能继续访问数据。对于 Pod 来说，Volumes 通过 .spec.volumes 提供给 Pod，容器通过 .spec.containers[*].volumeMounts 来将指定 Volumes 挂载到指定目录。

1.1.2. Persistent Volumes 和 Persistent Volumes Claim

PV 和 PVC 提供了两套 API 将存储的提供和消费分离。

[Read more]

< [Newer posts] :: [Older posts] >