ARC Cache算法

ARC(Adaptive Replacement Cache)是一种适应性Cache算法, 它结合了LRU与LFU。 LRU(Least recently used) 其核心思想是:假设刚visit的item,很有可能在未来被revisit 丢弃最近最少访问的items 通常用双链表实现 tips: redis并没有这样做,因为这样每个key至少会多出两个指针。 redis采用的是一种近似LRU,基本思想是随机取出一些key,形成一个小的POOL,然后在pool中采用LRU策略(相关源码:redis/src/evict.c) 缺点:忽略了frequency, 不适合大规模扫描等情况 LRU有一系列变种,比如LRU2, 2Q, LIRS等。 LFU(Least-frequently used) 其核心思想是:假设visit次数越多的item,很有可能在未来被revisit 适应大规模扫描 对热点友好 缺点:忽略了recency, 可能会积累不再使用的数据 tips: redis4.0开始支持了LFU,例如volatile-lfu, allkeys-lfu配置选项 ARC 整个Cache分成两部分,起始LRU和LFU各占一半,后续会动态适应调整partion的位置(记为p) 除此,LRU和LFU各自有一个ghost list(因此,一共4个list) 每次,被淘汰的item放到对应的ghost list中(ghost list只存key), 例如:如果被evicted的item来自LRU的部分, 则该item对应的key会被放入LRU对应的ghost list 第一次cache miss, 则会放入LRU 如果cache hit, 如果LFU中没有,则放入LFU 如果cache miss, 但在ghost list中命中,这说明对应的cache如果再大一丁点儿就好了: 如果存在于LRU ghost list, 则p=p+1;否则存在于LFU ghost list, p=p-1….

ethereum源码分析 – 主流程

主要入口 cmd/geth/main.go/main() 线程与协程 dlv threads 查看,19个左右线程 dlv goroutines 查看,91个左右协程 主流程 (a) init: app.Before 主要是加载环境, 配置Cache,GC参数, 启动测量等 (b) main: app.Run -> app.Action -> geth() (1)创建Node (2)启动Node (3)Node等待结束 创建Node和启动Node为核心流程。 创建Node: (1)RegisterEthService: Light, Fast, Full模式 les.New(): 轻量级 eth.New(): db,blockchain,network,mine,rpc等创建或打开 (2)RegisterDashboardService 用来监视状态 (3)RegisterShhService Whisper, 用于DApps之间通信 (4)RegisterGraphQLService 用于explore (5)RegisterEthStatsService 用于状态统计 其中(2)-(5)根据配置可选。 启动Node: (1)启动创建Node时注册的服务 (2)创建RPC client (3)钱包及钱包事件 (4)启动挖矿 (c) app.After 关闭程序

C++线程安全分析

C++线程安全分析 除了通过code review或者test来检测线程安全,有没有其它更好的办法? 答案是存在的,通过clang即可以进行这种检测,编译器对存在的线程安全问题会给出警告。 这种分析方法由Google开发,已经被Google大规模应用,参考 https://static.googleusercontent.com/media/research.google.com/zh-CN//pubs/archive/42958.pdf 示例example.cpp: #include “mutex.h” class BankAccount { private: Mutex mu; int balance GUARDED_BY(mu); void depositImpl(int amount) { balance += amount; // WARNING! Cannot write balance without locking mu. } void withdrawImpl(int amount) REQUIRES(mu) { balance -= amount; // OK. Caller must have locked mu. } public: void withdraw(int amount) {…

bitcoin源码分析 – 交易验证

Transaction — Verify 交易验证是bitcoin的核心逻辑之一。交易验证包含两个问题: (1)验证的时机 (2)如何验证。 when and where 交易 区块 how AcceptToMemoryPoolWorker VerifyScript when and where 交易 当交易即将放如交易内存池中时, 将进行交易的验证。 调用时机: init(即程序启动时): LoadMempool 交易消息: NetMsgType::TX Wallet: (1)CommitTransaction (2)ReacceptWalletTransactions (3)ResendWalletTransactionsBefore UpdateMempoolForReorg AcceptToMemoryPool函数调用栈如下: AcceptToMemoryPool: AcceptToMemoryPoolWithTime AcceptToMemoryPoolWorker CheckInputs VerifyScript 其中AcceptToMemoryPoolWorker交易验证最核心的函数。 区块 (1)当ConnectBlock(新块产生或收到新块)时, 会对区块包含的所有交易进行验证。 init: CVerifyDB::VerifyDB(需checklevel4,默认为3,故默认不执行) TestBlockValidity(miner.cpp里BlockAssembler::CreateNewBlock调用) CChainState::ConnectTip 部分代码如下所示: CChainState::ConnectBlock: for (unsigned int i = 0; i < block.vtx.size();…

bitcoin源码分析 – 区块操作

Block — 操作 区块产生 区块网络消息 区块回滚 区块序列化 区块产生 ProcessNewBlock 区块网络消息 区块回滚 (1) init: ReplayBlocks (2) ActivateBestChain() ActivateBestChain() ActivateBestChainStep() chainActive.FindFork // Disconnect active blocks which are no longer in the best chain. DisconnectTip DisconnectBlock UndoReadFromDisk // Build list of new blocks to connect. ConnectTip ConnectBlock WriteUndoDataForBlock 孤立块保留多长时间? setBlockIndexCandidates 区块序列化