• 2021-04-17

    并发编程的核心技术 – 多版本(Multi Version)

    Views: 278 | No Comments

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

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

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

    Posted by ideawu at 2021-04-17 18:20:34
  • 2020-06-21

    C++程序员容易走入性能优化误区

    Views: 1825 | No Comments

    有些 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 原则

    Posted by ideawu at 2020-06-21 09:56:02
  • 2020-06-19

    C++ bug free 原则

    Views: 2762 | No Comments

    ## 性能优化

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

    ## 内存拷贝

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

    ## 接口设计

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

    ## 并发和锁

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

    Posted by ideawu at 2020-06-19 12:48:51
  • 2020-04-09

    C++ const& 的坑

    Views: 4378 | 1 Comment

    我们一般很喜欢把函数的参数定义为 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 类.

    真是坑.

    Posted by ideawu at 2020-04-09 16:21:10
  • 2020-02-12

    LevelDB Seek() 特别慢的场景

    Views: 2999 | No Comments

    在某些场景, 特别是一次性删除大量的连续 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 的数据真正地从硬盘上删除.

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

    Posted by ideawu at 2020-02-12 15:22:23
  • 2020-01-21

    蛇形遍历数组

    Views: 5519 | No Comments

    蛇形遍历数组, 我的思路是使用两个点坐标再加上一个方向变量, 两个点同时在边缘上移动, 然后连线.

    但是, 其实这个问题本质就是从一点出发, 不断地 walk, 一次只 walk 一步, 需要保留方向状态. 如果一次 walk 完斜线, 则不用方向状态, 因为可以根据 walk 的起点来判断.

    Continue reading »

    Posted by ideawu at 2020-01-21 01:43:19
|<<<123456789>>>| 1/13 Pages, 76 Results.