Update your browser to view this website correctly. Update my browser now
元旦放假的第一天，在家没事干，用golang实现了一下mapreduce的单进程版本，github地址。处理对大文件统计最高频的10个单词，因为功能比较简单，所以设计没有解耦合。 本文先对mapreduce大体概念进行介绍，然后结合代码介绍一下，如果接下来几天有空，我会实现一下分布式高可用的mapreduce版本（1月6日update：这个主要看需求，1.如果master挂了，当前执行的任务丢了就丢了，接下来下发的任务还能执行，那么这个很好实现，可以做多个Master，每次任务分发给一个master执行，北向搞一个负载均衡器就可以，或者弄一个注册中心；2.如果要高可用指的是已经执行的mapreduce任务在主master挂掉后仍然继续执行，那么多个master之间需要做数据同步，可以用Redis或者kafka做消息同步，但是有种过度设计的感觉…
本文首先大概介绍一下https的协议原理（其实是TLS协议原理），然后给出构建https的go代码例子。 1.HTTPS协议 网上已经有很多资料介绍HTTPS协议了，我归纳一下，加深自己的记忆。 HTTPS是HTTP通过SSL/TLS加密的方式进行通讯，TLS是SSL的改进版本。TLS协议可以分为握手阶段和对话阶段，握手阶段采用非对称加密方式（密钥由第三方机构提供），对话阶段采用对称加密方式（密钥由握手阶段协商得出）。 握手阶段主要分为4个步骤（细分来说，可以有多个步骤，具体查看RFC文档）： 1.1 Client Hello 客户端向服务器端发起hello请求，同时带入以下信息： 客户端支持的加密方式 客户端支持的SSL/TLS协议版本号 客户端生成的随机数1，该随机数…
最近我的一位技术不错的同学想换工作，然后跟我吐槽在面试中碰到了一些奇怪的面试官问了一些不着边际的题目，让我这位同学很是苦恼。其实我之前一直想说说面试，但是也一直比较懒。这次听完他的谈话，结合我的一些面试别人的经验和自己被面试的经验，今天分别来谈谈从面试官角度和被面试者出发，我对一次”良好“面试的看法吧。因为我是做后台开发的，所以讲的东西可能有点偏重于后台开发，但是我觉得面试方法来说是具有普适性的。 1. 从面试官角度出发 面试题目应该覆盖足够广的程度。比如我是做后台开发的，我认为一次合格的后台开发面试应该覆盖到：数据结构&算法、操作系统、网络知识、某一门求职者擅长的编程语言。以上4个我认为是必须需要考察的，另外还有一些比如数据库、分布式、Linux基本操作等相应知识也可以进行适当的考察。不能一次面试只面操作系统，这个就没办法进行系统而全面的考察。 面试考…
线段树是一种比较强大的数据结构，主要用于在动态更新区间的情况下，保持查找和更新在O(log(n))级别的时间复杂度。虽然它不是一颗完全二叉树，但构造时按照完全二叉树进行构树，没有的话叶结点留空，数组按完全二叉树构造：对于父节点编号为x，其左右儿子结点分别为：2x和2x+1。如下图所示： Management range表示该结点的『负责输入结点』的范围，1-3表示负责输入结点1，2和3，即：in[1]，in[2]和in[3]。value值表示初始化值，刚开始构造时值为0，构造之后的值为子结点的『某种运算』结果：比如，对于『求区间最小值』，则value(4) = min(value(8), value(9))，value(1) = min(value(2), value(3))`，这个在图中未标出来。图中蓝色结点为输入的结点，虚线方向为数组的输…
2017_12_22更新：还是删了吧……小命要紧，万一真被抓了。…
给定一棵树，从树中任意结点出发，遍历m个结点，最少需要结果多少个结点，结点可以重复走。 思路：找树中最长的链，也就是树的“直径”，假设为d，如果m小于等于d，则输出m就可以了；如果m大于d，则输出d+(m-d)*2，这是因为最长链上的分支路径需要走2遍（一来一回）。那么，直径也就是最长链怎么求？先从任意一个叶子节点x出发，找到最长的路径，假设路径结尾是y节点；再以y为根，找出最长的路径，这条路径就是树的最长路径。两次dfs可以搞定了。 代码： #include <iostream> #include <vector> using namespace std; vector<int> vis; vector<vector<int>> tree; pair&l…
最近自己写的一段代码出现了很多僵死进程，简约版本代码如下： #include <stdio.h> #include <string> #include <unistd.h> #include <stdlib.h> #include <iostream> #include <sys/wait.h> #include <pthread.h> using namespace std; int cnt = 0; void sig_handler(int signo) { pid_t pid; int stat; pid = wait(&stat); cout << "cnt:" << ++cnt << ", pi…
Broadcom最近推出了他们的新产品broadview，提供telemetry的监控方式，将问题定位至芯片级别，其架构如下： 在交换机侧加入agent，提供对芯片级别的操作：包括信息采集以及报文注入等，北向提供REST接口提供信息交互，控制器侧提供操作的具体逻辑。其官网介绍的功能如下： Buffer statistics tracking Packet tracing and injection Black hole detection Performance metrics for BST Drop counters due to congestion Support for StrataXGS and StrataDNX silicon families Reference implementation for applications…
最近调研了一些关于数据中心网络监控的论文和解决方案，主要关于丢包和延时的定位排查，现在telemetry的技术比较火热，写点东西小结一下，越来越懒得写博客了，写的不是很详细，特别是后面几篇，也可能有理解不到位的地方，欢迎指正。 1. Pingmesh Pingmesh是微软在2015年提出的，其架构模式在那之前已经在微软的数据中心运行了超过4年，采用商用交换机，每天收集10TB的延迟数据。它能够解决以下三个问题： 定位业务的延迟是否因为网络 提供并且跟踪当前网络服务水平（service level agreement ） 自动排除障碍 微软数据中心采用CLOS架构，如下图所示。拥有的规模如下：服务器规模在10万级别，交换机规模为万，服务器上联万兆。论文中阐述的一些统计和架构如下：时延统计采用端到端，中控系统为微软自己的…
DataStore有三种监听事件DataChangeListener、DataTreeChangeListener和DOMDataTreeChangeListener，他们具体的区别可以参考这篇博客，本文主要介绍一下DataTreeChangeListener。DataTreeChangeListener可以用来监听整棵树或者某个子树，子树结点的改变将引发由该子节点递归到根结点整个支路结点都发生改变，原理是version号的变化，具体可以参考我之前的博客。 实验 yang文件 包含多级container的yang文件定义如下： container threshold { description "Threshold configuration"; container temperature {…
在C++中有多种方式可以进行数据拷贝，但它们实现的方式略有不同。 memcpy memcpy原型如下，其以字节为单位，可以用来拷贝非重合区域。也就是说如果拷贝的源、目的有重合部分的话，结果是undefined，意味着可能偶尔也是对的。但最好不要这么做，原则上memcpy是一种后向拷贝机制：从区间的最后一个元素开始进行拷贝，直到第一个元素。 void* memcpy( void* dest, const void* src, std::size_t count ); memmove memmove可以支持重合区域的拷贝，其实现可以理解为memmove用另外一块buffer缓存src数据，然后往dst拷贝。但实际上并不是这样，代码在输入时会进行判断：如果src地址小于dst地址，进行后向拷贝；反之如果src地址大于ds…
网上关于DataStore内部架构和实现细节太少了，大部分都是讲如何使用DataStore，而很少有分析从client开始读写到内存到硬盘的数据流，也没有相关性能分析之类的。由于不能满足『知其所以然』的需求，我只能自己看了。然而，官方的文档真的是杂而乱，在社区问了几个问题也没有反馈……无力吐槽了。以下是我吐血看文档和源码总结的，版本为Beylium，如果有不当之处，希望各位指出。 本文首先简单讲一下MD-SAL的大体架构，然后介绍DataStore内容，包括其内存db和硬盘db。内存db也就是所谓的In-Memory-DataStore主要存储两棵树：Operational Tree和 Config Tree。硬盘db对内存db序列化后写入硬盘，包括snapshot和journal两部分，用于重启后恢复内存db。 1.MD-SAL &emsp…
NeXt is an awesome toolkit developed by Cisco. It is an HTML5/JavaScript based toolkit for network web application which can be used to draw network topology, e.g., data center, laboratory network experiment. It has been added in OpenDaylight community which is an open source community of SDN controller. There are some tutorials that we can follow online like Next-Tutorials…
输出json格式时默认没有换行，不便于查看json结果，可以采用这样进行输出：json.dumps(ret, sort_keys = True, indent = 4, separators=(',', ': '))，进行缩进和换行，方便查看结果。 参考 http://stackoverflow.com/questions/16318543/cant-pretty-print-json-from-python…
codeforces越打越差，我都无力吐槽了，脑子真的赶不上当年了T_T。 A. One-dimensional Japanese Crossword 题意：挨个输出连续的B的个数。 解题：暴力即可。 B. Passwords 题意：给定一堆密码，Vanya 忘记密码，需要不断尝试，尝试的规则是：长度小的先试，长度一样的顺序不定。求Vanya 最长和最短的尝试次数，尝试k次失败后需要暂停5秒。 解题：暴力即可，注意边界情况的考虑。 C. Journey 题意：给定一个有向图，给定时间约束T，每条边有个时间长度，求在给定时间内经过点的最大值。 解题：简单的爆搜题，需要剪枝的是dist[x][node_nr] != -1 &am…
Use response.status to get return code when failed and use response.plain() or Restangular.stripRestangular(response) to get return clean data without any Restangular methods. Pay attention that the .plain() attribution is supported after 1.4.0 version of Restangular. Here comes the example: Restangular.all(xxx).post(cmd).then(function(response) { //console.log(response.plain()…
本文主要介绍如何在DLUX中添加一个模块，加完后我们可以通过http://[host-ip]:8181/index.html的左边侧导航栏访问到我们的页面。添加过程需要对ODL，DLUX和一堆前端的框架比较熟悉，否则会碰到一堆问题，折腾了我好长一段时间，现记录如下，也给有同样问题的人一点帮助。 以下是我从头开始操作的过程以及遇到的问题，注意，本文不是直接安装，而是通过源码编译进行安装。 提前安装软件：grunt、npm、bower。 在github上下载controller，dlux和odlparent，切换到同一分支，然后执行mvn clean install -DskipTests进行分别编译，需要首先安装odlparent，再controller和dlux。此处，注意分支要一致。对于controller和odlparent编译错误较少，…
STL中的关联容器分为set和map两大类，以及他们的衍生体multiset和multimap，这些容器均由红黑树（RB-tree）实现。另外，STL还提供了不在标准之外的关联式容器：hashtable以及以此为底层机制的hash_set，hash_map和他两的multi衍生体。 以红黑树和哈希表为底层结构构造的容器最大的不同是前者为直接排序而后者不是。 1.红黑树 我的这篇博客介绍了红黑树和AVL树的大概轮廓，具体插座和查找细节可以参考《算法导论》，此处不介绍这些细节了。红黑树是一种接近平衡的平衡二叉搜索树，拥有良好的查找、插入复杂度。 STL中的RB-tree提供了两种插入操作：insert_unique()和insert_equal()，前者表示被插入节点的key值独一无二，后者表示ke…
退役好久了，惭愧的是一直没搞过树状数组和线段树，以前都是队友搞的，最近刷codeforeces被树状数组卡了好几次，遂决定怒刷树状数组。 0.算法 本来想写写长篇的算法过程，从如何建树到如何维护更新，结果发现这篇博客写的很赞了，我也就不写了，就写写个人对算法的理解以及刷的题目吧。 树状数组的优点就在于维护了一个前序和树，算法的核心就是『前序和』，碰到的各种题目也都是将各种模型转换为前序和，然后再进行查找和插入操作。 其时间复杂度如下：查找和插入/更新都是O(log MaxVal)，其中MaxVal表示树的最大下标，非常适合插入频繁的操作。以下read(x)表示查找x的前序和，update(x, p)表示更新x下标对应的数组的数值为p，以下BIT为表示树状数组的简称。 模板…
在STL中，有以下几个序列式容器：array、vector、heap、priority_queue、list、slist、deque、stack、queue。其中vector、list、deque为三个标准容器（container）；stack和queue是在deque上进行封装而成的，专有名词叫做配接器（adapter）；array是C++内建容器，不对外使用；heap是基于vector封装的，priority_queue是基于heap封装的；slist是非标准的单向链表。 1.vector vector是C++中的动态数组，可以动态增删，而不需要类似静态数组自己维护空间的分配，其维护的也是一个连续线性空间，支持随机存取，良好的特性使得其成为STL中最常用的容器之一。 vector中有几个需要注意的概念： vecto…
