CodeMilk

life is not just live

自己动手实现一个RPC框架(二)

自己动手实现一个RPC框架
使用fastjson,netty,反射,动态代理,zookeeper实现一个RPC框架。

代码链接:https://github.com/liunaijie/self-rpc-framwork`

各模块说明:

  • rpc-commons
    通用设置模块,包括网络传输的数据格式,请求编号工具类,反射工具类等一些底层协议,工具相关的内容

  • rpc-register
    服务注册模块,主要包括服务的注册与发现功能。这里使用zookeeper来进行实现。
    在这里,服务端注册时,使用通用模块中的ServiceDescriptor,ResponseServiceDescription类来进行注册
    ResponseServiceDescription类是ServiceDescription的子类,添加了实现类,实例地址等属性。
    消费者查找服务时,发送ServiceDescription得到ResponseServiceDescription,一个类可能有多个实现类,多个实例,在返回时进行随机返回。
    对于同一个实现的不同版本实现,或多个服务实例这种情况随机返回没有问题。对于不同实现类,采用随机返回可能有些问题,但是在spring中对于多实现类也需要指定实现类,所以后面再考虑更改。

有序链表转换为二叉搜索树—LeetCode109

题目描述

给定一个单链表,其中的元素按升序排序,将其转换为高度平衡的二叉搜索树。

本题中,一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。

示例:

给定的有序链表: [-10, -3, 0, 5, 9],

一个可能的答案是:[0, -3, 9, -10, null, 5], 它可以表示下面这个高度平衡二叉搜索树:

1
2
3
	0
-3 9
-10 5

答案不唯一,只要满足平常二叉树的特性即可。

题目中给出的数组已经按升序排序,我们需要将其转换为平衡二叉树。

之前写过一篇平衡二叉树的插入,可以直接调用平衡二叉树的插入方法即可。但是这一次并不是使用插入方法,而是根据升序的特性来做。

自己动手实现一个RPC框架(一)

前言

现在微服务体系流行,而RPC框架作为微服务中重要的一环,为了弄明白RPC的整体过程,决定要自己动手实现一个RPC框架。

我们先了解一下什么是RPC,RPC全程是Remote Procedure Call,翻译过来就是远程过程调用,我们先思考一下没有使用rpc的项目的调用流程:

  1. 通过@Autoware注解注入另外的类
  2. 在需要调用的地方直接调用即可

当需要调用其他功能的接口时,比如调用其他公司的接口,或者调用自己公司内部的其他业务或功能接口。这时一般需要使用http来进行网络调用。

那么使用http调用其他的功能接口算不算是rpc调用呢?我感觉也是算的,因为这也是一种通过网络从计算机程序上请求服务的过程。

只不过由于调用的功能不严格意义上属于一个大项目,所以不算一个程序直接的内部调用,所以这里只讨论 一个大项目拆分成不同模块后,不同模块直接调用的过程。

RPC是原来一个程序分为多个不同的程序,分别运行在不同的jvm上。部署在多台机器上后,就涉及到网络通信,需要将调用的信息发送到被调用的机器上,调用完成后再进行返回。

rpc的流程图如下所示,

RPC调用流程

牵扯到网络请求,那么就可以使用之前的http请求,但是由于http请求需要封装一些对于我们而言无用的信息,所以使用http的方式可以采用,比如springcloud就采用了http来进行通信的方式,而这次我准备使用其他的网络通信方式,这一篇中先使用bio来实现网络通信。

还有一个序列化过程,它主要是将信息进行编解码,然后通过网络传输,因为网络传输中都是传输的二进制字节码文件,所以我们需要定义规则,将信息进行转换,消费者发送出去的信息生产者能明白其调用的内容,消费者也能明白生产者返回的信息。这一篇文章中也不去使用复杂的序列化方式,直接实现java中的Serializable接口。

二分查找及几种变形

二分查找

这个查找的要求是数组有序,我们要查找一个元素是不是存在于已排序数组中,先拿中间值与它比较,如果中间值比寻找值小则在中间值后面继续查找,否则在前面进行查找。

它的时间复杂度是o(logn)。所以它在查找时非常快,比如1024个数据他也就用10次就可以完成查找。

树的几种遍历方式

主要记录一下对于二叉树,进行遍历的几种方式,包括:

  • 前序遍历
  • 中序遍历
  • 后序遍历
  • 深度优先遍历
  • 广度优先遍历

我们以下面的这个二叉树结构为例,分别描述一下这几种遍历的方式有什么不同,以及给出java实现的代码。

用单链表简单实现LRU算法

什么是LRU算法

Least Recently Used,最近最少使用,当数据超过容量时,淘汰最近最少使用的一个然后再进行添加。

用单链表来进行实现:

维护一个链表,从头插入数据。当新数据插入时将新数据作为头部,指向旧的头结点。

向一个单链表插入数据,首先遍历这个链表,查看数据是否已经存在于链表中。如果存在,则删除原有数据,将新数据插入到头结点。

如果不存在,先看是否已经到达容量,如果没有到达容量则插入到头结点。如果到达容量则删除尾部节点,再进行插入。

在这个过程中,将最近使用过的又重新插入到了头部,在链表尾部的就是最近最少使用的一项,所以从尾部删除。

统计位数为偶数的数字—LeetCode1295

题目描述

给你一个整数数组 nums,请你返回其中位数为 偶数 的数字的个数。

示例 1:

输入:nums = [12,345,2,6,7896]
输出:2
解释:
12 是 2 位数字(位数为偶数)
345 是 3 位数字(位数为奇数)
2 是 1 位数字(位数为奇数)
6 是 1 位数字 位数为奇数)
7896 是 4 位数字(位数为偶数)
因此只有 12 和 7896 是位数为偶数的数字
示例 2:

输入:nums = [555,901,482,1771]
输出:1
解释:
只有 1771 是位数为偶数的数字。

提示:

1 <= nums.length <= 500
1 <= nums[i] <= 10^5

二叉树的最大深度-LeetCode104

题目描述

给定一个二叉树,找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

示例:
给定二叉树 [3,9,20,null,null,15,7],

3

/
9 20
/
15 7
返回它的最大深度 3 。