-
Notifications
You must be signed in to change notification settings - Fork 9
/
Copy pathindex.html
1476 lines (767 loc) · 97.2 KB
/
index.html
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
<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8">
<title></title>
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1">
<meta name="description" content="万物之始，大道至简，衍化至繁">
<meta property="og:type" content="website">
<meta property="og:title" content="鸟窝">
<meta property="og:url" content="https://colobu.com/">
<meta property="og:site_name" content="鸟窝">
<meta property="og:description" content="万物之始，大道至简，衍化至繁">
<meta name="twitter:card" content="summary">
<meta name="twitter:title" content="鸟窝">
<meta name="twitter:description" content="万物之始，大道至简，衍化至繁">
<link rel="alternative" href="/atom.xml" title="鸟窝" type="application/atom+xml">
<link rel="icon" href="/favicon.png">
<link rel="stylesheet" href="css/style.css" type="text/css">
<link href="//cdn.bootcdn.net/ajax/libs/font-awesome/6.6.0/css/all.min.css" rel="stylesheet">
<link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/fancybox/2.1.7/css/jquery.fancybox.min.css"
media="screen" type="text/css">
<link rel="stylesheet" href="//cdnjs.cloudflare.com/ajax/libs/animate.css/3.1.1/animate.min.css" media="screen"
type="text/css">
<link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/tonsky/FiraCode@1.207/distr/fira_code.css">
</head>
<body>
<div id="container">
<div id="wrap">
<header id="header">
<div id="banner"></div>
<div id="header-outer" class="outer">
<div id="header-title" class="inner">
<h1 id="logo-wrap" class="animated bounceInLeft">
<a href="" id="logo">鸟窝</a>
</h1>
<!-- <h2 id="subtitle-wrap" class="animated bounceInLeft"> -->
<h2 id="subtitle-wrap">
<!-- <a href="" id="subtitle">大道至简 Simplicity is the ultimate form of sophistication</a> -->
<a href="https://item.jd.com/14283252.html" target="_blank" style="color: #e32d40;text-decoration: none;"><b>《Go語言全功能開發養成書》繁体中文版发售。一书在手，并发无忧</b></a>
</h2>
</div>
<div id="header-inner" class="inner">
<nav id="main-nav">
<a id="main-nav-toggle" class="nav-icon"></a>
<a class="main-nav-link" href=""><i class="fa fa-home"> </i>首页</a>
<a class="main-nav-link" href="archives"><i class="fa fa-regular fa-folder-open"> </i>归档</a>
<a class="main-nav-link" href="https://github.com/smallnest"><i class="fa fa-brands fa-github-alt"> </i>github</a>
<div class="dropdown main-nav-link"><a class="main-nav-link" href="#"><i class="fa fa-brands fa-golang"> </i>Go学习资源</a>
<div class="dropdown-content">
<a href="/goasm"><i class="fa fa-brands fa-golang"></i> Go汇编示例</a>
<a href="https://gowebexamples.com"><i class="fa fa-brands fa-golang"></i> Go Web开发示例</a>
<a href="http://go-database-sql.org"><i class="fa fa-brands fa-golang"></i> Go 数据库开发教程</a>
<a href="https://colobu.com/gotips/"><i class="fa fa-brands fa-golang"></i> Go 语言编程技巧</a>
<hr>
<a href="http://rpcx.io"><i class="fa undefined"></i> RPCX官网</a>
<a href="http://cn.doc.rpcx.io"><i class="fa undefined"></i> RPC开发指南</a>
</div>
</div>
<div class="dropdown main-nav-link"><a class="main-nav-link" href="#"><i class="fa fa-brands fa-rust"> </i>Rust学习资源</a>
<div class="dropdown-content">
<a href="/perf-book"><i class="fa fa-brands fa-rust"></i> Rust高性能编程指南</a>
<a href="/rust100"><i class="fa fa-brands fa-rust"></i> 100个练习题学习Rust</a>
<a href="/atomics"><i class="fa fa-brands fa-rust"></i> Rust原子操作和锁</a>
<a href="/effective-rust"><i class="fa fa-brands fa-rust"></i> 高效Rust编程</a>
<a href="/thebook"><i class="fa fa-brands fa-rust"></i> Rust程序设计语言</a>
<a href="/nomicon"><i class="fa fa-brands fa-rust"></i> Rust死灵书</a>
<a href="/rust-reference"><i class="fa fa-brands fa-rust"></i> Rust参考手册</a>
<a href="/tlborm"><i class="fa fa-brands fa-rust"></i> Rust宏小册</a>
<a href="/async-book"><i class="fa fa-brands fa-rust"></i> Rust异步编程书</a>
<a href="/rust-by-example"><i class="fa fa-brands fa-rust"></i> 通过例子学Rust</a>
<a href="/api-guidelines"><i class="fa fa-brands fa-rust"></i> Rust API 编写指南</a>
<a href="/comprehensive-rust"><i class="fa fa-brands fa-rust"></i> 全面Rust课程</a>
<a href="/easy-rust"><i class="fa fa-brands fa-rust"></i> 简单英语学Rust</a>
<a href="/rust-patterns"><i class="fa fa-brands fa-rust"></i> Rust设计模式</a>
<a href="/2020/03/05/A-half-hour-to-learn-Rust/"><i class="fa fa-brands fa-rust"></i> 半小时学会Rust</a>
<a href="/rust-cookbook"><i class="fa fa-brands fa-rust"></i> Rust实用指南(cookbook)</a>
<a href="/rust-rand"><i class="fa fa-brands fa-rust"></i> Rust随机库</a>
<hr>
<a href="https://rpcx.io/r/E6v8U"><i class="fa undefined"></i> Rust for the Polyglot Programmer</a>
<a href="https://rpcx.io/r/oC5ii"><i class="fa undefined"></i> LifetimeKata</a>
<a href="https://tfpk.github.io/macrokata/"><i class="fa undefined"></i> macrokata</a>
</div>
</div>
<div class="dropdown main-nav-link"><a class="main-nav-link" href="#"><i class="fa undefined"> </i>出版书籍</a>
<div class="dropdown-content">
<a href="/ScalaCollectionsCookbook"><i class="fa undefined"></i> Scala集合技术手册（简/繁）</a>
<a href="https://cpgo.colobu.com/"><i class="fa undefined"></i> 深入理解Go并发编程（简/繁）</a>
<a href="https://item.jd.com/14347716.html"><i class="fa undefined"></i> 100个Go语言典型错误</a>
</div>
</div>
<a class="main-nav-link" href="ScalaCollectionsCookbook"><i class="fa fa-solid fa-book"> </i>Scala集合技术手册</a>
<a class="main-nav-link" href="about"><i class="fa fa-regular fa-address-card"> </i>关于</a>
</nav>
<nav id="sub-nav">
<a id="nav-rss-link" class="nav-icon" href="/atom.xml" title="RSS Feed"></a>
<a id="nav-search-btn" class="nav-icon" title="Search"></a>
</nav>
<div id="search-form-wrap">
<form action="https://www.google.com/search" method="get" accept-charset="utf-8" class="search-form">
<input type="search" id="search-word" name="q" maxlength="20" class="search-form-input" placeholder="Search">
<input type=hidden name=ie value="utf-8">
<input type=hidden name=oe value="utf-8">
<input type=hidden name=hl value="zh-CN">
<input type="submit" id="search-submit" value="" class="search-form-submit">
</form>
</div>
</div>
</div>
</header>
<div class="outer">
<section id="main">
<article id="post-the-state-of-simd-in-go" class="article article-type-post" itemscope
itemprop="blogPost">
<div class="article-meta">
<a href="2025/02/01/the-state-of-simd-in-go" class="article-date">
<time datetime="2025-02-01T15:39:40.000Z" itemprop="datePublished">2025年02月01日</time>
</a>
<div class="article-category">
<a class="article-category-link" href="categories/Go">Go</a>
</div>
<div class="article-author"> by smallnest</div>
</div>
<div class="article-inner">
<header class="article-header">
<h1 itemprop="name">
<a class="article-title" href="2025/02/01/the-state-of-simd-in-go">啥时候等到Go官方支持SIMD?</a>
</h1>
</header>
<div class="article-entry" itemprop="articleBody">
<img class="article-post-image" src="/images/logos/golang7.png">
<p>单指令多数据流（<code>SIMD</code>，Single Instruction Multiple Data）是一种并行计算技术，允许一条指令同时处理多个数据点。SIMD在现代CPU中广泛应用，能够显著提升计算密集型任务的性能，如图像处理、机器学习、科学计算等。随着Go语言在高性能计算领域的应用逐渐增多，SIMD支持成为了开发者关注的焦点。</p>
<p>当前很多主流和新型的语言都有相应的<code>simd</code>库了，比如C++、Rust、Zig等，但Go语言的<code>simd</code>官方支持还一直在讨论中(<a href="https://github.com/golang/go/issues/67520" target="_blank" rel="external">issue#67520</a>)。Go语言的设计目标是简单性和可移植性，而SIMD的实现通常需要针对不同的硬件架构进行优化，这与Go的设计目标存在一定冲突。因此，Go语言对SIMD的支持一直备受争议。<br>最近几周这个issue的讨论有活跃起来， 希望能快点支持。</p>
<p class="article-more-link">
<a href="2025/02/01/the-state-of-simd-in-go#more">阅读全文</a>
</p>
</div>
<footer class="article-footer">
</footer>
</div>
</article>
<article id="post-scan-clickhouse-service" class="article article-type-post" itemscope
itemprop="blogPost">
<div class="article-meta">
<a href="2025/01/31/scan-clickhouse-service" class="article-date">
<time datetime="2025-01-31T04:02:33.000Z" itemprop="datePublished">2025年01月31日</time>
</a>
<div class="article-category">
<a class="article-category-link" href="categories/Go">Go</a>
</div>
<div class="article-author"> by smallnest</div>
</div>
<div class="article-inner">
<header class="article-header">
<h1 itemprop="name">
<a class="article-title" href="2025/01/31/scan-clickhouse-service">DeepSeek数据库暴露？扫描一下，应该不止此一家吧!</a>
</h1>
</header>
<div class="article-entry" itemprop="articleBody">
<img class="article-post-image" src="/images/logos/golang8.png">
<p>DeepSeek出街老火了，整个AI界都在热火朝天的讨论它。</p>
<p>同时，安全界也没闲着，来自美国的攻击使它不得不通知中国大陆以外的手机号的注册，同时大家也对它的网站和服务安全性进行了审视，这不Wiz Research就发现它们的数据库面向公网暴露并且无需任何身份即可访问。这两个域名oauth2callback.deepseek.com:9000和dev.deepseek.com:9000。</p>
<p>AI的核心技术既需要这些清北的天才去研究，产品也需要专业的人才去打磨。像DeepSeek这么专业的公司都可能出现这样的漏洞，相信互联网上这么数据库无密码暴露的实例也应该不在少数(实际只找到了2个)。</p>
<p>基于上一篇《扫描全国的公网IP要多久》，我们改造一下代码，让它使用 <code>tcp_syn</code> 的方式探测clickhopuse的9000端口。</p>
<p>首先声明，所有的技术都是为了给大家介绍使用Go语言开发底层的网络程序所做的演示，不是为了介绍安全和攻击方面的内容，所以也不会使用已经成熟的端口和IP扫描工具如zmap、rustscan、nmap、masscan、Advanced IP Scanner、Angry IP Scanner、unicornscan等工具。</p>
<p>同时，也不会追求快速，我仅仅在家中的100M的网络中，使用一台10多年前的4核Linux机器进行测试，尽可能让它能出结果。我一般晚上启动它，早上吃过早餐后来查看结果。</p>
<p class="article-more-link">
<a href="2025/01/31/scan-clickhouse-service#more">阅读全文</a>
</p>
</div>
<footer class="article-footer">
</footer>
</div>
</article>
<article id="post-some-notes-about-go-io-fs-package" class="article article-type-post" itemscope
itemprop="blogPost">
<div class="article-meta">
<a href="2025/01/30/some-notes-about-go-io-fs-package" class="article-date">
<time datetime="2025-01-29T16:44:01.000Z" itemprop="datePublished">2025年01月30日</time>
</a>
<div class="article-category">
<a class="article-category-link" href="categories/Go">Go</a>
</div>
<div class="article-author"> by smallnest</div>
</div>
<div class="article-inner">
<header class="article-header">
<h1 itemprop="name">
<a class="article-title" href="2025/01/30/some-notes-about-go-io-fs-package">趁着假期， 快速了解 Go io/fs 包</a>
</h1>
</header>
<div class="article-entry" itemprop="articleBody">
<img class="article-post-image" src="/images/logos/golang8.png">
<p>Go 语言的 <code>io/fs</code> 包是 Go 1.16 版本引入的一个标准库包，它定义了文件系统的抽象接口。这个包提供了一种统一的方式来访问<strong>不同类型的文件系统</strong>，包括本地文件系统、内存文件系统、zip 文件等。</p>
<p class="article-more-link">
<a href="2025/01/30/some-notes-about-go-io-fs-package#more">阅读全文</a>
</p>
</div>
<footer class="article-footer">
<ul class="article-tag-list"><li class="article-tag-list-item"><a class="article-tag-list-link" href="tags/Go">Go</a></li></ul>
</footer>
</div>
</article>
<article id="post-how-long-to-scan-all-IPs-of-cn" class="article article-type-post" itemscope
itemprop="blogPost">
<div class="article-meta">
<a href="2025/01/27/how-long-to-scan-all-IPs-of-cn" class="article-date">
<time datetime="2025-01-26T16:38:47.000Z" itemprop="datePublished">2025年01月27日</time>
</a>
<div class="article-category">
<a class="article-category-link" href="categories/Go">Go</a>
</div>
<div class="article-author"> by smallnest</div>
</div>
<div class="article-inner">
<header class="article-header">
<h1 itemprop="name">
<a class="article-title" href="2025/01/27/how-long-to-scan-all-IPs-of-cn">扫描全国的公网IP需要多久？</a>
</h1>
</header>
<div class="article-entry" itemprop="articleBody">
<img class="article-post-image" src="/images/logos/golang8.png">
<p>自从加入百度负责物理网络的监控业务之后，我大部分的都是编写各种各样额度底层的网络程序。业余时间我也是编写一些有趣的网络程序，不仅仅是兴趣，也是为未来的某个业务探索一下技术方案。</p>
<p>而且这次，我想知道，就在我这一个10年前的小mini机器4核机器上，在家庭网络中扫描全国(中国大陆)的所有的公网IP地址需要多少时间。</p>
<p>利用它，我可以知道和全国各省市的运营商、云服务商的联通情况。有没有运营商的出口故障以及IP已没有被运营商或者有关部门劫持。</p>
<p>TL;DR: 一共扫描了<strong>3亿</strong>个地址(343142912)，当前ping的通的IP <strong>592万</strong>个(5923768)，耗时<strong>1小时</strong>(1h2m57.973755197s)。</p>
<p>这次我重构了以前的一个扫描公网IP的程序。先前的程序使用gopacket收发包，也使用gopacket组装包。但是gopacket很讨厌的的一个地方是它依赖libpcap库，没有办法在禁用CGO的情况下。</p>
<p>事实上利用Go的扩展包icmp和ipv4,我们完全可以不使用gopacket实现这个功能，本文介绍具体的实现。</p>
<p>程序的全部代码在：<a href="https://github.com/smallnest/fishfinder" target="_blank" rel="external">https://github.com/smallnest/fishfinder</a></p>
<p class="article-more-link">
<a href="2025/01/27/how-long-to-scan-all-IPs-of-cn#more">阅读全文</a>
</p>
</div>
<footer class="article-footer">
<ul class="article-tag-list"><li class="article-tag-list-item"><a class="article-tag-list-link" href="tags/Go">Go</a></li></ul>
</footer>
</div>
</article>
<article id="post-go-internal-ds-4-ary-heap" class="article article-type-post" itemscope
itemprop="blogPost">
<div class="article-meta">
<a href="2024/11/18/go-internal-ds-4-ary-heap" class="article-date">
<time datetime="2024-11-18T14:47:50.000Z" itemprop="datePublished">2024年11月18日</time>
</a>
<div class="article-category">
<a class="article-category-link" href="categories/Go">Go</a>
</div>
<div class="article-author"> by smallnest</div>
</div>
<div class="article-inner">
<header class="article-header">
<h1 itemprop="name">
<a class="article-title" href="2024/11/18/go-internal-ds-4-ary-heap">Go中秘而不宣的数据结构: 四叉堆，不是普通的二叉堆</a>
</h1>
</header>
<div class="article-entry" itemprop="articleBody">
<img class="article-post-image" src="/images/logos/golang8.png">
<p>Go语言中Timer以及相关的Ticker、time.After、time.AfterFunc 等定时器最终是以四叉堆的数据形式存放的。</p>
<p>全局的 timer 堆也经历过三个阶段的重要升级。</p>
<ul>
<li>Go 1.9 版本之前，所有的计时器由全局唯一的四叉堆维护，goroutine间竞争激烈。</li>
<li>Go 1.10 - 1.13，全局使用 64 个四叉堆维护全部的计时器，通过分片减少了竞争的压力，但是本质上还是没有解决 1.9 版本之前的问题</li>
<li>Go 1.14 版本之后，每个 P 单独维护一个四叉堆，避免了goroutine的竞争。 (后面我们再介绍 per-P 的数据结构)</li>
</ul>
<p>常见的堆(heap)常常以二叉堆的形式实现。可是为什么Go timer使用四叉堆呢？</p>
<p class="article-more-link">
<a href="2024/11/18/go-internal-ds-4-ary-heap#more">阅读全文</a>
</p>
</div>
<footer class="article-footer">
</footer>
</div>
</article>
<article id="post-heapmap" class="article article-type-post" itemscope
itemprop="blogPost">
<div class="article-meta">
<a href="2024/11/17/heapmap" class="article-date">
<time datetime="2024-11-17T09:17:13.000Z" itemprop="datePublished">2024年11月17日</time>
</a>
<div class="article-category">
<a class="article-category-link" href="categories/Go">Go</a>
</div>
<div class="article-author"> by smallnest</div>
</div>
<div class="article-inner">
<header class="article-header">
<h1 itemprop="name">
<a class="article-title" href="2024/11/17/heapmap">HeapMap, 一个混合功能的数据结构Go语言实现</a>
</h1>
</header>
<div class="article-entry" itemprop="articleBody">
<img class="article-post-image" src="/images/logos/golang8.png">
<p>今天在准备《秘而不宣》系列下一篇文章时，思绪飘散了，突然想到使用 Heap 的功能再加 HashTable (Map) 的功能，可以构造一种新的数据结构，然后把我聚合程序中的数据聚合数据结构替换掉，总之思绪翩翩。然后在网上搜了一下，这种数据结构其实早就有了，名字叫 <code>HeapMap</code>。</p>
<p class="article-more-link">
<a href="2024/11/17/heapmap#more">阅读全文</a>
</p>
</div>
<footer class="article-footer">
</footer>
</div>
</article>
<article id="post-go-internal-ds-cacheline" class="article article-type-post" itemscope
itemprop="blogPost">
<div class="article-meta">
<a href="2024/11/17/go-internal-ds-cacheline" class="article-date">
<time datetime="2024-11-17T08:19:01.000Z" itemprop="datePublished">2024年11月17日</time>
</a>
<div class="article-category">
<a class="article-category-link" href="categories/Go">Go</a>
</div>
<div class="article-author"> by smallnest</div>
</div>
<div class="article-inner">
<header class="article-header">
<h1 itemprop="name">
<a class="article-title" href="2024/11/17/go-internal-ds-cacheline">Go中秘而不宣的数据结构 CacheLinePad：精细化优化</a>
</h1>
</header>
<div class="article-entry" itemprop="articleBody">
<img class="article-post-image" src="/images/logos/golang8.png">
<p>在现代多核处理器中，高效的缓存机制极大地提升了程序性能，而“伪共享”问题却常常导致缓存机制的低效。</p>
<p class="article-more-link">
<a href="2024/11/17/go-internal-ds-cacheline#more">阅读全文</a>
</p>
</div>
<footer class="article-footer">
</footer>
</div>
</article>
<article id="post-go-internal-ds-treap" class="article article-type-post" itemscope
itemprop="blogPost">
<div class="article-meta">
<a href="2024/11/17/go-internal-ds-treap" class="article-date">
<time datetime="2024-11-17T08:19:00.000Z" itemprop="datePublished">2024年11月17日</time>
</a>
<div class="article-category">
<a class="article-category-link" href="categories/Go">Go</a>
</div>
<div class="article-author"> by smallnest</div>
</div>
<div class="article-inner">
<header class="article-header">
<h1 itemprop="name">
<a class="article-title" href="2024/11/17/go-internal-ds-treap">Go中秘而不宣的数据结构 Treap：随机化的二叉搜索树</a>
</h1>
</header>
<div class="article-entry" itemprop="articleBody">
<img class="article-post-image" src="/images/logos/golang8.png">
<script>function show_answer(btn, x) { if (btn.value === "显示答案") { btn.value = "隐藏答案" } else { btn.value = "显示答案" } var as = document.getElementById(x); if (as.style.display === "none") { as.style.display = "block" } else { as.style.display = "none" } }</script>
<p><code>treap</code> 是一棵二叉树，它同时维护二叉搜索树 （BST） 和堆的属性, 所以由此得名 (tree + heap ⇒ treap)。</p>
<p>从形式上讲，treap （tree + heap） 是一棵二叉树，其节点包含两个值，一个 <em>key</em> 和一个 <em>priority</em>，这样 <strong>key</strong> 保持 BST 属性，<strong>priority</strong> 是一个保持 heap 属性的随机值（至于是最大堆还是最小堆并不重要）。相对于其他的平衡二叉搜索树，treap的特点是实现简单，且能基本实现随机平衡的结构。属于弱平衡树。</p>
<p><code>treap</code> 由 Raimund Siedel 和 Cecilia Aragon 于 1989 年提出。</p>
<p>treap 通常也被称为“笛卡尔树”，因为它很容易嵌入到笛卡尔平面中：<br><img src="Pasted-image-20241026111752.png" alt=""></p>
<p>具体来说，<code>treap</code> 是一种在二叉树中存储键值对 <code>(X,Y)</code> 的数据结构，其特点是：按 <code>X</code> 值满足二叉搜索树的性质，同时按 <code>Y</code> 值满足二叉堆的性质。如果树中某个节点包含值 <code>(X₀,Y₀)</code>，那么：</p>
<ul>
<li>左子树中所有节点的X值都满足 <code>X ≤ X₀</code> (BST 属性)</li>
<li>右子树中所有节点的X值都满足 <code>X₀ ≤ X</code> (BST 属性)</li>
<li>左右子树中所有节点的Y值都满足 Y ≤ Y₀ （堆属性。这里以最大堆为例）</li>
</ul>
<p>在这种实现中， X是键（同时也是存储在 Treap 中的值），并且 Y称为<strong>优先级</strong>。如果没有优先级，则 treap 将是一个常规的二叉搜索树。</p>
<p>优先级（前提是每个节点的优先级都不相同）的特殊之处在于：它们可以确定性地决定树的最终结构（不会受到插入数据顺序的影响）。这一点是可以通过相关定理来证明的。<br>这里有个巧妙的设计：如果我们随机分配这些优先级值，就能在平均情况下得到一棵比较平衡的树（避免树退化成链表）。这样就能保证主要操作（如查找、插入、删除等）的时间复杂度保持在 O(log N) 水平。<br>正是因为这种随机分配优先级的特点，这种数据结构也被称为"随机二叉搜索树"。</p>
<p><img src="Pasted-image-20241026113542.png" alt=""></p>
<p>Treap维护堆性质的方法用到了旋转，且只需要进行两种旋转操作，因此编程复杂度较红黑树、AVL树要小一些。</p>
<p>红黑树的操作：<br><strong>插入</strong><br><em>以最大堆为例</em><br>给节点随机分配一个优先级，先和二叉搜索树的插入一样，先把要插入的点插入到一个叶子上，然后跟维护堆一样进行以下操作：</p>
<ol>
<li>如果当前节点的优先级比父节点大就进行2. 或3. 的操作</li>
<li>如果当前节点是父节点的左子叶就右旋</li>
<li>如果当前节点是父节点的右子叶就左旋。</li>
</ol>
<p><strong>删除</strong></p>
<p>因为 treap满足堆性质，所以只需要把要删除的节点旋转到叶节点上，然后直接删除就可以了。具体的方法就是每次找到优先级最大的子叶，向与其相反的方向旋转，直到那个节点被旋转到了叶节点，然后直接删除。</p>
<p><strong>查找</strong></p>
<p>和一般的二叉搜索树一样，但是由于 treap的随机化结构，Treap中查找的期望复杂度是 <code>O(logn)</code></p>
<p>以上是 treap 数据结构的背景知识，如果你想了解更多而关于 treap 的知识，你可以参考</p>
<ul>
<li><a href="https://en.wikipedia.org/wiki/Treap" target="_blank" rel="external">https://en.wikipedia.org/wiki/Treap</a></li>
<li><a href="https://medium.com/carpanese/a-visual-introduction-to-treap-data-structure-part-1-6196d6cc12ee" target="_blank" rel="external">https://medium.com/carpanese/a-visual-introduction-to-treap-data-structure-part-1-6196d6cc12ee</a></li>
<li><a href="https://cp-algorithms.com/data_structures/treap.html" target="_blank" rel="external">https://cp-algorithms.com/data_structures/treap.html</a></li>
</ul>
<h2 id="Go_运行时的_treap_和用途">Go 运行时的 treap 和用途</h2>
<p>在 Go 运行时 <a href="https://github.com/golang/go/blob/master/src/runtime/sema.go#L40" target="_blank" rel="external">sema.go#semaRoot</a> 中，定义了一个数据结构 <code>semaRoot</code>:</p>
<figure class="highlight go"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div><div class="line">7</div><div class="line">8</div><div class="line">9</div><div class="line">10</div><div class="line">11</div><div class="line">12</div><div class="line">13</div><div class="line">14</div><div class="line">15</div><div class="line">16</div><div class="line">17</div><div class="line">18</div><div class="line">19</div><div class="line">20</div><div class="line">21</div><div class="line">22</div><div class="line">23</div><div class="line">24</div><div class="line">25</div><div class="line">26</div><div class="line">27</div></pre></td><td class="code"><pre><div class="line"><span class="keyword">type</span> semaRoot <span class="keyword">struct</span> {</div><div class="line"> lock mutex</div><div class="line"> treap *sudog <span class="comment">// 不重复的等待者(goroutine)的平衡树(treap)的根节点</span></div><div class="line"> nwait atomic.Uint32 <span class="comment">// 等待者(goroutine)的数量</span></div><div class="line">}</div><div class="line"></div><div class="line"><span class="keyword">type</span> sudog <span class="keyword">struct</span> {</div><div class="line"> g *g</div><div class="line"></div><div class="line"> next *sudog</div><div class="line"> prev *sudog</div><div class="line"> elem unsafe.Pointer <span class="comment">// data element (may point to stack)</span></div><div class="line"></div><div class="line"> acquiretime <span class="typename">int64</span></div><div class="line"> releasetime <span class="typename">int64</span></div><div class="line"> ticket <span class="typename">uint32</span></div><div class="line"></div><div class="line"> isSelect <span class="typename">bool</span></div><div class="line"> success <span class="typename">bool</span></div><div class="line"></div><div class="line"> waiters <span class="typename">uint16</span></div><div class="line"></div><div class="line"> parent *sudog <span class="comment">// semaRoot binary tree</span></div><div class="line"> waitlink *sudog <span class="comment">// g.waiting list or semaRoot</span></div><div class="line"> waittail *sudog <span class="comment">// semaRoot</span></div><div class="line"> c *hchan <span class="comment">// channel</span></div><div class="line">}</div></pre></td></tr></table></figure>
<p>这是Go语言互斥锁(Mutex)底层实现中的关键数据结构，用于管理等待获取互斥锁的goroutine队列。我们已经知道，在获取 <code>sync.Mutex</code> 时，如果锁已经被其它 goroutine 获取，那么当前请求锁的 goroutine 会被 block 住，就会被放入到这样一个数据结构中 (所以你也知道这个数据结构中的 goroutine 都是唯一的，不重复)。</p>
<p><code>semaRoot</code> 保存了一个平衡树，树中的 <code>sudog</code> 节点都有不同的地址 <code>(s.elem)</code> ,每个 <code>sudog</code> 可能通过 <code>s.waitlink</code> 指向一个链表，该链表包含等待相同地址的其他 <code>sudog</code>。对具有相同地址的 <code>sudog</code> 内部链表的操作时间复杂度都是O(1).。扫描顶层semaRoot列表的时间复杂度是 <code>O(log n)</code>,其中 <code>n</code> 是具有被阻塞goroutine的不同地址的数量（这些地址会散列到给定的semaRoot）。</p>
<p><code>semaRoot</code> 的 <code>treap *sudog</code> 其实就是一个 treap, 我们来看看它的实现。</p>
<h2 id="增加一个元素（入队）">增加一个元素（入队）</h2>
<p>增加一个等待的goroutine(<code>sudog</code>)到 <code>semaRoot</code> 的 <code>treap</code> 中，如果 <code>lifo</code> 为 <code>true</code>，则将 <code>s</code> 替换到 <code>t</code> 的位置，否则将 <code>s</code> 添加到 <code>t</code> 的等待列表的末尾。</p>
<figure class="highlight go"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div><div class="line">7</div><div class="line">8</div><div class="line">9</div><div class="line">10</div><div class="line">11</div><div class="line">12</div><div class="line">13</div><div class="line">14</div><div class="line">15</div><div class="line">16</div><div class="line">17</div><div class="line">18</div><div class="line">19</div><div class="line">20</div><div class="line">21</div><div class="line">22</div><div class="line">23</div><div class="line">24</div><div class="line">25</div><div class="line">26</div><div class="line">27</div><div class="line">28</div><div class="line">29</div><div class="line">30</div><div class="line">31</div><div class="line">32</div><div class="line">33</div><div class="line">34</div><div class="line">35</div><div class="line">36</div><div class="line">37</div><div class="line">38</div><div class="line">39</div><div class="line">40</div><div class="line">41</div><div class="line">42</div><div class="line">43</div><div class="line">44</div><div class="line">45</div><div class="line">46</div><div class="line">47</div><div class="line">48</div><div class="line">49</div><div class="line">50</div><div class="line">51</div><div class="line">52</div><div class="line">53</div><div class="line">54</div><div class="line">55</div><div class="line">56</div><div class="line">57</div><div class="line">58</div><div class="line">59</div><div class="line">60</div><div class="line">61</div></pre></td><td class="code"><pre><div class="line"><span class="keyword">func</span> (root *semaRoot) queue(addr *<span class="typename">uint32</span>, s *sudog, lifo <span class="typename">bool</span>) {</div><div class="line"> <span class="comment">// 设置这个要加入的节点</span></div><div class="line"> s.g = getg()</div><div class="line"> s.elem = unsafe.Pointer(addr)</div><div class="line"> s.next = <span class="constant">nil</span></div><div class="line"> s.prev = <span class="constant">nil</span></div><div class="line"> s.waiters =<span class="number"> 0</span></div><div class="line"></div><div class="line"> <span class="keyword">var</span> last *sudog</div><div class="line"> pt := &root.treap</div><div class="line"> <span class="comment">// 从根节点开始</span></div><div class="line"> <span class="keyword">for</span> t := *pt; t != <span class="constant">nil</span>; t = *pt { <span class="comment">// ①</span></div><div class="line"> <span class="comment">// 如果地址已经在列表中,则加入到这个地址的链表中</span></div><div class="line"> <span class="keyword">if</span> t.elem == unsafe.Pointer(addr) {</div><div class="line"> <span class="comment">// 如果地址已经在列表中，并且指定了先入后出flag,这是一个替换操作</span></div><div class="line"> <span class="keyword">if</span> lifo {</div><div class="line"> <span class="comment">// 替换操作</span></div><div class="line"> *pt = s</div><div class="line"> s.ticket = t.ticket</div><div class="line"> ... <span class="comment">// 把t的各种信息复制给s</span></div><div class="line"> } <span class="keyword">else</span> {</div><div class="line"> <span class="comment">// 增加到到等待列表的末尾</span></div><div class="line"> <span class="keyword">if</span> t.waittail == <span class="constant">nil</span> {</div><div class="line"> t.waitlink = s</div><div class="line"> } <span class="keyword">else</span> {</div><div class="line"> t.waittail.waitlink = s</div><div class="line"> }</div><div class="line"> t.waittail = s</div><div class="line"> s.waitlink = <span class="constant">nil</span></div><div class="line"> <span class="keyword">if</span> t.waiters<span class="number">+1</span> !=<span class="number"> 0</span> {</div><div class="line"> t.waiters++</div><div class="line"> }</div><div class="line"> }</div><div class="line"> <span class="keyword">return</span></div><div class="line"> }</div><div class="line"> last = t</div><div class="line"> <span class="comment">// 二叉搜索树查找</span></div><div class="line"> <span class="keyword">if</span> <span class="typename">uintptr</span>(unsafe.Pointer(addr)) < <span class="typename">uintptr</span>(t.elem) { <span class="comment">// ②</span></div><div class="line"> pt = &t.prev</div><div class="line"> } <span class="keyword">else</span> {</div><div class="line"> pt = &t.next</div><div class="line"> }</div><div class="line"> }</div><div class="line"></div><div class="line"> <span class="comment">// 为新节点设置ticket.这个ticket是一个随机值，作为随机堆的优先级，用于保持treap的平衡。</span></div><div class="line"> s.ticket = cheaprand() |<span class="number"> 1</span> <span class="comment">// ③</span></div><div class="line"> s.parent = last</div><div class="line"> *pt = s</div><div class="line"></div><div class="line"> <span class="comment">// 根据优先级(ticket)旋转以保持treap的平衡</span></div><div class="line"> <span class="keyword">for</span> s.parent != <span class="constant">nil</span> && s.parent.ticket > s.ticket { <span class="comment">// ④</span></div><div class="line"> <span class="keyword">if</span> s.parent.prev == s {</div><div class="line"> root.rotateRight(s.parent) <span class="comment">// ⑤</span></div><div class="line"> } <span class="keyword">else</span> {</div><div class="line"> <span class="keyword">if</span> s.parent.next != s {</div><div class="line"> <span class="built_in">panic</span>(<span class="string">"semaRoot queue"</span>)</div><div class="line"> }</div><div class="line"> root.rotateLeft(s.parent) <span class="comment">// ⑥</span></div><div class="line"> }</div><div class="line"> }</div><div class="line">}</div></pre></td></tr></table></figure>
<p>① 是遍历 treap 的过程，当然它是通过搜索二叉树的方式实现。 <code>addr</code>就是我们一开始讲的treap的key，也就是 <code>s.elem</code>。<br>首先检查 <code>addr</code> 已经在 treap 中，如果存在，那么就把 <code>s</code> 加入到 <code>addr</code> 对应的 <code>sudog</code> 链表中，或者替换掉 <code>addr</code> 对应的 <code>sudog</code>。</p>
<p>这个<code>addr</code>, 如果对于<code>sync.Mutex</code>来说，就是 <code>Mutex.sema</code>字段的地址。</p>
<figure class="highlight go"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div></pre></td><td class="code"><pre><div class="line"><span class="keyword">type</span> Mutex <span class="keyword">struct</span> {</div><div class="line"> state <span class="typename">int32</span></div><div class="line"> sema <span class="typename">uint32</span></div><div class="line">}</div></pre></td></tr></table></figure>
<p>所以对于阻塞在同一个<code>sync.Mutex</code>上的goroutine，他们的<code>addr</code>是相同的，所以他们会被加入到同一个<code>sudog</code>链表中。<br>如果是不同的<code>sync.Mutex</code>锁，他们的<code>addr</code>是不同的，那么他们会被加入到这个treap不同的节点。</p>
<p>进而，你可以知道，这个<code>rootSema</code>是维护多个<code>sync.Mutex</code>的等待队列的，可以快速找到不同的<code>sync.Mutex</code>的等待队列,也可以维护同一个<code>sync.Mutex</code>的等待队列。<br>这给了我们启发，如果你有类似的需求，可以参考这个实现。</p>
<p>③就是设置这个节点的优先级，它是一个随机值，用于保持treap的平衡。这里有个技巧就是总是把优先级最低位设置为1，这样保证优先级不为0.因为优先级经常和0做比较，我们将最低位设置为1，就表明优先级已经设置。</p>
<p>④ 就是将这个新加入的节点旋转到合适的位置，以保持treap的平衡。这里的旋转操作就是上面提到的左旋和右旋。稍后看。</p>
<h2 id="移除一个元素（出队）">移除一个元素（出队）</h2>
<p>对应的，还有出对的操作。这个操作就是从treap中移除一个节点，这个节点就是一个等待的goroutine(<code>sudog</code>)。</p>
<p><code>dequeue</code> 搜索并找到在<code>semaRoot</code>中第一个因<code>addr</code>而阻塞的<code>goroutine</code>。<br>比如需要唤醒一个goroutine, 让它继续执行(比如直接将锁交给它，或者唤醒它去争抢锁)。</p>
<figure class="highlight go"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div><div class="line">7</div><div class="line">8</div><div class="line">9</div><div class="line">10</div><div class="line">11</div><div class="line">12</div><div class="line">13</div><div class="line">14</div><div class="line">15</div><div class="line">16</div><div class="line">17</div><div class="line">18</div><div class="line">19</div><div class="line">20</div><div class="line">21</div><div class="line">22</div><div class="line">23</div><div class="line">24</div><div class="line">25</div><div class="line">26</div><div class="line">27</div><div class="line">28</div><div class="line">29</div><div class="line">30</div><div class="line">31</div><div class="line">32</div><div class="line">33</div><div class="line">34</div><div class="line">35</div><div class="line">36</div><div class="line">37</div><div class="line">38</div><div class="line">39</div><div class="line">40</div><div class="line">41</div><div class="line">42</div><div class="line">43</div><div class="line">44</div><div class="line">45</div></pre></td><td class="code"><pre><div class="line"><span class="keyword">func</span> (root *semaRoot) dequeue(addr *<span class="typename">uint32</span>) (found *sudog, now, tailtime <span class="typename">int64</span>) {</div><div class="line"> ps := &root.treap</div><div class="line"> s := *ps</div><div class="line"> <span class="keyword">for</span> ; s != <span class="constant">nil</span>; s = *ps { <span class="comment">// ①， 二叉搜索树查找</span></div><div class="line"> <span class="keyword">if</span> s.elem == unsafe.Pointer(addr) { <span class="comment">// ②</span></div><div class="line"> <span class="keyword">goto</span> Found</div><div class="line"> }</div><div class="line"> <span class="keyword">if</span> <span class="typename">uintptr</span>(unsafe.Pointer(addr)) < <span class="typename">uintptr</span>(s.elem) {</div><div class="line"> ps = &s.prev</div><div class="line"> } <span class="keyword">else</span> {</div><div class="line"> ps = &s.next</div><div class="line"> }</div><div class="line"> }</div><div class="line"> <span class="keyword">return</span> <span class="constant">nil</span>,<span class="number"> 0</span>,<span class="number"> 0</span></div><div class="line"></div><div class="line">Found: <span class="comment">// ③</span></div><div class="line"> ...</div><div class="line"> <span class="keyword">if</span> t := s.waitlink; t != <span class="constant">nil</span> { <span class="comment">// ④</span></div><div class="line"> *ps = t</div><div class="line"> ...</div><div class="line"> } <span class="keyword">else</span> { <span class="comment">// ⑤</span></div><div class="line"> <span class="comment">// 旋转s到叶节点，以便删除</span></div><div class="line"> <span class="keyword">for</span> s.next != <span class="constant">nil</span> || s.prev != <span class="constant">nil</span> {</div><div class="line"> <span class="keyword">if</span> s.next == <span class="constant">nil</span> || s.prev != <span class="constant">nil</span> && s.prev.ticket < s.next.ticket {</div><div class="line"> root.rotateRight(s)</div><div class="line"> } <span class="keyword">else</span> {</div><div class="line"> root.rotateLeft(s)</div><div class="line"> }</div><div class="line"> }</div><div class="line"></div><div class="line"> <span class="comment">// ⑤ 删除s</span></div><div class="line"> <span class="keyword">if</span> s.parent != <span class="constant">nil</span> {</div><div class="line"> <span class="keyword">if</span> s.parent.prev == s {</div><div class="line"> s.parent.prev = <span class="constant">nil</span></div><div class="line"> } <span class="keyword">else</span> {</div><div class="line"> s.parent.next = <span class="constant">nil</span></div><div class="line"> }</div><div class="line"> } <span class="keyword">else</span> {</div><div class="line"> root.treap = <span class="constant">nil</span></div><div class="line"> }</div><div class="line"> tailtime = s.acquiretime</div><div class="line"> }</div><div class="line"> ... <span class="comment">// 清理s的不需要的信息</span></div><div class="line"> <span class="keyword">return</span> s, now, tailtime</div><div class="line">}</div></pre></td></tr></table></figure>
<p>① 是遍历 treap 的过程，当然它是通过搜索二叉树的方式实现。 <code>addr</code>就是我们一开始讲的treap的key，也就是 <code>s.elem</code>。如果找到了，就跳到 <code>Found</code> 标签。如果没有找到，就返回 <code>nil</code>。</p>
<p>④是检查这个地址上是不是有多个等待的goroutine，如果有，就把这个节点替换成链表中的下一个节点。把这个节点从treap中移除并返回。<br>如果就一个goroutine，那么把这个移除掉后，需要旋转treap，直到这个节点被旋转到叶节点，然后删除这个节点。</p>
<p>这里的旋转操作就是上面提到的左旋和右旋。</p>
<h2 id="左旋_rotateLeft">左旋 rotateLeft</h2>
<p><code>rotateLeft</code> 函数将以 <code>x</code> 为根的子树左旋，使其变为 <code>y</code> 为根的子树。<br>左旋之前的结构为 <code>(x a (y b c))</code>，旋转后变为 <code>(y (x a b) c)</code>。</p>
<figure class="highlight go"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div><div class="line">7</div><div class="line">8</div><div class="line">9</div><div class="line">10</div><div class="line">11</div><div class="line">12</div><div class="line">13</div><div class="line">14</div><div class="line">15</div><div class="line">16</div><div class="line">17</div><div class="line">18</div><div class="line">19</div><div class="line">20</div><div class="line">21</div><div class="line">22</div><div class="line">23</div><div class="line">24</div><div class="line">25</div></pre></td><td class="code"><pre><div class="line"><span class="keyword">func</span> (root *semaRoot) rotateLeft(x *sudog) {</div><div class="line"> <span class="comment">// p -> (x a (y b c))</span></div><div class="line"> p := x.parent</div><div class="line"> y := x.next</div><div class="line"> b := y.prev</div><div class="line"></div><div class="line"> y.prev = x <span class="comment">// ①</span></div><div class="line"> x.parent = y <span class="comment">// ②</span></div><div class="line"> x.next = b <span class="comment">// ③</span></div><div class="line"> <span class="keyword">if</span> b != <span class="constant">nil</span> {</div><div class="line"> b.parent = x <span class="comment">// ④</span></div><div class="line"> }</div><div class="line"></div><div class="line"> y.parent = p <span class="comment">// ⑤</span></div><div class="line"> <span class="keyword">if</span> p == <span class="constant">nil</span> {</div><div class="line"> root.treap = y <span class="comment">// ⑥</span></div><div class="line"> } <span class="keyword">else</span> <span class="keyword">if</span> p.prev == x { <span class="comment">// ⑦</span></div><div class="line"> p.prev = y</div><div class="line"> } <span class="keyword">else</span> {</div><div class="line"> <span class="keyword">if</span> p.next != x {</div><div class="line"> throw(<span class="string">"semaRoot rotateLeft"</span>)</div><div class="line"> }</div><div class="line"> p.next = y</div><div class="line"> }</div><div class="line">}</div></pre></td></tr></table></figure>
<p>具体步骤：</p>
<ul>
<li>将 <code>y</code> 设为 <code>x</code> 的父节点(②)，<code>x</code> 设为 <code>y</code> 的左子节点(①)。</li>
<li>将 <code>b</code> 设为 <code>x</code> 的右子节点(③)，并更新其父节点为 <code>x</code>(④)。</li>
<li>更新 <code>y</code> 的父节点为 <code>p</code>(⑤)，即 <code>x</code> 的原父节点。如果 <code>p</code> 为 nil，则 y 成为新的树根(⑥)。</li>
<li>根据 <code>y</code> 是 <code>p</code> 的左子节点还是右子节点，更新对应的指针(⑦)。</li>
</ul>
<p><img src="Pasted-image-20241026130741.png" alt=""><br>左旋为<br><img src="Pasted-image-20241026130908.png" alt=""></p>
<h2 id="右旋_rotateRight">右旋 rotateRight</h2>
<p>rotateRight 旋转以节点 y 为根的树。<br>将 <code>(y (x a b) c)</code> 变为 <code>(x a (y b c))</code>。</p>
<figure class="highlight go"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div><div class="line">7</div><div class="line">8</div><div class="line">9</div><div class="line">10</div><div class="line">11</div><div class="line">12</div><div class="line">13</div><div class="line">14</div><div class="line">15</div><div class="line">16</div><div class="line">17</div><div class="line">18</div><div class="line">19</div><div class="line">20</div><div class="line">21</div><div class="line">22</div><div class="line">23</div><div class="line">24</div><div class="line">25</div></pre></td><td class="code"><pre><div class="line"><span class="keyword">func</span> (root *semaRoot) rotateRight(y *sudog) {</div><div class="line"> <span class="comment">// p -> (y (x a b) c)</span></div><div class="line"> p := y.parent</div><div class="line"> x := y.prev</div><div class="line"> b := x.next</div><div class="line"></div><div class="line"> x.next = y <span class="comment">// ①</span></div><div class="line"> y.parent = x <span class="comment">// ②</span></div><div class="line"> y.prev = b <span class="comment">// ③</span></div><div class="line"> <span class="keyword">if</span> b != <span class="constant">nil</span> {</div><div class="line"> b.parent = y <span class="comment">// ④</span></div><div class="line"> }</div><div class="line"></div><div class="line"> x.parent = p <span class="comment">// ⑤</span></div><div class="line"> <span class="keyword">if</span> p == <span class="constant">nil</span> {</div><div class="line"> root.treap = x <span class="comment">// ⑥</span></div><div class="line"> } <span class="keyword">else</span> <span class="keyword">if</span> p.prev == y { <span class="comment">// ⑦</span></div><div class="line"> p.prev = x</div><div class="line"> } <span class="keyword">else</span> {</div><div class="line"> <span class="keyword">if</span> p.next != y {</div><div class="line"> throw(<span class="string">"semaRoot rotateRight"</span>)</div><div class="line"> }</div><div class="line"> p.next = x</div><div class="line"> }</div><div class="line">}</div></pre></td></tr></table></figure>
<p>具体步骤：</p>
<ul>
<li>将 y 设为 x 的右子节点(①), x 设为 y 的父节点(②)</li>
<li>将 b 设为 y 的左子节点(③)，并更新其父节点为 y(④)</li>
<li>更新 x 的父节点为 p(⑤)，即 y 的原父节点。如果 p 为 nil，则 x 成为新的树根(⑥)</li>
<li>根据 x 是 p 的左子节点还是右子节点，更新对应的指针(⑦)</li>
</ul>
<p><img src="Pasted-image-20241026132048.png" alt=""><br>右旋为<br><img src="Pasted-image-20241026132245.png" alt=""></p>
<p>理解了左旋和右旋，你就理解了出队代码中这一段为什么把当前节点旋转到叶结点中了：</p>
<figure class="highlight go"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div><div class="line">7</div><div class="line">8</div></pre></td><td class="code"><pre><div class="line"><span class="comment">// 旋转s到叶节点，以便删除</span></div><div class="line"><span class="keyword">for</span> s.next != <span class="constant">nil</span> || s.prev != <span class="constant">nil</span> {</div><div class="line"> <span class="keyword">if</span> s.next == <span class="constant">nil</span> || s.prev != <span class="constant">nil</span> && s.prev.ticket < s.next.ticket {</div><div class="line"> root.rotateRight(s)</div><div class="line"> } <span class="keyword">else</span> {</div><div class="line"> root.rotateLeft(s)</div><div class="line"> }</div><div class="line">}</div></pre></td></tr></table></figure>
<p>整体上看，treap这个数据结构确实简单可维护。左旋和右旋的代码量很少，结合图看起来也容易理解。 出入队的代码也很简单，只是简单的二叉搜索树的操作，加上旋转操作。</p>
<p>这是我介绍的Go秘而不宣的数据结构第三篇，希望你喜欢。你还希望看到Go运行时和标准库中的哪些数据结构呢，欢迎留言。</p>
<p>我会不定期的从关注者列表并点赞文章的同学中选出一位，送出版商和出版社的老师赠送的书，欢迎参与。</p>
</div>
<footer class="article-footer">
</footer>
</div>
</article>
<article id="post-go-internal-ds-bitvec" class="article article-type-post" itemscope
itemprop="blogPost">
<div class="article-meta">
<a href="2024/11/17/go-internal-ds-bitvec" class="article-date">
<time datetime="2024-11-17T08:18:48.000Z" itemprop="datePublished">2024年11月17日</time>
</a>
<div class="article-category">
<a class="article-category-link" href="categories/Go">Go</a>
</div>
<div class="article-author"> by smallnest</div>
</div>
<div class="article-inner">
<header class="article-header">
<h1 itemprop="name">
<a class="article-title" href="2024/11/17/go-internal-ds-bitvec">Go中秘而不宣的数据结构 BitVec, 资源优化方法之位向量</a>
</h1>
</header>
<div class="article-entry" itemprop="articleBody">
<img class="article-post-image" src="/images/logos/golang8.png">
<p>位图(bitmap)是一种优雅而高效的数据结构,它巧妙地利用了计算机最底层的位运算能力。你可以把它想象成一个巨大的开关阵列,每个开关只有打开和关闭两种状态 —— 这就是位图的本质。每一位都可以独立控制,却又可以通过位运算实现群体操作。</p>
<p>在实际应用中,位图的威力令人惊叹。设想你需要在海量数据中查找重复的数字,传统的哈希表或数组都会占用大量内存。而位图却能巧妙地用一个比特位标记一个数字的出现情况,极大地压缩了存储空间。在处理<strong>10亿个不重复的整数</strong>时,位图仅需要<strong>125MB内存</strong>,相比其他数据结构动辄需要几个GB,效率提升显著。</p>
<p>位图的运用也体现在我们日常使用的数据库系统中。数据库会用位图索引来加速查询,尤其是对于性别、状态这样的枚举字段,一个位图就能快速定位满足条件的记录。比如在电商系统中,快速筛选出"在售且有库存"的商品,位图索引可以通过简单的位与运算瞬间得出结果。</p>
<p>在大规模系统的权限控制中,位图也显示出其独特魅力。用户的各项权限可以编码到不同的位上,判断权限时只需一条位运算指令,既高效又直观。比如一个CMS系统,可以用一个32位的整数表示用户的全部权限状态,包括读、写、管理等多个维度。</p>
<p><strong>布隆过滤器</strong>更是位图思想的精妙应用。它用多个哈希函数在位图上标记数据,能够以极小的内存代价判断一个元素是否可能存在。这在网页爬虫、垃圾邮件过滤等场景下广泛应用。虽然可能有小概率的误判,但在实际应用中往往是可以接受的权衡。</p>
<p>正是由于以上特点,位图在处理<strong>海量数据、状态标记、数据压缩、快速统计</strong>等场景中表现出色。它用最简单的方式解决了最复杂的问题,这正是计算机科学之美的体现。</p>
<p class="article-more-link">
<a href="2024/11/17/go-internal-ds-bitvec#more">阅读全文</a>
</p>
</div>
<footer class="article-footer">
</footer>
</div>
</article>
<article id="post-go-internal-ds-runq" class="article article-type-post" itemscope
itemprop="blogPost">
<div class="article-meta">
<a href="2024/10/20/go-internal-ds-runq" class="article-date">
<time datetime="2024-10-20T04:17:47.000Z" itemprop="datePublished">2024年10月20日</time>
</a>
<div class="article-category">
<a class="article-category-link" href="categories/Go">Go</a>
</div>
<div class="article-author"> by smallnest</div>
</div>
<div class="article-inner">
<header class="article-header">
<h1 itemprop="name">
<a class="article-title" href="2024/10/20/go-internal-ds-runq">Go中秘而不宣的数据结构 runq, 难怪运行时调度那么好</a>
</h1>
</header>
<div class="article-entry" itemprop="articleBody">
<img class="article-post-image" src="/images/logos/golang5.png">
<p>首先，让我们先来回顾 Go 运行时的 GPM 模型。这方面的介绍网上的资料都非常非常多了，但是我们也不妨回顾一下：</p>
<blockquote>
<p>GPM模型中的G代表goroutine。每个goroutine只占用几KB的内存,可以轻松创建成千上万个。G包含了goroutine的栈、指令指针和其他信息,如阻塞channel的等待队列等。</p>
<p>P代表processor,可以理解为一个抽象的CPU核心。P的数量默认等于实际的CPU核心数,但可以通过环境变量进行调整。P维护了一个本地的goroutine队列,还负责执行goroutine并管理与之关联的上下文信息。</p>
<p>M代表machine,是操作系统线程。一个M必须绑定一个P才能执行goroutine。当一个M阻塞时,运行时会创建一个新的M或者复用一个空闲的M来保证P的数量总是等于GOMAXPROCS的值,从而充分利用CPU资源。</p>
<p>在这个模型中,P扮演了承上启下的角色。它连接了G和M,实现了用户层级的goroutine到操作系统线程的映射。这种设计允许Go在用户空间进行调度,避免了频繁的系统调用,大大提高了并发效率。</p>
<p>调度过程中,当一个goroutine被创建时,它会被放到P的本地队列或全局队列中。如果P的本地队列已满,一些goroutine会被放到全局队列。当P执行完当前的goroutine后,会优先从本地队列获取新的goroutine来执行。如果本地队列为空,P会尝试从全局队列或其他P的队列中偷取goroutine。</p>
<p>这种工作窃取(work-stealing)算法确保了负载的动态平衡。当某个P的本地队列为空时,它可以从其他P的队列中窃取一半的goroutine,这有效地平衡了各个P之间的工作负载。</p>
</blockquote>
<p class="article-more-link">
<a href="2024/10/20/go-internal-ds-runq#more">阅读全文</a>
</p>
</div>
<footer class="article-footer">
</footer>
</div>
</article>
<nav id="page-nav">
<span class="page-number current">1</span><a class="page-number" href="page/2">2</a><a class="page-number" href="page/3">3</a><span class="space">…</span><a class="page-number" href="page/66">66</a><a class="extend next" rel="next" href="page/2">下一页 »</a>
</nav>
</section>
<aside id="sidebar">
<div class="widget-wrap">
<h3 class="widget-title">访问者来源</h3>
<div class="widget">
<script type="text/javascript" id="clstr_globe" src="//clustrmaps.com/globe.js?d=Hf4EJSi2XvL6TMcuFSH51Qn6nf5nZ8qnjVBnWCQ4FGc"></script>
</div>
</div>
<div class="widget-wrap">
<h3 class="widget-title">微信公众号</h3>
<div class="widget">
<img width="100%" src="/images/widgets/gopatterns.jpg">
</div>
</div>
<div class="widget-wrap">
<h3 class="widget-title">极客时间专栏</h3>
<div class="widget">
<a href="https://time.geekbang.org/column/intro/100061801">
<img width="100%" src="/images/widgets/geekbang.png">
</a>
</div>
</div>
<div class="widget-wrap">
<h3 class="widget-title">出版图书</h3>
<div class="widget">
<a href="https://cpgo.colobu.com/">
<img width="100%" src="/cpgolang/cpgo.png">
</a>
</div>
<div class="widget">
<a href="https://www.books.com.tw/products/0010991366">
<img width="100%" src="/cpgolang/cpgo2.jpg">
</a>
</div>
<div class="widget">
<a href="https://item.jd.com/14347716.html">
<img width="100%" src="/100gomistakes/cover.png">
</a>
</div>
<div class="widget">
<a href="/ScalaCollectionsCookbook/">
<img width="100%" src="/ScalaCollectionsCookbook/scala_collections_cookbook.jpg">
<img width="100%" src="/ScalaCollectionsCookbook/scala_collections_cookbook_tw.png">
</a>
</div>
</div>
<div class="widget-wrap">
<h3 class="widget-title">分类</h3>
<div class="widget">
<ul class="category-list"><li class="category-list-item"><a class="category-list-link" href="categories/Android">Android</a><span class="category-list-count">12</span></li><li class="category-list-item"><a class="category-list-link" href="categories/C">C++</a><span class="category-list-count">2</span></li><li class="category-list-item"><a class="category-list-link" href="categories/DOTNET">DOTNET</a><span class="category-list-count">1</span></li><li class="category-list-item"><a class="category-list-link" href="categories/Docker">Docker</a><span class="category-list-count">5</span></li><li class="category-list-item"><a class="category-list-link" href="categories/Go">Go</a><span class="category-list-count">301</span></li><li class="category-list-item"><a class="category-list-link" href="categories/Java">Java</a><span class="category-list-count">64</span></li><li class="category-list-item"><a class="category-list-link" href="categories/Linux">Linux</a><span class="category-list-count">8</span></li><li class="category-list-item"><a class="category-list-link" href="categories/Rust">Rust</a><span class="category-list-count">16</span></li><li class="category-list-item"><a class="category-list-link" href="categories/Scala">Scala</a><span class="category-list-count">18</span></li><li class="category-list-item"><a class="category-list-link" href="categories/go">go</a><span class="category-list-count">1</span></li><li class="category-list-item"><a class="category-list-link" href="categories/k8s">k8s</a><span class="category-list-count">1</span></li><li class="category-list-item"><a class="category-list-link" href="categories/rust">rust</a><span class="category-list-count">10</span></li><li class="category-list-item"><a class="category-list-link" href="categories/分享">分享</a><span class="category-list-count">1</span></li><li class="category-list-item"><a class="category-list-link" href="categories/前端开发">前端开发</a><span class="category-list-count">18</span></li><li class="category-list-item"><a class="category-list-link" href="categories/区块链">区块链</a><span class="category-list-count">8</span></li><li class="category-list-item"><a class="category-list-link" href="categories/大数据">大数据</a><span class="category-list-count">60</span></li><li class="category-list-item"><a class="category-list-link" href="categories/工具">工具</a><span class="category-list-count">28</span></li><li class="category-list-item"><a class="category-list-link" href="categories/数据库">数据库</a><span class="category-list-count">3</span></li><li class="category-list-item"><a class="category-list-link" href="categories/架构">架构</a><span class="category-list-count">27</span></li><li class="category-list-item"><a class="category-list-link" href="categories/算法">算法</a><span class="category-list-count">4</span></li><li class="category-list-item"><a class="category-list-link" href="categories/管理">管理</a><span class="category-list-count">2</span></li><li class="category-list-item"><a class="category-list-link" href="categories/网络编程">网络编程</a><span class="category-list-count">13</span></li><li class="category-list-item"><a class="category-list-link" href="categories/设计模式">设计模式</a><span class="category-list-count">1</span></li><li class="category-list-item"><a class="category-list-link" href="categories/读书笔记">读书笔记</a><span class="category-list-count">2</span></li><li class="category-list-item"><a class="category-list-link" href="categories/运维">运维</a><span class="category-list-count">2</span></li><li class="category-list-item"><a class="category-list-link" href="categories/高并发编程">高并发编程</a><span class="category-list-count">20</span></li></ul>
</div>
</div>
<div class="widget-wrap">
<h3 class="widget-title">标签云</h3>
<div class="widget tagcloud">
<a href="tags/Android" style="font-size: 15.00px;">Android</a><a href="tags/ApacheBench" style="font-size: 11.25px;">ApacheBench</a><a href="tags/Bower" style="font-size: 10.00px;">Bower</a><a href="tags/C" style="font-size: 10.00px;">C#</a><a href="tags/CDN" style="font-size: 10.00px;">CDN</a><a href="tags/CQRS" style="font-size: 10.00px;">CQRS</a><a href="tags/CRC" style="font-size: 10.00px;">CRC</a><a href="tags/CSS" style="font-size: 11.25px;">CSS</a><a href="tags/CompletableFuture" style="font-size: 10.00px;">CompletableFuture</a><a href="tags/Comsat" style="font-size: 10.00px;">Comsat</a><a href="tags/Curator" style="font-size: 18.75px;">Curator</a><a href="tags/DSL" style="font-size: 10.00px;">DSL</a><a href="tags/Disruptor" style="font-size: 10.00px;">Disruptor</a><a href="tags/Docker" style="font-size: 11.25px;">Docker</a><a href="tags/Ember" style="font-size: 11.25px;">Ember</a><a href="tags/FastJson" style="font-size: 10.00px;">FastJson</a><a href="tags/Fiber" style="font-size: 10.00px;">Fiber</a><a href="tags/GAE" style="font-size: 10.00px;">GAE</a><a href="tags/GC" style="font-size: 12.50px;">GC</a><a href="tags/Gnuplot" style="font-size: 10.00px;">Gnuplot</a><a href="tags/Go" style="font-size: 16.25px;">Go</a><a href="tags/Gradle" style="font-size: 10.00px;">Gradle</a><a href="tags/Grunt" style="font-size: 10.00px;">Grunt</a><a href="tags/Gulp" style="font-size: 10.00px;">Gulp</a><a href="tags/Hadoop" style="font-size: 10.00px;">Hadoop</a><a href="tags/Hazelcast" style="font-size: 10.00px;">Hazelcast</a><a href="tags/IPFS" style="font-size: 10.00px;">IPFS</a><a href="tags/Ignite" style="font-size: 10.00px;">Ignite</a><a href="tags/JVM" style="font-size: 10.00px;">JVM</a><a href="tags/Java" style="font-size: 17.50px;">Java</a><a href="tags/Kafka" style="font-size: 20.00px;">Kafka</a><a href="tags/Lambda" style="font-size: 13.75px;">Lambda</a><a href="tags/Linux" style="font-size: 12.50px;">Linux</a><a href="tags/LongAdder" style="font-size: 10.00px;">LongAdder</a><a href="tags/MathJax" style="font-size: 10.00px;">MathJax</a><a href="tags/Maven" style="font-size: 11.25px;">Maven</a><a href="tags/Memcached" style="font-size: 10.00px;">Memcached</a><a href="tags/Metrics" style="font-size: 10.00px;">Metrics</a><a href="tags/Mongo" style="font-size: 12.50px;">Mongo</a><a href="tags/Netty" style="font-size: 15.00px;">Netty</a>