-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathspringcloud.txt
More file actions
5233 lines (3878 loc) · 284 KB
/
Copy pathspringcloud.txt
File metadata and controls
5233 lines (3878 loc) · 284 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
学习 Spring Cloud Alibaba 的关键在于理解微服务架构的核心问题,以及每个组件是如何解决这些问题的,然后通过实际项目场景串联组件,而不是孤立地学习单个组件。你觉得 “学了用不起来”,本质上是缺乏对 “组件在实际业务中解决什么问题” 的理解,以及 “如何将组件串联起来形成完整流程” 的实践。
一、先明确:Spring Cloud Alibaba 解决什么问题?
微服务架构下,会遇到几个核心问题:
服务太多,地址不好管理(服务注册与发现)→ Nacos
服务之间需要调用,手写 HTTP 请求太麻烦(服务调用)→ Feign
配置太多太散,改配置要重启服务(配置中心)→ Nacos Config
服务可能故障,需要熔断降级(容错)→ Sentinel
外部请求需要统一入口(API 网关)→ Gateway
二、用一个 “迷你电商项目” 串联所有组件(实践步骤)
以 “下单流程” 为例(订单服务→调用商品服务扣库存→调用用户服务查余额),一步步把组件用起来:
步骤 1:拆分服务,明确职责(先有 “微服务”,再谈 “组件”)
先把项目拆成 3 个独立服务:
用户服务(user-service):管理用户信息、查询用户余额
商品服务(product-service):管理商品信息、扣减库存
订单服务(order-service):创建订单,依赖前两个服务
步骤 2:用 Nacos 实现服务注册与发现(让服务 “彼此可见”)
解决的问题:服务地址会变(比如扩容、部署),不能写死 IP,需要动态管理。
操作步骤:
启动 Nacos 服务器(本地单机版即可);
每个服务引入 Nacos 依赖(以 Spring Boot 为例):
xml
<dependency>
<groupId>com.alibaba.cloud</groupId>
<artifactId>spring-cloud-starter-alibaba-nacos-discovery</artifactId>
</dependency>
每个服务的application.yml配置 Nacos 地址:
yaml
spring:
cloud:
nacos:
discovery:
server-addr: localhost:8848 # Nacos服务器地址
application:
name: user-service # 服务名(关键!Nacos通过服务名识别服务)
启动服务后,在 Nacos 控制台(http://localhost:8848/nacos)能看到 3 个服务已注册。
步骤 3:用 Feign 实现服务调用(让服务 “互相通信”)
解决的问题:订单服务需要调用商品 / 用户服务,手写RestTemplate太繁琐,Feign 可以用 “接口 + 注解” 简化 HTTP 调用。
操作步骤:
订单服务引入 Feign 依赖:
xml
<dependency>
<groupId>org.springframework.cloud</groupId>
<artifactId>spring-cloud-starter-openfeign</artifactId>
</dependency>
启动类加@EnableFeignClients注解,开启 Feign 功能;
定义 Feign 客户端(本质是 “远程服务的接口代理”):
java
运行
// 调用商品服务的Feign客户端
@FeignClient(name = "product-service") // 对应商品服务在Nacos的服务名
public interface ProductFeignClient {
// 调用商品服务的扣库存接口(路径要和商品服务的Controller一致)
@PostMapping("/product/deduct")
Result deductStock(@RequestParam("productId") Long productId, @RequestParam("count") Integer count);
}
// 调用用户服务的Feign客户端
@FeignClient(name = "user-service")
public interface UserFeignClient {
@GetMapping("/user/getBalance")
Result<Integer> getBalance(@RequestParam("userId") Long userId);
}
订单服务的业务逻辑中直接注入 Feign 客户端使用:
java
运行
@Service
public class OrderService {
@Autowired
private ProductFeignClient productFeignClient;
@Autowired
private UserFeignClient userFeignClient;
public Result createOrder(Long userId, Long productId, Integer count) {
// 1. 调用用户服务查余额
Result<Integer> balanceResult = userFeignClient.getBalance(userId);
// 2. 调用商品服务扣库存
Result deductResult = productFeignClient.deductStock(productId, count);
// 3. 创建订单(省略DB操作)
return Result.success("订单创建成功");
}
}
步骤 4:用 Nacos Config 做配置中心(统一管理配置)
解决的问题:每个服务的配置文件散落在各自项目中,改配置需要重启服务(比如商品服务的 “库存预警阈值” 可能经常调整)。
操作步骤:
服务引入 Nacos Config 依赖:
xml
<dependency>
<groupId>com.alibaba.cloud</groupId>
<artifactId>spring-cloud-starter-alibaba-nacos-config</artifactId>
</dependency>
创建bootstrap.yml(优先级高于application.yml),配置 Nacos Config 地址:
yaml
spring:
cloud:
nacos:
config:
server-addr: localhost:8848
file-extension: yaml # 配置文件格式
application:
name: product-service # 配置文件名前缀(Nacos中配置文件名为:product-service.yaml)
在 Nacos 控制台 “配置管理” 中添加配置(比如商品服务的库存预警阈值):
yaml
# 配置内容(Data ID: product-service.yaml)
product:
stock:
warning-threshold: 10 # 库存低于10就预警
服务中用@Value或@ConfigurationProperties读取配置:
java
运行
@RestController
public class ProductController {
@Value("${product.stock.warning-threshold}")
private Integer warningThreshold;
@GetMapping("/product/warning")
public Result getWarningThreshold() {
return Result.success(warningThreshold);
}
}
改配置时,直接在 Nacos 控制台修改,服务会自动刷新(需要在类上加@RefreshScope)。
步骤 5:用 Sentinel 做熔断降级(保护服务不被拖垮)
解决的问题:如果商品服务故障(比如响应超时),订单服务一直等待,会导致订单服务资源耗尽(“雪崩效应”),需要熔断 / 降级。
操作步骤:
引入 Sentinel 依赖:
xml
<dependency>
<groupId>com.alibaba.cloud</groupId>
<artifactId>spring-cloud-starter-alibaba-sentinel</artifactId>
</dependency>
配置 Sentinel 控制台地址(application.yml):
yaml
spring:
cloud:
sentinel:
transport:
dashboard: localhost:8080 # Sentinel控制台地址
对 Feign 调用添加熔断策略(application.yml):
yaml
feign:
sentinel:
enabled: true # 开启Feign的Sentinel支持
定义 Feign 客户端的熔断降级类(服务调用失败时执行):
java
运行
// 商品服务Feign客户端的降级类
@Component
public class ProductFeignFallback implements ProductFeignClient {
@Override
public Result deductStock(Long productId, Integer count) {
// 降级逻辑:返回“库存扣减失败,请稍后重试”
return Result.fail("当前商品服务繁忙,请稍后再试");
}
}
// 在FeignClient中指定降级类
@FeignClient(name = "product-service", fallback = ProductFeignFallback.class)
public interface ProductFeignClient { ... }
启动 Sentinel 控制台,当商品服务故障时,订单服务会自动触发降级,避免被拖垮。
步骤 6:用 Gateway 做 API 网关(统一入口 + 路由转发)
解决的问题:前端调用后端服务时,不需要记多个服务地址,统一通过网关访问(比如/api/user/*转发到用户服务,/api/order/*转发到订单服务)。
操作步骤:
创建网关服务(gateway-service),引入依赖:
xml
<dependency>
<groupId>org.springframework.cloud</groupId>
<artifactId>spring-cloud-starter-gateway</artifactId>
</dependency>
<dependency>
<groupId>com.alibaba.cloud</groupId>
<artifactId>spring-cloud-starter-alibaba-nacos-discovery</artifactId>
</dependency>
配置路由规则(application.yml):
yaml
spring:
cloud:
gateway:
routes:
- id: user-route # 路由ID
uri: lb://user-service # 转发到用户服务(lb表示负载均衡)
predicates:
- Path=/api/user/** # 匹配路径:/api/user/*转发到用户服务
filters:
- StripPrefix=1 # 去掉路径中的/api前缀(实际转发到/user/*)
- id: order-route
uri: lb://order-service
predicates:
- Path=/api/order/**
filters:
- StripPrefix=1
前端调用时,直接访问网关地址:
http://localhost:8080/api/order/create → 网关转发到订单服务。
分布式系统下的十二种核心算法!!!!!!!!!!!!!!
一、布隆过滤器(Bloom Filter):用极小空间判断 “有没有”
1. 核心定位
一种空间效率极高的概率型数据结构,专门用来判断 “某个元素是否在一个集合中”。它的特点是:不会漏判(不存在的元素一定能判断对),但可能误判(存在的元素有极小概率判断错)。
2. 通俗原理
可以类比成 “小区快递柜”:
先准备一个很长的 “空柜子”(对应算法中的位数组,每个位置只有 0 或 1 两种状态)。
当一个快递(对应元素)放入时,用 3~5 个不同的 “快递员”(对应哈希函数),每个快递员会把快递放到柜子的一个固定位置(比如哈希函数 1 算出来放第 10 位,哈希函数 2 算出来放第 25 位),并把这些位置的状态从 0 改成 1。
当判断 “某个快递是否在柜子里” 时,同样让这 3~5 个快递员去查对应的位置:
如果所有位置都是 1,说明 “大概率在里面”(可能误判,因为其他快递可能刚好把这些位置占了);
如果有任何一个位置是 0,说明 “一定不在里面”(没放进去过,这些位置不可能被改)。
3. 优缺点
优点:空间占用极小(存储 100 万数据,只需约 1MB)、判断速度极快(只走几次哈希)。
缺点:有 “假阳性” 误判(不能用它判断 “一定存在”)、不支持删除元素(删了会影响其他元素的判断)。
4. 典型场景
缓存穿透防护:先查布隆过滤器,不存在就直接返回,避免请求打到数据库。
海量数据去重:比如爬虫判断 “某个 URL 是否已经爬过”,无需存储所有 URL。
分布式系统中判断 “某个 ID 是否在集群中”:比如 HBase 判断行键是否存在。
二、HyperLogLog(HLL):用极小空间统计 “有多少个不同的”
1. 核心定位
一种基数估算算法,用来统计 “一个集合中不同元素的个数”(即基数)。它的特点是:空间占用极小,精度可控制,不需要存储所有元素。
2. 通俗原理
可以类比成 “通过抛硬币估算班级人数”:
让每个同学(对应元素)抛硬币,记录 “第一次抛出正面之前,连续抛了多少次反面”(比如 A 同学抛了 3 次反面才出正面,记录 3;B 同学抛了 5 次,记录 5)。
找到所有同学中 “连续反面次数最多的那个值”(比如最多是 6 次)。
根据这个 “最大值” 估算总人数:因为 “连续 6 次反面” 的概率是 (1/2)^6=1/64,所以大概有 64 个同学(算法会用更精准的公式修正这个估算值)。
HLL 的实际逻辑类似:
把每个元素通过哈希函数转换成一个很长的二进制数(比如 64 位)。
统计这个二进制数中 “从开头开始连续的 0 的个数”(比如 “000101...” 的连续 0 个数是 3)。
把所有元素的 “连续 0 个数” 分组统计,找到每组的最大值,再用公式估算总基数。
3. 优缺点
优点:空间占用极小(统计 1 亿数据,只需约 12KB)、支持动态新增数据、精度可通过参数控制(默认误差率约 0.81%)。
缺点:结果是估算值(不是精确值)、不支持删除元素(删了无法修正基数)。
4. 典型场景
互联网产品的 UV 统计:比如统计 “某页面一天有多少个不同用户访问”,无需存储所有用户 ID。
数据库中的基数统计:比如 MySQL 的COUNT(DISTINCT)在数据量大时,会用 HLL 优化性能。
流处理系统中的实时基数统计:比如 Flink 统计 “实时日志中不同设备 ID 的个数”。
三、一致性哈希(Consistent Hashing):解决 “节点变动时数据大规模迁移” 的问题
1. 核心定位
一种分布式系统负载均衡算法,主要用来解决 “传统哈希在节点新增 / 删除时,大量数据需要重新映射” 的痛点,让节点变动时 “只迁移少量数据”。
2. 通俗原理
可以类比成 “环形商场的店铺分配”:
画一个 “环形地图”(对应算法中的哈希环),把环的范围分成 0~2^32-1 的数字(像时钟一样循环)。
把每个服务器节点(比如缓存节点、数据库节点)通过哈希函数转换成一个数字,然后放到环上的对应位置(比如节点 A 哈希后是 100,就放在环上 100 的位置)。
把需要存储的数据也通过同样的哈希函数转换成数字,然后在环上 “顺时针找最近的节点”,把数据存到这个节点上(比如数据 X 哈希后是 150,顺时针最近的节点是 200 的节点 B,就存在 B 上)。
关键优化:虚拟节点如果节点太少,容易出现 “数据倾斜”(比如 3 个节点集中在环的某一段,导致某节点存了 80% 的数据)。解决办法是给每个真实节点 “复制多个分身”(即虚拟节点),比如节点 A 对应 10 个虚拟节点,分别放在环的不同位置,这样数据就能更均匀地分布。
3. 优缺点
优点:节点新增 / 删除时,只迁移 “该节点在环上负责的那段数据”(迁移量极小)、支持数据均匀分布(通过虚拟节点)。
缺点:实现需要处理 “虚拟节点映射”、极端情况下仍可能有数据倾斜(需调整虚拟节点数量)。
4. 典型场景
Redis 哈希槽确实基于一致性哈希的核心思想(解决节点变动少迁移数据),但它不是完全照搬的 “标准一致性哈希”,而是做了更工程化的优化,相当于 “一致性哈希的进阶版”。
下面用 “相同核心 + 关键差异” 的逻辑,把两者的关系讲透,避免混淆底层实现。
一、先肯定:两者的核心目标完全一致
无论是标准一致性哈希,还是 Redis 哈希槽,解决的都是同一个分布式痛点:避免节点新增 / 删除时,全量数据重新映射。
举个例子:
没有这两种机制时,若 3 个 Redis 节点,数据按 “hash(key) % 3” 分配,当新增 1 个节点(变成 4 个),所有数据的 “%结果” 都会变,导致100% 数据需要迁移;
有了一致性哈希 / 哈希槽后,新增节点时,只需要迁移 “新节点负责的那部分数据”(通常是 1/N,N 是总节点数),迁移量大幅降低。
分布式缓存:比如 Redis Cluster、Memcached 的集群部署,用一致性哈希分配数据。
分布式数据库:比如 Cassandra、MongoDB 的分片集群,用一致性哈希决定数据存在哪个分片。
CDN 节点调度:判断用户请求应该路由到哪个 CDN 节点获取资源。
算法实现思路
先举个通俗例子帮你理解核心价值:
传统哈希(比如 key%服务器数量):如果服务器从 3 台扩容到 4 台,几乎所有 key 的映射关系都会失效,导致大量缓存穿透,数据库压力骤增。
一致性哈希:服务器扩容 / 缩容时,只有少量 key 的映射关系变化,极大减少缓存失效问题,这是它的核心优势。
二、一致性哈希算法的核心实现思路(分 4 步)
把整个逻辑拆解成 4 个可落地的步骤,每一步都对应代码里的核心逻辑:
步骤 1:构建「哈希环」
逻辑:把哈希值的取值范围(通常用 0 ~ 2^32 - 1,约 42 亿)想象成一个首尾相连的环形(比如 0 和 2^32-1 挨着)。
类比:就像一个圆形的跑道,跑道上的每一个点对应一个哈希值。
步骤 2:将「物理服务器节点」映射到哈希环
逻辑:
给每个物理服务器一个唯一标识(比如 192.168.1.1:8080、192.168.1.2:8080);
对这个标识做哈希计算(比如 MD5 哈希),得到一个 0~2^32-1 之间的整数;
把这个整数作为服务器在哈希环上的「位置」,将服务器节点挂到环上。
步骤 3:将「数据 (key)」映射到服务器
逻辑:
对数据的 key 做和服务器相同的哈希计算,得到一个哈希值;
在哈希环上顺时针查找,找到第一个比这个 key 哈希值大的服务器节点;
这个节点就是该 key 要分配的服务器。
特殊情况:如果 key 的哈希值是环上最大的,就分配给环上第一个节点(首尾相连)。
步骤 4:解决「哈希环偏斜」问题(虚拟节点)
问题:如果物理节点太少,可能集中在环的某一段,导致 key 分配不均(比如一个节点扛 90% 的流量)。
解决方案:给每个物理节点创建多个「虚拟节点」(比如 1 个物理节点对应 100 个虚拟节点):
虚拟节点的标识:物理节点标识 + 序号(比如 192.168.1.1:8080#1、192.168.1.1:8080#2);
把虚拟节点映射到哈希环上;
查找 key 时,先找到对应的虚拟节点,再通过虚拟节点找到对应的物理节点。
代码关键部分解析
哈希函数 _hash:
用 MD5 而非 Python 内置的hash(),因为hash()的结果是随机的(每次运行程序不同),而 MD5 是稳定的;
把 MD5 的 16 进制结果转成整数,并限制在0~2^32-1,符合哈希环的范围。
有序哈希环 hash_ring:
用bisect.insort保证列表始终有序,这样可以用二分查找(bisect_right)快速定位,时间复杂度从 O (n) 降到 O (logn)。
虚拟节点处理:
每个物理节点生成virtual_node_num个虚拟节点,通过#序号区分;
查找 key 时先找虚拟节点,再映射到物理节点,解决节点分布不均的问题。
核心查找逻辑 get_node:
bisect_right找到第一个比 key_hash 大的虚拟节点位置;
如果 key_hash 是环上最大的(idx 等于环长度),则取第一个节点(环首尾相连)。
五、总结
一致性哈希的核心是「哈希环 + 顺时针映射」,解决了传统哈希扩容 / 缩容时缓存大量失效的问题;
虚拟节点是关键优化,用来解决哈希环偏斜(节点分布不均)的问题,数量越多分配越均衡(通常设 100~200);
代码核心步骤:构建哈希环→节点映射→key 映射→虚拟节点优化,照着这个逻辑就能写出可运行的一致性哈希算法。
把公众号上面的内容直接抄过来吧,感觉他讲得更加详细
负载均衡:由于访问人数太多,我们的网站部署了多台服务器个共同提供相同的服务,但每台服务器上存储的数据不同。为了保证请求的正确响应,相同参数(key)的请求(比如同个 IP 的请求、同一个用户的请求)需要发到同一台服务器处理。
分布式缓存:由于缓存数据量太大,我们部署了多台缓存服务器共同提供缓存服务。缓存数据需要尽可能均匀地分布式在这些缓存服务器上,通过 key 可以找到对应的缓存服务器。
普通哈希算法
大家很快就能想到哈希+取模这个经典组合
node_number=hash(key) % N
hash(key): 使用哈希函数(建议使用性能较好的非加密哈希函数,例如 SipHash、MurMurHash3、CRC32、DJB)对唯一键进行哈希。
% N: 对哈希值取模,将哈希值映射到一个介于 0 到 N-1 之间的值,N 为节点数/服务器数。
然而,传统的哈希取模算法有一个比较大的缺陷就是:无法很好的解决机器/节点动态减少(比如某台机器宕机)或者增加的场景(比如又增加了一台机器)。
想象一下,服务器的初始数量为 4 台 (N = 4),如果其中一台服务器宕机,N 就变成了 3。此时,对于同一个 key,hash(key) % 3 的结果很可能与 hash(key) % 4 完全不同。
这意味着几乎所有的数据映射关系都会错乱。在分布式缓存场景下,这会导致大规模的缓存失效和缓存穿透,瞬间将压力全部打到后端的数据库上,引发系统雪崩。
据估算,当节点数量从 N 变为 N-1 时,平均有 (N-1)/N 比例的数据需要迁移,这个比例 趋近于 100% 。这种“牵一发而动全身”的效应,在生产环境中是完全不可接受的。
为了更好地解决这个问题,一致性哈希算法诞生了。
一致性哈希算法在 1997 年由麻省理工学院提出
是一种特殊的哈希算法,在移除或者添加一个服务器时,能够尽可能小地改变已存在的服务请求与处理请求服务器之间的映射关系。一致性哈希解决了传统哈希算法在分布式哈希表(Distributed Hash Table,DHT)中存在的动态伸缩等问题 。
一致性哈希算法的底层原理也很简单,关键在于哈希环的引入。
一致性哈希算法将哈希空间组织成一个环形结构,将数据和节点都映射到这个环上,然后根据顺时针的规则确定数据或请求应该分配到哪个节点上。通常情况下,哈希环的起点是 0,终点是 2^32 - 1,并且起点与终点连接,故这个环的整数分布范围是 [0, 2^32-1] 。
传统哈希算法是对服务器数量取模,一致性哈希算法是对哈希环的范围取模,固定值,通常为 2^32:
服务器/节点如何映射到哈希环上呢?也是哈希取模。例如,一般我们会根据服务器的 IP 或者主机名进行哈希,然后再取模。
hash(服务器ip)% 2^32
图片在文件夹中
我们将数据和节点都映射到哈希环上,环上的每个节点都负责一个区间。对于上图来说,每个节点负责的数据情况如下:
Node1: 负责 Node4 到 Node1 之间的区域(包含 value6)。
Node2: 负责 Node1 到 Node2 之间的区域(包含 value1, value2)。
Node3: 负责 Node2 到 Node3 之间的区域(包含 value3)。
Node4: 负责 Node3 到 Node4 之间的区域(包含 value4, value5)。
假设 Node2 节点被移除的话,那 Node3 就要负责 Node2 的数据,直接迁移 Node2 的数据到 Node3 即可,其他节点不受影响。
图片同样在文件夹中
同样地,如果我们在 Node1 和 Node2 之间新增一个节点 Node5,那么原本应该由 Node2 负责的一部分数据(即哈希值落在 Node1 和 Node5 之间的数据,如图中的 value1)现在会由 Node5 负责。我们只需要将这部分数据从 Node2 迁移到 Node5 即可,同样只影响了相邻的节点,影响范围非常小。
图片同样在文件夹中
数据倾斜问题
理想情况下,节点在环上是均匀分布的。然而,现实可能并不是这样的,尤其是节点数量比较少的时候。节点可能被映射到附近的区域,这样的话,就会导致绝大部分数据都由其中一个节点负责。
示例图在文件夹中
对于上图来说,每个节点负责的数据情况如下:
Node1: 负责 Node4 到 Node1 之间的区域(包含 value6)。
Node2: 负责 Node1 到 Node2 之间的区域(包含 value1)。
Node3: 负责 Node2 到 Node3 之间的区域(包含 value2,value3, value4, value5)。
Node4: 负责 Node3 到 Node4 之间的区域。
除了数据倾斜问题,还有一个隐患。当新增或者删除节点的时候,数据分配不均衡。例如,Node3 被移除的话,Node3 负责的所有数据都要交给 Node4,随后所有的请求都要达到 Node4 上。假设 Node4 的服务器处理能力比较差的话,那可能直接就被干崩了。理想情况下,应该有更多节点来分担压力。
如何解决这些问题呢?答案是引入虚拟节点。
虚拟节点
虚拟节点就是对真实的物理节点在哈希环上虚拟出几个它的分身节点。数据落到分身节点上实际上就是落到真实的物理节点上,通过将虚拟节点均匀分散在哈希环的各个部分。
如下图所示,Node1、Node2、Node3、Node4 这 4 个节点都对应 3 个虚拟节点(下图只是为了演示,实际情况节点分布不会这么有规律)。
依旧文件夹
对于上图来说,每个节点最终负责的数据情况如下:
Node1:value4
Node2:value1,value3
Node3:value5
Node4:value2,value6
引入虚拟节点的好处是巨大的:
数据均衡: 虚拟节点越多,环上的“服务器点”就越密集,数据分布自然就越均匀,从根本上解决了数据倾斜问题。通常,每个真实节点对应的虚拟节点数在 100 到 200 之间,例如 Nginx 选择为每个权重分配 160 个虚拟节点。这里的权重的是为了区分服务器,例如处理能力更强的服务器权重越高,进而导致对应的虚拟节点越多,被命中的概率越大。
容错性增强: 这才是虚拟节点最精妙的地方。当一个物理节点宕机,它相当于在环上的多个虚拟节点同时下线。这些虚拟节点原本负责的数据和流量,会自然地、均匀地分散给环上其他多个不同的物理节点去接管,而不会将压力集中于某一个邻居节点。这极大地提升了系统的稳定性和容错能力。
四、Operational Transformation(OT):解决 “多人实时协同编辑” 的冲突
1. 核心定位
一种实时协同编辑算法,专门解决 “多个人同时编辑同一个文档(如文档、表格)时,操作冲突如何同步” 的问题,保证所有人看到的内容一致。
2. 通俗原理
可以类比成 “多人同时修改一份 Word 文档”:
假设 A 和 B 同时编辑同一行文字,A 想把 “苹果” 改成 “苹果 1”,B 想把 “苹果” 改成 “苹果 2”。
如果没有 OT,A 的修改先传到服务器,B 的修改再传过去时,会发现 “原始内容已经变了”(从 “苹果” 变成了 “苹果 1”),B 的修改就会冲突。
OT 的解决逻辑:
每个操作都带 “上下文信息”:比如 A 的操作记录 “在位置 5,把‘苹果’改成‘苹果 1’”,B 的操作记录 “在位置 5,把‘苹果’改成‘苹果 2’”。
服务器收到 A 的操作后,会把 A 的操作 “转换” 成适合 B 的上下文:比如告诉 B“你原本要改的‘苹果’,现在已经变成‘苹果 1’了,你需要把‘苹果 1’改成‘苹果 12’”(实际转换会更精细,比如按字符位置调整)。
转换后,B 的操作就能正确执行,最终文档变成 “苹果 12”,A 和 B 看到的内容一致。
OT 的实际逻辑更严谨:
把每个编辑操作(如插入、删除字符)拆解成 “操作类型 + 位置 + 内容”。
当多个操作并发时,通过 “操作转换函数”,把后到的操作 “适配” 到已更新的文档状态上,避免冲突。
最后通过 “操作同步协议”,确保所有客户端的操作顺序和内容一致。
3. 优缺点
优点:支持低延迟实时协同(操作秒级同步)、能处理复杂的编辑冲突(如跨段落修改)。
缺点:实现复杂(需要设计转换函数和同步协议)、对网络延迟敏感(延迟高时可能出现短暂不一致)。
4. 典型场景
在线文档工具:Google Docs、腾讯文档、飞书文档的实时协同编辑功能。
在线表格工具:Google Sheets、石墨表格的多人同时编辑。
代码协作工具:GitHub Codespaces、GitPod 的多人实时写代码功能。
五 四叉树(Quadtree):给 “空间数据” 建索引的高效结构
1. 核心定位
一种空间索引数据结构,专门用于管理 “二维空间数据”(如地图坐标、图像像素、游戏场景)。它通过 “不断把空间分成 4 个小象限” 的方式,快速定位和检索空间中的目标。
2. 通俗原理
可以类比 “地图分块导航”:
先把整个区域(比如一张城市地图)看成一个 “大正方形”(根节点)。
如果这个正方形里的目标(比如店铺、路口)太多,就把它平均分成 4 个 “小正方形”(4 个子节点,即四象限)。
每个小正方形如果目标还是太多,就继续分,直到每个小正方形里的目标数量很少(或达到设定阈值),停止分割。
当需要查找 “某坐标附近的目标” 时,不用遍历整个地图,只需找到目标所在的 “小正方形”,再在这个小范围内搜索,效率大幅提升。
比如在游戏中,判断 “玩家是否碰到敌人”:
把游戏地图分成多个四叉树节点,玩家只需要检测自己所在节点及相邻节点的敌人,不用检测全地图敌人。
3. 优缺点
优点:空间检索速度快(避免全量遍历)、适合稀疏空间数据(大部分区域无目标时,无需细分)。
缺点:空间分布不均时效率下降(比如某象限目标极多,会分很多层)、不适合高维数据(二维以上更适合 K-D 树等结构)。
4. 典型场景
地理信息系统(GIS):比如地图 APP 查找 “某位置 500 米内的餐厅”,用四叉树快速定位区域。
游戏开发:比如 Unity、Unreal 引擎中的 “碰撞检测”,只检测玩家所在区域的物体。
图像压缩与处理:比如 JPEG 图像的分块处理,用四叉树划分图像区域,优化压缩效率。
六 、LossyCount:用有限空间统计 “流数据高频元素” 的算法
1. 核心定位
一种流数据频率估算算法,专门解决 “数据流无限(如实时日志)、内存有限” 的场景,能在不存储所有数据的情况下,估算出 “出现频率较高的元素”(即 Top-K 元素),允许少量误差(“Lossy” 意为 “有损”)。
2. 通俗原理
可以类比 “超市记高频商品”:
超市经理想知道 “哪些商品卖得最多”,但没时间记每笔交易,只带了一个小本子(对应有限内存)。
本子上只记 “商品名 + 当前销量”,且设定一个 “最小计数阈值”(比如 10)。
每卖出一件商品:
如果商品在本子上,销量 + 1;
如果不在本子上,且本子没满,就记下来(销量 = 1);
如果本子满了,就把所有商品的销量 - 1,销量变成 0 的商品从本子上删掉(相当于 “过滤低频商品”)。
最后本子上剩下的,就是 “大概率卖得最多的商品”(可能有少量误差,但能排除绝大多数低频商品)。
算法的核心逻辑:通过 “定期减计数” 过滤低频元素,用有限内存保留高频元素,同时估算它们的频率。
3. 优缺点
优点:内存占用极低(只存高频元素)、支持无限流数据(无需存储历史数据)、实现简单。
缺点:结果有误差(低频元素可能被误判为高频,或高频元素频率估算不准)、无法统计低频元素(只关注 Top-K)。
4. 典型场景
实时日志分析:比如统计 “某小时内访问量最高的 10 个接口”,无需存储所有接口的访问记录。
网络流量监控:比如统计 “某时间段内发送数据包最多的 10 个 IP”,节省内存开销。
电商实时推荐:比如统计 “当前直播间被点击最多的 5 个商品”,快速更新推荐列表。
七 射线法(RayCasting):判断 “点是否在空间区域内” 的经典算法
1. 核心定位
一种空间几何判断算法,主要用于判断 “一个点是否在某个多边形(或闭合区域)内部”,广泛应用于图形学、地理围栏等场景。
2. 通俗原理
可以类比 “穿线找区域”:
假设你站在一个点(目标点 P)上,向一个固定方向(比如正右方)画一条 “无限长的射线”。
观察这条射线与多边形的 “边” 相交的次数:
如果相交次数是奇数,说明点在多边形内部(射线穿进穿出次数不对等,最终在内部);
如果相交次数是偶数(包括 0 次),说明点在多边形外部(射线穿进穿出次数对等,最终在外部)。
比如判断 “你是否在学校操场内”:
把操场看成一个多边形,你所在的位置是点 P,向右画一条射线,数射线穿过操场边界的次数:穿 1 次(奇数)→ 在内部,穿 2 次(偶数)→ 在外部。
3. 优缺点
优点:逻辑简单易懂、计算效率高(只需遍历多边形的边,计算交点)、支持任意复杂多边形(包括凹多边形)。
缺点:需处理 “边界特殊情况”(比如射线刚好穿过多边形的顶点或边,需特殊判断避免误算)、只适用于二维空间(三维空间需用其他算法)。
4. 典型场景
地理围栏:比如外卖 APP 判断 “用户地址是否在配送范围内”,配送范围是多边形,用户地址是点。
图形学:比如 PS 中判断 “鼠标点击是否在选区内部”,选区是多边形,点击位置是点。
游戏场景:比如判断 “玩家是否进入了安全区”,安全区是闭合区域,玩家坐标是点。
八 Rsync:实现 “增量数据同步” 的高效协议
1. 核心定位
一种数据同步协议,专门解决 “两台设备之间同步大文件 / 大量文件时,避免全量传输” 的问题。它只传输 “源文件与目标文件的差异部分”,大幅减少网络带宽消耗。
2. 通俗原理
可以类比 “抄作业只补差异”:
小明(目标设备)有一份旧作业,小红(源设备)有更新后的作业,两人想让作业一致。
小明先把自己的旧作业 “撕成小块”(比如每 10 行撕成一块),给每块算一个 “指纹”(哈希值),然后把这些指纹发给小红。
小红拿到指纹后,对照自己的新作业:
找到 “新作业中与旧作业指纹相同的块”(这些块内容没变,不用传);
只把 “新作业中指纹不同的块”(内容有变化)和 “新增的块” 发给小明。
小明拿到这些差异块后,用自己旧作业的不变块,加上小红发的差异块,拼成和小红一样的新作业,完成同步。
Rsync 的核心逻辑:通过 “分块哈希对比” 找到差异,只传差异数据,而非全量文件。
3. 优缺点
优点:带宽利用率极高(大文件同步时,差异部分可能只占原文件的 1%)、支持跨平台(Linux/Windows/macOS 都能用)、同步后数据完全一致(无误差)。
缺点:首次同步开销大(目标设备需计算全部分块的哈希)、对小文件同步优势不明显(小文件分块哈希的开销可能超过全量传输)。
4. 典型场景
服务器数据备份:比如公司服务器每天备份数据到异地备份机,用 Rsync 只传当天变化的文件块。
代码仓库同步:比如开发者用rsync命令同步本地代码和服务器代码,只传修改过的文件。
大文件分享:比如朋友之间传 10GB 的视频,用 Rsync 先传一次,后续更新时只传剪辑过的差异部分。
九 漏桶算法(Leaky Bucket):控制 “流量输出速率” 的经典限流算法
1. 核心定位
一种流量控制算法,主要用于限制 “数据传输或请求处理的速率”,确保系统按 “匀速” 处理请求,避免突发流量冲垮系统(比如秒杀时的大量请求)。
2. 通俗原理
可以类比 “带孔的水桶接水”:
有一个水桶(对应 “请求缓冲区”),水桶底部有一个小孔(对应 “系统处理能力”),水以固定速度从小孔流出(系统匀速处理请求)。
外部的水(对应 “用户请求”)随机倒入水桶:
如果水桶没满,水就加入水桶(请求进入缓冲区等待);
如果水桶满了,多余的水就溢出(请求被丢弃或返回 “限流提示”);
无论倒入的水有多快,流出的速度始终固定(系统处理速率不变)。
比如秒杀系统限流:
系统每秒能处理 1000 个请求(水桶孔的出水速度),水桶容量是 500(最多缓存 500 个请求)。
秒杀开始时,每秒有 10000 个请求涌入,水桶迅速装满,多余的 9500 个请求被丢弃,系统只按每秒 1000 个的速度处理缓存的请求,不会被冲垮。
3. 优缺点
优点:输出速率绝对平稳(避免系统处理忽快忽慢)、实现简单(只需维护 “当前水量” 和 “流出速率” 两个变量)。
缺点:应对突发流量能力差(即使系统有空闲,也不能快速处理缓存外的请求)、缓冲区设置难(容量太小易丢请求,太大易导致请求延迟过高)。
4. 典型场景
API 接口限流:比如开放平台限制 “每个用户每秒最多调用 10 次接口”,用漏桶控制输出速率。
网络带宽控制:比如路由器限制 “某设备每秒最多上传 1MB 数据”,避免单个设备占用所有带宽。
消息队列消峰:比如消息队列用漏桶算法控制 “向消费端推送消息的速率”,避免消费端被消息压垮。
十 默克尔树(Merkle Tree):快速校验 “数据一致性” 的哈希树
1. 核心定位
一种哈希树数据结构,主要用于快速验证 “两个数据集是否完全一致”,或 “某条数据是否属于某个数据集”。它通过 “分层哈希” 的方式,把大量数据的校验浓缩成一个 “根哈希”,大幅减少校验成本。
2. 通俗原理
可以类比 “快递包裹的分层校验”:
假设一批快递有 8 个包裹(对应 “叶子节点”),每个包裹贴一个 “独有的标签”(哈希值,比如包裹 1 的哈希是 H1,包裹 2 是 H2)。
把包裹两两分组,每组算一个 “组合标签”(比如 H1 和 H2 的组合哈希是 H12 = 哈希 (H1+H2),H3 和 H4 的组合哈希是 H34 = 哈希 (H3+H4)),这些组合标签是 “第二层节点”。
再把第二层的标签两两分组,算 “更高层的组合标签”(比如 H12 和 H34 的组合哈希是 H1234),直到最后得到一个 “总标签”(根哈希,比如 H12345678)。
当验证 “这批快递是否完整” 时,不用逐个查 8 个包裹:
只需对比双方的 “总标签”(根哈希),如果相同,说明快递完全一致;
如果不同,再对比下一层的标签(比如 H1234 和 H5678),快速定位哪一半出了问题,直到找到具体的错误包裹。
Merkle Tree 的核心逻辑:叶子节点是原始数据的哈希,非叶子节点是其两个子节点哈希的组合哈希,根节点是整个树的 “唯一标识”。
3. 优缺点
优点:数据校验效率高(只需对比根哈希,无需全量数据)、支持局部校验(只需某条数据的 “哈希路径”,不用整个数据集)、安全性高(修改任何一条数据都会导致根哈希变化,无法伪造)。
缺点:构建树的开销大(需计算所有节点的哈希,数据量大时耗时)、只支持静态数据(数据频繁修改时,树的重构成本高)。
4. 典型场景
区块链技术:比如比特币、以太坊用 Merkle Tree 存储交易记录,每个区块的根哈希作为区块的唯一标识,快速验证交易是否被篡改。
分布式存储:比如 IPFS(星际文件系统)用 Merkle Tree 校验 “不同节点存储的文件是否一致”,只需对比根哈希。
数据库备份校验:比如数据库备份后,用 Merkle Tree 生成根哈希,恢复时对比根哈希,快速判断备份是否完整。
以上所有算法我会给出简单的java代码demo,具体如何在项目中应用非常灵活,等到遇到的时候可以协助AI一起解决哦,保准能看懂哦
import java.util.BitSet;
import java.util.Random;
public class BloomFilter {
// 位数组大小(2^20约100万,可根据数据量调整)
private static final int BIT_SIZE = 1 << 20;
// 哈希函数数量(一般3-5个,越多误判率越低但性能略降)
private static final int HASH_NUM = 3;
private BitSet bits;
private Random[] randoms; // 不同种子的随机数生成器(模拟不同哈希函数)
public BloomFilter() {
bits = new BitSet(BIT_SIZE);
randoms = new Random[HASH_NUM];
for (int i = 0; i < HASH_NUM; i++) {
randoms[i] = new Random(i); // 固定种子,保证哈希函数稳定
}
}
// 添加元素
public void add(String key) {
for (Random r : randoms) {
int hash = Math.abs(r.nextInt(BIT_SIZE)); // 生成0~BIT_SIZE-1的哈希值
bits.set(hash); // 标记对应位为1
}
}
// 判断元素是否可能存在(true=可能存在,false=一定不存在)
public boolean mightContain(String key) {
for (Random r : randoms) {
int hash = Math.abs(r.nextInt(BIT_SIZE));
if (!bits.get(hash)) { // 只要有一位为0,一定不存在
return false;
}
}
return true;
}
// 演示:缓存穿透防护场景
public static void main(String[] args) {
BloomFilter filter = new BloomFilter();
// 模拟数据库中的key
String[] dbKeys = {"user1", "user2", "user3"};
for (String key : dbKeys) {
filter.add(key);
}
// 测试存在的key(应返回true)
System.out.println(filter.mightContain("user1")); // true
// 测试不存在的key(应返回false)
System.out.println(filter.mightContain("user4")); // false
// 可能存在误判(概率极低)
}
}
基数估算代码
二、HyperLogLog(基数估算)
场景:UV 统计(估算独立用户数)
java
运行
import java.util.Random;
public class HyperLogLog {
// 分桶数(2^10=1024桶,精度较高)
private static final int BUCKET_NUM = 1 << 10;
private int[] buckets; // 每个桶存储最大前导零数
private Random random;
public HyperLogLog() {
buckets = new int[BUCKET_NUM];
random = new Random();
}
// 添加元素(用户ID)
public void add(String userId) {
// 模拟哈希:将userId转为64位随机数(实际应使用稳定哈希函数)
long hash = Math.abs(userId.hashCode() ^ random.nextLong());
// 取前10位作为桶索引(2^10=1024)
int bucketIndex = (int) (hash >>> 54); // 64-10=54
// 取后54位,计算前导零个数(最多54个)
long remaining = hash & ((1L << 54) - 1);
int leadingZeros = 64 - 10 - Long.numberOfLeadingZeros(remaining); // 前导零数
// 更新桶的最大值
if (leadingZeros > buckets[bucketIndex]) {
buckets[bucketIndex] = leadingZeros;
}
}
// 估算基数(独立用户数)
public long estimateCardinality() {
double sum = 0;
for (int bucket : buckets) {
sum += 1.0 / (1 << bucket); // 1/(2^bucket)
}
double avg = sum / BUCKET_NUM;
// 修正系数(经验值,针对1024桶)
double alpha = 0.79402;
long estimate = (long) (alpha * BUCKET_NUM * BUCKET_NUM / avg);
return estimate;
}
// 演示:统计网站UV
public static void main(String[] args) {
HyperLogLog hll = new HyperLogLog();
// 模拟1000个独立用户访问
for (int i = 0; i < 1000; i++) {
hll.add("user" + i);
}
// 估算结果(误差约1%)
System.out.println("估算UV:" + hll.estimateCardinality()); // 约1000
}
}
三、一致性哈希(Consistent Hashing)
场景:分布式缓存节点路由(数据分配到缓存节点)
java
运行
import java.util.SortedMap;
import java.util.TreeMap;
public class ConsistentHash {
// 虚拟节点数量(每个真实节点对应100个虚拟节点,减少数据倾斜)
private static final int VIRTUAL_NODE_NUM = 100;
// 哈希环(key=哈希值,value=真实节点名)
private SortedMap<Integer, String> circle = new TreeMap<>();
// 添加节点
public void addNode(String nodeName) {
for (int i = 0; i < VIRTUAL_NODE_NUM; i++) {
// 虚拟节点名:nodeName#i
String virtualNode = nodeName + "#" + i;
int hash = Math.abs(virtualNode.hashCode());
circle.put(hash, nodeName); // 虚拟节点映射到真实节点
}
}
// 移除节点
public void removeNode(String nodeName) {
for (int i = 0; i < VIRTUAL_NODE_NUM; i++) {
String virtualNode = nodeName + "#" + i;
int hash = Math.abs(virtualNode.hashCode());
circle.remove(hash);
}
}
// 查找数据对应的节点
public String getNode(String dataKey) {
int hash = Math.abs(dataKey.hashCode());
// 顺时针找第一个大于等于当前哈希的节点
SortedMap<Integer, String> subMap = circle.tailMap(hash);
if (subMap.isEmpty()) {
// 若没有,取环的第一个节点(循环)
return circle.get(circle.firstKey());
} else {
return subMap.get(subMap.firstKey());
}
}
// 演示:缓存节点路由
public static void main(String[] args) {
ConsistentHash ch = new ConsistentHash();
// 添加3个缓存节点
ch.addNode("cache-node1");
ch.addNode("cache-node2");
ch.addNode("cache-node3");
// 测试数据路由
System.out.println("user123 路由到:" + ch.getNode("user123")); // 固定节点
System.out.println("order456 路由到:" + ch.getNode("order456")); // 固定节点
// 移除一个节点,查看路由变化(只有部分数据迁移)
ch.removeNode("cache-node2");
System.out.println("移除node2后,user123 路由到:" + ch.getNode("user123"));
}
}
四、四叉树(Quadtree)
场景:地图 POI 检索(查找某区域内的兴趣点)
java
运行
import java.util.ArrayList;
import java.util.List;
// 二维点坐标
class Point {
double x, y;
Point(double x, double y) {
this.x = x;
this.y = y;
}
}
// 矩形区域(四叉树节点的边界)
class Rect {
double x1, y1; // 左上角
double x2, y2; // 右下角
Rect(double x1, double y1, double x2, double y2) {
this.x1 = x1;
this.y1 = y1;
this.x2 = x2;
this.y2 = y2;
}
// 判断点是否在区域内
boolean contains(Point p) {
return p.x >= x1 && p.x <= x2 && p.y >= y1 && p.y <= y2;
}
}
public class Quadtree {
private static final int CAPACITY = 4; // 每个节点最多存储4个点,超过则分裂
private Rect boundary; // 节点边界
private List<Point> points = new ArrayList<>(); // 节点内的点
private Quadtree[] children; // 四个子节点(NW, NE, SW, SE)
public Quadtree(Rect boundary) {
this.boundary = boundary;
}
// 插入点
public boolean insert(Point p) {
// 点不在边界内,直接返回
if (!boundary.contains(p)) return false;
// 未达容量,直接存储
if (points.size() < CAPACITY) {
points.add(p);
return true;
}
// 达容量,分裂并创建子节点
if (children == null) split();
// 插入到子节点
for (Quadtree child : children) {
if (child.insert(p)) return true;
}
return false;
}
// 分裂为四个子节点
private void split() {
double midX = (boundary.x1 + boundary.x2) / 2;
double midY = (boundary.y1 + boundary.y2) / 2;
// 西北(NW)、东北(NE)、西南(SW)、东南(SE)
children = new Quadtree[4];
children[0] = new Quadtree(new Rect(boundary.x1, boundary.y1, midX, midY));
children[1] = new Quadtree(new Rect(midX, boundary.y1, boundary.x2, midY));
children[2] = new Quadtree(new Rect(boundary.x1, midY, midX, boundary.y2));
children[3] = new Quadtree(new Rect(midX, midY, boundary.x2, boundary.y2));
}
// 检索区域内的所有点
public List<Point> query(Rect area, List<Point> result) {
if (!overlaps(boundary, area)) return result;
// 检查当前节点的点是否在检索区域内
for (Point p : points) {
if (area.contains(p)) {
result.add(p);
}
}
// 递归查询子节点
if (children != null) {
for (Quadtree child : children) {
child.query(area, result);
}
}
return result;
}
// 判断两个矩形是否重叠
private boolean overlaps(Rect a, Rect b) {
return a.x1 <= b.x2 && a.x2 >= b.x1 && a.y1 <= b.y2 && a.y2 >= b.y1;
}
// 演示:地图POI检索
public static void main(String[] args) {
// 地图范围:x(0-100), y(0-100)
Quadtree quadtree = new Quadtree(new Rect(0, 0, 100, 100));
// 插入POI点
quadtree.insert(new Point(10, 20));
quadtree.insert(new Point(30, 40));
quadtree.insert(new Point(60, 70));
quadtree.insert(new Point(80, 90));
// 检索区域:x(20-70), y(30-80)内的POI
Rect searchArea = new Rect(20, 30, 70, 80);
List<Point> result = new ArrayList<>();
quadtree.query(searchArea, result);
System.out.println("检索到的POI数量:" + result.size()); // 2个(30,40和60,70)
}
}
五、漏桶算法(Leaky Bucket)
场景:API 接口限流(控制每秒请求数)
java
运行
public class LeakyBucket {
private final double capacity; // 桶容量(最多缓存的请求数)
private final double leakRate; // 漏水速率(每秒处理的请求数)
private double currentWater; // 当前水量(缓存的请求数)
private long lastLeakTime; // 上次漏水时间(毫秒)
public LeakyBucket(double capacity, double leakRate) {
this.capacity = capacity;
this.leakRate = leakRate;
this.currentWater = 0;
this.lastLeakTime = System.currentTimeMillis();
}