一、Algorithm
本周算法完成如下：
1.1 题目来源【Leetcode 108 将有序数组转换为二叉搜索树】
1.2 题目描述
将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。
本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
示例:
给定有序数组: [-10,-3,0,5,9],
一个可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面这个高度平衡二叉搜索树：
0
/ \
-3 9
/ /
-10 5
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/convert-sorted-array-to-binary-search-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。 ### 1.3 解题如下：
package cn.mayday.algorithms.day20191222;
/**
* @author: mayday
* @version: 1.0
*
* 运行通过
*/
public class Leetcode108sortedArrayToBST {
public TreeNode sortedArrayToBST(int[] nums) {
// 异常条件直接返回
if (nums == null || nums.length == 0) {
return null;
}
return buildTreeLoop(nums, 0, nums.length - 1);
}
/**
* 递归方法构造二叉树
*
* @param nums 原数组
* @param leftPosition 左子树坐标
* @param rightPosition 右子树坐标
* @return 二叉平衡树根节点
*/
private TreeNode buildTreeLoop(int[] nums, int leftPosition, int rightPosition) {
// 递归结束条件
if (leftPosition > rightPosition) {
return null;
}
int middlePosition = leftPosition + (rightPosition - leftPosition) / 2;
int value = nums[middlePosition];
TreeNode root = new TreeNode(value);
root.left = buildTreeLoop(nums, leftPosition, middlePosition - 1);
root.right = buildTreeLoop(nums, middlePosition + 1, rightPosition);
return root;
}
/**
* Definition for a binary tree node.
*/
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
val = x;
}
}
}
1.4 总结
这道题考核对二叉搜索树、树的构造、中序遍历的理解，归根到底为二叉树中序遍历的逆过程
平衡二叉搜索树特征
1. 若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值
2. 若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值
3. 任意节点的左、右子树也分别为二叉搜索树
4. 没有键值相等的节点
基于以上性质，我们可以得出一个二叉搜索树的特性：二叉搜索树的中序遍历结果为递增序列。
二、Review
2.1 文章内容
Facebook的论文《Scaling Memcache at Facebook》
继续上周的基本看完了，介绍了FaceBook在缓存设计的架构，集群中的延迟优化和负载处理，失败处理机制、以及多Region时的处理机制。
三、Tip
继续学习使用了阿里巴巴 开源的Arthas 工具，强烈推荐。
3.1 附 官方学习文档
https://alibaba.github.io/arthas/
3.2 附：用户案例地址
https://github.com/alibaba/arthas/issues?q=label%3Auser-case
github中提供了很多使用案例，Github完整案例见用户案例,对应项目issue中使用label:user-case 搜索结果
筛选出部分和自己相关的部分案例如下
| 案例标题 | 使用特性 |
|---|---|
| Arthas协助排查线上skywalking不可用问题 #Issue557 | 该案例使用了watch特性，能够动态监控指定类、指定方法、输出的指定结果 |
| 利用Arthas排查Spring Boot应用NoSuchMethodError #issue160 | 该案例使用了sc命令来查找类，使用jad查看反编绎的源代码，从而知晓该版本jar包中无指定方法 |
| 【Arthas问题排查集】活用ognl表达式 #11 | ognl表达式–你值得拥有–更复杂的使用 |
| Arthas的一些特殊用法文档说明 #71 | 特殊用法 |
以上内容同步见简书博客。
四、Share
4.1 分享内容：
本周分享内容为RocketMQ官方设计文档 https://github.com/apache/rocketmq/blob/master/docs/cn/design.md 中关于页缓存与内存映射的理解
其中关于页缓存与内存映射描述如下：
页缓存（PageCache)是OS对文件的缓存，用于加速对文件的读写。
一般来说，程序对文件进行顺序读写的速度几乎接近于内存的读写速度，主要原因就是由于OS使用PageCache机制对读写访问操作进行了性能优化，将一部分的内存用作PageCache。对于数据的写入，OS会先写入至Cache内，随后通过异步的方式由pdflush内核线程将Cache内的数据刷盘至物理磁盘上。对于数据的读取，如果一次读取文件时出现未命中PageCache的情况，OS从物理磁盘上访问读取文件的同时，会顺序对其他相邻块的数据文件进行预读取。
在RocketMQ中，ConsumeQueue逻辑消费队列存储的数据较少，并且是顺序读取，在PageCache机制的预读取作用下，Consume Queue文件的读性能几乎接近读内存，即使在有消息堆积情况下也不会影响性能。而对于CommitLog消息存储的日志数据文件来说，读取消息内容时候会产生较多的随机访问读取，严重影响性能。如果选择合适的系统IO调度算法，比如设置调度算法为“Deadline”（此时块存储采用SSD的话），随机读的性能也会有所提升。
另外，RocketMQ主要通过MappedByteBuffer对文件进行读写操作。其中，利用了NIO中的FileChannel模型将磁盘上的物理文件直接映射到用户态的内存地址中（这种Mmap的方式减少了传统IO将磁盘文件数据在操作系统内核地址空间的缓冲区和用户应用程序地址空间的缓冲区之间来回进行拷贝的性能开销），将对文件的操作转化为直接对内存地址进行操作，从而极大地提高了文件的读写效率（正因为需要使用内存映射机制，故RocketMQ的文件存储都使用定长结构来存储，方便一次将整个文件映射至内存）。
4.2 整理总结如下：
-
1、PageCache的预读取机制+顺序读取 大大提高了读性能，基本接近于读内存。
-
2、RocketMQ存储机制中，存储文件中ConsumeQueue和CommitLog分别表示存储消息索引和存储消息本体。
-
3、RocketMQ采用了FileChannel模型，实现MMAP（内存映射），大大提高了文件的读写效率。
-
4、RocketMQ的文件存储之所以使用定长结构，是为了方便将整个文件MMAP。
关于存储结构见下图
总结：RocketMQ中的消息本体还是存储在commit Log磁盘文件中。而消费队列是逻辑抽象的概念，并没有这样一个队列真实存在，而是抽象出来的一个按照指定Topic分类的索引文件系统，按照topic/queueId等分类保存各自topic的所有消息的在磁盘文件中的索引。（这样就能根据该索引快速定位到消息本体内容）
