Skip to content

Commit 14eec1a

Browse files
author
XiguoHu
committed
brpc website 1.0 fix links jump problem in overview page
1 parent 306a907 commit 14eec1a

File tree

29 files changed

+523
-100
lines changed

29 files changed

+523
-100
lines changed

‎content/en/docs/Builtin Services/buildin_services/_index.md

Lines changed: 11 additions & 11 deletions
Original file line numberDiff line numberDiff line change
@@ -8,7 +8,7 @@ description: >
88
---
99
# Builtin Services
1010

11-
Builtin services expose internal status of servers in different pespectives, making development and debugging over brpc more efficient. brpc serves builting services via HTTP, which can be easily accessed through curl and web browsers. Servers respond plain text or html according to `User-Agent` in the request header, or you may append `?console=1` to the uri to force the server to respond in plain text. Check the [example](http://brpc.baidu.com:8765/) running on our dev machine(only accessible from Baidu internal) for more details. If the port is forbidden from where you run curl or web browser (e.g. not all ports are accessible from a web browser inside Baidu), you can use [rpc_view](rpc_view.md) for proxying.
11+
Builtin services expose internal status of servers in different pespectives, making development and debugging over brpc more efficient. brpc serves builting services via HTTP, which can be easily accessed through curl and web browsers. Servers respond plain text or html according to `User-Agent` in the request header, or you may append `?console=1` to the uri to force the server to respond in plain text. Check the [example](http://brpc.baidu.com:8765/) running on our dev machine(only accessible from Baidu internal) for more details. If the port is forbidden from where you run curl or web browser (e.g. not all ports are accessible from a web browser inside Baidu), you can use [rpc_view](../../tools/rpc_view/) for proxying.
1212

1313
Following 2 screenshots show accesses to builtin services from a web browser and a terminal respectively. Note that the logo is the codename inside Baidu, and being modified to brpc in opensourced version.
1414

@@ -22,25 +22,25 @@ Following 2 screenshots show accesses to builtin services from a web browser and
2222

2323
# Security Mode
2424

25-
To avoid potential attacks and information leaks, builtin services **must** be hidden on servers that may be accessed from public, including the ones proxied by nginx or other http servers. Click [here](server.md#security-mode) for more details.
25+
To avoid potential attacks and information leaks, builtin services **must** be hidden on servers that may be accessed from public, including the ones proxied by nginx or other http servers. Click [here](../../server/basics/#security-mode) for more details.
2626

2727
# Main services:
2828

29-
[/status](status.md): displays brief status of all services.
29+
[/status](../status/): displays brief status of all services.
3030

31-
[/vars](vars.md): lists user-customizable counters on miscellaneous metrics.
31+
[/vars](../vars/): lists user-customizable counters on miscellaneous metrics.
3232

33-
[/connections](../cn/connections.md): lists all connections and their stats.
33+
[/connections](../connections/): lists all connections and their stats.
3434

35-
[/flags](../cn/flags.md): lists all gflags, some of them are modifiable at run-time.
35+
[/flags](../flags/): lists all gflags, some of them are modifiable at run-time.
3636

37-
[/rpcz](../cn/rpcz.md): traces all RPCs.
37+
[/rpcz](../rpcz/): traces all RPCs.
3838

39-
[cpu profiler](../cn/cpu_profiler.md): analyzes CPU hotspots.
39+
[cpu profiler](../cpu_profiler/): analyzes CPU hotspots.
4040

41-
[heap profiler](../cn/heap_profiler.md): shows how memory are allocated.
41+
[heap profiler](../heap_profiler/): shows how memory are allocated.
4242

43-
[contention profiler](../cn/contention_profiler.md): analyzes lock contentions.
43+
[contention profiler](../contention_profiler/): analyzes lock contentions.
4444

4545
# Other services
4646

@@ -56,7 +56,7 @@ To avoid potential attacks and information leaks, builtin services **must** be h
5656

5757
![img](/images/docs/protobufs_service.png)
5858

59-
[/vlog](http://brpc.baidu.com:8765/vlog) shows all the [VLOG](streaming_log.md#VLOG) that can be enabled(not working with glog).
59+
[/vlog](http://brpc.baidu.com:8765/vlog) shows all the [VLOG](../../c++-base/streaming-log/#vlog) that can be enabled(not working with glog).
6060

6161
![img](/images/docs/vlog_service.png)
6262

‎content/en/docs/Builtin Services/status/_index.md

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -6,7 +6,7 @@ date: 2021-08-12
66
description: >
77
Learn about status service.
88
---
9-
[/status](http://brpc.baidu.com:8765/status) shows primary statistics of services inside the server. The data sources are same with [/vars](vars.md), but stats are grouped differently.
9+
[/status](http://brpc.baidu.com:8765/status) shows primary statistics of services inside the server. The data sources are same with [/vars](../vars/), but stats are grouped differently.
1010

1111
![img](/images/docs/status.png)
1212

‎content/en/docs/C++ Base/FlatMap/_index.md

Lines changed: 141 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -6,3 +6,144 @@ date: 2021-08-12
66
description: >
77
Learn about bRPC FlatMap.
88
---
9+
# NAME
10+
11+
FlatMap - Maybe the fastest hashmap, with tradeoff of space.
12+
13+
# EXAMPLE
14+
15+
```c++
16+
#include <string>
17+
#include <butil/logging.h>
18+
#include <butil/containers/flat_map.h>
19+
20+
void flatmap_example() {
21+
butil::FlatMap<int, std::string> map;
22+
// bucket_count: initial count of buckets, big enough to avoid resize.
23+
// load_factor: element_count * 100 / bucket_count, 80 as default.
24+
int bucket_count = 1000;
25+
int load_factor = 80;
26+
map.init(bucket_count, load_factor);
27+
map.insert(10, "hello");
28+
map[20] = "world";
29+
std::string* value = map.seek(20);
30+
CHECK(value != NULL);
31+
32+
CHECK_EQ(2UL, map.size());
33+
CHECK_EQ(0UL, map.erase(30));
34+
CHECK_EQ(1UL, map.erase(10));
35+
36+
LOG(INFO) << "All elements of the map:";
37+
for (butil::FlatMap<int, std::string>::const_iterator it = map.begin(); it != map.end(); ++it) {
38+
LOG(INFO) << it->first << " : " << it->second;
39+
}
40+
map.clear();
41+
CHECK_EQ(0UL, map.size());
42+
}
43+
```
44+
45+
# DESCRIPTION
46+
47+
[FlatMap](https://github.com/brpc/brpc/blob/master/src/butil/containers/flat_map.h)可能是最快的哈希表，但当value较大时它需要更多的内存，它最适合作为检索过程中需要极快查找的小字典。
48+
49+
原理：把开链桶中第一个节点的内容直接放桶内。由于在实践中，大部分桶没有冲突或冲突较少，所以大部分操作只需要一次内存跳转：通过哈希值访问对应的桶。桶内两个及以上元素仍存放在链表中，由于桶之间彼此独立，一个桶的冲突不会影响其他桶，性能很稳定。在很多时候，FlatMap的查找性能和原生数组接近。
50+
51+
# BENCHMARK
52+
53+
下面是FlatMap和其他key/value容器的比较：
54+
55+
- [AlignHashMap](https://svn.baidu.com/app/ecom/nova/trunk/public/util/container/alignhash.h)：闭链中较快的实现。
56+
- [CowHashMap](https://svn.baidu.com/app/ecom/nova/trunk/afs/smalltable/cow_hash_map.hpp)：smalltable中的开链哈希表，和普通开链不同的是带Copy-on-write逻辑。
57+
- [std::map](http://www.cplusplus.com/reference/map/map/)：非哈希表，一般是红黑树。
58+
59+
```
60+
TRACE: 12-30 13:19:53: * 0 [test_flat_map.cpp:474] [ value = 8 bytes ]
61+
TRACE: 12-30 13:19:53: * 0 [test_flat_map.cpp:521] Sequentially inserting 100 into FlatMap/AlignHashMap/CowHashMap/std::map takes 15/19/30/102ns
62+
TRACE: 12-30 13:19:53: * 0 [test_flat_map.cpp:558] Sequentially erasing 100 from FlatMap/AlighHashMap/CowHashMap/std::map takes 7/11/33/146ns
63+
TRACE: 12-30 13:19:53: * 0 [test_flat_map.cpp:521] Sequentially inserting 1000 into FlatMap/AlignHashMap/CowHashMap/std::map takes 10/28/26/93ns
64+
TRACE: 12-30 13:19:53: * 0 [test_flat_map.cpp:558] Sequentially erasing 1000 from FlatMap/AlighHashMap/CowHashMap/std::map takes 6/9/29/100ns
65+
TRACE: 12-30 13:19:53: * 0 [test_flat_map.cpp:521] Sequentially inserting 10000 into FlatMap/AlignHashMap/CowHashMap/std::map takes 10/21/26/130ns
66+
TRACE: 12-30 13:19:53: * 0 [test_flat_map.cpp:558] Sequentially erasing 10000 from FlatMap/AlighHashMap/CowHashMap/std::map takes 5/10/30/104ns
67+
TRACE: 12-30 13:19:53: * 0 [test_flat_map.cpp:474] [ value = 32 bytes ]
68+
TRACE: 12-30 13:19:53: * 0 [test_flat_map.cpp:521] Sequentially inserting 100 into FlatMap/AlignHashMap/CowHashMap/std::map takes 23/31/31/130ns
69+
TRACE: 12-30 13:19:53: * 0 [test_flat_map.cpp:558] Sequentially erasing 100 from FlatMap/AlighHashMap/CowHashMap/std::map takes 9/11/72/104ns
70+
TRACE: 12-30 13:19:53: * 0 [test_flat_map.cpp:521] Sequentially inserting 1000 into FlatMap/AlignHashMap/CowHashMap/std::map takes 20/53/28/112ns
71+
TRACE: 12-30 13:19:53: * 0 [test_flat_map.cpp:558] Sequentially erasing 1000 from FlatMap/AlighHashMap/CowHashMap/std::map takes 7/10/29/101ns
72+
TRACE: 12-30 13:19:53: * 0 [test_flat_map.cpp:521] Sequentially inserting 10000 into FlatMap/AlignHashMap/CowHashMap/std::map takes 20/46/28/137ns
73+
TRACE: 12-30 13:19:53: * 0 [test_flat_map.cpp:558] Sequentially erasing 10000 from FlatMap/AlighHashMap/CowHashMap/std::map takes 7/10/29/112ns
74+
TRACE: 12-30 13:19:53: * 0 [test_flat_map.cpp:474] [ value = 128 bytes ]
75+
TRACE: 12-30 13:19:53: * 0 [test_flat_map.cpp:521] Sequentially inserting 100 into FlatMap/AlignHashMap/CowHashMap/std::map takes 34/109/91/179ns
76+
TRACE: 12-30 13:19:53: * 0 [test_flat_map.cpp:558] Sequentially erasing 100 from FlatMap/AlighHashMap/CowHashMap/std::map takes 8/11/33/112ns
77+
TRACE: 12-30 13:19:53: * 0 [test_flat_map.cpp:521] Sequentially inserting 1000 into FlatMap/AlignHashMap/CowHashMap/std::map takes 28/76/86/169ns
78+
TRACE: 12-30 13:19:53: * 0 [test_flat_map.cpp:558] Sequentially erasing 1000 from FlatMap/AlighHashMap/CowHashMap/std::map takes 8/9/30/110ns
79+
TRACE: 12-30 13:19:53: * 0 [test_flat_map.cpp:521] Sequentially inserting 10000 into FlatMap/AlignHashMap/CowHashMap/std::map takes 28/68/87/201ns
80+
TRACE: 12-30 13:19:53: * 0 [test_flat_map.cpp:558] Sequentially erasing 10000 from FlatMap/AlighHashMap/CowHashMap/std::map takes 9/9/30/125ns
81+
TRACE: 12-30 13:19:53: * 0 [test_flat_map.cpp:474] [ value = 8 bytes ]
82+
TRACE: 12-30 13:19:53: * 0 [test_flat_map.cpp:521] Randomly inserting 100 into FlatMap/AlignHashMap/CowHashMap/std::map takes 14/56/29/157ns
83+
TRACE: 12-30 13:19:53: * 0 [test_flat_map.cpp:558] Randomly erasing 100 from FlatMap/AlighHashMap/CowHashMap/std::map takes 9/11/31/181ns
84+
TRACE: 12-30 13:19:53: * 0 [test_flat_map.cpp:521] Randomly inserting 1000 into FlatMap/AlignHashMap/CowHashMap/std::map takes 11/17/27/156ns
85+
TRACE: 12-30 13:19:53: * 0 [test_flat_map.cpp:558] Randomly erasing 1000 from FlatMap/AlighHashMap/CowHashMap/std::map takes 6/10/30/204ns
86+
TRACE: 12-30 13:19:53: * 0 [test_flat_map.cpp:521] Randomly inserting 10000 into FlatMap/AlignHashMap/CowHashMap/std::map takes 13/26/27/212ns
87+
TRACE: 12-30 13:19:53: * 0 [test_flat_map.cpp:558] Randomly erasing 10000 from FlatMap/AlighHashMap/CowHashMap/std::map takes 7/11/38/309ns
88+
TRACE: 12-30 13:19:53: * 0 [test_flat_map.cpp:474] [ value = 32 bytes ]
89+
TRACE: 12-30 13:19:53: * 0 [test_flat_map.cpp:521] Randomly inserting 100 into FlatMap/AlignHashMap/CowHashMap/std::map takes 24/32/32/181ns
90+
TRACE: 12-30 13:19:53: * 0 [test_flat_map.cpp:558] Randomly erasing 100 from FlatMap/AlighHashMap/CowHashMap/std::map takes 10/12/32/182ns
91+
TRACE: 12-30 13:19:53: * 0 [test_flat_map.cpp:521] Randomly inserting 1000 into FlatMap/AlignHashMap/CowHashMap/std::map takes 21/46/35/168ns
92+
TRACE: 12-30 13:19:53: * 0 [test_flat_map.cpp:558] Randomly erasing 1000 from FlatMap/AlighHashMap/CowHashMap/std::map takes 7/10/36/209ns
93+
TRACE: 12-30 13:19:53: * 0 [test_flat_map.cpp:521] Randomly inserting 10000 into FlatMap/AlignHashMap/CowHashMap/std::map takes 24/46/31/240ns
94+
TRACE: 12-30 13:19:53: * 0 [test_flat_map.cpp:558] Randomly erasing 10000 from FlatMap/AlighHashMap/CowHashMap/std::map takes 8/11/40/314ns
95+
TRACE: 12-30 13:19:53: * 0 [test_flat_map.cpp:474] [ value = 128 bytes ]
96+
TRACE: 12-30 13:19:53: * 0 [test_flat_map.cpp:521] Randomly inserting 100 into FlatMap/AlignHashMap/CowHashMap/std::map takes 36/114/93/231ns
97+
TRACE: 12-30 13:19:53: * 0 [test_flat_map.cpp:558] Randomly erasing 100 from FlatMap/AlighHashMap/CowHashMap/std::map takes 9/12/35/190ns
98+
TRACE: 12-30 13:19:53: * 0 [test_flat_map.cpp:521] Randomly inserting 1000 into FlatMap/AlignHashMap/CowHashMap/std::map takes 44/94/88/224ns
99+
TRACE: 12-30 13:19:53: * 0 [test_flat_map.cpp:558] Randomly erasing 1000 from FlatMap/AlighHashMap/CowHashMap/std::map takes 8/10/34/236ns
100+
TRACE: 12-30 13:19:53: * 0 [test_flat_map.cpp:521] Randomly inserting 10000 into FlatMap/AlignHashMap/CowHashMap/std::map takes 46/92/93/314ns
101+
TRACE: 12-30 13:19:53: * 0 [test_flat_map.cpp:558] Randomly erasing 10000 from FlatMap/AlighHashMap/CowHashMap/std::map takes 12/11/42/362ns
102+
TRACE: 12-30 13:19:53: * 0 [test_flat_map.cpp:576] [ value = 8 bytes ]
103+
TRACE: 12-30 13:19:53: * 0 [test_flat_map.cpp:637] Seeking 100 from FlatMap/AlignHashMap/CowHashMap/std::map takes 4/7/12/54ns
104+
TRACE: 12-30 13:19:53: * 0 [test_flat_map.cpp:637] Seeking 1000 from FlatMap/AlignHashMap/CowHashMap/std::map takes 3/7/11/78ns
105+
TRACE: 12-30 13:19:53: * 0 [test_flat_map.cpp:637] Seeking 10000 from FlatMap/AlignHashMap/CowHashMap/std::map takes 4/8/13/172ns
106+
TRACE: 12-30 13:19:53: * 0 [test_flat_map.cpp:576] [ value = 32 bytes ]
107+
TRACE: 12-30 13:19:53: * 0 [test_flat_map.cpp:637] Seeking 100 from FlatMap/AlignHashMap/CowHashMap/std::map takes 5/8/12/55ns
108+
TRACE: 12-30 13:19:53: * 0 [test_flat_map.cpp:637] Seeking 1000 from FlatMap/AlignHashMap/CowHashMap/std::map takes 4/8/11/82ns
109+
TRACE: 12-30 13:19:53: * 0 [test_flat_map.cpp:637] Seeking 10000 from FlatMap/AlignHashMap/CowHashMap/std::map takes 6/10/14/164ns
110+
TRACE: 12-30 13:19:53: * 0 [test_flat_map.cpp:576] [ value = 128 bytes ]
111+
TRACE: 12-30 13:19:53: * 0 [test_flat_map.cpp:637] Seeking 100 from FlatMap/AlignHashMap/CowHashMap/std::map takes 7/9/13/56ns
112+
TRACE: 12-30 13:19:53: * 0 [test_flat_map.cpp:637] Seeking 1000 from FlatMap/AlignHashMap/CowHashMap/std::map takes 6/10/12/93ns
113+
TRACE: 12-30 13:19:53: * 0 [test_flat_map.cpp:637] Seeking 10000 from FlatMap/AlignHashMap/CowHashMap/std::map takes 9/12/21/166ns
114+
TRACE: 12-30 13:19:53: * 0 [test_flat_map.cpp:576] [ value = 8 bytes ]
115+
TRACE: 12-30 13:19:53: * 0 [test_flat_map.cpp:637] Seeking 100 from FlatMap/AlignHashMap/CowHashMap/std::map takes 4/7/11/56ns
116+
TRACE: 12-30 13:19:53: * 0 [test_flat_map.cpp:637] Seeking 1000 from FlatMap/AlignHashMap/CowHashMap/std::map takes 3/7/11/79ns
117+
TRACE: 12-30 13:19:53: * 0 [test_flat_map.cpp:637] Seeking 10000 from FlatMap/AlignHashMap/CowHashMap/std::map takes 4/9/13/173ns
118+
TRACE: 12-30 13:19:53: * 0 [test_flat_map.cpp:576] [ value = 32 bytes ]
119+
TRACE: 12-30 13:19:53: * 0 [test_flat_map.cpp:637] Seeking 100 from FlatMap/AlignHashMap/CowHashMap/std::map takes 5/8/12/54ns
120+
TRACE: 12-30 13:19:53: * 0 [test_flat_map.cpp:637] Seeking 1000 from FlatMap/AlignHashMap/CowHashMap/std::map takes 4/8/11/100ns
121+
TRACE: 12-30 13:19:53: * 0 [test_flat_map.cpp:637] Seeking 10000 from FlatMap/AlignHashMap/CowHashMap/std::map takes 6/10/14/165ns
122+
TRACE: 12-30 13:19:53: * 0 [test_flat_map.cpp:576] [ value = 128 bytes ]
123+
TRACE: 12-30 13:19:53: * 0 [test_flat_map.cpp:637] Seeking 100 from FlatMap/AlignHashMap/CowHashMap/std::map takes 7/9/12/56ns
124+
TRACE: 12-30 13:19:53: * 0 [test_flat_map.cpp:637] Seeking 1000 from FlatMap/AlignHashMap/CowHashMap/std::map takes 6/10/12/88ns
125+
TRACE: 12-30 13:19:53: * 0 [test_flat_map.cpp:637] Seeking 10000 from FlatMap/AlignHashMap/CowHashMap/std::map takes 9/14/20/169ns
126+
```
127+
# Overview of hashmaps
128+
129+
哈希表是最常用的数据结构，它的基本原理是通过[计算哈希值](http://en.wikipedia.org/wiki/Hash_function)把不同的key分散到不同的区间，在查找时通过key的哈希值能快速地缩小查找区间。在使用恰当参数的前提下，哈希表在大部分时候能在O(1)时间内把一个key映射为value。像其他算法一样，这个“O(1)”在不同的实现中差异很大。哈希表的实现一般有两部分：
130+
131+
## 计算哈希值(非加密型)
132+
133+
即把key散列开的方法，最常见的莫过于线性同余，但一个好的哈希算法(非加密型)要考虑很多因素：
134+
135+
- 结果是确定的。
136+
- [雪崩效应](http://en.wikipedia.org/wiki/Avalanche_effect)：输入中一个bit的变化应该尽量影响输出所有bit的变化。
137+
- 输出应尽量在值域中均匀分布。
138+
- 充分利用现代cpu特性：成块计算，减少分支，循环展开等等。
139+
140+
大部分哈希算法针对的只是一个key，不会耗用太多的cpu。影响主要来自哈希表的整体数据分布，对于工程师来说，选用何种算法得看实践效果，一些最简单的方法也许就有很好的效果。通用算法可选择Murmurhash。
141+
142+
## 解决冲突
143+
144+
哈希值可能重合，解决冲突是哈希表性能的另一关键因素。常见的冲突解决方法有：
145+
146+
- 开链哈希(open hashing, closed addressing): 开链哈希表是链表的数组，其中链表一般称为桶。当若干个key落到同一个桶时，做链表插入。这是最通用的结构，有很多优点：占用内存为O(NumElement * (KeySize + ValueSize + SomePointers))，resize时候不会使之前的存放key/value的内存失效。桶之间是独立的，一个桶的冲突不会影响到其他桶，平均查找时间较为稳定，独立的桶也易于高并发。缺点是至少要两次内存跳转：先跳到桶入口，再跳到桶中的第一个节点。对于一些很小的表这个问题不明显，因为当表很小时，节点内存是接近的，但当表变大时，访存就愈发随机。如果一次访存在50ns左右（2G左右主频），开链哈希的查找时间往往就在100ns以上。在检索端的层层ranking过程中，对一些热点字典的查找1秒内可能有几百万次以上，开链哈希有时会成为热点。一些产品线可能对开链哈希的内存也有诟病，因为每对key/value都需要额外的指针。
147+
- [闭链哈希](http://en.wikipedia.org/wiki/Open_addressing)(closed hashing or open addressing): 闭链的初衷是减少内存跳转，桶不再是链表入口，而只需要记录一对key/value与一些标记，当桶被占时，按照不同的探查方法直到找到空桶为止。比如线性探查就是查找下一个桶，二次探查是按1,2,4,9...平方数位移查找。优点是：当表很空时或冲突较少时，查找只需要一次访存，也不需要管理节点内存池。但仅此而已，这个方法带来了更多缺点：桶个数必须大于元素个数，resize后之前的内存全部失效，难以并发. 更关键的是聚集效应：当区域内元素较多时（超过70%，其实不算多），大量元素的实际桶和它们应在的桶有较大位移。这使哈希表的主要操作都要扫过一大片内存才能找到元素，性能不稳定难以预测。闭链哈希表在很多人的印象中“很快”，但在复杂的应用中往往不如开链哈希表，并且可能是数量级的慢。闭链有一些衍生版本试图解决这个问题，比如[Hopscotch hashing](http://en.wikipedia.org/wiki/Hopscotch_hashing)。
148+
- 混合开链和闭链：一般是把桶数组中的一部分拿出来作为容纳冲突元素的空间，典型如[Coalesced hashing](http://en.wikipedia.org/wiki/Coalesced_hashing)，但这种结构没有解决开链的内存跳转问题，结构又比闭链复杂很多，工程效果并不好。
149+
- 多次哈希：一般用多个哈希表代替一个哈希表，当发生冲突时（用另一个哈希值）尝试另一个哈希表。典型如[Cuckoo hashing](http://en.wikipedia.org/wiki/Cuckoo_hashing)，这个结构也没有解决内存跳转。

0 commit comments

Comments
 (0)