idea's blog

Latch(Binary Semaphore) 不同于信号量(Counting Semaphore), 也不同于条件变量, 它是一种合并信号成一个标记的通信方式, 可用于实现 Batch 操作. 例如, 两个线程围绕一个标记, 一个设置(生产者), 一个复位(消费者). 如果标记已设置, 则消费者立即复位然后返回. 如果标记未设置, 则消费者等待标记被设置.

在生产者消费者编程模式中, 生产者产生任务, 任务被加入队列中, 同时通过 Latch 告知消费者. 使用 Latch 的话, 可能多个任务产生之后, 消费者才会获知消息, 于是, 便可以将多个任务合并处理, 也即所谓的 Batch(批量)操作. 同时, 只要有任务, 标记就一定会被设置, 消费者不会漏掉任务.

如果使用条件变量, 那么消费者可能漏消息. 因为, 如果消费者在忙于处理任务时, 生产者的通知将会被丢弃.

如果使用信号量, 那么消费者进行 Batch 操作之后, 后续的堆积的信号会导致空操作, 因为任务已经处理完了, 但信号还在.

Continue reading »

在单机编程时代, 每一项数据只有唯一的一份, 对数据的修改也是 in-place 的. 但是, 在并发编程领域, 包括分布式系统, 数据多版本(Multi Version, Versioning)是核心.

我们先从单机编程的内存操作出发. 对于内存的操作, 都是原地(in-place)更新的. 对象和内存空间强绑定, 当更新对象时, 是将对象的内存空间擦除然后用新数据写覆盖. 到了多线程编程时代, 就引入了锁机制, 因为擦除和写操作过程不是原子性的, 可能擦除到一半时, 就被其它线程读取了, 因此要加锁.

单机的硬盘操作, 基本也是借鉴内存操作, 也是对象和硬盘空间强绑定. 至少大部分程序员的思想是这样的, 这样比较直观. 跟内存操作一样, in-place 也遇到了操作的原子性挑战. 内存本来就是易失的(掉电后丢失), 但硬盘不一样, 数据需要持久化(掉电不丢失), 即使靠加锁解决了访问原子性问题, 但解决不了数据丢失问题. 所以, 硬盘操作是最先引入多版本技术的. 当需要修改某个对象时, 在另外的地方保存对象的新数据, 然后在另外的地方原子性地修改指向新数据的"指针". 事实上, 指针的修改也是多版本的, 不是 in-place 的, 后面会细说.
Continue reading »

有些 C++ 程序员, 特别是只写 C++ 没有写过 Python/PHP 等慢语言的程序员, 容易对性能有心智负担, 就像着了魔一样, 每写 3 行代码必有一行代码因为性能考虑而优化使得代码变形(复杂而晦涩).

我认为, 任何系统级的代码, 都不应该刻意地在代码层面"形式化"地在表面功夫上面考虑性能优化, 而是应该把心思放到如何让代码更简洁和清晰上面. 如果逻辑清晰度能提高 10%, 代码行数能减少 10%, 即使单个模块性能下降 20%, 也应该做这笔交易. 理论上, 即使单个模块性能下降 20%, 整个系统的性能下降也许只有 1%(阿姆达尔定律). 根据经验, 如果代码行数减少逻辑清晰度增加, 带来的往往是性能提升而不是下降.

如果一个 C++ 写的系统中用到了超过 3 处 std::move, 就证明程序员有心智负担了. std::move 并不是性能优化的手段, 而是检测系统是否变臭的标记. 为了不让检测方法失效, 也就是为了避免程序员逃避检测, std::move 外面裹了一层糖衣, 吸引那些着了魔的程序员主动来接受检测主动暴露. 这个符号证明程序员花了大量的精力去追求表面功夫, 而不是把心思放在如何让系统更简洁和清晰上面.

lock free 也是检测一个 C++ 系统是否发臭的标记, 如果你能在代码中感受到程序员在极力避免使用锁, 也就是明明可以用一行锁解决的事, 它偏偏封装了 5 个辅助类, 引入了 3 个概念, 那么, 显然你也闻到了发臭的味道.

为什么要强调 C++ 呢? 因为一个 C++ 程序员诞生的时候, 他有极高的机率沾染上"过度优化"的毛病, 这个毛病一直伴随许多 C++ 程序员的职业生命周期. 这是一个慢性病, 影响程序员的个人职业发展, 毁坏程序员参与开发的系统.

相关文章: C++ bug free 原则

## 性能优化

* 过早优化是万恶之源
* 严禁在编程语言的语法层面进行性能优化, 只在逻辑层面和功能结构上进行优化

## 内存拷贝

* 不要害怕内存拷贝
* 如果想避免内存拷贝, 只能显式地用指针(引用)传递来共享内存, 严禁使用 std::move()
* 如果指针传递的路径太长, 或者指针的使用者职责不单一, 那就用内存拷贝

## 接口设计

* 不要为了性能考虑而设计 batch 接口, 所有函数都以一次处理一个对象为原则

## 并发和锁

* 串行化使得系统的结构更简洁和清晰
* 减少并发的长度(粒度), 一旦并发, 要尽快结束并发, 合并结果, 然后再串行化地做后续处理
* 如果串行化是性能瓶颈, 那就用 worker 线程模型, worker 的逻辑必须非常单一且简短
* 如果锁能让代码结构更简洁和清晰, 那么放弃部分性能也值得

我们一般很喜欢把函数的参数定义为 const&, 这样即能传引用减少内存拷贝, 也能限定参数为 const 类型不可修改, 似乎很美好. 但是, 如果把对象的属性传给函数, 而对象又被删除时, 就会出错.

struct C
{
    std::string id;
};

class S
{
    C *c = NULL;

    void f1(){
        c = new C();
        c->id = "a";
        f2(c->id);
    }

    void f2(const std::string &id){
        delete c;
        c = new C();
        c->id = "b";
        printf("deleted %s\n", id.c_str()); // core
    }
};

当然, 理论上是写代码的人的错误. 但是, 这确实是一个大坑. 我相信, 这种 case 在实际中还是有不少的. 函数的编写者可能仅仅把参数当作一个无害的对象, 完全没有意识到, 参数变量是和某个要销毁的对象是绑定的. 但是, 又不能强制规定 string 类型只能传值, 然后期待编译器能优化 string 类.

真是坑.

在某些场景, 特别是一次性删除大量的连续 key 的情况下, LevelDB 的 Seek() 操作将变得特别慢. 我在源码中打点, 简单分析了其出现的原因.

首先, LevelDB 对 Delete 操作处理, 是将被删除的 Key 做标记, 并在未来某个时间将真正的数据和这个标记从硬盘上删除. 在真正的删除之前, 标记本身也会排序(即 key-type)存储在 sst 文件中.

所以, 如果删除大量的连续 key, 那么这些 key 会聚集在一起, 存储在某个 sst 文件中. 当 Seek() 操作时, 会定位到这个 sst 文件头部, 然后开始扫描, 跳过所有标记, 直到找到非标记的 key. 显然, 跳过的 key 越多, 耗时就越长. 而一个 sst 可能存储几十万个 key 标记, 这样操作就是秒级别, 甚至是数秒级别! 而且 CPU 占用是 100%.

对应的源码在 db_iter.cc 中:

void DBIter::FindNextUserEntry(bool skipping, std::string* skip) {
    // Loop until we hit an acceptable entry to yield
    do {
        ParsedInternalKey ikey;
        if (ParseKey(&ikey) && ikey.sequence <= sequence_) {
            switch (ikey.type) {
                case kTypeDeletion:
                    // Arrange to skip all upcoming entries for this key since
                    // they are hidden by this deletion.
                    SaveKey(ikey.user_key, skip);
                    skipping = true;
                    break;
                case kTypeValue:
                    if (skipping &&
                            user_comparator_->Compare(ikey.user_key, *skip) <= 0) {
                        // Entry hidden
                    } else {
                        valid_ = true;
                        saved_key_.clear();
                        return;
                    }
                    break;
            }
        }
        iter_->Next();
    } while (iter_->Valid());
}

其中, case kTypeDeletion 分支就是跳过删除标记. 这个缺陷目前来看, 是无法解决的, 只能期待 compaction 把这些 obsoleted 的数据真正地从硬盘上删除.

另一种方案是重新设计数据结构, 把删除标记分开存储, 这样就可以快速的跳过, 而不用扫描遍历.