Posts

All problems in computer science can be solved by another level of indirection. ...

终于结束了😊 ...

阳康复活，重拾实验！ ...

...

做完这个就专升本了😊 ...

刷leetcode的时候看到这么道题， 这个NestedInteger很明显组成了一棵树，并且我们只要输出叶子节点。于是一个DFS把所有元素抽成一个List，再生成一个迭代器在实现要求。 public class NestedIterator implements Iterator<Integer> { Iterator<Integer> iterator; List<Integer> list = new LinkedList<>(); public NestedIterator(List<NestedInteger> nestedList) { iterate(nestedList); iterator = list.iterator(); } public void iterate(List<NestedInteger> nestedList){ for(NestedInteger n : nestedList) { if (n.isInteger()){ list.add(n.getInteger()); } else{ iterate(n.getList()); } } } @Override public Integer next() { return iterator.next(); } @Override public boolean hasNext() { return iterator.hasNext(); } } 但是如果数据很大，我们又只要迭代一小部分满足条件的元素之后，就中止迭代，那么这种预加载的模式就会浪费时间在构造上，所以应该有一个懒加载模式。 用一个栈来存储迭代器，栈顶就是当前的迭代器。 public class NestedIterator implements Iterator<Integer> { Deque<Iterator<NestedInteger>> dq = new LinkedList<>(); Integer cur; public NestedIterator(List<NestedInteger> nestedList) { dq....

LRU是Least Recently Used的缩写，即最近最少使用算法。 插入时是最新的数据，如果缓存已满，要淘汰最旧的数据。 更新时把旧元素变为最新数据，无需淘汰。 读取时把元素变为最新数据，无需淘汰。 数组侧重读，链表侧重写。因为数组在删除插入非末尾元素的时候，需要调整余下元素的位置，所以链表会更合适。至于读，可以用哈希表提升性能。 链表和哈希表结合，这不就是java的LinkedHashMap么。LinkedHashMap会按put的顺序组织元素，链表头最旧，链表尾最新，LinkedHashMap有个accessOrder的属性，当为true时，访问元素的时候会把元素从原来的位置移除，放到链表尾，即最新的位置。因此如果要用LinkedHashMap实现一个LRU缓存，只需要给定一个容量，当元素超过这个容量的时候，把链表头（最旧）的元素移除就可以了。当然这只是一个idea，因为LinkedHashMap不是线程安全的，而缓存往往伴随多线程。 Guava的LRU 每个java程序员应该都用过Guava，guava的核心结构也是哈希表，为了线程安全，guava采用了segment分段的设计，而java8之前的ConcurrentHashMap也是采用分段来保证线程安全。 因此Guava的LRU是针对segment的，每个segment有自己的accessQueue,writeQueue,是两个双向链表，和哈希表本身结合，一个标准的LRU算法就呼之欲出了。 Redis的LRU redis作为一个内存数据库，内存弥足珍贵，我们可以在内存不足时设定几种淘汰策略，默认是不驱逐，而LRU是可选择之一。 redis维护的key数量之多，如果用双向链表和哈希来做LRU，占用额外的空间会比我们应用里实现一个LRU多的多。 因此redis采取的是不严格的LRU，LFU亦如是。 typedef struct redisObject { unsigned type:4; unsigned encoding:4; unsigned lru:LRU_BITS; /* LRU time (relative to global lru_clock) or * LFU data (least significant 8 bits frequency * and most significant 16 bits access time). */ int refcount; void *ptr; } robj; 在redis里，一个key对应一个redisObject，redisObject有个属性是lru，长度为LRU_BITS24位。 然后redis还自己维护了一个全局时钟。 struct redisServer { pid_t pid; char *configfile; // 全局时钟，他的取值是 mstime()/LRU_CLOCK_RESOLUTION) & LRU_CLOCK_MAX // LRU_CLOCK_RESOLUTION表示精度，默认是1s， // 所以这个取值每过 2^24 * 1s ≈ 194天 就会归零 unsigned lruclock:LRU_BITS; ....

补码是什么？记得C语言课本上写的，负数补码就是反码+1。很简单的一句话，但是讲的不明不白的。 为什么负数补码是反码+1？ 为什么正数的补码是其本身？ 为什么127下一个数是-128？ 下面拿一个字节来扯淡。 正数的编码是其本身 在计算机里，全部都是用补码表示数，补码就是一种对数的编码规则，一个二进制数就是一个code point，类似于unicode是一种字符的编码规则，一个code point可以对应一个真值。包括原码和反码，都是一种编码。所以这可以解答第二个问题，因为在补码里，我们把二进制0000 0000规定为0，最高位0的编码为正数，所以正数的补码是其本身，更确切的说法，在补码中，正数的编码是其本身。 所以8bit的范围是[-128,127]，当然我们可以规定8bit的范围是[-129,126]，或者[-127,128]这样做的后果就是：正数的编码不是其本身。 这会导致什么呢，我觉得这不会导致什么，无非就是对二进制认知会出现点问题，比如代码里写byte a = 1;，那么我们期望得到00000001，但是如果编码不是[-128,127]，那么我们声明的byte就不是我们期望的二进制序列——我们得按编码规则然后推出00000001对应的真值是多少，然后才能正确赋值。但是从计算的角度来说，只要编码确定了，计算就不会出错。 原码和反码 有很多谈补码的，有一个观点是补码是在反码的基础上设计出来的，再加上这句负数补码是反码+1，就似乎更是如此了。 但是这有点由果推因的味道。反码英文是1's complement，称“1补数”，补码是2's complement，称“2补数”，其中complement的意思就是补码（后续补码单指2's complement），所以这两种码应该是不能看作依赖关系的，只能说两者之间可以互相推导。 从原码开始说起，原码是这么编码的：最高位是符号位，0是正数，1是负数，其他表示绝对值。但是对计算机来说，还得判断最高位才能计算，不行🙅。 反码是最高位作为符号位，负数保留符号位1不变，剩下位按位取反。反码只是为了让符号位参与计算，计算结果和真值计算结果相比，时对时错，其中根本问题是有两个0（+0/-0），这需要通过循环进位的规则才能正确应用。 要正确应用反码，运算规则是，如果最高位产生进位，要把进位循环进位到最低位。比如0100 1000 + 1100 1000进行计算，结果是1 0001 0000，那么在模=2^8的情况下最终结果应该是0001 0001。我的理解是，最高位进位，说明越过了(+0/-0)，是少一个数的，需要+1来调整。 Internet协议IPv4，ICMP，UDP以及TCP都使用同样的16位反码检验和算法。虽然大多数计算机缺少“循环进位”硬件，但是这种额外的复杂性是可以接受的，因为“对于所有位（bit）位置上的错误都是同样敏感的”。 在UDP中，全0表示省略了可选的检验和特性。另外一种表示：FFFF，指示了0的检验和。 （在IPv4中，TCP和ICMP都强制性地规定了检验和，而在IPv6中可以省略）。 补码 补码系统利用了模的思想，模就是用来表示一个计数范围，比如⏰的计量范围是0～11，模=12。二进制0000 0000～1111 1111的模就是1 0000 0000。 上面说到模，补码系统就是这么规定：一个数和他的二补码之和等于模。在8位数中，1 0000 0000和0的值是等价的，所以一个数和他的二补码之和等于0，那么，一个负数在补码系统里可以用正数的二补码来表示。同时可以得出一个结论，求一个数的相反数，只要求他的二补码就好了。 由于n的二补码=(模 - n)=(1 0000 0000 - n)=1 + 1111 1111 - n，1111 1111 - n刚好又是按位取反，是反码，所以一个数的二补码是反码+1。但这只能作为一个定理，不能作为定义。-128不适用“负数补码是反码+1”，但是，在补码系统里，这个数却是存在的。事实上，-128的二补码等于其本身。 编码是有序的 在我看来，二进制没有正负之分，这个正负是人为加上去的，机器并不需要知道当前的数的正负。他只要拿到0000 1000和1111 1101相加，得到0000 0101，那么这个0000 0101是表示什么，机器不感兴趣。所以说即使8bit的范围变成[-129,126]或者[-127，128]，也不影响结果，只要编码是有序的，二进制计算法则总能保证结果是正确的（当然，这就不是补码了）。 这里的有序，指的是二进制的顺序和真值的顺序是一致的。比如不可以规定{01111 1111,0111 1110,...,1000 0001,1000 0000}对应[-128,127]，这样二进制顺序和真值顺序不一致。 像原码，-15 -> -14，其编码1000 1111->1000 1110，这是不按顺序的。反码大致保证了顺序，但是存在两个0的code point，需要引入额外的调整才能消处两个0的问题。...

如果要在redis查找遍历key，keys命令会阻塞，是不能用的，这时就要用scan命令。 scan命令支持传入cursor、match pattern、count、type(6.0新增type)，根据游标，返回count数量的符合条件的key，以及新游标。注意这个count只是一个期望值，看源码就知道为什么不是确切值。 db是由dict组成的，set、hash、ziplist也是有dict类型的，dict发生扩容和缩容的话，如果按自然数的方法去遍历，扩容会重复遍历，缩容会遗漏遍历。 假设dict稳定状态下，dict size从8变成16，刚访问过index为3的桶，接下来就应该遍历4-15桶，由于原先0-3号的桶的key有一部分挪到8-11中（+8），后面就会重复遍历到。 假设dict size从8变成4，刚访问过index为3的桶，那么接下来就是遍历结束了，这样原先4-7号的桶就会漏掉（-4）。 如果在扩容缩容情况下，需要遍历两条数组，同样会遇到上面的问题。 看看redis是怎么解决的。 redis不采用自然数顺序遍历，而是采用高位顺序遍历，也就是对游标前进的方式是酱紫的：用对应数组的掩码将游标的值截断（准确地说不是截断，可以先用截断理解） —> 左右翻转 -> 自增 -> 左右翻转回来。 这个算法的原理是，数组扩容是*2，那么每次扩容，旧数组的元素哈希值& new_mask得到下标，要么在原来的桶，要么是原来桶的index*2，具体表现为最高位分别是0和1。那么从高位起开始遍历的话，如果去掉最高位，其实遍历的顺序和旧数组是一样的。 举个例子， 原来的顺序是 000 100 010 110 那么扩容后，顺序是 (0)000 (1)000 (0)100 (1)100 (0)010 (1)010 (0)110 (1)100 括号里就是最高位，去掉最高位，和原来的数组是一致的。 遍历实现 代码基于6.0，主要分为两部分，一部分是dict非rehash状态，一部分是rehash状态。 // 这个函数将游标v的元素放到privdata，并用算法推进cursor， unsigned long dictScan(dict *d, unsigned long v, dictScanFunction *fn, dictScanBucketFunction* bucketfn, void *privdata) { dictht *t0, *t1; const dictEntry *de, *next; unsigned long m0, m1; if (dictSize(d) == 0) return 0; /* Having a safe iterator means no rehashing can happen, see _dictRehashStep....

两阶段提交 innodb和bin log需要进行两阶段提交(Two-Phase Commit Protocol，2PC)，目的是为了保证日志一致性，要么都存在，要么都不存在。 要说明的是，两阶段提交不止redo log和binlog有关，undo log也是参与者。 XID是事务根据事务第一条query生成的id，通过XID将redo log和binlog关联起来。在上一篇的binlog日志里也能看到XID的身影。 两阶段提交，其实就是innodb prepare，写binlog，innodb commit； 具体是， prepare阶段，redo log写入根据事务提交时的刷盘策略决定是否刷盘，然后将log segment(不是回滚段！！！)标为TRX_UNDO_PREPARED；binlog不做任何事 commit阶段，binlog写入binlog日志；接着innodb将修改undo log segment状态，并在redo log写入一个commit log。 如果没有两阶段提交，redo log和binlog各写各的，中间发生崩溃，就会出现不一致的情况。 先写binlog，再写redo log：如果redo log没写成功，就会造成崩溃恢复的时候，主库没有、从库有的情况，主从不一致。 先写redo log，再写binlog：如果binlog没写成功，就会造成崩溃恢复的时候，主库有、从库没有的情况，主从不一致。 说白了，为了保证事务，总是得做一些冗余的操作，例如tcp多次握手挥手，都是通过冗余操作来保证两个业务之间一致。 redo log和binlog顺序不一致的问题 两阶段的提交不只如此，如果只是像上面那样，还会出现主从不一致的情况。 热备问题 T1 (--prepare--binlog[pos100]--------------------------------------------commit) T2 (-----prepare-----binlog[pos200]----------commit) T3 (--------prepare-------binlog[pos300]------commit) online-backup(----------------------------------------------backup------------) 假设3个事务如上，那么 redo log prepare的顺序：T1 --> T2 --> T3 binlog的写入顺序： T1 --> T2 --> T3 redo log commit的顺序： T2 --> T3 --> T1 可以看到redo log提交的顺序和bin log不一致了，这是不允许的，会导致主从不一致。 online-backup表示热备，因为从库在建立的时候需要对主库进行一次备份。当T2，T3提交后，这时热备来读位置，读到最后一个提交的事务T3，由于这个阶段不是读binlog的，所以T1没有被复制到，接下来的binlog复制从T3开始，所以会漏掉T1的数据。 复制问题 《MySQL5.7 核心技术揭秘：MySQL Group commit》（见参考）举了一个例子，就是有一行数据，x=1，y=1 T1:x=y+1,y=x+1; T2:y=x+1,x=y+1;...