GreenHatHGのBlog

前提：搞懂https://www.geeksforgeeks.org/extendible-hashing-dynamic-approach-to-dbms/ Whyhttps://15445.courses.cs.cmu.edu/fall2022/project1/ 待补充，可看原论文设计要点： Page Fault Access Memory/Disk Dynamic File Organization Balance Radix Search Tree Static & Dynamic Hash Concepts $h$: fixed hash function $K$: is a key $K’$: $h(K)$, also $pseudokey$. We choose pseudokeys to be of fixed length, such as 32 bits. The pseudokeys are of fixed length, the keys need not be. $I(K)$: is associated information:...

背景 链接：https://15445.courses.cs.cmu.edu/fall2022/project0/ 目的：因为后续的项目都是使用c++编写，所以提供一个入门c++项目给新手熟悉下。 要求：给出基本的代码框架，填充核心代码实现trie树的插入、查找、删除。最终要求为并发版本，但是不要求性能，所以可以一把大锁直接梭哈。 环境：使用clang-12，c++17标准 使用到的常见cpp知识点： unique_ptr管理内存资源 类的常见知识，比如构造函数，类方法等 rvalue与move shared_mutex trie树简单记录下trie树 作用又称前缀树或字典树，存储公共前缀字符串比较高效，一般用于字符串查找。 在项目中的应用是将(key, value)插入到trie树，类似hashmap的作用，但是使用trie树实现。 普通的trie树如下： 项目中要求实现的trie树： 上面是将(ab, 1)和(ac, “val”)插入到trie。注意项目中的value都是同类型的，这里是不同类型 结构给出的代码框架中总共有三个类 TrieNode：除了带有valu...

17-Virtual-Memory-ConceptsPhysical and Virtual Addressing Main memory: an array of M contiguous(连续的) byte-size cells(单元). Each byte has a unique physical address (PA) {0, 1, 2, 3 … } The most natural way for a CPU to access memory would be to use physical addresses. We call this approach physical addressing. When the CPU executes the load instruction, it generates an effective physical address and passes it to main memory over the memory bus. The main memory fetches the 4-byte wor...

18-Virtual-Memory-SystemsSimple memory system exampleAddress Translation Example #1 PPN实际不存在页表中 MMU做的第一件事是检查TLB，将VA中的VPN的TLBI(0x3)和TLBT(0x03)提取出来。所以会去查set3找到tag为3的line，找到对应的line并且valid为1，TLB将PPN(0D)返回给MMU MMU使用0D构建物理地址。将VA的VPO复制到PA的PPO，0D作为PA的PPN，由此构成了一个物理地址 将地址发送给cache，提取出CI(0x5)、CT(0x0D)，所以会去查set5找到tag为0xD的line，找到并且valid为1，因为CO为0，所以找到B0(36) cache将该字节通过MMU返回给CPU，并将其存到一个寄存器中。 Address Translation Example #2 VA中的VPN的TLBI=TLBT=0，TLB的set=0&tag=0的line的valid=0，TLB miss 通过VPN=0查找页表，valid=1有效，...

玩客云捡垃圾，40块钱还行，民间大佬弄出了刷Linux的方法，可惜是32位，不过也凑合用，比斐讯N1折腾了那么一点。 beancountbeancount介绍可以看下面几个文章，整挺好。之前是用ios端的Moze3，感觉还是差了点意思。 Beancount复式记账（一）：为什么 复式记账指北（三）：如何打造不半途而废的记账方案 使用 Beancount 管理家庭财务 · 构建我的被动收入 使用 Costflow 提高 Beancount 记账效率 bot-docker这里推荐使用kaaass/beancount_bot_costflow_docker，参考上面第二篇文章，里面有详细说明。不过上面的镜像只支持64位，只能自己弄32位的docker镜像。 Dockerfile从beancount_bot_costflow_docker的Dockerfile修改而来 12345678910111213141516171819202122232425262728FROM alpine:3.6WORKDIR /appADD requirements.txt /appENV PYTHONU...

来源：https://www.ardanlabs.com/blog/2019/05/garbage-collection-in-go-part2-gctraces.html 开关GC的对比有一个从不同的新闻提供商下载RSS并搜索的应用程序 在关闭GC的情况下测试并发请求应用程序耗时情况 12345$ go build$ GOGC=off ./project > /dev/null# 10k requests using 100 connectionshey -m POST -c 100 -n 10000 "http://localhost:5000/search?term=topic&cnn=on&bbc=on&nyt=on" 处理10k个请求需要4188ms，每秒处理约2387个请求 在开启GC的情况下呢， 123456$ GODEBUG=gctrace=1 ./project > /dev/nullgc 3 @3.182s 0%: 0.015+0.59+0.096 ms clock, 0.19+0.10/1.3/3.0...

来源：https://go.dev/talks/2012/concurrency.slide The boring function runs, like a boring party guest. 12345678910111213func boring(msg string) { for i := 0; ; i++ { fmt.Println(msg, i) time.Sleep(time.Duration(rand.Intn(1e3)) * time.Millisecond) }}func main() { go boring("boring!") fmt.Println("I'm listening.") time.Sleep(2 * time.Second) fmt.Println("You're boring; I'm leaving.")} A channel connects the main and bor...

来源：Go Concurrency Patterns: Pipelines and cancellation - The Go Programming Language What is pipeline receive values from upstream via inbound channels perform some function on that data, usually producing new values send values downstream via outbound channels Squaring numbers Generator Pattern converts a list of integers to a channel that emits the integers in the list 12345678910func gen(nums ...int) <-chan int{ out := make(chan int) go func() { for _, n := range nums{...

来源：https://www.ardanlabs.com/blog/2018/12/garbage-collection-in-go-part1-semantics.html Garbage collectors responsibility tracking heap memory allocations freeing up allocations that are no longer needed keeping allocations that are still in-use As of version 1.12, the Go programming language uses a non-generational concurrent tri-color mark and sweep collector. 非分代并发三色标记和扫描收集器 Collector Behaviorcollection工作会经历三个阶段 Mark Setup - STW(Stop The World) Marking - Concurrent Mark Termination - STW...

为什么要阅读这篇论文 cache coherence distributed transactions distributed crash recovery 三者的相互作用 整体的设计 a network file system，与现有的应用程序共同工作，类似普通的unix程序。可以将petal想象成一个磁盘，通过网络将数据共享给Frangipani，看起来就像从普通磁盘上读取数据 预期用途 一个文件系统，能保存自己的home目录以及共享的项目文件，在任何的workstation（可以理解是个人PC）能拿到自己的home目录以及所需要的所有文件。 没有涉及到安全问题，彼此电脑之间互相信任，适用于小群体 Frangipani的设计 强一致性 caching in each workstation — write-back 所有对文件的更新最初只是在workstation cache中完成—速度快 包括创建文件、目录、重命名等 比如ws1(workstation user 1)想要创建并读写/grades：Frangipani会从Petal读取/infomation的信息并保存...