最近我开发了一个接口，这个接口需要从 Redis 上读取一系列规则，判断请求是否满足这些规则。服务使用 Java 开发，垃圾回收器选择了 G1。由于请求量很大，且用户对性能要求较高，查询延迟（TP999）必须尽可能低。 每次请求最多会读取 5 条规则，也有可能读取不到规则。每条规则的形式是一个 Map，且比较大，每个 Map 大约 1 到 2 KB。规则数量非常庞大，并且会有更新操作，因此将所有规则全部做成本地缓存是不现实的。我们估算，大部分请求会读取 2 到 3 条规则，只有极少部分请求会读取 5 条规则（我们通过布隆过滤器来快速判断并拦截那些会读取 5 条规则的请求，从而减少查询时间）。 为了尽量减少查询延迟，我们考虑过一种方案，即提前将请求可能用到的所有规则（最多 5 条）通过 mget 一次性加载到内存中。这样，无论请求最终读取多少条规则，都能以较低的延迟完成查询，虽然加载 5 条规则的时间略长一点。但这种做法的缺点是，无论请求最终需要多少条规则，都会预先加载 5 条规则，这些规则的生命周期仅限于一次请求。如果请求量很大，频繁的内存分配可能会导致 GC 增加，甚至触发 G1 的 MixedGC，从而引发 STW（Stop-the-World）。 如果不提前加载规则，每次请求最多需要读取 5 条规则时，就会调用 5 次 Redis 请求，导致查询延迟增大，TP999 的表现就不好了。 这个问题困扰了我一段时间，不过现在我已经想通了。我的结论是，“提前加载所有需要的规则”。因为 GC 问题可以通过水平扩容来解决，而 TP999 的问题，只有通过提前加载所需的规则才能根本解决。 使用 Java 这种有垃圾回收机制的语言，追求单机的极致性能其实是一个伪命题。虚拟机和垃圾回收器的存在意味着，不管怎么优化，也不可能达到顶级稳定的性能。Java 的优势在于减少了开发的复杂度，避免了过多的性能调优工作。对于单机性能，我们只需要确保性能不至于太差，而在流量压力大的情况下，可以通过水平扩容来解决。如果为了 GC 优化而不提前加载规则，那么每个请求的 TP999 延迟很难通过外部手段来解决，也无法通过水平扩容来解决。 因此，我认为，业务开发中应该进行性能优化，但优化要适度。因为业务代码可能会在半年内被重构或删除，而根据用户体验法则，响应时间超过 150ms 会让用户明显感到不适。如果真的需要追求极致性能，应该优先考虑选择高性能的语言和框架，而不是在现有的技术栈上做过度的调优。

我在用Rust写一个JVM，整个项目从三个月前开始准备，查阅了大量的资料，也写了不少代码做试验，直到最近才走上正规，进入了稳定的开发阶段。 其中最困扰我的是如何设计DcVm的内存模型来表达Java的对象，我在之前没有用C++、Rust这种无GC的语言系统性的写过大项目，也没有过编写虚拟机或者语言解释器的经验，这部分着实花了我很久才找到一点头绪。 一开始的时候，我打算照搬KiVM的设计，KiVM是用C++编写的JVM，使用了一种简化的oop-klass模型。然而我在使用Rust编写时，发现照搬oop-klass模型实在是太复杂了，非常难以实现。oop-klass模型使用了大量的继承关系，并且oop-klass之前有引用的关系。官方也提到这种模型的实现里面有历史原因，比如markOop不是一个oop。我希望DcVM是一个简单的、优先考虑可读性而不是性能的教学用的JVM（未来打算进行可视化），所以我不想在新实现的时候还要背负hotspot这种成熟的、性能高的的JVM的复杂实现。 然后我又去研究了rjvm的设计，rjvm使用Rust编写的Jvm，它的实现是类似与解释性语言的虚拟机实现，在底层通过复杂的指针操作，将类型信息直接写入内存，这在写简单的解释型语言的虚拟机时是个场景的做法，但是Java的字节码里是有类型信息的，底层这种大量的指针操作使得代码很不直观，作者也对这部分实现不满意。 百思不得其解时，我读到了Writing Interpreters in Rust: a Guide这边教程，这个教程并不是写JVM的，而是教如何写一个解释型语言的虚拟机实现的。代码很好，让我学到了很多rust的使用方式，我尝试使用其中TaggedPtr, FatPtr, ScopterPtr, TaggedScopterPtr, RawPtr各种Ptr来表示我的底层实现。我发现这太复杂了，我大部分实现都在思考用什么Ptr，这些ptr在教程里的好处是在虚拟机实现的时候写代码在编译期能拿到类型，但这只使用与解释型语言，因为他们的类型是固定的几种，而Java是可以自定义类型的。 最终，我决定简化oop-klass模型，将oop始作数据的存储区，将klass始作算法的存储区，DcVM的类型分为三类：原始类型、instance和Array, 原始类型是int、long这些，而Instance是自定义的类型，每个instanceOop会指向一个instanceKlass(虚拟机运行时同一个类可以很多个oop， 但只能有1个klass), Array是个递归的结构（里面可以存Array, Instance或原始类型）。整体的实现目前没有使用裸指针，先用typed_arena做了简单的内存分配(后面要自己写内存分配器和垃圾回收), 所以代码里有大量的引用的生命周期参数。目前我简单的将所有的生命周期都写成一样的，后续对生命周期理解深入了之后需要做一下优化。

陈丹青说他那个年代的人都很憨，现在人不够憨，一开口就知道你这个人想要骗我。 的确如此，虚伪的人越来越多。虚伪的定义太哲学，以致于说道虚伪，并没有什么特别的感受，只是有一个这个人不是很好的印象。 把虚伪具体点讲，一个人一张口就知道他是想要骗我。虚伪的人的赞美，就像他抽烟后吐出的烟圈，虚无缥缈，毫无穿透力，你能感觉的到他虚伪的赞美是无力的，只能在屋子里转悠，进入不了任何人的内心。 这个资本的世界，虚伪的人越来越多，总是想着去欺骗，去忽悠别人，把真相隐藏起来，不真诚。和别人对话目的性太强，就是想要获得利益，没有利益的事不做，只想着去收割其他人。 希望在这种世界里，我仍能够保持纯真，不愿意做虚伪的人，虚伪的人活不长久也不会过的开心，每天勾心斗角，也不会有真正的朋友。

SECTIONS { . = 0x80000; /* Kernel load address for AArch64 */ .text : { KEEP(*(.text.boot)) *(.text .text.* .gnu.linkonce.t*) } .rodata : { *(.rodata .rodata.* .gnu.linkonce.r*) } PROVIDE(_data = .); .data : { *(.data .data.* .gnu.linkonce.d*) } .bss (NOLOAD) : { . = ALIGN(16); __bss_start = .; *(.bss .bss.*) *(COMMON) __bss_end = .; } _end = .; /DISCARD/ : { *(.comment) *(.gnu*) *(.note*) *(.eh_frame*) } } __bss_size = (__bss_end - __bss_start)>>3; 每个链接脚本都需要有SECTIONS，每个SECTIONS里面可以定义多个secname，比如示例里的....

分为两个问题，一个是为什么创建HashMap时的容量都是2的幂次方，第二个是为什么扩容时是扩大两倍。 容量为2的幂次方 目的是为了更快的取模，假设容量为N，哈希值是hash，如果N是2的幂次方，则hash % N = hash & (N - 1) 2的幂次方的二进制表示，只有最高位是1，其他位都是0，2的幂次方减一的二进制表示则全部是1。 hash & (N -1)本质上是只保留hahs的末尾几位，得到的结果一定小于N, 在0到N-1之间。 扩容扩大两倍 扩大两倍可以保证原有的元素要么保持在原来的索引上，要么移动到原索引加N的位置，可以保证数据在扩张后的分布不会变得更差。 首先map的容量都是2的幂次方，那么扩大两倍，本质上就是在取模的时候多保留一位，那么原来的哈希值如果上一位是0，则扩容后取模的结果不会变，如果上一位是1，那么扩容后取模的结果就是二进制数最前面加上1 在二进制最高位+1，相当于十进制里+N，比如从16扩大到32，那么相当于本来取4位，变成取5位，取5位相当于在原来的索引上+16 举个例子: hash值是110010，此时map的大小是16，那么取后4位，0010做索引，也就是2 扩大两倍后（总大小是32），取后5位，也就是10010做索引，结果是18 扩大两倍后会不会有在扩容前没有hash冲突的两个hash值，扩容后hash冲突了 按照上文的结论，扩容后，原来hash值要么还在原来的索引上，要么在原来的索引+N的位置上（N是扩容前的大小） 两个索引（在扩容前不冲突）在扩容后只可能有3种情况： 两个索引位置都不变，那么扩容后也不会有冲突 两个索引的位置都+N，那么也不会有冲突 一个索引变化，另一个不变化 第三种情况，有没有可能出现，扩容前不冲突，扩容后冲突的情况。因为扩容后，索引要么不变，要么+N，如果想要扩容后发生冲突，那么需要两个hash值，为hash1，hash2 假设 hash1与hash2在扩容前不冲突，扩容后冲突。 则一定有: hash1在扩容后+N，hash2扩容后不移动 扩容前hash2的索引正好比hash1大N 扩容前取模运算保留低位的n位，而扩容后保留n+1位， 因为hash1在扩容后+N，说明hash1的第n+1位是1，而hash2扩容后不移动，说明hash2的第n+1位是0， 扩容前hash2的索引正好比hash1大N, 就需要hash2的索引的低n-1位和hash1的索引的低n-1位相同。并且hash2的索引的第n位是1，hash1的索引的第n位是0 那么我们会得到 n+1 n 相同的低位 hash1: 1 0 XXX hash2: 0 1 XXX 因为hash1和hash2的低n+1位不完全一致，所以扩容后取n位hash1和hash2不可能落到一个索引上，假设不成立。

操作系统的职责之一是直接操作硬件并暴露更好用的接口给应用程序。操作系统直接操作的众多硬件中，就有内存。 内存需要通过地址来访问，直接访问内存的地址是物理地址。如果每个应用程序直接使用物理地址存放并读取自己的数据，会有很多问题（最典型的是程序A可以修改程序B的数据）。 所以操作系统对应用程序屏蔽了物理地址，应用程序只能使用虚拟地址来存放并读取自己的数据。操作系统拿到应用程序想要使用的虚拟地址，转化为物理地址做实际的存储，所以操作系统承担了一个中间人的身份。 假如我们需要操作一块512GB的内存，并且我们使用64bit的虚拟地址（也就是指针的大小是64bit）。512GB是2^39字节，也就是说有2^39个地址需要表示。如何用一个64bit的指针，去表示2^39个地址，是一门学问。有一种表示的方案叫做Sv39, Sv39只使用到了39个bit, 其他的bit用于拓展等用途。 操作系统在做虚拟地址到物理地址的转化，本质上操作系统需要在内存中维护一个哈希表，这个哈希表当然越小越好，接下来所述的各种方案和优化，目的都是为了让这张哈希表更小。 一个虚拟地址，经过这个哈希表，可以拿到一个物理地址。（当然实际的编程中，不是使用常见的哈希表，会有一些编程技巧）。 首先我们使用2^27个PTE，每个PTE用一个字节表示，那么2^27个PTE一共占用128MB，这么多PTE合在一起叫做Page Table。128MB确实大，后面会做优化。现在来看这种情况如何使用。 虚拟地址中的27位地址交给PTE后，可以拿到一个PPN，PPN+虚拟地址中的offset（大小是12位）可以拼接得到物理地址。虚拟地址中的offset实际上是一个页的大小，留offset实际上是部分保留了应用程序中的代码和数据的相对位置。如果不考虑Page Table的大小, offset为0的话, 代码位置自由度是最高的，实际上是操作系统去安排所有应用程序的每一个代码和数据的物理地址位置，也可以做到没有任何内存碎片， 但是代价太大了， 本质是内存只能用一半，另一半全放Page Table了。如果offset设置和物理地址一样大, 那操作系统控制不了应用程序代码直接的相对关系，只能同时服务一个应用。 如果512GB的内存中都要使用128MB来做虚拟地址到物理地址的转化，实在是太浪费了。可以使用三级缓存，也就是一级Page Table找到二级Page Table, 二级Page Table找到三级，三级找到物理地址。 这个实现思路很多人都能看懂，但是为什么这样可以节省内存？ 首先，三级缓存的所有页表不可能同时都放到内存里，如果整个三级缓存的所有页表都出现，那需要2^9 + 2^9 * 2^44+2^9 * 2^44 * 2^44个PTE，也就是1.5845633e+29这么多的PTE。显然装不下。首先，确认的是如果要使用三级缓存寻址512GB的内存，1.5845633e+29这么多的PTE中的每个页表是都有可能出现的，但是我们也能确定，这么多页表不可能同时出现，甚至大部分时候就使用3到4张。这个结论的论据也比较简单，程序的局部性原理。运行过程中如果一些页表不需要使用了就可以下掉了。这相当于火车运行时，一直从火车后把铁路放到火车前面，这样总体的铁路长度就很短。 每个2^9的page table占0.5KB，如果一个进程占用的地址不超过2^21也就是2M（一张页表9bit, offset12bit），那只会分配1.5KB的page table，每大于2M会增加0.5KB的页,每多2^30既1GB（1+9+12），会多分1kb，这几乎很小很小了。

前言 Mysql的事务机制，各类书籍博客上都讲了很多，八股文也基本都有，但是我属于不实践都搞不懂的笨蛋，所有本文来通过实践理解mysql的四个事务级别。 mysql安装（已经安装的可以跳过） 首先安装mysql，我使用的是Mac，安装mysql很简单。 brew install mysql 接着执行 brew services start mysql启动mysql 因为只是在本地测试，直接使用mysql -u root登录就可以 本文的目的是想要实践mysql的事务，为了更加直观的操作，所以不使用额外的客户端操作mysql，但是直接使用终端比较麻烦，所以我推荐安装mycli 在Mac上的安装也很简单，brew install mycli 这时就可以使用mycli -u root连接mysql了 测试数据准备 本文的测试数据使用官方的测试数据集, 按照readme文档，设置数据就好。 开始研究 首先执行select * from employees limit 10;看一下有那些数据。 ANSI SQL标准定义了4种隔离级别。 READ UNCOMMITTED READ COMMITTED REPEATABLE READ SERIALIZABLE READ UNCOMMITTED 如其名所描述，这种数据库隔离级别的特征肯定是读到uncommitted的数据。首先我们打开不同的终端，开启两个数据库连接。在两个数据库终端中设置当前会话的事务提交类型为READ UNCOMMITTED SET SESSION TRANSACTION ISOLATION LEVEL READ UNCOMMITTED; 接着在两个数据库连接中都开启事务 start transaction; 首先，我们在两个事务中都查询一下编号为10002的员工的性别。 select * from employees where emp_no = '10002'; 打开第三个终端，查询当前事务的状态。 SELECT * FROM INFORMATION_SCHEMA.INNODB_TRX\G 当前，有两个事务，分别是281479414878104和28147941487731，他们的事务级别也都是READ UNCOMMITTE，值得注意的是trx_weight这个字段。InnoDB目前处理死锁的方式是将持有最少行级排他锁的事务回滚。为了解决死锁,InnoDB 选择一个小的权重的事务来回滚。...

给定一个矩阵, 通过for循环可以有多少种遍历方式以及各种遍历方式的方向是怎么样的? 给定矩阵比较抽象, 我们举一个更具体的例子: 给定一个字符串"babad", 有多少种不同的遍历方式?各种遍历方式的遍历方向又是什么样子的? 右斜遍历 s = "babad" n = len(s) for L in range(n): for i in range(n): j = i + L if(j >= n): continue print((i,j))

力扣 931. 下降路径最小和 是一道经典的动态规划题，但是我卡在了边界问题上。 如何优雅的处理col为0和col为n-1的情况。 dp[row][col] = min(dp[row-1][max(col-1,0)], dp[row-1][col], dp[row-1][min(col+1,n-1)]) 通过max和min来约束边界。