• 2020-02-12

    LevelDB Seek() 特别慢的场景

    Views: 2522 | 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-02-11

    Git 提示 fatal: HTTP request failed

    Views: 2150 | No Comments

    新机器莫名其妙 git 提示

    error:  while accessing https://github.com/ideawu/ssdb/info/refs
    
    fatal: HTTP request failed
    

    原来要升级 nss:

    sudo yum update nss
    
    Posted by ideawu at 2020-02-11 21:07:51
  • 2020-01-21

    算法题分类及解题思路

    Views: 3228 | No Comments

    * 暴力破解(brute force)

    暴力破解, 就是穷举. 穷举的方式一般用递归, O(n^2). 优化的思路是减少递归步骤:

    1. 更加严格的静态递归条件
    2. 增加 close_list, 动态地判断是否需要进行递归, close_list 根据执行情况动态变化

    另外的一种优化方向是消除递归. 因为递归是可以通过递归栈 open_list 来消除的. 可以对栈进行动态排序, 优先进行最可能成功的下一个步骤(A*). 这种排序优化, 导致可以使用不同的数据结构来存储递归栈: stack, queue, priority_queue.

    有序性, 有序子集: 有一种非常常用的优化思路是利用输入条件的局部有序性(存在有序的子集), 不再穷举这些有序的子集. 在处理这些有序子集时, 采用 O(n) 或者 O(K) 算法, 最差也能采用二分法 O(logN), 而且其它元素与这些有序子集结合时, 也不再需要穷举.

    A* 算法: open_list 根据沉没成本G和未来成本(H)之和来决定下一个处理步骤, 达成即最优.

    * 动态规划(dynamic programming)

    动态规划与暴力破解类似, 都是分而治之的思路, 但又不相同. 动态规划的下一个处理步骤是唯一的, 而且 open_list 初始可以确定, 后续单调递减. 下一个步骤的处理除了依赖自身的静态条件, 还依赖之前的处理结果集, 并维护这个结果集. 有点像消除了递归之后的暴力破解, 但暴力破解的 open_list 不是初始固定的.

    * 直观解法(coding)

    这类问题的解法非常直观, 一般没有算法上的优化空间, 也不需要技巧, 纯粹是为了训练编程能力. 考察做题者对变量的状态判断是否完备充分, 判断路径是否最简, if 分支是否可以合并等等. 所以, 就是考察边界条件的判断, 还有逻辑条件精减, 要求有非常强的逻辑思维能力.

    一般这类题就是链表翻转, 有序链表合并, 删除重复元素, 数组遍历(螺旋向内, 螺旋向外, 蛇形, 等等), partition 等.

    要点是: 边界判断, 分支合并, 简化重合边界的处理, 增加虚拟节点进行辅助.

    Posted by ideawu at 2020-01-21 09:38:57
  • 2020-01-21

    蛇形遍历数组

    Views: 4637 | No Comments

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

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

    Continue reading »

    Posted by ideawu at 01:43:19
  • 2020-01-15

    在有序的KV引擎之上建造结构化数据库引擎

    Views: 6640 | No Comments

    KV 数据结构极大地简化了存储引擎的接口和实现. 基本的 KV 接口一般就是 Get(), Set(), 实现上代码也很简单, 极简的实现可以直接利用编码语言提供的 map(哈希, 红黑树)来提供内存数据结构, 而且硬盘上直接 dump 内存数据即可(类似 Redis 的策略).

    不过, KV 存储引擎自己省事了, 但使用者不喜欢, 因为大部分的业务并不是 KV 所能表达的, 业务需要丰富的数据结构, 表格(table), 列表(list), map 等各种容器. 另外还需要排序功能, 业务依赖排序.

    Continue reading »

    Posted by ideawu at 2020-01-15 19:30:00
  • 2020-01-15

    分而治之算法(divide and conquer)

    Views: 4193 | No Comments

    分而治之算法(divide and conquer)是计算机算法领域最常用最有效的算法之一, 体现到编程上就是树(数据结构), 递归函数. 一般的代码模板是这样的:

    func recursive(N){
    	if(!N){return;}
    	a, b = split(N); // divide 
    	proc(a);         // conquer a
    	recursive(b);      // process b
    }
    

    对于寻路, 分段处理最终达成目标这种模式的问题, 一般的代码模板是:

    func recursive(N){
    	if(!N){return;}
    	a, b = split(N); // divide 
    	r = proc(a);     // conquer a
    	if(r){recursive(r + b);}  // conquer remain + b
    	recursive(b);      // process b
    }
    

    多了一步:

    if(r){recursive(r + b);}
    

    因为前一段的剩余, 要和后一段组成新的问题, 然后被处理.

    Posted by ideawu at 16:36:14 Tags:
|<<<123456789>>>| 5/129 Pages, 773 Results.