我太菜了

喜欢写Hello World的未来程序员.

Raft中的领导人选举

分布式一致性问题

原来姹紫嫣红开遍 似这般都付与断井颓垣 极简解释 为了能够很容易地浏览整个过程，先从一个最小的Raft民主集群出发，即一开始是3个群众（单数是为了能让某个候选人拿到多数票）。如下图，发起选举时，有可能发生如下三种情况。 可以看出，前两种都能够选出领导人，第三种因为“瓜分”选票的原因，没有候选人拿到多数选票，则本轮选票无效。之后会再次发生超时（Election Time...

Posted by bbkgl on October 22, 2019

Raft中用到的RPC

分布式一致性问题

韶华不为少年留 恨悠悠 几时休 在阅读Raft论文的时候发现其中用到了三种RPC，都是由领导人发出： 心跳包RPC，用于维持领导人的权威 发送请求投票的 RPC，拉票 附加条目 RPC，用于其他服务器的日志复制 其实第一种和第三种是同一类型的RPC，只是在不同情况下作用不一样：当其entries域为空时，该RPC作为Leader的心跳；当entrie...

Posted by bbkgl on October 20, 2019

分布式一致性算法Raft概述

分布式一致性问题

渐行渐远渐无书 水阔鱼沉何处问 前几天的一篇文章已经讲过了拜占庭将军问题，从而引出了分布式的一致性问题，Raft正是一种以较易理解的方式解决该问题的算法。 说实话，我这几天看了Raft的英文，也看了Raft的中文译文版，然后又找了很多大佬的博文看了，实在没觉得Raft容易理解或者是容易实现，如果真要自己实现的话还真的一头雾水，当然看懂讲的什么东西还是不难的。 Raft通过...

Posted by bbkgl on October 19, 2019

序列化二叉树

你快乐吗？

恨登山临水 手寄七弦桐 目送归鸿 C++，创建二叉树。 看到这道题，一开始我想到的是利用中序+前/后序还原二叉树。后面写着写着觉得代码写太长了，这不符合剑指offer的风格，遂停下敲键盘的手，研究了以下普通前序的整数序列和这个字符串序列的区别，然后就发现了一个之前忽略的重要信息，那就是空结点！ 为什么之前需要中序+前/后序才能确定一颗二叉树呢，因为这里说的前中后序序...

Posted by bbkgl on October 18, 2019

把二叉树打印成多行

你快乐吗？

对一张琴 一壶酒 一溪云 C++，层序遍历，和上题几乎一样的。 思路直接看上一道题吧。 非递归： /* struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : val(x), lef...

Posted by bbkgl on October 17, 2019

按之字形顺序打印二叉树

你快乐吗？

叹隙中驹 石中火 梦中身 C++，层序遍历。 其实主要就是把层序遍历的层数记住，至于怎么记住有很多种方法，我这里用的是内层循环每次把一层全部压入vector实现的。其实我还写过前序递归的，思路也是类似的，也更简单，具体可以参考leetcode102。 非递归的如下： /* struct TreeNode { int val; struct Tree...

Posted by bbkgl on October 16, 2019

对称的二叉树

你快乐吗？

若教随马逐郎行 不辞多少程 C++，dfs。 定义一个函数： 判断两个结点（left, right）是否相等，如果相等继续下一步，否则返回false 继续递归判断left的左儿子和righr的右儿子是否相等，且left的右儿子和righr的左儿子是否相等，即对称判断 终止条件，两个指针都为空 代码： /* struct TreeNode { i...

Posted by bbkgl on October 16, 2019

拜占庭将军问题

分布式一致性问题

情黯黯 闷腾腾 身如秋后蝇 最近一直在看分布式存储相关的东西，然后都提到了一个问题，拜占庭将军问题。既然绕不过，索性我就把这些都看一下。 引用百度百科的定义：拜占庭将军问题（Byzantine failures），是由莱斯利·兰伯特提出的点对点通信中的基本问题。含义是在存在消息丢失的不可靠信道上试图通过消息传递的方式达到一致性是不可能的。因此对一致性的研究一般假设信道...

Posted by bbkgl on October 15, 2019

球队“食物链”

你快乐吗？

竹杖芒鞋轻胜马 谁怕？ 一蓑烟雨任平生 这是PTA上一道作业题，大概就是在有向图中找出一个字典序最小的环，要求这个环连接了所有的点。 首先想到的就是DFS了，思路如下： 根据输入，建立所有的有向边，当然可能出现双向的 使用深度优先遍历，用一个vector记录路径，用一个vis数组记录当前路径经过的点 每进入下一个点前，判断这个点有没有访问过，是不是...

Posted by bbkgl on October 13, 2019

使用select函数监测http请求超时

socket超时

人生如逆旅 我亦是行人 最近研究怎么实现HTTP请求超时检测并踢掉请求的功能。 一开始想到用linux的信号机制，可是用了感觉问题挺多的，好多时候不生效，要么就是不能一个进程里重复用。 然后就在博客上找，基本都是说select的，索性我就两个都用了，DNS请求用信号，TCP连接和HTTP请求用seletct。 一般我们用select都是在用到多路复用的情况下，也就是委托...

Posted by bbkgl on October 13, 2019

FEATURED TAGS
Blog leetcode C++ 剑指offer http Raft Linux Hadoop 设计模式 CV 链表 动态规划 图 拓扑排序 快排 二叉树 leveldb 数学 数组 二分 dfs profile hash表 字符串 贪心 01背包 最小堆 单调栈 luajit 计算机网络 操作系统 共享内存 linux 原地哈希 双指针 滑动窗口 UE4 编译原理
ABOUT ME

写过Hello World, 下过矿。

✉️ zoujiakun@zju.edu.cn

FRIENDS