算法笔记：跳表（r1）

skiplist

algorithm

这是读书时一篇旧文搬运.几年后再次回顾下算法.

跳表是一种著名数据结构。

原理应该不用介绍了，rocksdb/redis内部都有使用skiplist。

相对于红黑树，它的优势我认为是实现简单，并且容易无锁化。

本文主要讨论：

阅读更多

分布式笔记 - Raft（1）

分布式

Q&A

线性一致性？

个人认为，分布式系统的一致性与多核内存模型中涉及的一致性异曲同工，所以分布式系统的线性一致性我认为可以参考类似多核系统的线性一致性定义来理解。

fsm: finite-state-machine

个人理解为有状态分布式服务的每个独立实例（进程+数据），本质上都可以是个有限状态机（fsm）

阅读更多

rust的引用规则小例1

rust

rust的借用有个规则，1个对象如果要被借用：

  1. 要么被多次不可变借用
  2. 要么被1次可变借用

这个文章就举个例子来让人更加深入理解上述规则.

一个hashmap，希望删除其中的某些kv对，怎么做？

阅读更多

rocksdb性能压测

DB

压测rocksdb引擎，有两种思路：

  1. 自己写一个benchmark工具： 根据自己关心的kv pattern和access pattern，生成对应的kv pairs，然后入库，并发起对应的请求，最后收集结果。 通常不同类型的数据库都有符合不同数据模型的负载模型和不同的建模，如：TP型数据库的TPCxxx，AP型数据库的xxxx，图数据库的LDBC等。 这类思路下有很多相关工具，如：
阅读更多

parameter pack和递归模板展开

c++

需求

做一个libevent的wrapper，有个需求，用户对某个fd的可读事件感兴趣，要求在产生这个事件时，调用他传入的某个可调用对象及其参数。 libevent的回调类似：void LibeventCallback(int fd, short flag, void* arg);

要求： 1、用户传入的可调用对象fn，拿的参数是可变的，第一个参数为某个特定类型，用于感知fd和flag，后续其他为用户自定义参数

阅读更多

c++ notes：recall of move-semantics and rvalue-reference (1)

c++

几年前，整理了一份rvalue相关笔记：以前的一份笔记，梳理近况时，发现某些问题还是没有弄清楚。

Universal Reference

  • Q: 什么场景下需要考虑这个问题？ A：模板元编程时，需要考虑兼容各种传入参数类型时（尤其是『左值/右值』）。基本上我感觉就是为了处理完美转发问题。比如写一个工厂函数模板，需要同时兼容传入的参数是左值和右值的情况，核心点是一个右值无法用于初始化一个左值引用，c++11之前要解决这个问题，要么写很多重复偏特化模板，要么付出拷贝参数的代价。

    c++11引入右值引用之后，上述问题可以通过universal reference来解决，即传入参数是左值时，形参的类型推导为左值引用，是右值时，推导为右值引用，同时只需要提供一套模板即可。

  • Q: 什么是Universal Reference? A: 形如T&&, T不含有任何的cv限定符, 且T需要被推导

    G1. If a variable or parameter is declared to have type T&& for some deduced type T, that variable or parameter is a universal reference.

阅读更多