why

这个ppt¹十分有趣，决定做个阅读记录，作者是Yoshinori Matsunobu是mysql rocks工程师 ，rocksdb上见过他的pr

why

科普概念

背景知识: 分布式事务和2pc在参考链接¹中有介绍，2pc协议是分布式事务的一个解决方案，2pc主要缺陷

1. 同步阻塞问题。执行过程中，所有参与节点都是事务阻塞型的。当参与者占有公共资源时，其他第三方节点访问公共资源不得不处于阻塞状态。
2. 单点故障。由于协调者的重要性，一旦协调者发生故障。参与者会一直阻塞下去。尤其在第二阶段，协调者发生故障，那么所有的参与者还都处于锁定事务资源的状态中，而无法继续完成事务操作。（如果是协调者挂掉，可以重新选举一个协调者，但是无法解决因为协调者宕机导致的参与者处于阻塞状态的问题）
3. 数据不一致。在二阶段提交的阶段二中，当协调者向参与者发送commit请求之后，发生了局部网络异常或者在发送commit请求过程中协调者发生了故障，这回导致只有一部分参与者接受到了commit请求。而在这部分参与者接到commit请求之后就会执行commit操作。但是其他部分未接到commit请求的机器则无法执行事务提交。于是整个分布式系统便出现了数据部一致性的现象。
4. 二阶段无法解决的问题：协调者再发出commit消息之后宕机，而唯一接收到这条消息的参与者同时也宕机了。那么即使协调者通过选举协议产生了新的协调者，这条事务的状态也是不确定的，没人知道事务是否被已经提交。

rocksdb 2pc实现 见参考链接^{2, 3} 主要多了prepare操作。这个需求来自myrocks，作为mysql引擎需要xa事务机制myrocks学习可以见参考链接⁴

2pc实现简单说

txn->Put(...);
txn->Prepare();
txn->Commit();

我一开始是找myrocksxa事务是咋实现的，myrocks引擎在代码storage/myrocks里，但是翻了半天没找到。

找手册，这⁵有个myrocks配置选项

rocksdb_enable_2pc

• Description: Enable two phase commit for MyRocks. When set, MyRocks will keep its data consistent with the binary log (in other words, the server will be a crash-safe master). The consistency is achieved by doing two-phase XA commit with the binary log.
• Commandline: --rocksdb-enable-2pc={0|1}
• Scope: Global
• Dynamic: Yes
• Data Type: boolean
• Default Value: ON

全程配置allow_2pc就能模拟xa事务吗? 我针对这个改了一版db_bench

dbbench改动，增加allow_2pc配置，如果有这个配置，就true， 调用定义DEFINE_bool就好了（gflags这个库也很好玩，之前吐槽没有命令行的库，孤陋寡闻）

机器32核，脚本参考mark改的，执行脚本

bash r.sh 10000000 60 32 4 /home/vdb/rocksdb-5.14.3/rdb 0 /home/vdb/rocksdb-5.14.3/db_bench

核心代码

#set -x
numk=$1
secs=$2
val=$3
batch=$4
dbdir=$5
sync=$6
dbb=$7

# sync, dbdir, concurmt, secs, dop

function runme {
  a_concurmt=$1
  a_dop=$2
  a_extra=$3
  a_2pc=$4

  rm -rf $dbdir; mkdir $dbdir
  # TODO --perf_level=0

$dbb --benchmarks=randomtransaction --use_existing_db=0 --sync=$sync --db=$dbdir --wal_dir=$dbdir --num=$numk --duration=$secs --num_levels=6 --key_size=8 --value_size=$val --block_size=4096 --cache_size=$(( 20 * 1024 * 1024 * 1024 )) --cache_numshardbits=6 --compression_type=none --compression_ratio=0.5 --level_compaction_dynamic_level_bytes=true --bytes_per_sync=8388608 --cache_index_and_filter_blocks=0 --benchmark_write_rate_limit=0 --write_buffer_size=$(( 64 * 1024 * 1024 )) --max_write_buffer_number=4 --target_file_size_base=$(( 32 * 1024 * 1024 )) --max_bytes_for_level_base=$(( 512 * 1024 * 1024 )) --verify_checksum=1 --delete_obsolete_files_period_micros=62914560 --max_bytes_for_level_multiplier=8 --statistics=0 --stats_per_interval=1 --stats_interval_seconds=60 --histogram=1 --allow_concurrent_memtable_write=$a_concurmt --enable_write_thread_adaptive_yield=$a_concurmt --memtablerep=skip_list --bloom_bits=10 --open_files=-1 --level0_file_num_compaction_trigger=4 --level0_slowdown_writes_trigger=20 --level0_stop_writes_trigger=30 --max_background_jobs=8 --max_background_flushes=2 --threads=$a_dop --merge_operator="put" --seed=1454699926 --transaction_sets=$batch --compaction_pri=3 $a_extra -enable_pipelined_write=false -allow_2pc=$a_2pc
}

for dop in 1 2 4 8 16 24 32 40 48 ; do
for concurmt in 0 1 ; do
for pc in 0 1; do

fn=o.dop${dop}.val${val}.batch${batch}.concur${concurmt}.notrx
runme $concurmt $dop "" $pc >& $fn
q1=$( grep ^randomtransaction $fn | awk '{ print $5 }' )

t=transaction_db
fn=o.dop${dop}.val${val}.batch${batch}.concur${concurmt}.pessim
runme $concurmt $dop --${t}=1 $pc >& $fn
q2=$( grep ^randomtransaction $fn | awk '{ print $5 }' )

t=optimistic_transaction_db
fn=o.dop${dop}.val${val}.batch${batch}.concur${concurmt}.optim
runme $concurmt $dop --${t}=1 $pc >& $fn
q3=$( grep ^randomtransaction $fn | awk '{ print $5 }' )

echo $dop mt${concurmt} allow2pc${pc} $q1 $q2 $q3 | awk '{ printf "%s\t%s\t%s\t%s\t%s\t%s\n", $1, $2, $3, $4, $5, $6 }'

done
done
done

能看到是allow_2pc和和其他项组合的。

测试结果发现数据没有不同

线程数， 是否并发写， 是否开启2pc， 无事务，悲观事务，乐观事务

1       mt0     allow2pc0       39512   22830   21238
1       mt0     allow2pc1       40720   23014   22767
1       mt1     allow2pc0       40539   22683   22131
1       mt1     allow2pc1       36361   21680   23592
2       mt0     allow2pc0       62337   33972   27747
2       mt0     allow2pc1       62725   33941   27553
2       mt1     allow2pc0       62535   33640   31501
2       mt1     allow2pc1       62127   34320   30636
4       mt0     allow2pc0       64864   41878   25235
4       mt0     allow2pc1       65517   41184   26055
4       mt1     allow2pc0       93863   49895   28183
4       mt1     allow2pc1       89718   48726   29027
8       mt0     allow2pc0       79444   52166   26142
8       mt0     allow2pc1       80186   51643   26254
8       mt1     allow2pc0       139753  72598   24661
8       mt1     allow2pc1       136604  73382   25482
16      mt0     allow2pc0       87555   61620   22809
16      mt0     allow2pc1       88055   61812   21631
16      mt1     allow2pc0       193535  98820   21272
16      mt1     allow2pc1       190517  98582   21007
24      mt0     allow2pc0       91718   65400   20736
24      mt0     allow2pc1       92319   64477   20505
24      mt1     allow2pc0       226268  111956  20453
24      mt1     allow2pc1       224815  111901  21005
32      mt0     allow2pc0       88233   65121   20683
32      mt0     allow2pc1       89150   65643   20127
32      mt1     allow2pc0       111623  120843  20626
32      mt1     allow2pc1       230557  120421  20124
40      mt0     allow2pc0       87062   66972   20093
40      mt0     allow2pc1       86632   66814   20590
40      mt1     allow2pc0       113856  60101   20280
40      mt1     allow2pc1       115139  58768   20264
48      mt0     allow2pc0       87093   68637   20153
48      mt0     allow2pc1       87283   68382   19537
48      mt1     allow2pc0       122819  64030   19796
48      mt1     allow2pc1       126721  64090   19907

同事zcw指出这种测试可能不对，我的测试 2pc和悲观乐观事务是组合的形式，这可能并不合理,乐观事务这个参数没意义，allow_2pc只是一个配置，表示rocksdb支持而已，还是要调用prepare才能实现应用的xa，我之前错误的理解allow_2pc配置后会在rocksdb内部有prepare过程（我之前好像看到了）

还是回头看db_bench，看db_bench到底怎么测试的 所有randomtransaction会调用doinsert来真正的执行

定义在transaction_test_util.cc中，果不其然 找到txn->prepare调用

bool RandomTransactionInserter::DoInsert(DB* db, Transaction* txn,
                                         bool is_optimistic) {
	...
  // pick a random number to use to increment a key in each set
    ...
  // For each set, pick a key at random and increment it
    ...
	
  if (s.ok()) {
    if (txn != nullptr) {
      bool with_prepare = !is_optimistic && !rand_->OneIn(10);
      if (with_prepare) {
        // Also try commit without prepare
        s = txn->Prepare();
        assert(s.ok());
        ROCKS_LOG_DEBUG(db->GetDBOptions().info_log,
                        "Prepare of %" PRIu64 " %s (%s)", txn->GetId(),
                        s.ToString().c_str(), txn->GetName().c_str());
        db->GetDBOptions().env->SleepForMicroseconds(
            static_cast<int>(cmt_delay_ms_ * 1000));
      }
      if (!rand_->OneIn(20)) {
        s = txn->Commit();

注意with_prepare这句，这句表明，不是乐观事务，悲观事务，会注意这个取反，会90%调用prepare，调用prepare的事务可以确定肯定是xa事务。所以我需要加个配置项，改成100%的，也应该加个完全不调用prepare的做对照

另外，这个rand_->OneIn(10)实现的很好玩。看测试代码总能发现这些犄角旮旯的需求以及好玩的实现

改动点⁶

• 加上transaction_db_xa
• 所有 FLAGS_transaction_db都得或上FLAGS_transaction_db_xa，避免遗漏，或者不复用，单独再写
• randomTransaction入口

void RandomTransaction(ThreadState* thread) {
while (!duration.Done(1)) {
  bool success;

  // RandomTransactionInserter will attempt to insert a key for each
  // # of FLAGS_transaction_sets
  if (FLAGS_optimistic_transaction_db) {
    success = inserter.OptimisticTransactionDBInsert(db_.opt_txn_db);
  } else if (FLAGS_transaction_db) {
    TransactionDB* txn_db = reinterpret_cast<TransactionDB*>(db_.db);
    success = inserter.TransactionDBInsert(txn_db, txn_options);
  } else if (FLAGS_transaction_db_xa) {
    TransactionDB* txn_db = reinterpret_cast<TransactionDB*>(db_.db);
    success = inserter.TransactionDBXAInsert(txn_db, txn_options);
  } else {
    success = inserter.DBInsert(db_.db);
  }

加上个flags_transaction_db_xa 对应的option也得注意，要enable allow_2pc

没enable allow_2pc做了个测试，结果真的就是降低了10%，没啥参考价值的感觉。 最后一列是100% prepare

1       mt0     37353   21628   22018   21845
1       mt1     38089   21171   22606   21688
2       mt0     62627   31901   27003   32895
2       mt1     62029   33865   31083   33691
4       mt0     64915   41651   26226   40853
4       mt1     88089   51123   29066   48673
8       mt0     79742   51276   25154   49865
8       mt1     134687  72683   25000   71469
16      mt0     88103   61816   21568   60656
16      mt1     192417  98546   21265   97890
24      mt0     91989   64858   20592   63141
24      mt1     232313  111736  20706   110083
32      mt0     91073   65840   20399   64103
32      mt1     221337  61289   20164   118167
40      mt0     85909   66244   20144   64709
40      mt1     116536  59155   20119   55437
48      mt0     86006   68390   19828   66910
48      mt1     125246  63577   19700   61621

我enable allow2pc 100%prepare 测了一组数据，作为对照，测了一个0%prepare

#set -x
numk=$1
secs=$2
val=$3
batch=$4
dbdir=$5
sync=$6
dbb=$7

# sync, dbdir, concurmt, secs, dop

function runme {
  a_concurmt=$1
  a_dop=$2
  a_extra=$3

  rm -rf $dbdir; mkdir $dbdir
  # TODO --perf_level=0

$dbb --benchmarks=randomtransaction --use_existing_db=0 --sync=$sync --db=$dbdir --wal_dir=$dbdir --num=$numk --duration=$secs --num_levels=6 --key_size=8 --value_size=$val --block_size=4096 --cache_size=$(( 20 * 1024 * 1024 * 1024 )) --cache_numshardbits=6 --compression_type=none --compression_ratio=0.5 --level_compaction_dynamic_level_bytes=true --bytes_per_sync=8388608 --cache_index_and_filter_blocks=0 --benchmark_write_rate_limit=0 --write_buffer_size=$(( 64 * 1024 * 1024 )) --max_write_buffer_number=4 --target_file_size_base=$(( 32 * 1024 * 1024 )) --max_bytes_for_level_base=$(( 512 * 1024 * 1024 )) --verify_checksum=1 --delete_obsolete_files_period_micros=62914560 --max_bytes_for_level_multiplier=8 --statistics=0 --stats_per_interval=1 --stats_interval_seconds=60 --histogram=1 --allow_concurrent_memtable_write=$a_concurmt --enable_write_thread_adaptive_yield=$a_concurmt --memtablerep=skip_list --bloom_bits=10 --open_files=-1 --level0_file_num_compaction_trigger=4 --level0_slowdown_writes_trigger=20 --level0_stop_writes_trigger=30 --max_background_jobs=8 --max_background_flushes=2 --threads=$a_dop --merge_operator="put" --seed=1454699926 --transaction_sets=$batch --compaction_pri=3 $a_extra -enable_pipelined_write=false
}

for dop in 1 2 4 8 16 24 32 40 48 ; do
for concurmt in 0 1 ; do

fn=o.dop${dop}.val${val}.batch${batch}.concur${concurmt}.notrx
runme $concurmt $dop ""  >& $fn
q1=$( grep ^randomtransaction $fn | awk '{ print $5 }' )

t=transaction_db
fn=o.dop${dop}.val${val}.batch${batch}.concur${concurmt}.pessim
runme $concurmt $dop --${t}=1  >& $fn
q2=$( grep ^randomtransaction $fn | awk '{ print $5 }' )

t=optimistic_transaction_db
fn=o.dop${dop}.val${val}.batch${batch}.concur${concurmt}.optim
runme $concurmt $dop --${t}=1  >& $fn
q3=$( grep ^randomtransaction $fn | awk '{ print $5 }' )

t=transaction_db_xa
fn=o.dop${dop}.val${val}.batch${batch}.concur${concurmt}.pessimxa
runme $concurmt $dop --${t}=1  >& $fn
q4=$( grep ^randomtransaction $fn | awk '{ print $5 }' )


fn=o.dop${dop}.val${val}.batch${batch}.concur${concurmt}.pessimnopre
runme $concurmt $dop --${t}=-1  >& $fn #-1 for no prepare
q5=$( grep ^randomtransaction $fn | awk '{ print $5 }' )
echo $dop mt${concurmt} $q1 $q2 $q3 $q4 $q5 | awk '{ printf "%s\t%s\t%s\t%s\t%s\t%s\t%s\n", $1, $2, $3, $4, $5, $6, $7 }'

done
done

markdown 不能调格间距，真破

这个数据作为参考。

另外，有个2pc的bug 值得关注一下 pr https://github.com/facebook/rocksdb/pull/1768

reference

1. 分布式事务，2pc 3pc https://www.hollischuang.com/archives/681
2. rocksdb 2pc实现 https://github.com/facebook/rocksdb/wiki/Two-Phase-Commit-Implementation
3. rocksdb 事务，其中有2pc事务讲解https://zhuanlan.zhihu.com/p/31255678
4. myrocks deep dive，不错，关于rocksdb的部分提纲摰领https://www.percona.com/live/plam16/sites/default/files/slides/myrocksdeepdive201604-160419162421.pdf
5. https://mariadb.com/kb/en/library/myrocks-system-variables/
6. 我的测试改动 https://github.com/wanghenshui/rocksdb/tree/14.3-modified-db-bench
7. 一个excel小知识，生成的数据如何整理成excel格式，选择这列 ->{数据}菜单 ->分列->按照空格分列，https://zhidao.baidu.com/question/351335222
8. cockroachdb 用rocksdb 2pc的一个讨论，有时间仔细看看 https://github.com/cockroachdb/cockroach/issues/16948

why

这篇文章是一个cppcon ppt的阅读记录，没法翻墙看视频有点遗憾。有机会再看视频吧。

在ppt中，作者分析了基于数据变动模型的缺点，变动的数据带来各种各样的引用，导致复杂的数据变化。不变的数据模型才是主流。作者不是想要在c++中实现Haskell数据结构模型，是做了个数据结构式的 git ，这就很有意思了。

每个vector都算一个snapshot。

咱们先回想一下git是怎么实现的 ->object一个数组存起来，hash kv存起来，每个object有自己的ref链表，构成object链，也就是分支，每个ref到具体的object（对应commit）也就是快照，不可更改

imm 数组看起来很像了。怎么实现呢？

树 ,引用中有很多链接，是作者的思想来源

这个细节我后面单独开帖子分析吧，一时半会写不完感觉

后面的PPT是作者用immer这个库实现一个mvc模式的软件，一个编辑器

mvc的毛病

改进方案

我感觉这个东西就是Immutable.js的思路？

reference

• ppt地址，https://sinusoid.es/talks/immer-cppcon17
• repo地址 https://github.com/arximboldi/immer
• 作者在ppt中列举了这几个链接
  • purely functional data structure https://www.cs.cmu.edu/~rwh/theses/okasaki.pdf 这本书似乎没有中文版
  • finger tree http://www.staff.city.ac.uk/~ross/papers/FingerTree.html
  • Array Mapped Tries. 2000 https://infoscience.epfl.ch/record/64394/files/triesearches.pdf
  • RRB-Trees: Efficient Immutable Vectors. 2011https://infoscience.epfl.ch/record/169879/files/RMTrees.pdf
  • value identity and state https://www.infoq.com/presentations/Value-Identity-State-Rich-Hickey

和文章没什么关系的to review link

• cpp source https://www.includecpp.org/resources/
• 之前对编译期正则有所耳闻，看这个ppt的时候发现了这个talk，和网站。很牛逼的工作，提了提案 https://compile-time.re

只要遇到的问题多，天天都能水博客

之前遇到一个问题 link，解决方案是改成-std=gnu99，这是前提

这次我用到了pthread_spinlock，实现个简单的队列，我在redis的makefile中改了，但是编译还是提示

 error: unknown type name 'pthread_spinlock_t'
  pthread_spinlock_t head_lock;

经过我走读makefile，发现 src/.make-settings文件中有缓存之前的编译配置，导致make还是按照 -std=c99 编译的，手动改成-std=gnu99就好了。

注意

• 这降低了可移植性。（macos貌似没有spinlock？）
• 需要了解redis makefile流程。可能是大家都觉得简单，没见有人讲这个。

参考

• gcc使用spinlock https://stackoverflow.com/questions/13661145/using-spinlocks-with-gcc

• features.h https://github.com/bminor/glibc/blob/0a1f1e78fbdfaf2c01e9c2368023b2533e7136cf/include/features.h#L154-L175

• __USE_XOPEN2K 定义，实际上和GNU相关。https://stackoverflow.com/questions/33076175/why-is-struct-addrinfo-defined-only-if-use-xopen2k-is-defined
• 解释__USE_XOPEN2K https://stackoverflow.com/questions/13879302/purpose-of-use-xopen2k8-and-how-to-set-it
• __GNU_SOURCE 和___USE_GNU区别https://blog.csdn.net/robertsong2004/article/details/52861078
  • 简单说，有_GNU_SOURCE就有__USE_GNU ,一个内部用，一个外部用，指定编译选项gnu也会启用
  • g++默认编译带GNU，gcc不带
• 介绍__GNU_SOURCE 和__USE_GNUhttps://stackoverflow.com/questions/7296963/gnu-source-and-use-gnu
• 一个-std=c99报错，rwlock也不是标准的，需要pthread.h，也得用gnu https://stackoverflow.com/questions/15673492/gcc-compile-fails-with-pthread-and-option-std-c99
• spinlock manpage ，注意_POSIX_C_SOURCE >= 200112L http://man7.org/linux/man-pages/man3/pthread_spin_lock.3.html

关于 软连接硬链接inode相关概念，这篇文章深入浅出的阐释了一下, 讲的很好。主要是inode和文件系统的概念不熟，这些概念以及linux的实现，对很多应用都有影响（比如文件分元数据和实际数据，这个设计很多编码方案都这么搞，linux相关设计概念可是个宝藏，读一遍显然是记不住的）

简单说，硬链接是复制inode，增加源文件引用计数，不改变数据域，软连接是增加一层，数据域维护整个文件。

找个对应的c++的概念来理解软硬链接，那就是硬链接就像shared_ptr 维护同一个数据，软连接就是raw pointer，或者说weak_ptr（但是没有提升能力） 硬链接总能保证数据是有效的 ，软链接只是数据的一个粗糙的引用语义，文件不存在软连接就无意义了。

查看软链接

 ls -lR / 2> /dev/null | grep /etc/ | grep ^l

硬链接无法查看，只能通过inode判断。

ls -ilh
...
1194549 -rwxr-xr-x    4 root root      768608 May  2  2016 c++
1194549 -rwxr-xr-x    4 root root      768608 May  2  2016 g++
...

但是能查找，列出当前目录下所有硬链接文件

find . -type f -a \! -links 1

` 硬链接的缺陷？`

• 只能对已存在的文件进行创建
• 不能交叉文件系统进行硬链接的创建 ，inode会重复。
• 不能对目录进行创建，只可对文件创建 因为 . 和 ..也是硬链接，文件系统的一部分。如果对目录进行硬链接就环了。

为什么需要硬链接？

参考这个问题和回答

主要需求点是删除一个不会影响其他，又能复用文件

比如上面的例子，c++和g++实际上是同一个文件

再比如busybox命令工具箱，只有一个文件，所有的命令实现都是busybox文件的硬链接。删除文件不影响其他命令

再比如数据备份，直接硬链接，用在数据库备份上，十分迅速，这个文章可以阅读一下。http://www.mikerubel.org/computers/rsync_snapshots/#Incremental

还有文件锁应用， link unlink，pidfile？

why

详细的文档是非常重要的，对可用性，可维护性都是极大的帮助，比如git文档，比如Rocksdb文档，比如tidb文档, 通过文档学软件要快速。写这种博客就是为了加速这个过程

git 很像文件系统，很多概念可以相互学习补充，git也算是 kv数据库了

简单梳理下git功能，实际上git官方教程做的非常好，下面的总结也是官方教程的复述 教程地址https://git-scm.com/book/zh

git是怎么存储提交的

commit会有tree来维护对应信息，具体在blob中

如果有变动，tree维护新的对应关系，commit向前移动，每次commit对应的快照就是所谓的分支起点了（都是指针节点）

如果创建新分支，就对应着生成新的指针节点（如果已经有分支，不能创建，因为已经有指针占位了）

而切换工作指针，就是把HEAD指针放到不同的分支指针上。这样也就能理解HEAD了。

fast forward

考虑一个补丁合入

git checkout -b hotfix
...
git commit ...
git checkout master
git merge hotfix

master指针转移到hotfix后面。这也就是fast-foward，直接挪到前面。还有一些概念可以见参考链接1中的内容

内部数据结构

.git目录下 主要关注HEAD 及 index 文件，objects 及 refs 目录。

• objects 目录存储所有数据内容
• refs 目录存储指向数据 (分支) 的提交对象的指针
• HEAD 文件指向当前分支
• index 文件保存了暂存区域信息

首先，git算是一个内容寻址的文件系统 ，这个高大上的名词，就是一个kv-store，hash-based，重复的数据（hash相同）地址相同。

index 更像是leveldb里的manifest。记录变更。这些东西都是相通的。

objects包含commit tree blob三种数据类型，编码算法相同，type字段不一样。内部有object数据结构，这三个是派生出来的。

refs就是指针。内部有heads目录，分支头指针。

object数据结构如下

struct object_list {
	struct object *item;
	struct object_list *next;
	const char *name;
};

struct object {
	unsigned parsed : 1;
	unsigned used : 1;
	unsigned int flags;
	unsigned char sha1[20];
	const char *type;
	struct object_list *refs;
	void *util;
};

extern int nr_objs;
extern struct object **objs;

所有对象(tree blob commit tag)都在objs这个数组中，ref添加到object的字段上。多线复杂的提交线就靠ref这个链表来串起来。

具体实现还要挨个走一遍。简单看头文件只能分析个大概。

object目录下有255个目录 00-ff 取的是 算出来的sha值的前两个

比如算出来的是47a013e660d408619d894b20806b1d5086aab03b，会存成objects/47/a013e660d408619d894b20806b1d5086aab03b

有机会走读一下代码更好。

reference

1. 官方 git内部原理，做的十分好 （就是pro git 2）https://git-scm.com/book/zh/v1/Git-%E5%86%85%E9%83%A8%E5%8E%9F%E7%90%86

2. git v0.99源码，基本上基础类型都有了https://git.kernel.org/pub/scm/git/git.git/tree/?h=v0.99&id=a3eb250f996bf5e12376ec88622c4ccaabf20ea8

3. 这个博客讲了一嘴代码，有点乱，找不到源头博客 https://blog.csdn.net/varistor/article/details/10223573

4. git原理 图文 http://marklodato.github.io/visual-git-guide/index-zh-cn.html

5. git原理介绍，讲解.git内部结构的 https://zhuanlan.zhihu.com/p/45510461

6. 内容寻址 文件系统https://en.wikipedia.org/wiki/Content-addressable_storage

7. 这个博客讲的不错

   1. git对象 http://jingsam.github.io/2018/06/03/git-objects.html
   2. git 引用 http://jingsam.github.io/2018/10/12/git-reference.html
   3. git 对象hashhttp://jingsam.github.io/2018/06/10/git-hash.html
   4. git 存储 http://jingsam.github.io/2018/06/15/git-storage.html

** TL; DR **

valgrind也可以画函数调用图！鹅妹子樱！

需要安装valgrind和kcachegrind

valgrind --tool=callgrind python xxx.py
kcachegrind

即可

如果kcachegrind实在编不出来（我就是）

可以考虑转成dot文件用graphviz处理

有gprof2dot工具 地址 单文件

python gprof2dot.py --format=callgrind --output=out.dot  callgrind.out.32281
dot -Tsvg out.dot -o graph1.svg

今天知乎上看到一个问题，问python pow是怎么实现的，首先想到的是dis看字节码

>>> import dis
>>> dis.dis(pow)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "/usr/lib64/python2.7/dis.py", line 49, in dis
    type(x).__name__
TypeError: don't know how to disassemble builtin_function_or_method objects

只能找翻源码，随手一搜，发现了个解答，利用valgrind找定义，真是个好方法，我以前都是直接翻代码，比较hardcore但是费时间。

网上介绍valgrind，都是什么内存检测工具，实际上还可以做profile, 也可以生成调用关系。

KDE我装了一下午！我曹！各种难装！kde开发太吃苦了吧，搭个环境这么费劲谁还愿意折腾！最后编kcachegrind提示缺少kde4！KDE4安装各种依赖我放弃。

找到了另一个生成图的解决方案，gprof2dot，不多说了

测试代码

for _ in range(10000000):
    pow(2,2)

按照上面的操作之后，画图如下

能看到调用到PyNumber_Power下面就没了。libpython2.7.so.1.0我用各种操作抓这个地址符号，都抓不到。

 readelf -Ws libpython2.7.so.1.0	#这个grep不到结果
 objdump -TC libpython2.7.so.1.0	#这个grep 地址得不到结果
 nm -gC libpython2.7.so.1.0 		#这个空的

代码在这https://github.com/python/cpython/blob/a24107b04c1277e3c1105f98aff5bfa3a98b33a0/Objects/abstract.c#L1030

没仔细研究，应该内部调用的还是glibc

伯努利算法，白努力大数定律

伯努利试验

硬币拥有正反两面，一次的上抛至落下，最终出现正反面的概率都是50%。假设一直抛硬币，直到它出现正面为止，我们记录为一次完整的试验，间中可能抛了一次就出现了正面，也可能抛了4次才出现正面。无论抛了多少次，只要出现了正面，就记录为一次试验。这个试验就是伯努利试验。

那么对于多次的伯努利试验，假设这个多次为n次。就意味着出现了n次的正面。假设每次伯努利试验所经历了的抛掷次数为k。第一次伯努利试验，次数设为k1，以此类推，第n次对应的是kn。

其中，对于这n次伯努利试验中，必然会有一个最大的抛掷次数k，例如抛了12次才出现正面，那么称这个为k_max，代表抛了最多的次数。

伯努利试验容易得出有以下结论：

1. n 次伯努利过程的投掷次数都不大于 k_max。
2. n 次伯努利过程，至少有一次投掷次数等于 k_max

最终结合极大似然估算的方法，发现在n和k_max中存在估算关联：n = 2^(k_max)

但这种算法，在小数据规模估算误差较大

修正1. LogLog求和求平均数 C*n*2^(∑k_max)/n

修正2. HyperLogLog 内部平均换成调和平均算法，C*n* n/ ∑1/2^k_max降低小数据误差

转化成实现模型

1. key转成bit串，视为一组伯努利试验

2. 分桶，视为n次伯努利试验

   在redis中一共有16384组，每组6个bit， 一共12k

3. 映射过程 一个key生成64位的bit串，分两部分，前14代表桶，2^14正好是16384，剩下50位的做试验,观测k_max保存到对应的桶中。50位对应最大的二进制110010，六位就能表达。

   1. 这就是pfadd的原理，pfcount就是按照公式计算
   2. 如果落到同一个桶，大则更新，否则不变

4. 和Log啥关系？上面公式中的C和p相关，其中p=log₂n

   switch (p) {
      case 4:
          constant = 0.673 * n * n;
      case 5:
          constant = 0.697 * n * n;
      case 6:
          constant = 0.709 * n * n;
      default:
          constant = (0.7213 / (1 + 1.079 / n)) * n * n;
   }
   

优化？

ref

• https://juejin.im/post/5c7900bf518825407c7eafd0
• 观察hyperloglog http://content.research.neustar.biz/blog/hll.html

一个开篇，把一些文章读完，争取写个sicp小demo出来。 鸽了

这是个巨坑，指望瞬间掌握是不现实的。只是期望把之前学到的东西重新复习一遍，串起来。同领域的概念总会走到一起，如果没有，那就是深度不够。

• Programming Languages: Application and Interpretation http://cs.brown.edu/courses/cs173/2012/book/
• 上面的中文版 https://lotuc.gitbooks.io/plai-cn/content/
• PLT理论书单 https://steshaw.org/plt/

引用一个答案 说的戳中我内心。

作者：啥玩应啊

链接：https://www.zhihu.com/question/36328468/answer/68011955

来源：知乎

著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

题主，请原谅我借你这个问题多说两句，有心的人看一看，我相信或许对这些人有些帮助，也算我在知乎的最后一答了吧（至少我现在是这么想的）。

很抱歉近段时间诸多邀请都没有回答，主要原因很简单，我不懂。你让我说，我东拉西扯的也能整两句，忽悠到几个赞和几个感谢刷个存在感，在虚拟的社会中聊以慰藉一下自己都鄙视的虚荣心，骗骗自己，骗骗时间。但仅仅这样我既帮助不了提问的人，又不能给自己带来真正分享的快乐（因为我真不懂啊，这就是为什么我非常羡慕R大），而且又因为我这么一个答案的更新或多或少刺激了一些关注者的多巴胺，让他们总期待知乎上马上会有一些有用的东西，而且他们总假设这些东西一旦能知道，就能掌握，继而就能成功。这样短时间还好，长时间后人是非常容易浮躁的。世界太大，知识领域太多，我只是个nobody，所以这些话就讲讲给自己小圈子的人听吧，那些关注题主这个问题的，PLT的人。

我相信在知乎关注PLT的人大多数都是年龄比我小的，而且有的小很多（我是一个快毕业的，在这个领域混的博士），很难能可贵的是在中国这样的环境中（我们的中国计算机学会CCF甚至连编程语言的专委都没有，是被软件工程专委代理行事的）看到这么一群年轻的同学对PLT感兴趣，想好好努力好好做。你们的热情和对知识的渴望深深地吸引到了我，加之我也想在知乎上交两个志同道合的朋友（很庆幸我交到了），所以我就在知乎里呆了几个月，说实话确实长了见识，但是同时也发现一些问题，我想借这个题目简单说一下，也算我为你们这些未来有着无限潜能的PLT界（或其他）的有用之材添一舀水吧。我虽资质平平，在知乎上比我牛的人多的太多，但是毕竟本人还算是一个愿意做自我检讨和总结的人，带过不少优秀的学生，在自己的小领域内做出过一些算是有用的贡献，所以下面的话不是妄谈，算是一点心得，主要讲给那些励志于在PLT中想做contribution的人。

PLT这么大，读过基本书的人自然大有人在，有的人一边读，一边敲，自然有多一层的收获。可是这，但凡目标明确些的、有点坚持的人都可以做到。你会发现这些人往往会搬运问题和答案，但是鲜有人会解决问题。典型的就是在知乎上科普上的解答，答案中的话虽都出于自己的理解，但是还是书中的话，传来传去的话，书的作者想让你知道的话。

想在PLT中做出贡献，要学会放弃，放弃你科普的时间，放弃你自己读科普书的时间。因为一旦你赤裸裸地面对一个真正的问题的时候，你会发现你其实懂的实在是很欠火候。你会发现你已有的知识树要倒过来重来一遍，一些叶子放大了，更绿了，一些平常在知乎讨论挣破皮的问题变的不值一谈了，但一些隐藏的枝干却被发现了，它们才是求解问题的关键，无论你指出它们的位置和重要性，还是自己添加枝干叶子，甚至把这颗树拔倒了，都是一种贡献。

不要想着现在只有多读书，读广书将来才会融汇贯通，你没有这个时间。在一个真正问题下暴露出来的知识，你一点点顺藤摸瓜找出的知识才是你的知识，这个问题是上下文，在这个上下文下说出来的见解的深度、清晰度才能标示着你在PLT中真正的水平，所谓论文也。

所以，你想在PLT做贡献，不要时间都花在读书读论文上。要读问题，悟问题，书和论文是工具，是参考，之前有一个大致的理解就够了。我拿自己举例，我读博之前自以为OO的一些设计已经有一定的理解了，本科时国内外OO设计和编程的书读的多，代码敲的也多，真东西也干过，自以为掌握一些真谛。博士期间当真正有一个问题的时候，从问题本身出发的时候才发现，自己懂的多么少，已有的知识只够在思路中游走，一个一个自认为熟悉的概念设计回到书中做确定然后从新理解，发现原来它们被设计成这样还会有这等好处（在书中未提及是因为现在的教材都是科普的，没必要那么深）。未有的知识却无从参考，自己想法设法自己定义它们理解它们，慢慢的发现这些自己定义设计的东西和XXX其他方向的XX概念是相似的，然后又找到相关书籍和论文不停的查阅、理解、讨论以精确确定自己的理解到底是多了几分，还是欠了几分，还是换种表达就是完全一样的。。。现在这个实际的PLT界中公开的棘手问题我相信我理解一些了，起码我贡献的用于解决它的方法是目前世界上最好的发表出来的方法。我没有读过很多PLT的书籍，甚至可以说是知乎里面懂PLT的人中读过PLT书最少的人之一了。但是通过真正问题的带动，我这一遭豁然开朗了很多。

你没法什么都懂，什么都懂又有什么用呢？真懂和懂的很多一定有一个平衡，PLT中的这些大师们也都是各有所长，都是通过一个个真的问题（例如好的论文的发表）带动自己对这一领域慢慢了解，慢慢贯通的，之后的书是他们写出来的，留给我们读的。你通过他的书和实现他项目的代码是成为不了他的。

读问题和悟问题固然重要，但前提是你得有一个好的问题。在知乎中PLT里我几乎看不到这样的好问题。怎么样找一个好的问题难，怎样精确地定义一个好的问题难上加难。鉴于我以上这些话都是说给那些日后励志给PLT做贡献的人听的，所以我假设你想要在研究上发力，例如读一个硕士或博士。如果你现在是本科，我建议你把基础打好，问一个题主这样的问题后，回去好好选两本书好好用功，少上知乎，虽然现在没有什么好的大问题要你提出解决，但是你在学一个东西的时候肯定有各种乱起八糟的小问题，这些问题之所以被问及往往是因为你是在看书不是在读书。每次读书前都带着目的去读，别想一下子就都吃懂，如果那些小问题跟你读书的目的（读当前这遍的目的）相关你就试着自己解决它理解它，不想关你就扔掉它。不要随便问问题，这个习惯不好。慢慢的，你了解了，你自然在专业上说话谈吐就不一样了，这样你申请一些好的学校的老师老师就能注意到你了，以后解决大问题的机会就更大了，我不相信一个老师跟姚培森这样的学生聊过后决定不要他，机会是自己的，自己努力争取吧。如果你已经是硕士或博士，那么就利用一下自己的老师和自己讨论一些要解决的问题吧，如果你的老师水平一般或不管你，你就看看国外好的研究组的基金和论文，结合一下自己的兴趣，起码大的方向不会差太多，但是也要注意避免竞争。

多读书，多敲代码，写几个编译器解释器就觉得把书和知识理解透了是一种经验性的偏见，如果单纯的想着这样就已经强过很多人了，能找个好工作受重视，这种大家都懂的、知乎里常说的方法倒不失为一种比较实际的手段。但是年轻人的价值怎么能用当前社会认可的价值来衡量呢，不为了多挣那么几万块钱，也不用为了给国家争口气，也不用为了给这个世界的知识库留下一点自己的贡献，就为了在知识中寻找一个无限可能的自我来慰藉这有限的生命吧。

实际上我说了这么多都是王明阳的“知行合一”。你看这句话谁都听过吧，谁都感觉自己懂那个意思吧，又有谁在做呢。“知”乎？不“行”怎知呼，“行”就让真正的问题去带动吧，少上网看热闹，快点踏踏实实动起来吧。

注：寥寥心得，一家之谈，不为争辩，但求知己者闻而有所明。

我最近这几个月，主要是在划水，没有明确目标的划水，然后在知乎上答题，瞎答强答，慰藉自己没有浪费时间。实际上就是上面说的，一种showoff，没看书没实践，还是粗人一个。怎么能就仅仅止步于此呢？

实际上我CS的概念基本都不熟，完全没有概念。需要补课的东西太多，干着急，紧张的划水着。

从这篇开始，争取真的多写点东西。不要在踌躇了。

也得把自己的 收藏夹整理一下。

参考

• crushhttps://zhuanlan.zhihu.com/p/58888246
• http://www.xuxiaopang.com/2016/11/08/easy-ceph-CRUSH/