vampire`blogs

redis cluster集群hash slot算法 redis cluster有固定的16384个hash slot，对每个key计算CRC16值，然后对16384取模，可以获取key对应的hash slot redis cluster中每个master都会持有部分slot，比如有3个master，那么可能每个master持有5000多个hash slot hash slot让node的增加和移除很简单，增加一个master，就将其他master的hash slot移动部分过去，减少一个master，就将它的hash slot移动到其他master上去 移动hash slot的成本是非常低的 客户端的api，可以对指定的数据，让他们走同一个hash slot，通过hash tag来实现

垃圾回收器简介 Serial和Serial Old垃圾回收器：分别用来回收新生代和老年代的垃圾对象 工作原理就是单线程运行，垃圾回收的时候会停止我们自己写的系统的其他工作线程，让我们系统直接卡死不动，然 后让他们垃圾回收，这个现在一般写后台Java系统几乎不用。 ParNew和CMS垃圾回收器：ParNew现在一般都是用在新生代的垃圾回收器，CMS是用在老年代的垃圾回收器，他 们都是多线程并发的机制，性能更好，现在一般是线上生产系统的标配组合。 G1垃圾回收器：统一收集新生代 和老年代，采用了更加优秀的算法和设计机制，是下下周的重点，一周都会来分析 G1垃圾回收器的工作原理和优缺点。 最常用的新生代垃圾回收器：ParNew ​ 通常大家线上系统都是ParNew垃圾回收器作为新生 代的垃圾回收器 当然现在即使有了G1，其实很多线上系统还是用的ParNew。新生代的ParNew垃圾回收器主打的就是多线程垃圾回收机制，另外一种Serial垃圾回收器主打的是单线程垃 圾回收，他们俩都是回收新生代的，唯一的区别就是单线程和多线程的区别，但是垃圾回收算法是完全一样的。使用“-XX:+UsePa ...

leetcode-376. 摆动序列 1234567891011121314151617181920212223242526272829class Solution { public int wiggleMaxLength(int[] nums) { int n = nums.length; int[][] dp = new int[n+1][2]; if(n==0){ return 0; } // 表示前面是下降 dp[1][0] = 1; // 表示前面是上升 dp[1][1] = 1; for(int i = 2; i <=n; i++){ if(nums[i-1]>nums[i-2]){ // 上升 dp[i][1] = dp[i-1][0] + 1; ...

leetcode-55. 跳跃游戏 12345678910111213class Solution { public boolean canJump(int[] nums) { int n = nums.length; int idx = nums[0]; for(int i = 0; i <= idx; i++){ idx = Math.max(idx, i + nums[i]); if (idx >= n - 1) { return true; } } return false; }}

redis哨兵底层原理 1、sdown和odown转换机制 sdown和odown两种失败状态 sdown是主观宕机，就一个哨兵如果自己觉得一个master宕机了，那么就是主观宕机 odown是客观宕机，如果quorum数量的哨兵都觉得一个master宕机了，那么就是客观宕机 sdown达成的条件很简单，如果一个哨兵ping一个master，超过了is-master-down-after-milliseconds指定的毫秒数之后，就主观认为master宕机 sdown到odown转换的条件很简单，如果一个哨兵在指定时间内，收到了quorum指定数量的其他哨兵也认为那个master是sdown了，那么就认为是odown了，客观认为master宕机 2、哨兵集群的自动发现机制 哨兵互相之间的发现，是通过redis的pub/sub系统实现的，每个哨兵都会往__sentinel__:hello这个channel里发送一个消息，这时候所有其他哨兵都可以消费到这个消息，并感知到其他的哨兵的存在 每隔两秒钟，每个哨兵都会往自己监控的某个master+slaves对应的__sentinel__: ...

redis异步复制、集群脑裂 1、两种数据丢失的情况 主备切换的过程，可能会导致数据丢失 （1）异步复制导致的数据丢失 因为master -> slave的复制是异步的，所以可能有部分数据还没复制到slave，master就宕机了，此时这些部分数据就丢失了 （2）脑裂导致的数据丢失 脑裂，也就是说，某个master所在机器突然脱离了正常的网络，跟其他slave机器不能连接，但是实际上master还运行着 此时哨兵可能就会认为master宕机了，然后开启选举，将其他slave切换成了master 这个时候，集群里就会有两个master，也就是所谓的脑裂 此时虽然某个slave被切换成了master，但是可能client还没来得及切换到新的master，还继续写向旧master的数据可能也丢失了 因此旧master再次恢复的时候，会被作为一个slave挂到新的master上去，自己的数据会清空，重新从新的master复制数据 2、解决异步复制和脑裂导致的数据丢失 min-slaves-to-write 1 min-slaves-max-lag 10 要求至少有1个slave， ...

1123. 最深叶节点的最近公共祖先 原始思路： 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556class Solution { LinkedList<TreeNode> queue = new LinkedList<TreeNode>(); HashSet<TreeNode> deepSet = new HashSet<>(); TreeNode ans; boolean bool = true; public TreeNode lcaDeepestLeaves(TreeNode root) { search(root); ans = root; dfs(root, new HashSet<TreeNode>()); return ans; } ...

31. 下一个排列 123456789101112131415161718192021222324252627282930313233343536373839404142434445class Solution { public void nextPermutation(int[] nums) { int n = nums.length; if (n <= 1){ return; } boolean b = true; for (int i = n-1; i >= 0 ; i--) { // 选出比nums[i]大的最小的index int k = -1; for (int j = i+1; j <= n - 1 ; j++){ if (nums[j] > nums[i]){ ...

redis replication的原理 1、复制的完整流程 （1）slave node启动，仅仅保存master node的信息，包括master node的host和ip，但是复制流程没开始 master host和ip是从哪儿来的，redis.conf里面的slaveof配置的 （2）slave node内部有个定时任务，每秒检查是否有新的master node要连接和复制，如果发现，就跟master node建立socket网络连接 （3）slave node发送ping命令给master node （4）口令认证，如果master设置了requirepass，那么salve node必须发送masterauth的口令过去进行认证 （5）master node第一次执行全量复制，将所有数据发给slave node （6）master node后续持续将写命令，异步复制给slave node 2、数据同步相关的核心机制 指的就是第一次slave连接msater的时候，执行的全量复制，那个过程里面你的一些细节的机制 （1）master和slave都会维护一个offset ma ...

主从复制原理、断点续传 1、主从架构的核心原理 当启动一个slave node的时候，它会发送一个PSYNC命令给master node 如果这是slave node重新连接master node，那么master node仅仅会复制给slave部分缺少的数据; 否则如果是slave node第一次连接master node，那么会触发一次full resynchronization 开始full resynchronization的时候，master会启动一个后台线程，开始生成一份RDB快照文件，同时还会将从客户端收到的所有写命令缓存在内存中。RDB文件生成完毕之后，master会将这个RDB发送给slave，slave会先写入本地磁盘，然后再从本地磁盘加载到内存中。然后master会将内存中缓存的写命令发送给slave，slave也会同步这些数据。 slave node如果跟master node有网络故障，断开了连接，会自动重连。master如果发现有多个slave node都来重新连接，仅仅会启动一个rdb save操作，用一份数据服务所有slave node。 2、主从 ...