早起120小时写代码第一期：kvcore

day1： 2022-4-17 看斗鱼 看手机 晚上6点22点 时间规划和紧急措施陷入时间黑洞 #象与骑象人，根本控制不大象，强制无效

手写KV引擎(第一部分)-实现单机kv引擎

【硬核课堂】LevelDB 源码分析

git clone git@github.com:wangcy6/coreKV-CPP.git

lesson05-sstable

https://hardcore.feishu.cn/docs/doccnjVdgWAfAEmg3g1HYqKvyhg

Lesson1.1 skiplist

• 文档：https://hardcore.feishu.cn/docs/doccnPpGqZcPRpHwmSSGVUQhs5f
• 提问1：面试官：为啥 redis 使用跳表(skiplist)而不是使用 red-black？

Skip lists: a probabilistic alternative to balanced trees

https://15721.courses.cs.cmu.edu/spring2018/papers/08-oltpindexes1/pugh-skiplists-cacm1990.pdf

• . If p = 1/2, using MaxLevel = 16 is appropriate for data structures containing up to 216 elements.

​

看java怎么实现的

​ https://github.com/openjdk-mirror/jdk7u-jdk/blob/master/src/share/classes/java/util/concurrent/ConcurrentSkipListMap.java

• https://www.cl.cam.ac.uk/research/srg/netos/papers/2007-cpwl.pdf [提问]

1. 范围查找等价

2. redis的sl层级比二叉平衡树要低很多，源码中SKIPLIST_P用的是0.25，层次数期望值相当于四叉平衡树

3. skip list 是 Concurrency-Friendly，Non-Blocking

看c++怎么实现的？原子操作和顺序一致性 对比

C++ Concurrency in Action

位置：第一本书:c++ 11 必读书籍 Effective Modern C++

看 文章自己写的

• Choose Concurrency-Friendly Data Structures（翻译）
• Effective Concurrency: Choose Concurrency-Friendly Data Structures
• https://programmerclick.com/article/70581257539/

1. To illustrate, let’s consider two common data structures: linked lists and balanced trees.

1
2
3
4
5
6
7
8
9

So red-black trees cause some problems for concurrent code:

It's hard to run updates truly concurrently because updates arbitrarily far apart in the tree can touch the same nodes—especially the root, but also other higher-level nodes to lesser degrees—and therefore contend with each other. We have lost the ability to make truly localized changes.

The tree performs extra internal housekeeping writes. This increases the amount of shared data that needs to be written and synchronized across caches to publish what would be a small update in another data structure.

所以红黑树给并发代码带来了一些问题：
很难真正同时运行更新，因为在树中任意相隔很远的更新可能会触及相同的节点——尤其是根，但也会触及其他更高级别的节点，但程度较低——因此会相互竞争。 我们已经失去了进行真正本地化更改的能力。
树执行额外的内部管理写入。 这增加了需要跨缓存写入和同步的共享数据量，以发布另一个数据结构中的小更新

day2: memory

阅读资料

• https://hardcore.feishu.cn/docs/doccngOEJpWCod99boj8LHbt43c

  开始日期：4-27 20:11 —结束日期：

  • 记free 多次引发的内存踩踏事件
  • LevelDB源码剖析之Arena内存管理
  • 【leveldb】arena内存结构
  • 基础1：中庸之道 —— arena内存管理
  • 面试中遇到的问题：一个指针重复释放会出现什么情况
  • 内存管理：设计Arena

• 问题来源：

  章节：corekv-cpp之内存池

  函数：void* SimpleFreeListAlloc::Allocate(int32_t n)

​

​ memory_usage_.fetch_add(n, std::memory_order_relaxed);

​ 多线程 加锁 级别自己分不清楚。

阅读：

1. C++11多线程 内存序(std::memory_order_relaxed)
2. C++ Concurrency in Action
3. https://www.cplusplus.com/reference/atomic/
4. C++11多线程 内存序(std::memory_order_consume)

结果：

Modification orders

data dependency

atomic operations on the same object may never be reordered

针对同一个对象的原子操作不会被重排序。

关于std::memory_order_relaxed具备如下几个功能：

作用于原子变量 不具有synchronizes-with关系 对于同一个原子变量，在同一个线程中具有happens-before关系（言外之意，不同的原子变量不具有happens-before关系，可以乱序执行） 由3可知，在一个线程中，如果某个表达式已经看到原子变量的某个值a，则该表达式的后续表达式只能看到a或者比a更新的值 ———————————————— 版权声明：本文为CSDN博主「qls315」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。 原文链接：https://blog.csdn.net/qls315/article/details/119930248

1. 阅读文章：https://blog.csdn.net/qls315/article/details/119930248

输出：同样代码 memory_order_relaxed具备如下几个功能：不保证同步

2. 第五章节 p143

happens-before relationship

• 章节：corekv-cpp之内存池

  函数：void* SimpleFreeListAlloc::Allocate(int32_t n)

  select_free_list = freelist_ + M_FreelistIndex(n);

  问题1： freelist_都是空闲的内存吗？为啥没有遍历直接获取了。分配也没有标记该node被使用？

  问题2:和freelist_ union设计有关系吗？这个stl源码解析 houjie时候 没看明白?

  多个空闲链表 判断是否被占用，union 结果能实现遍历吗？

atomic类 多线程通过fetch__xx函数 一个变量进行 加减没有问题。

多线程 对不同变量进行 做同步 load,store 使用条件是什么？

例如 x y 写操作必须在同一个线程内完成，才满足 happens-before and synchronizes-with。 2个线程分别 x 和y写 肯定不满足

The happens-before relationship

英文：Listing 5.10 Using std::memory_order_consume to synchronize data https://en.cppreference.com/w/cpp/atomic/memory_order

中文：https://blog.csdn.net/qls315/article/details/119930248

memory_order_acquire: （可以理解为 mutex 的 lock 操作）

1. 对读取施加 acquire 语义（load），在代码中这条语句后面所有读写操作都无法重排到这个操作之前，即 load-store 不能重排为 store-load, load-load 也无法重排为 load-load
2. 在这个原子变量上施加 release 语义的操作发生之后，acquire 可以保证读到所有在 release 前发生的写入

memory_order_acquire：修饰load操作。

1. 后面读写操作代码，顺序，不能提前执行。
2. 我读取是比尔写入成功的。

memory_order_acquire memory_order_consume：

atomic_compare_exchange_strong

知道c++提供原子操作类atomic 提供的接口有哪几个？

4个 atomic_fetch_add atomic_load atomic_store atomic_compare_exchange_strong

memory_order_release:（可以理解为 mutex 的 unlock 操作）

1. 对写入施加 release 语义（store）， 在代码中这条语句前面的所有读写操作都无法被重排到这个操作之后 ，即 store-store 不能重排为 store load-store 也无法重排为 store-load

2. 当前线程内的所有写操作，对于其他对这个原子变量进行 acquire 的线程可见

3. 当前线程内的与这块内存有关的所有写操作，对于其他对这个原子变量进行 consume 的线程可见 https://www.cnblogs.com/lizhanzhe/p/10893016.html

day3

1. LSM-tree读写放大

• LSM-tree 的主要劣势是读写放大【不明白】