Skip to content

Commit d180ca2

Browse files
author
henryjia
committed
0531
1 parent 0db0f89 commit d180ca2

18 files changed

Lines changed: 467 additions & 225 deletions

File tree

‎docs/.DS_Store‎

0 Bytes
Binary file not shown.

‎docs/_images/.DS_Store‎

0 Bytes
Binary file not shown.

‎docs/_images/interview/mysql-cache-demo.png‎

350 KB
Loading

‎docs/data-structure-algorithms/soultion/Array-Solution.md‎

Lines changed: 43 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -362,7 +362,49 @@ public int maxArea(int[] height){
362362
> 输出: 4
363363
> ```
364364
365-
**思路**：
365+
**思路**：减而治之（逐渐缩小问题规模） 基于快排
366+
367+
```java
368+
class Solution {
369+
Random random = new Random();
370+
371+
public int findKthLargest(int[] nums, int k) {
372+
return quickSelect(nums, 0, nums.length - 1, nums.length - k);
373+
}
374+
375+
public int quickSelect(int[] a, int l, int r, int index) {
376+
int q = randomPartition(a, l, r);
377+
if (q == index) {
378+
return a[q];
379+
} else {
380+
return q < index ? quickSelect(a, q + 1, r, index) : quickSelect(a, l, q - 1, index);
381+
}
382+
}
383+
384+
public int randomPartition(int[] a, int l, int r) {
385+
int i = random.nextInt(r - l + 1) + l;
386+
swap(a, i, r);
387+
return partition(a, l, r);
388+
}
389+
390+
public int partition(int[] a, int l, int r) {
391+
int x = a[r], i = l - 1;
392+
for (int j = l; j < r; ++j) {
393+
if (a[j] <= x) {
394+
swap(a, ++i, j);
395+
}
396+
}
397+
swap(a, i + 1, r);
398+
return i + 1;
399+
}
400+
401+
public void swap(int[] a, int i, int j) {
402+
int temp = a[i];
403+
a[i] = a[j];
404+
a[j] = temp;
405+
}
406+
}
407+
```
366408
367409

368410

‎docs/distribution/.DS_Store‎

0 Bytes
Binary file not shown.

‎docs/distribution/README.md‎

Lines changed: 45 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -2,9 +2,9 @@
22

33
> 一说分布式架构，就会看到各种 SOA、RMI、RPC 等等一脸懵逼的词汇，而且还特别容易混淆各种概念，记住这些吧，就不会质疑自己程序员的身份了。
44
5-
## SOA
5+
### SOA
66

7-
SOA(Service Oriented Architecture) ，中文意思就是**面向服务构架**，它其实就是一种软件架构设计思想，不是具体的某种技术实现。
7+
SOA(Service Oriented Architecture) ，中文意思就是**面向服务架构**，它其实就是一种软件架构设计思想，不是具体的某种技术实现。
88

99
为什么会出现这种思想呢？
1010

@@ -22,11 +22,11 @@ SOA(Service Oriented Architecture) ，中文意思就是**面向服务构架**
2222
2323

2424

25-
SOAP、REST、RPC 就是根据这种设计模式构建出来的规范，其中 SOAP 通俗理解就是 http+xml 的形式，REST 就是 http+json 的形式，RPC 是基于 socket 的形式
25+
SOAP、REST、RPC 就是根据这种设计模式构建出来的规范，其中 SOAP 通俗理解就是 http+xml 的形式，REST 就是 http+json 的形式，RPC 大都是基于 socket 的形式
2626

2727

2828

29-
## SOAP
29+
### SOAP
3030

3131
Simple Object Access Protocol，即简单对象访问协议， 简称 SOAP。
3232

@@ -42,7 +42,7 @@ https://segmentfault.com/a/1190000003772529
4242

4343

4444

45-
## RPC
45+
### RPC
4646

4747
了解上面的RMI，它的主要的流程就是Client<-->stub<-->[NETWORK]<-->skeleton<-->Server，还有一个比较重要的概念就是RMIRegistry，其实大家网上去查RPC的时候流程其实都差不多，可能叫法和底层东西有点不一样，其实其实现所遵循的模型还是类似的。主要的区别的话是RMI是只适用于java的，而RPC任何语言都可以；第二点就是他们两者的调用方式不一样，最终的目标还是一致
4848

@@ -66,7 +66,7 @@ http://blog.jobbole.com/92290/
6666

6767

6868

69-
## rest
69+
### rest
7070

7171
比如有个url：http:www.test.com/user/1，这个地址既要表示删除id为1的用户、又要表示修改id为1的用户，还要表达获取id为1的用户，那么，就要用到http1.1的不同的请求方法：get、post、delete、put，
7272

@@ -78,12 +78,48 @@ http://www.jianshu.com/p/65ab865a5e9f
7878

7979

8080

81-
## RMI
81+
### RMI
8282

8383
SOA思想提出以后，就有很多基于在这个模型上的产物，很多适用于分布式的产物，同时也是越来越庞大系统的产物。Java RMI （Remote Method Invocation 远程方法调用）是用Java在JDK1.1中实现的，它大大增强了Java开发分布式应用的能力。而RMI就是开发百分之百纯Java的网络分布式应用系统的核心解决方案，所以如果不是java的系统就不能使用RMI，这也是其缺点之一。RMI全部的宗旨就是尽可能简化远程接口对象的使用，相当于在服务器端暴露服务，通过bind或者rebind方法注册到RMIRegistry中，注册的信息中包含url，以及相应的类。客户端在在注册中心根据url得到远程对象（stub，存根），然后调用stub远程调用方法。
8484

8585

8686

87-
参考文章：http://www.jianshu.com/p/2c78554a3f36
8887

89-
http://blog.csdn.net/guyuealian/article/details/51992182
88+
89+
### SOA架构和微服务架构的区别
90+
91+
> 首先SOA和微服务架构是一个层面的东西，而对于ESB和微服务网关是一个层面的东西，一个谈到是架构风格和方法，一个谈的是实现工具或组件。
92+
>
93+
> 1.SOA（Service Oriented Architecture）“面向服务的架构”:他是一种设计方法，其中包含多个服务， 服务之间通过相互依赖最终提供一系列的功能。一个服务通常以独立的形式存在与操作系统进程中。各个服务之间通过网络调用。
94+
>
95+
> 2.微服务架构:其实和 SOA 架构类似,微服务是在 SOA 上做的升华，微服务架构强调的一个重点是“业务需要彻底的组件化和服务化”，原有的单个业务系统会拆分为多个可以独立开发、设计、运行的小应用。这些小应用之间通过服务完成交互和集成。
96+
>
97+
> 微服务架构 = 80%的SOA服务架构思想 + 100%的组件化架构思想 + 80%的领域建模思想
98+
99+
100+
101+
### API网关
102+
103+
API网关是一个服务器，是系统的唯一入口。
104+
105+
API 网关并不是微服务场景中必须的组件，如下图，不管有没有 API 网关，后端微服务都可以通过 API 很好地支持[客户端](https://www.zhihu.com/search?q=客户端&search_source=Entity&hybrid_search_source=Entity&hybrid_search_extra={"sourceType"%3A"answer"%2C"sourceId"%3A578705309})的访问。
106+
107+
108+
109+
![img](https://pica.zhimg.com/80/v2-0903a05306217b52effca6ebb80b45ea_1440w.jpg?source=1940ef5c)
110+
111+
但对于服务数量众多、复杂度比较高、规模比较大的业务来说，引入 API 网关也有一系列的好处：
112+
113+
- 聚合接口使得服务对调用者透明，客户端与后端的耦合度降低
114+
- 聚合后台服务，节省流量，提高性能，提升用户体验
115+
- 提供安全、流控、过滤、缓存、计费、监控等 API 管理功能
116+
117+
118+
119+
从面向对象设计的角度看，它与外观模式类似。API网关封装了系统内部架构，为每个客户端提供一个定制的API。它可能还具有其它职责，如身份验证、监控、负载均衡、缓存、请求分片与管理、静态响应处理。API网关方式的核心要点是，所有的客户端和消费端都通过统一的网关接入微服务，在网关层处理所有的非业务功能。通常，网关也是提供REST/HTTP的访问API。服务端通过API-GW注册和管理服务。
120+
121+
### References:
122+
123+
- http://www.jianshu.com/p/2c78554a3f36
124+
125+
- http://blog.csdn.net/guyuealian/article/details/51992182

‎docs/distribution/ZooKeeper/Consistency-Protocol.md‎

Lines changed: 12 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -1,5 +1,7 @@
11
# 「分布式一致性协议」从2PC、3PC、Paxos到 ZAB
22

3+
## CAP
4+
35
设计一个分布式系统必定会遇到一个问题—— **因为分区容忍性（partition tolerance）的存在，就必定要求我们需要在系统可用性（availability）和数据一致性（consistency）中做出权衡** 。这就是著名的 `CAP` 定理。
46

57
![](https://cdn.jsdelivr.net/gh/Jstarfish/picBed/zk/007S8ZIlly1gevqnrlzg6j30b60as3ys.jpg)
@@ -8,7 +10,7 @@
810

911
> 大多数分布式系统都分布在多个子网络。每个子网络就叫做一个区（partition）。分区容错的意思是，区间通信可能失败。比如，一台服务器放在中国，另一台服务器放在美国，这就是两个区，它们之间可能无法通信。
1012
>
11-
> 一般来说，分区容错无法避免，因此可以认为 CAP 的 P 总是成立。
13+
> 一般来说，分区容错无法避免，因此可以认为 CAP 的 P 总是成立。(因为我们前提分布式系统，分布的服务都没法通信了，还玩个啥）
1214
>
1315
> ![img](https://www.wangbase.com/blogimg/asset/201807/bg2018071602.png)
1416
>
@@ -20,6 +22,14 @@
2022
2123

2224

25+
### 与 BASE 的关系
26+
27+
BASE 是 Basically Available（基本可用）、Soft state（软状态）和 Eventually consistent（最终一致性）三个短语的简写。
28+
29+
BASE是对CAP中一致性和可用性权衡的结果，其来源于对大规模互联网系统分布式实践的结论，是基于CAP定理逐步演化而来的，其核心思想是即使无法做到强一致性（Strong consistency），但每个应用都可以根据自身的业务特点，采用适当的方式来使系统达到最终一致性（Eventual consistency）。
30+
31+
32+
2333
## 一致性模型
2434

2535
一致性（Consistency）是指多副本（Replications）问题中的数据一致性。关于分布式系统的一致性模型有以下几种：
@@ -189,7 +199,7 @@ ZAB（Zookeeper Atomic Broadcast） 协议是为分布式协调服务 Zookeeper
189199
2. Leader 服务器生成一个对应的事务 Proposal，并为这个事务生成一个全局递增的唯一的ZXID（通过其 ZXID 来进行排序保证顺序性）
190200
3. Leader 将这个事务发送给所有的 Follows 节点
191201
4. Follower 节点将收到的事务请求加入到历史队列（Leader 会为每个 Follower 分配一个单独的队列先进先出，顺序保证消息的因果关系）中，并发送 ack 给 Leader
192-
5. 当 Leader 收到超过半数 Follower 的 ack 消息，Leader会广播一个 commit 消息
202+
5. 当 Leader 收到超过半数 Follower 的 ack 消息，Leader 会广播一个 commit 消息
193203
6. 当 Follower 收到 commit 请求时，会判断该事务的 ZXID 是不是比历史队列中的任何事务的 ZXID 都小，如果是则提交，如果不是则等待比它更小的事务的 commit
194204

195205
![zab-commit](https://cdn.jsdelivr.net/gh/Jstarfish/picBed/zk/zab-commit.png)

‎docs/distribution/ZooKeeper/Hello-Zookeeper.md‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -369,7 +369,7 @@ Zookeeper 将所有数据存储在内存中，数据模型是一棵树（Znode T
369369
- 所谓持久节点是指一旦这个 ZNode 被创建了，除非主动进行 ZNode 的移除操作，否则这个 ZNode 将一直保存在 Zookeeper 上。
370370
- 而临时节点就不一样了，它的生命周期和客户端会话绑定，一旦客户端会话失效，那么这个客户端创建的所有临时节点都会被移除。
371371

372-
另外，ZooKeeper 还允许用户为每个节点添加一个特殊的属性：**SEQUENTIAL。**也被叫做 **顺序结点**，一旦节点被标记上这个属性，那么在这个节点被创建的时候，Zookeeper 会自动在其节点名后面追加上一个整型数字，这个整型数字是一个由父节点维护的自增数字。
372+
另外，ZooKeeper 还允许用户为每个节点添加一个特殊的属性：**SEQUENTIAL**。也被叫做 **顺序结点**，一旦节点被标记上这个属性，那么在这个节点被创建的时候，Zookeeper 会自动在其节点名后面追加上一个整型数字，这个整型数字是一个由父节点维护的自增数字。
373373

374374

375375

‎docs/distribution/rpc/Hello-RPC.md‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -138,7 +138,7 @@ RPC框架负责屏蔽底层的传输方式(TCP或者UDP)、序列化方式( XML/
138138

139139
由于各个服务部署在不同机器，服务间的调用涉及到网络通信过程，如果服务消费方每调用一个服务都要写一坨网络通信相关的代码，不仅使用复杂而且极易出错。
140140

141-
如果有一种方式能让我们像调用本地服务一样调用远程服务，而让调用者对网络通信这些细节透明，那么将大大提高生产力。这种方式其实就是RPC（Remote Procedure Call Protocol），在各大互联网公司中被广泛使用，如阿里巴巴的hsf、dubbo（开源）、Facebook的thrift（开源）、Google grpc（开源）、Twitter的finagle等。
141+
如果有一种方式能让我们像调用本地服务一样调用远程服务，而让调用者对网络通信这些细节透明，那么将大大提高生产力。这种方式其实就是RPC（Remote Procedure Call Protocol），在各大互联网公司中被广泛使用，如阿里巴巴的hsf、dubbo（开源）、Facebook的thrift（开源）、Google grpc（开源）、Twitter的 finagle 等。
142142

143143
我们首先看下一个RPC调用的具体流程：
144144

‎docs/interview/Collections-FAQ.md‎

Lines changed: 11 additions & 18 deletions
Original file line numberDiff line numberDiff line change
@@ -382,7 +382,7 @@ public E get(int index) {
382382

383383

384384

385-
### Hash冲突及解决办法
385+
## Hash冲突及解决办法
386386

387387
解决哈希冲突的方法一般有：开放定址法、链地址法（拉链法）、再哈希法、建立公共溢出区等方法。
388388

@@ -1183,14 +1183,7 @@ void transfer(Entry[] newTable, boolean rehash) {
11831183
}
11841184
```
11851185

1186-
这个方法的功能是将原来的记录重新计算在新桶的位置，然后迁移过去。
1187-
1188-
![](https://cdn.jsdelivr.net/gh/Jstarfish/picBed/others/mysql-1.7-resize.png)
1189-
1190-
多线程HashMap的resize
1191-
1192-
我们假设有两个线程同时需要执行resize操作，我们原来的桶数量为2，记录数为3，需要resize桶到4，原来的记录分别为：[3,A],[7,B],[5,C]，在原来的map里面，我们发现这三个entry都落到了第二个桶里面。
1193-
假设线程thread1执行到了transfer方法的Entry next = e.next这一句，然后时间片用完了，此时的e = [3,A], next = [7,B]。线程thread2被调度执行并且顺利完成了resize操作，需要注意的是，此时的[7,B]的next为[3,A]。此时线程thread1重新被调度运行，此时的thread1持有的引用是已经被thread2 resize之后的结果。线程thread1首先将[3,A]迁移到新的数组上，然后再处理[7,B]，而[7,B]被链接到了[3,A]的后面，处理完[7,B]之后，就需要处理[7,B]的next了啊，而通过thread2的resize之后，[7,B]的next变为了[3,A]，此时，[3,A]和[7,B]形成了环形链表，在get的时候，如果get的key的桶索引和[3,A]和[7,B]一样，那么就会陷入死循环。
1186+
具体原因如上题
11941187

11951188

11961189

@@ -1824,22 +1817,22 @@ HashSet 的底层其实就是 HashMap，只不过我们 **HashSet 是实现了 S
18241817

18251818

18261819

1827-
## 参考与感谢
1820+
## References
18281821

18291822
所有内容都是基于源码阅读和各种大佬之前总结的知识整理而来，输入并输出，奥利给。
18301823

1831-
https://www.javatpoint.com/java-arraylist
1824+
- https://www.javatpoint.com/java-arraylist
18321825

1833-
https://www.runoob.com/java/java-collections.html
1826+
- https://www.runoob.com/java/java-collections.html
18341827

1835-
https://www.javazhiyin.com/21717.html
1828+
- https://www.javazhiyin.com/21717.html
18361829

1837-
https://yuqirong.me/2018/01/31/LinkedList内部原理解析/
1830+
- https://yuqirong.me/2018/01/31/LinkedList内部原理解析/
18381831

1839-
https://youzhixueyuan.com/the-underlying-structure-and-principle-of-hashmap.html
1832+
- https://youzhixueyuan.com/the-underlying-structure-and-principle-of-hashmap.html
18401833

1841-
《HashMap源码详细分析》http://www.tianxiaobo.com/2018/01/18/HashMap-源码详细分析-JDK1-8/
1834+
- 《HashMap源码详细分析》http://www.tianxiaobo.com/2018/01/18/HashMap-源码详细分析-JDK1-8/
18421835

1843-
《ConcurrentHashMap1.7源码分析》https://www.cnblogs.com/chengxiao/p/6842045.html
1836+
- 《ConcurrentHashMap1.7源码分析》https://www.cnblogs.com/chengxiao/p/6842045.html
18441837

1845-
http://www.justdojava.com/2019/12/18/java-collection-15.1/
1838+
- http://www.justdojava.com/2019/12/18/java-collection-15.1/

0 commit comments

Comments
 (0)