从Go标准库strings看字符串匹配算法

redstorm 发表了文章 • 0 个评论 • 24 次浏览 • 2 小时前 • 来自相关话题

Go的标准库本身质量非常高,本文主要深入strings库,从源代码中探查字符串匹配常用算法的具体实现

我们先看一个简单的例子开始。

在目标字符串中检查是否有子串等于匹配文本,这是非常常见的操作. 最容易让人想到的算法就是从目标... 查看全部

Go的标准库本身质量非常高,本文主要深入strings库,从源代码中探查字符串匹配常用算法的具体实现


我们先看一个简单的例子开始。


在目标字符串中检查是否有子串等于匹配文本,这是非常常见的操作. 最容易让人想到的算法就是从目标字符串第一位开始,逐个字符与待匹配文本比较.匹配成功则指针右移继续比较,要不然从目标文本的第二位开始和待匹配文本继续逐个比较。如果指针先到达待匹配文本末尾,则匹配成功,要不然匹配失败。该算法称之为朴素算法,非常容易理解,但效率也比较慢.具体实现如下:


#include<stdio.h>
#include<string.h>
void search(char *pat, char *txt)
{
int M = strlen(pat);
int N = strlen(txt);
int i;
// 只需要遍历目标文本 N-M 次, 因为从目标文本的 N-M 位开始的子串,长度永远小于 M, 所以不会匹配成功
for (i = 0; i <= N - M; i++)
{
int j;
for (j = 0; j < M; j++)
{
if (txt[i+j] != pat[j])
break;
}
if (j == M)
{
printf("Pattern found at index %d \n", i);
}
}
}

int main()
{
char *txt = "AABAACAADAABAAABAA";
char *pat = "AABA";
search(pat, txt);
return 0;
}

Go 标准库中的strings.Contains函数使用了Rabin-Karp算法, 主要思想如下:


假设匹配文本的长度为M,目标文本的长度为N



  1. 计算匹配文本的hash值

  2. 计算目标字符串中每个长度为M的子串的hash值(需要计算N-M+1次)

  3. 比较hash值, 如果hash值不同,字符串必然不匹配,如果hash值相同,还需要使用朴素算法再次判断


步骤2中每次都要重新计算hash, Rabin-Karp算法的优点在于设计了一个特别的hash算法,使其在计算下一个子串的hash时可以利用之前的hash结果, 以达到加速计算的效果。将每一个字节看作数字, 选择一个比较大的质数作为base. 字节的值是包含在基数之内的


举例说明:

文本为"abracadabra",base为101,那么 hash("abr") = 97 101的2次方 + 98 101的1次方 + 114 101的0次方= 999509

下一个子串 "bra"的hash值为 98
101的2次方 + 114 101的1次方 + 97 101的0次方. 我们可以利用之前"abr"的hash值, 写成:



//       base  old hash      new 'a'    old 'a' base

hash("bra") = 1011
hash("abr") + (97 × 101的0次方) - (97 × 101的3次方)



可以看出hash算法里要点是确立一个非常大的数字作为base,同时根据子串长度得到乘数因子(上述的 101的3次方,其实就是base的len(待匹配文本)次方).


src/strings/strings_amd64.go相关代码注释


// 选择非常大的一个质数16777619 作为 base 
const primeRK = 16777619

// hashStr 返回子串的hash值和乘数因子
func hashStr(sep string) (uint32, uint32) {
hash := uint32(0)
for i := 0; i < len(sep); i++ {
hash = hash*primeRK + uint32(sep[i]) //计算hash值
}
// 计算(最高位 + 1)位的乘数因子, 使用位移, 没有使用 i--, 可以有效减少循环次数. i >>=1 相当于遍历二进制的每一位
var pow, sq uint32 = 1, primeRK
for i := len(sep); i > 0; i >>= 1 {
if i&1 != 0 {
pow *= sq
}
sq *= sq
}
return hash, pow
}

// Index 返回sep在s里第一次匹配时的index, 无法匹配则返回-1.
func Index(s, sep string) int {
n := len(sep)
// 先分析一些常见情况, 起到进一步加速的效果
switch {
case n == 0:
return 0
case n == 1: //如果为一个字节,则调用IndixByte(汇编语言)
return IndexByte(s, sep[0])
case n <= shortStringLen: //如果sep的长度小于31且大于1, 则使用汇编代码(也是一种优化).
return indexShortStr(s, sep)
case n == len(s):
if sep == s {
return 0
}
return -1
case n > len(s):
return -1
}
// 使用Rabin-Karp算法匹配
// 步骤1 初始计算待匹配的文本的hash值和乘数因子,
hashsep, pow := hashStr(sep)
var h uint32
for i := 0; i < n; i++ {
h = h*primeRK + uint32(s[i]) // 步骤2 计算长度跟sep一样的s子串的hash值
}
if h == hashsep && s[:n] == sep {
return 0
}
for i := n; i < len(s); {
// 利用先前的hash值, 计算新的hash值
h *= primeRK // 乘以base
h += uint32(s[i]) // 加上下一个字符的 hash 值
h -= pow * uint32(s[i-n]) // 减去先前子串的第一个字符的hash值
i++
// 如果hash相等则继续使用朴素算法比较, 如果hash不一致,则直接用下一个匹配
if h == hashsep && s[i-n:i] == sep {
return i - n
}
}
return -1
}

strings库里还实现了BM算法, 在这之前,我们先来看另一个非常经典的KMP算法


假设检查bacbababaabcbab是否包含abababca, 此时发现第6位不一样


bacbababaabcbab   
abababca
|
第六位

朴素算法:
bacbababaabcbab
abababca
|
移动一位后开始重新比较

KMP算法:
bacbababaabcbab
abababca
|
直接移动两位后开始重新比较

如果按朴素算法则按上面所示需要搜索词移一位后重新从第一位开始匹配。仔细想想, 前5个字符ababa已经匹配成功,也就是我们已经知道双方的文本, 通过提前的计算,可以多移几位, 而不仅仅移一位. 这样可以加快搜索


KMP算法的主要原理如下:

s为目标文本, 长度为m

p为搜索词,长度为n

假设p[i]与s[x]匹配失败,那么p[i-1]与s[x-1]是匹配成功的, 则试图找到一个索引 j, 使得p[0:j] = p[i-j-1:i-1] (p[0:j] 包含p[j])

如果有则s[x]继续与p[j+1]进行比较, 相当于搜索词移动i-j-1位

无则s[x]与p[0]比较. (具体代码实现时无可以表示为-1, 这样+1 后正好为0) 相当于搜索词移动i位


void cal(char *p, int *next)
{
int i;
int k;
/*第一次字符前面没有索引了, 算corner case, 直接赋值为-1*/
next[0] = -1;
/* 循环每一个索引, 并计算next值 */
for (i = 1; p[i] != '\0'; i++) {
/* 获取前一个索引的next值 */
k = next[i - 1];
/* 当p[i] != p[k + 1]时, 则令 k = next[k], 直到相等或者k == -1 退出*/
while (p[i] != p[k + 1]) {
if (k == -1) {
k = -2;
break;
}
k = next[k];
}
/* 1. p[i] == p[k + 1] 则 i对应的next值为 ++k
2. 无索引时, k= -2, 则++k正好为-1
*/
next[i] = ++k;
}
}

int kmp(char *p, char*t)
{
/*next为数组, 存储搜索词里每一个索引对应的next值, 使得 p[0:next[i]] == p[i-j-1:i-1]*/
int next[strlen(p)];
cal(p, next);
int i, j;
i = 0;
j = 0;
while (p[i] != '\0' && t[j] != '\0') {
if (p[i] == t[j]) {
/* 值相等, 则指针 i, j 都递增 */
i++;
j++;
} else {
if (i == 0) {
j++;
continue;
}
i = next[i - 1] + 1;
}
}
if (p[i] == '\0') {
return 0;
} else {
return 1;
}
}

Go语言里在 strings/search.go 里使用了Boyer-Moore字符串搜索算法, 这个思想和KMP类似,都是根据Pattern自身计算出移动的步数. 有两个优化点:



  1. BM算法是从后向前逐渐匹配.

  2. kmp里的通过已匹配的文本增加移动步数的叫做好规则,那么BM里同时还增加了坏规则


假定Text为"HERE IS A SIMPLE EXAMPLE",Pattern为"EXAMPLE"。

当T[i] != P[j], P[j]右边都匹配时时, 具体的移动规则如下:

坏字符规则: 此时T[i]定义为坏字符, 如果P[0..j-1]中包含T[i]这个字符, 则移动T使坏字符与相等的字符对齐, 如果不包含,则直接移动len(P)


HERE IS A SIMPLE EXAMPLE
|
EXAMPLE

此时P为坏字符, 因EXAMPLE包含P, 则T的i指针右移二位使之对齐,然后重新开始从P的末端继续匹配(下面打X处).

HERE IS A SIMPLE EXAMPLE
| X
EXAMPLE

如下场景,T中的M与P中的E不匹配, 按Go的代码实现,是移动两位(取该字符到P末尾的最短距离),没完全按上面的规则实现
大家是不是发现没有跳跃前进,反而匹配又倒回到之前已完成的匹配过程。 Go代码这么做是为了实现简单。
因为还有好规则可以保证最终的移动步数是正确的
ABCADADEEFXYZ
|
AYEDADE
移动为
ABCADADEEFXYZ
| X
AYEDADE

好后缀规则: 当发生不匹配时,之前已经匹配成功的,称之为好字符. 如下I和A不匹配, 后面的MPLE就是好后缀. 首先检查P里是否好后缀只出现过一次: 比如此时的MPLE作为好后缀在整个字符串EXAMPLE中只出现过一次



  • 不是, 则移动P使T中的好后缀与P中长度相等的字符串对齐

  • 是, 则继续检查好后缀的所有后缀(比如PLE,PL,E)是否和同等长度的P前缀相等, 如果相等则移动P使之对齐, 不相等则移动 len(P).

    这里相当于要求后缀必须出现在P的首部, 如果非首部, 因前缀的前一个字符必然不相等,则整个字符串肯定无法匹配


HERE IS A SIMPLE EXAMPLE
||||
EXAMPLE
MPLE, PLE,LE没法和首部匹配,但后缀E和P前缀相等, 则移动T使其对齐,从打X出继续从后向前比较
HERE IS A SIMPLE EXAMPLE
| X
EXAMPLE

具体的代码注释如下:


func makeStringFinder(pattern string) *stringFinder {
f := &stringFinder{
pattern: pattern,
goodSuffixSkip: make([]int, len(pattern)),
}
// last 是pattern最后一个字符的索引
last := len(pattern) - 1

// 创建坏字符表,记录不匹配时T的i指针移动步数
// 第一阶段,初始化256个字符全部移动 len(pattern) 步
for i := range f.badCharSkip {
f.badCharSkip[i] = len(pattern)
}

// 第二阶段:从左到右遍历pattern,更新其索引与P末尾的距离,结果就是该字符到末尾的最小距离
// 没有计算last byte的距离, 因为移动至少要一步。 没有0步。
for i := 0; i < last; i++ {
f.badCharSkip[pattern[i]] = last - i
}

// 创建好后缀表
// 第一阶段: 此时pattern[i+1:]都是已经匹配的,且好后缀只出现了一次
// 计算T中的指针要移动的步数
lastPrefix := last
for i := last; i >= 0; i-- {
if HasPrefix(pattern, pattern[i+1:]) {
lastPrefix = i + 1
}
// 好后缀时T的指针移动分两步,首先移动到与 pattern的末尾对齐,即 last - i
// lastPrefix 用来记录 pattern[i+1:]中所有后缀与同等长度的前缀相等时的最大索引
// 然后移动 lastPrefix步
f.goodSuffixSkip[i] = lastPrefix + last - i
}
// 第二阶段: 好后缀在pattern前面部分还出现过, 如下计算相应的移动步数
// 会覆盖之前第一阶段的部分值。但好后缀出现过移动步数比没出现的小。所以最终值是正确的
// 举例: "mississi" 中好后缀是issi, 在pattern[1]处出现过,所以移动步数为 last-i + lenSuffix
for i := 0; i < last; i++ {
lenSuffix := longestCommonSuffix(pattern, pattern[1:i+1])
if pattern[i-lenSuffix] != pattern[last-lenSuffix] {
// (last-i) is the shift, and lenSuffix is len(suffix).
f.goodSuffixSkip[last-lenSuffix] = lenSuffix + last - i
}
}
return f
}
// longestCommonSuffix 仅仅比较两个字符串的共同后缀的长度, 没有则为0
func longestCommonSuffix(a, b string) (i int) {
for ; i < len(a) && i < len(b); i++ {
if a[len(a)-1-i] != b[len(b)-1-i] {
break
}
}
return
}

// next 主要返回p在text里第一次匹配时的索引, 不匹配则返回-1
func (f *stringFinder) next(text string) int {
// i 是T(即变量text)中要检查的字符索引, j为P中要检查的字符索引

// 因从后向前比较, 所以i初始化为P的最后一位索引
i := len(f.pattern) - 1
for i < len(text) {
// 每次比较时都从p的最后一位开始比较
j := len(f.pattern) - 1
for j >= 0 && text[i] == f.pattern[j] {
i--
j--
}
// j为负数,说明匹配成功, 则直接返回 i+ 1
if j < 0 {
return i + 1
}
// j为非负, 表明text[i] != f.pattern[j], 则从坏字符表和好后缀表中获取分别获取i需要移动的步数, 取最大值并使移动到新位置
i += max(f.badCharSkip[text[i]], f.goodSuffixSkip[j])
}
return -1
}

Go并发机制

simple 发表了文章 • 0 个评论 • 377 次浏览 • 2017-10-08 22:31 • 来自相关话题

不知道为什么有三张图在这里无法显示,有点郁闷!!! ->查看全部

不知道为什么有三张图在这里无法显示,有点郁闷!!! ->原文链接


1. C/C++ 与 Go语言的“价值观”对照


之前看过 白明老师 在GopherChina2017的一篇演讲文章《Go coding in go way》,里面提到C/C++/Go三门语言价值观,感觉很有意思,分享给大家感受一下:


C的价值观摘录



  • 相信程序员:提供指针和指针运算,让C程序员天马行空的发挥

  • 自己动手,丰衣足食:提供一个很小的标准库,其余的让程序员自造

  • 保持语言的短小和简单

  • 性能优先


C++价值观摘录



  • 支持多范式,不强迫程序员使用某个特定的范式

  • 不求完美,但求实用(并且立即可用)


Go价值观



  • Overall Simplicity 全面的简单

  • Orthogonal Composition 正交组合

  • Preference in Concurrency 偏好并发


用一句话概括Go的价值观:
Go is about orthogonal composition of simple concepts with preference in concurrency(Go是在偏好并发的环境下的简单概念/事物的正交组合).


从Go的价值观介绍可以看出 Go很适合并发编程,可以说其是为并发而生的一门语言,那它的并发机制如何?这正是这篇文章想要介绍的。


2. 从线程实现模型说起


线程的实现模型主要有3种:内核级线程模型、用户级线程模型和混合型线程模型。它们之间最大的区别在于线程与内核调度实体KSE(Kernel Scheduling Entity)之间的对应关系上。所谓的内核调度实体KSE 就是指可以被操作系统内核调度器调度的对象实体,有些地方也称其为内核级线程,是操作系统内核的最小调度单元。


2.1 内核级线程模型


用户线程与KSE是1对1关系(1:1)。大部分编程语言的线程库(如linux的pthread,Java的java.lang.Thread,C++11的std::thread等等)都是对操作系统的线程(内核级线程)的一层封装,创建出来的每个线程与一个不同的KSE静态关联,因此其调度完全由OS调度器来做。这种方式实现简单,直接借助OS提供的线程能力,并且不同用户线程之间一般也不会相互影响。但其创建,销毁以及多个线程之间的上下文切换等操作都是直接由OS层面亲自来做,在需要使用大量线程的场景下对OS的性能影响会很大。


2.2 用户级线程模型


用户线程与KSE是多对1关系(M:1),这种线程的创建,销毁以及多个线程之间的协调等操作都是由用户自己实现的线程库来负责,对OS内核透明,一个进程中所有创建的线程都与同一个KSE在运行时动态关联。现在有许多语言实现的 协程 基本上都属于这种方式。这种实现方式相比内核级线程可以做的很轻量级,对系统资源的消耗会小很多,因此可以创建的数量与上下文切换所花费的代价也会小得多。但该模型有个致命的缺点,如果我们在某个用户线程上调用阻塞式系统调用(如用阻塞方式read网络IO),那么一旦KSE因阻塞被内核调度出CPU的话,剩下的所有对应的用户线程全都会变为阻塞状态(整个进程挂起)。

所以这些语言的协程库会把自己一些阻塞的操作重新封装为完全的非阻塞形式,然后在以前要阻塞的点上,主动让出自己,并通过某种方式通知或唤醒其他待执行的用户线程在该KSE上运行,从而避免了内核调度器由于KSE阻塞而做上下文切换,这样整个进程也不会被阻塞了。


2.3 混合型线程模型


用户线程与KSE是多对多关系(M:N), 这种实现综合了前两种模型的优点,为一个进程中创建多个KSE,并且线程可以与不同的KSE在运行时进行动态关联,当某个KSE由于其上工作的线程的阻塞操作被内核调度出CPU时,当前与其关联的其余用户线程可以重新与其他KSE建立关联关系。当然这种动态关联机制的实现很复杂,也需要用户自己去实现,这算是它的一个缺点吧。Go语言中的并发就是使用的这种实现方式,Go为了实现该模型自己实现了一个运行时调度器来负责Go中的"线程"与KSE的动态关联。此模型有时也被称为 两级线程模型即用户调度器实现用户线程到KSE的“调度”,内核调度器实现KSE到CPU上的调度


三种模型的示意图如下:
图片1


3. Go并发调度: G-P-M模型


3.1 G-P-M模型


有了上面的认识,我们可以开始真正的介绍Go的并发机制了,先用一段代码展示一下在Go语言中新建一个“线程”(Go语言中称为Goroutine)的样子:


// 用go关键字加上一个函数(这里用了匿名函数)
// 调用就做到了在一个新的“线程”并发执行任务
go func() {
// do something in one new goroutine
}()

功能上等价于Java8的代码:


new java.lang.Thread(() -> { 
// do something in one new thread
}).start();

可以看到Go的并发用起来非常简单,用了一个语法糖将内部复杂的实现结结实实的包装了起来。其内部可以用下面这张图来概述:
图片2
其图中的G, P和M都是Go语言运行时系统(其中包括内存分配器,并发调度器,垃圾收集器等组件,可以想象为Java中的JVM)抽象出来概念和数据结构对象:

G:Goroutine的简称,上面用go关键字加函数调用的代码就是创建了一个G对象,是对一个要并发执行的任务的封装,也可以称作用户态线程。属于用户级资源,对OS透明,具备轻量级,可以大量创建,上下文切换成本低等特点。

M:Machine的简称,在linux平台上是用clone系统调用创建的,其与用linux pthread库创建出来的线程本质上是一样的,都是利用系统调用创建出来的OS线程实体。M的作用就是执行G中包装的并发任务。Go运行时系统中的调度器的主要职责就是将G公平合理的安排到多个M上去执行。其属于OS资源,可创建的数量上也受限了OS,通常情况下G的数量都多于活跃的M的。

P:Processor的简称,逻辑处理器,主要作用是管理G对象(每个P都有一个G队列),并为G在M上的运行提供本地化资源。

从2.3节介绍的两级线程模型来看,似乎并不需要P的参与,有G和M就可以了,那为什么要加入P这个东东呢?

其实Go语言运行时系统早期(Go1.0)的实现中并没有P的概念,Go中的调度器直接将G分配到合适的M上运行。但这样带来了很多问题,例如,不同的G在不同的M上并发运行时可能都需向系统申请资源(如堆内存),由于资源是全局的,将会由于资源竞争造成很多系统性能损耗,为了解决类似的问题,后面的Go(Go1.1)运行时系统加入了P,让P去管理G对象,M要想运行G必须先与一个P绑定,然后才能运行该P管理的G。这样带来的好处是,我们可以在P对象中预先申请一些系统资源(本地资源),G需要的时候先向自己的本地P申请(无需锁保护),如果不够用或没有再向全局申请,而且从全局拿的时候会多拿一部分,以供后面高效的使用。就像现在我们去政府办事情一样,先去本地政府看能搞定不,如果搞不定再去中央,从而提供办事效率。

而且由于P解耦了G和M对象,这样即使M由于被其上正在运行的G阻塞住,其余与该M关联的G也可以随着P一起迁移到别的活跃的M上继续运行,从而让G总能及时找到M并运行自己,从而提高系统的并发能力。

Go运行时系统通过构造G-P-M对象模型实现了一套用户态的并发调度系统,可以自己管理和调度自己的并发任务,所以可以说Go语言原生支持并发自己实现的调度器负责将并发任务分配到不同的内核线程上运行,然后内核调度器接管内核线程在CPU上的执行与调度。


3.2 调度过程


Go运行时完整的调度系统是很复杂,很难用一篇文章描述的清楚,这里只能从宏观上介绍一下,让大家有个整体的认识。


// Goroutine1
func task1() {
go task2()
go task3()
}

假如我们有一个G(Goroutine1)已经通过P被安排到了一个M上正在执行,在Goroutine1执行的过程中我们又创建两个G,这两个G会被马上放入与Goroutine1相同的P的本地G任务队列中,排队等待与该P绑定的M的执行,这是最基本的结构,很好理解。 关键问题是:

a.如何在一个多核心系统上尽量合理分配G到多个M上运行,充分利用多核,提高并发能力呢?
如果我们在一个Goroutine中通过go关键字创建了大量G,这些G虽然暂时会被放在同一个队列, 但如果这时还有空闲P(系统内P的数量默认等于系统cpu核心数),Go运行时系统始终能保证至少有一个(通常也只有一个)活跃的M与空闲P绑定去各种G队列去寻找可运行的G任务,该种M称为自旋的M。一般寻找顺序为:自己绑定的P的队列,全局队列,然后其他P队列。如果自己P队列找到就拿出来开始运行,否则去全局队列看看,由于全局队列需要锁保护,如果里面有很多任务,会转移一批到本地P队列中,避免每次都去竞争锁。如果全局队列还是没有,就要开始玩狠的了,直接从其他P队列偷任务了(偷一半任务回来)。这样就保证了在还有可运行的G任务的情况下,总有与CPU核心数相等的M+P组合 在执行G任务或在执行G的路上(寻找G任务)。

b. 如果某个M在执行G的过程中被G中的系统调用阻塞了,怎么办?

在这种情况下,这个M将会被内核调度器调度出CPU并处于阻塞状态,与该M关联的其他G就没有办法继续执行了,但Go运行时系统的一个监控线程(sysmon线程)能探测到这样的M,并把与该M绑定的P剥离,寻找其他空闲或新建M接管该P,然后继续运行其中的G,大致过程如下图所示。然后等到该M从阻塞状态恢复,需要重新找一个空闲P来继续执行原来的G,如果这时系统正好没有空闲的P,就把原来的G放到全局队列当中,等待其他M+P组合发掘并执行。

图片3

c. 如果某一个G在M运行时间过长,有没有办法做抢占式调度,让该M上的其他G获得一定的运行时间,以保证调度系统的公平性?

我们知道linux的内核调度器主要是基于时间片和优先级做调度的。对于相同优先级的线程,内核调度器会尽量保证每个线程都能获得一定的执行时间。为了防止有些线程"饿死"的情况,内核调度器会发起抢占式调度将长期运行的线程中断并让出CPU资源,让其他线程获得执行机会。当然在Go的运行时调度器中也有类似的抢占机制,但并不能保证抢占能成功,因为Go运行时系统并没有内核调度器的中断能力,它只能通过向运行时间过长的G中设置抢占flag的方法温柔的让运行的G自己主动让出M的执行权。

说到这里就不得不提一下Goroutine在运行过程中可以动态扩展自己线程栈的能力,可以从初始的2KB大小扩展到最大1G(64bit系统上),因此在每次调用函数之前需要先计算该函数调用需要的栈空间大小,然后按需扩展(超过最大值将导致运行时异常)。Go抢占式调度的机制就是利用在判断要不要扩栈的时候顺便查看以下自己的抢占flag,决定是否继续执行,还是让出自己。

运行时系统的监控线程会计时并设置抢占flag到运行时间过长的G,然后G在有函数调用的时候会检查该抢占flag,如果已设置就将自己放入全局队列,这样该M上关联的其他G就有机会执行了。但如果正在执行的G是个很耗时的操作且没有任何函数调用(如只是for循环中的计算操作),即使抢占flag已经被设置,该G还是将一直霸占着当前M直到执行完自己的任务。


4. Goroutine与Channel: 锁之外的另一种同步机制


在主流的编程语言中为了保证多线程之间共享数据安全性和一致性,都会提供一套基本的同步工具集,如锁,条件变量,原子操作等等。Go语言标准库也毫不意外的提供了这些同步机制,使用方式也和其他语言也差不多。

除了这些基本的同步手段,Go语言还提供了一种新的同步机制: Channel,它在Go语言中是一个像int, float32等的基本类型,一个channel可以认为是一个能够在多个Goroutine之间传递某一类型的数据的管道。Go中的channel无论是实现机制还是使用场景都和Java中的BlockingQueue很接近。


使用方式


// 声明channel变量
var syncChan = make(chan int) // 无缓冲channel,主要用于两个Goroutine之间建立同步点
var cacheChan = make(chan int, 10) // 缓冲channel
// 向channel中写入数据
syncChan <- 1
cacheChan <- 1
// 从channel读取数据
var i = <-syncChan
var j = <-cacheChan

几乎等价于的Java中的操作:


TransferQueue<Integer> syncQueue = new LinkedTransferQueue<Integer>();
BlockingQueue<Integer> cacheQueue = new ArrayBlockingQueue<Integer>(10);

syncQueue.transfer(1);
cacheQueue.put(1);

int i = syncQueue.take();
int j = cacheQueu.take();

使用场景

a. 与Java的BlockingQueue一样用在需要生产者消费者模型的并发环境中。

b. 锁同步场景下一种替代方案。在Go的并发编程中有一句很经典的话:不要以共享内存的方式去通信,而要以通信的方式去共享内存。在Go语言中并不鼓励用锁保护共享状态的方式在不同的Goroutine中分享信息(以共享内存的方式去通信)。而是鼓励通过channel将共享状态或共享状态的变化在各个Goroutine之间传递(以通信的方式去共享内存),这样同样能像用锁一样保证在同一的时间只有一个Goroutine访问共享状态。但这的确需要转换以前用锁做并发同步的思维方式,大家觉得那种适合自己和自己的使用场景就用哪种好了,并不能很简单、绝对地说哪种方式更好,更高效。


5. Go语言对网络IO的优化


在谈论高性能网络IO编程时,我们几乎都离不开epoll/kqueue/iocp等技术术语了,如Java最新的的NIO,Node等等的高性能网络IO模型都是基于这些技术实现的。诞生于21世纪,有互联网时代的C语言之称的Go语言,这么重视高并发,当然不会放过对网络的优化。且Go语言中对网络IO的优化很巧妙,让你可以用和以前一样的(同步的)思维方式去编程的同时(而不是反人类的异步方式),还能享受到与异步方式几乎同等高效的运行性能。那Go语言中是如何做的呢?主要是从两方面下手的:

a. 将标准库中的网络库全部封装为非阻塞形式,防止其阻塞底层的M并导致内核调度器切换上下文带来的系统开销。

b. 运行时系统加入epoll机制(针对Linux系统),当某一个Goroutine在进行网络IO操作时,如果网络IO未就绪,就将其该Goroutine封装一下,放入epoll的等待队列中,当前G挂起,与其关联的M可以继续运行其他G。当相应的网络IO就绪后,Go运行时系统会将等待网络IO就绪的G从epoll就绪队列中取出(主要在两个地方从epoll中获取已网络IO就绪的G列表,一是sysmon监控线程中,二是自旋的M中),再由调度器将它们像普通的G一样分配给各个M去执行。

Go语言将高性能网络IO的实现方式直接集成到了Go本身的运行时系统中,与Go的并发调度系统协同高效的工作,让开发人员可以简单,高效地进行网络编程。


6. 总结


Go语言并不完美,它是以软件工程为目的的语言设计。其实现的并发机制也并不是什么革新的技术,只是将这些经典的理论和技术以一种简洁高效的方式组合了起来,并用简单抽象的API或语法糖开放给开发人员,着实减轻了开发人员编程的心智负担。而且其通过引入channel机制,将另一种并发编程模型(CSP: 通信顺序进程)带给了我们,给我们提供了使用其他并发编程思维方式的机会(有关CSP模型建议大家看看《七周七并发模型》这本书的第六章),Goroutine与Channel的组合是一对很有powerful的并发工具,相信其可以给你带了更好的并发编程体验。


7. 参考


《Go并发编程实战》 第2版

《Go语言学习笔记》

也谈goroutine调度器

Go coding in go way

golang string和[]byte的对比

sheepbao 发表了文章 • 0 个评论 • 302 次浏览 • 2017-09-30 16:42 • 来自相关话题

golang string和[]byte的对比

为啥string和[]byte类型转换需要一定的代价?
为啥内置函数copy会有一种特殊情况copy(dst []byte, src string) int查看全部

golang string和[]byte的对比


为啥string和[]byte类型转换需要一定的代价?

为啥内置函数copy会有一种特殊情况copy(dst []byte, src string) int?

string和[]byte,底层都是数组,但为什么[]byte比string灵活,拼接性能也更高(动态字符串拼接性能对比)?

今天看了源码探究了一下。

以下所有观点都是个人愚见,有不同建议或补充的的欢迎emial我aboutme


何为string?


什么是字符串?标准库builtin的解释:


type string

string is the set of all strings of 8-bit bytes, conventionally but not necessarily representing UTF-8-encoded text. A string may be empty, but not nil. Values of string type are immutable.

简单的来说字符串是一系列8位字节的集合,通常但不一定代表UTF-8编码的文本。字符串可以为空,但不能为nil。而且字符串的值是不能改变的。

不同的语言字符串有不同的实现,在go的源码中src/runtime/string.go,string的定义如下:


type stringStruct struct {
str unsafe.Pointer
len int
}

可以看到str其实是个指针,指向某个数组的首地址,另一个字段是len长度。那到这个数组是什么呢?
在实例化这个stringStruct的时候:


func gostringnocopy(str *byte) string {
ss := stringStruct{str: unsafe.Pointer(str), len: findnull(str)}
s := *(*string)(unsafe.Pointer(&ss))
return s
}

哈哈,其实就是byte数组,而且要注意string其实就是个struct。


何为[]byte?


首先在go里面,byte是uint8的别名。而slice结构在go的源码中src/runtime/slice.go定义:


type slice struct {
array unsafe.Pointer
len int
cap int
}

array是数组的指针,len表示长度,cap表示容量。除了cap,其他看起来和string的结构很像。

但其实他们差别真的很大。


区别


字符串的值是不能改变


在前面说到了字符串的值是不能改变的,这句话其实不完整,应该说字符串的值不能被更改,但可以被替换。 还是以string的结构体来解释吧,所有的string在底层都是这样的一个结构体stringStruct{str: str_point, len: str_len},string结构体的str指针指向的是一个字符常量的地址,
这个地址里面的内容是不可以被改变的,因为它是只读的,但是这个指针可以指向不同的地址,我们来对比一下string、[]byte类型重新赋值的区别:


s := "A1" // 分配存储"A1"的内存空间,s结构体里的str指针指向这快内存
s = "A2" // 重新给"A2"的分配内存空间,s结构体里的str指针指向这快内存

其实[]byte和string的差别是更改变量的时候array的内容可以被更改。


s := []byte{1} // 分配存储1数组的内存空间,s结构体的array指针指向这个数组。
s = []byte{2} // 将array的内容改为2

因为string的指针指向的内容是不可以更改的,所以每更改一次字符串,就得重新分配一次内存,之前分配空间的还得由gc回收,这是导致string操作低效的根本原因。


string和[]byte的相互转换


将string转为[]byte,语法[]byte(string)源码如下:


func stringtoslicebyte(buf *tmpBuf, s string) []byte {
var b []byte
if buf != nil && len(s) <= len(buf) {
*buf = tmpBuf{}
b = buf[:len(s)]
} else {
b = rawbyteslice(len(s))
}
copy(b, s)
return b
}

func rawstring(size int) (s string, b []byte) {
p := mallocgc(uintptr(size), nil, false)

stringStructOf(&s).str = p
stringStructOf(&s).len = size

*(*slice)(unsafe.Pointer(&b)) = slice{p, size, size}

return
}

可以看到b是新分配的,然后再将s复制给b,至于为啥copy函数可以直接把string复制给[]byte,那是因为go源码单独实现了一个slicestringcopy函数来实现,具体可以看src/runtime/slice.go


将[]byte转为string,语法string([]byte)源码如下:


func slicebytetostring(buf *tmpBuf, b []byte) string {
l := len(b)
if l == 0 {
// Turns out to be a relatively common case.
// Consider that you want to parse out data between parens in "foo()bar",
// you find the indices and convert the subslice to string.
return ""
}
if raceenabled && l > 0 {
racereadrangepc(unsafe.Pointer(&b[0]),
uintptr(l),
getcallerpc(unsafe.Pointer(&buf)),
funcPC(slicebytetostring))
}
if msanenabled && l > 0 {
msanread(unsafe.Pointer(&b[0]), uintptr(l))
}
s, c := rawstringtmp(buf, l)
copy(c, b)
return s
}

func rawstringtmp(buf *tmpBuf, l int) (s string, b []byte) {
if buf != nil && l <= len(buf) {
b = buf[:l]
s = slicebytetostringtmp(b)
} else {
s, b = rawstring(l)
}
return
}

依然可以看到s是新分配的,然后再将b复制给s。

正因为string和[]byte相互转换都会有新的内存分配,才导致其代价不小,但读者千万不要误会,对于现在的机器来说这些代价其实不值一提。
但如果想要频繁string和[]byte相互转换(仅假设),又不会有新的内存分配,能有办法吗?答案是有的。


package string_slicebyte_test

import (
"log"
"reflect"
"testing"
"unsafe"
)

func stringtoslicebyte(s string) []byte {
sh := (*reflect.StringHeader)(unsafe.Pointer(&s))
bh := reflect.SliceHeader{
Data: sh.Data,
Len: sh.Len,
Cap: sh.Len,
}
return *(*[]byte)(unsafe.Pointer(&bh))
}

func slicebytetostring(b []byte) string {
bh := (*reflect.SliceHeader)(unsafe.Pointer(&b))
sh := reflect.StringHeader{
Data: bh.Data,
Len: bh.Len,
}
return *(*string)(unsafe.Pointer(&sh))
}

func TestStringSliceByte(t *testing.T) {
s1 := "abc"
b1 := []byte("def")
copy(b1, s1)
log.Println(s1, b1)

s := "hello"
b2 := stringtoslicebyte(s)
log.Println(b2)
// b2[0] = byte(99) unexpected fault address

b3 := []byte("test")
s3 := slicebytetostring(b3)
log.Println(s3)
}

答案虽然有,但强烈推荐不要使用这种方法来转换类型,因为如果通过stringtoslicebyte将string转为[]byte的时候,共用的时同一块内存,原先的string内存区域是只读的,一但更改将会导致整个进程down掉,而且这个错误是runtime没法恢复的。


如何取舍?


既然string就是一系列字节,而[]byte也可以表达一系列字节,那么实际运用中应当如何取舍?



  • string可以直接比较,而[]byte不可以,所以[]byte不可以当map的key值。

  • 因为无法修改string中的某个字符,需要粒度小到操作一个字符时,用[]byte。

  • string值不可为nil,所以如果你想要通过返回nil表达额外的含义,就用[]byte。

  • []byte切片这么灵活,想要用切片的特性就用[]byte。

  • 需要大量字符串处理的时候用[]byte,性能好很多。


最后脱离场景谈性能都是耍流氓,需要根据实际场景来抉择。

一个多功能心跳发送包——yapool

千手扉间 发表了文章 • 0 个评论 • 223 次浏览 • 2017-09-14 19:42 • 来自相关话题

自己实现了一个多功能心跳包

传送门 https://github.com/CrocdileChan/yapool

因为之... 查看全部

自己实现了一个多功能心跳包


传送门 https://github.com/CrocdileChan/yapool


因为之前的项目需要,我将一部分功能逻辑抽象出来,这个包可以供给做分布式的小伙伴用来造轮子。


基于这个包,可以轻易的实现服务发现、健康监测以及集群数据采集功能,心跳可以分为多个等级,开发者可以在里面定义自己需要传送到center(或者叫master)的讯息,center端可以对该信息进行处理。

go 1.9 多线程安全MAP 函数模块

alalmn 发表了文章 • 0 个评论 • 531 次浏览 • 2017-08-28 16:02 • 来自相关话题

package main

//go 1.9  多线程安全MAP  函数模块
//QQ:29295842  欢迎技术交流
import (
    //  "fmt"
    "s... 			查看全部
					
package main

//go 1.9 多线程安全MAP 函数模块
//QQ:29295842 欢迎技术交流
import (
// "fmt"
"sync"
)

var (
map_list sync.Map //广告配置信息
wgx sync.WaitGroup //
)

func Thread_map_add(id string, rows_map map[string]interface{}) { //添加数据
map_list.Store(id, rows_map)
}

func Thread_map_revise(id string, rows_map map[string]interface{}) { //修改
wgx.Add(1) //线程数
go func() {
map_list.LoadOrStore(id, rows_map) //修改
wgx.Done()
}()
wgx.Wait() //等待
}

func Thread_map_delete(id string) { //删除
wgx.Add(1) //线程数
go func() {
map_list.Delete(id) //删除
wgx.Done()
}()
wgx.Wait() //等待
}

func Thread_map_read(id string) (bool, string, map[string]interface{}) { //读取
read_bool := false
value := make(map[string]interface{})
value2, err := map_list.Load(id) //key读取
if err {
if valuexa, ok := value2.(map[string]interface{}); ok {
value = valuexa
read_bool = true
}
}
//fmt.Print("===%v==%v==\n", data, err)
//遍历读取
// map_list.Range(func(key, value2 interface{}) bool { //读取数据
// fmt.Println(key, "-----------", value2)
// // if valuexa, ok := value2.(map[string]interface{}); ok {
// // read_bool = true
// // //key = fmt.Sprintf("%v", key)
// // value = valuexa
// // }
// return true
// })
return read_bool, id, value
}

//fmt.Println("----------------")

// rows_map := make(map[string]interface{})
// rows_map["db_name"] = "098765"
// rows_map["list"] = "1234567"

// map_add("abc", rows_map)
// rows_map = make(map[string]interface{})
// rows_map["db_name"] = "aaaaaa"
// rows_map["list"] = "bbbbbbb"
// //map_add("123", rows_map)
// map_revise("abc", rows_map)
// rows_map3 := make(map[string]interface{})
// rows_map3["db_name"] = "rrrrr"
// rows_map3["list"] = "eeeeeee"
// map_add("1234", rows_map3)

// read_bool, key, re_map := map_read("abc")
// fmt.Printf("==%v==%v==%v==\n", read_bool, key, re_map["db_name"])

redis 分布式锁

toukii 发表了文章 • 0 个评论 • 316 次浏览 • 2017-08-26 12:48 • 来自相关话题

rddlock

github.com/everfore/rddlock

redis distribute lock

... 查看全部

rddlock


github.com/everfore/rddlock


redis distribute lock


redis 分布式锁, 实现原理:redis分布式锁


Usage


Lock & UnLock


lockkey := "lock-key"
timeout_ms := 3000

locked, ex := rddlock.Lock(rds, lockkey, timeout_ms)
defer reelock.UnLock(rds, lockkey, ex)

LockRetry


retry_times := 10
locked, ex := reelock.LockRetry(rds, lockkey, timeout_ms, retry_times) // get lock by retry
defer reelock.UnLock(rds, lockkey, ex)

UnLockUnsafe


直接删除key,可能会有问题:若删除之前,该key已经超时且被其他进程获得锁,将会删除其他进程的锁;删除之后,锁被释放,进而会有其他进程2获得锁。。。雪崩


locked, _ := rddlock.Lock(rds, lockkey, timeout_ms)
defer reelock.UnLockUnsafe(rds, lockkey)

SyncDo 异步执行任务


err := SyncDo(rds, lockkey, timeout_ms, func(timeout chan bool) chan bool {
ret := make(chan bool, 1)
go func() {
fmt.Println("doing...")
// TODO SOMETHING
select {
case <-timeout:
// do the rollback
break
case ret <- true:
fmt.Println("success end.")
}
}()
return ret
})

test


success:200, avg:1.1074123 ms
failed:0, avg:NaN ms
--- PASS: TestLockTime (10.59s)

#local-redis
=== RUN TestLockRetryTime
success:200, avg:1.1741205 ms
failed:0, avg:NaN ms
--- PASS: TestLockRetryTime (10.58s)

#uat-redis
=== RUN TestLockRetryTime
success:200, avg:12.572702 ms
failed:0, avg:NaN ms
--- PASS: TestLockRetryTime (10.59s)

欢迎指正 github.com/everfore/rddlock

PHP编码gzdeflate与Golang解码DEFLATE

qiangmzsx 发表了文章 • 0 个评论 • 175 次浏览 • 2017-08-25 00:00 • 来自相关话题

8月7日@黄同学找我问:“数据存到redis是gzdeflate压缩过的数据,golang从redis取出来,解压缩失败”。很多从PHP转Golang的业务经常会遇到,所以写下这篇博文,希望可以帮助更多人。
想要使用golang解码php的编... 查看全部

8月7日@黄同学找我问:“数据存到redis是gzdeflate压缩过的数据,golang从redis取出来,解压缩失败”。很多从PHP转Golang的业务经常会遇到,所以写下这篇博文,希望可以帮助更多人。

想要使用golang解码php的编码,那么就应该需要知道gzdeflate函数的算法是什么,先到gzdeflate文档,查看了一下发现:

gzdeflate使用的是纯粹的DEFLATE格式。这就与golang的compress/flate包一致了。有了了解就可以看着golang文档实现代码了。遂与@黄同学同学写了几个函数进行验证,最后定稿如下:


package main

import (
"strings"
"fmt"
"compress/flate"
"bytes"
"io/ioutil"
"github.com/bitly/go-simplejson"
)

func main() {

str:="test123"
b:=Gzdeflate(str,-1)
ss:=Gzdecode(string(b))
fmt.Println(ss)
}

// 解码
func Gzdecode(data string) string {
if data == "" {
return ""
}
r :=flate.NewReader(strings.NewReader(data))
defer r.Close()
out, err := ioutil.ReadAll(r)
if err !=nil {
fmt.Errorf("%s\n",err)
return ""
}
return string(out)
}

// 编码
func Gzdeflate(data string,level int) []byte {
if data == "" {
return []byte{}
}
var bufs bytes.Buffer
w,_ :=flate.NewWriter(&bufs,level)
w.Write([]byte(data))
w.Flush()
defer w.Close()
return bufs.Bytes()
}

// 编码
func GzdeflateForString(data string,level int) string {
if data == "" {
return ""
}
var bufs bytes.Buffer
w,_ :=flate.NewWriter(&bufs,level)
w.Write([]byte(data))
w.Flush()
defer w.Close()
return bufs.String()
}

经过@黄同学同学测试可以正确使用。留下wiki供后续遇到的同学查看。

Golang Label使用方法

haohongfan 发表了文章 • 0 个评论 • 292 次浏览 • 2017-08-22 10:00 • 来自相关话题

发现golang的label也是比较强大的, 这里看了一些资料, 搜集了一些特点, 欢迎指正 http://www.haoho...

[译]go styleguide

回复

Xargin 发起了问题 • 1 人关注 • 0 个回复 • 500 次浏览 • 2017-08-04 17:39 • 来自相关话题

NoPoint Docker — 云时代的程序分发方式

Julyqi 发表了文章 • 0 个评论 • 281 次浏览 • 2017-07-28 16:17 • 来自相关话题

要说最近一年云计算业界有什么大事件?Google Compute Engine 的正式发布?Azure入华?还是AWS落地中国?留在每个人大脑中的印象可能各不相同,但要是让笔者来排名的话那么Docker绝对应该算是第一位的。如果你之前听说过它的话,那么也... 查看全部

要说最近一年云计算业界有什么大事件?Google Compute Engine 的正式发布?Azure入华?还是AWS落地中国?留在每个人大脑中的印象可能各不相同,但要是让笔者来排名的话那么Docker绝对应该算是第一位的。如果你之前听说过它的话,那么也许你会说“没错,就是它”,因为几乎世界各地的开发、运维都在谈论着Docker;如果你还没听说过Docker,那么我真的建议你花上5分钟来阅读本文。


https://community.clouderwork.com/article/view/59633469d009d.html


总之笔者认为Docker还是非常有趣的一个东西,值得大家花些时间体验一下,相信在各位的工作中多多少少都能用的上Docker。

GOLANG中DEFER, PANIC, RECOVER用法

回复

haohongfan 发起了问题 • 1 人关注 • 0 个回复 • 440 次浏览 • 2017-07-21 11:37 • 来自相关话题

beego & bee 1.9.0 released

astaxie 发表了文章 • 0 个评论 • 673 次浏览 • 2017-07-19 01:07 • 来自相关话题

beego:

  1. Fix the new repo address for casbin #2654
  2. Fix cache/memory fatal error: concurrent map iteration a... 查看全部

beego:



  1. Fix the new repo address for casbin #2654

  2. Fix cache/memory fatal error: concurrent map iteration and map write #2726

  3. AddAPPStartHook func modify #2724

  4. Fix panic: sync: negative WaitGroup counter #2717

  5. incorrect error rendering (wrong status) #2712

  6. validation: support int64 int32 int16 and int8 type #2728

  7. validation: support required option for some struct tag valids #2741

  8. Fix big form parse issue #2725

  9. File log add RotatePerm #2683

  10. Fix Oracle placehold #2749

  11. Supported gzip for req.Header has Content-Encoding: gzip #2754

  12. Add new Database Migrations #2744

  13. Beego auto generate sort ControllerComments #2766

  14. added statusCode and pattern to FilterMonitorFunc #2692

  15. fix the bugs in the "ParseBool" function in the file of config.go #2740


Bee



  1. Added MySQL year data type #443

  2. support multiple http methods #445

  3. The DDL migration can now be generated by adding a -ddl and a proper "alter" or "create" as argument value. #455

  4. Fix: docs generator skips everything containing 'vendor' #454

  5. get these tables information in custom the option #441

  6. read ref(pk) #444

  7. Add command bee server to server static folder.


https://github.com/astaxie/beego/pull/2771

给httprouter添加pprof功能

narutoinfo 发表了文章 • 0 个评论 • 294 次浏览 • 2017-07-18 19:40 • 来自相关话题

给httprouter添加pprof

1:获取包

go get github.com/feixiao/htt... 			查看全部
					

给httprouter添加pprof


1:获取包


go get github.com/feixiao/httpprof

2:进入所在目录,获取依赖


 govendor sync

3:编译运行example


go build

4:外部项目添加使用,只需要参考example的使用即可


func Index(w http.ResponseWriter, r *http.Request, _ httprouter.Params) {
fmt.Fprint(w, "Welcome!\n")
}

func Hello(w http.ResponseWriter, r *http.Request, ps httprouter.Params) {
fmt.Fprintf(w, "hello, %s!\n", ps.ByName("name"))
}

func main() {
router := httprouter.New()

// 在原来的httprouter的使用基础只是添加了这一句代码
router = httpprof.WrapRouter(router)

router.GET("/", Index)
router.GET("/hello/:name", Hello)

log.Fatal(http.ListenAndServe(":8080", router))
}

udp编程的那些事与golang udp的实践

sheepbao 发表了文章 • 0 个评论 • 1235 次浏览 • 2017-06-26 10:30 • 来自相关话题

udp编程的那些事与golang udp的实践

tcp/ip大协议中,tcp编程大家应该比较熟,应用的场景也很多,但是udp在现实中,应用也不少,而在大部分博文中,都很少对udp的编程进行研究,最近研究了一下udp编程,正好做个记录。<... 查看全部

udp编程的那些事与golang udp的实践


tcp/ip大协议中,tcp编程大家应该比较熟,应用的场景也很多,但是udp在现实中,应用也不少,而在大部分博文中,都很少对udp的编程进行研究,最近研究了一下udp编程,正好做个记录。

sheepbao 2017.06.15


tcp Vs udp


tcp和udp都是著名的传输协议,他们都是基于ip协议,都在OSI模型中传输层。tcp我们都很清楚,它提供了可靠的数据传输,而udp我们也知道,它不提供数据传输的可靠性,只是尽力传输。
他们的特性决定了它们很大的不同,tcp提供可靠性传输,有三次握手,4次分手,相当于具有逻辑上的连接,可以知道这个tcp连接的状态,所以我们都说tcp是面向连接的socket,而udp没有握手,没有分手,也不存在逻辑上的连接,所以我们也都说udp是非面向连接的socket。

我们都畏惧不知道状态的东西,所以即使tcp的协议比udp复杂很多,但对于系统应用层的编程来说,tcp编程其实比udp编程容易。而udp相对比较灵活,所以对于udp编程反而没那么容易,但其实掌握后udp编程也并不难。


udp协议


udp的首部


        2               2       (byte)
+---+---+---+---+---+---+---+---+ -
| src port | dst port | |
+---+---+---+---+---+---+---+---+ 8(bytes)
| length | check sum | |
+---+---+---+---+---+---+---+---+ -
| |
+ data +
| |
+---+---+---+---+---+---+---+---+

udp的首部真的很简单,头2个字节表示的是原端口,后2个字节表示的是目的端口,端口是系统层区分进程的标识。接着是udp长度,最后就是校验和,这个其实很重要,现在的系统都是默认开启udp校验和的,所以我们才能确保udp消息传输的完整性。如果这个校验和关闭了,那会让我们绝对会很忧伤,因为udp不仅不能保证数据一定到达,还不能保证即使数据到了,这个数据是否是正确的。比如:我在发送端发送了“hello”,而接收端却接收到了“hell”。如果真的是这样,我们就必须自己去校验数据的正确性。还好udp默认开发了校验,我们可以保证udp的数据完整性。


udp数据的封装


                                    +---------+
| 应用数据 |
+---------+
| |
v v
+---------+---------+
| udp首部 | 应用数据 |
+---------+---------+
| |
v UDP数据报 v
+---------+---------+---------+
| ip首部 | udp首部 | 应用数据 |
+---------+---------+---------+
| |
v IP数据报 v
+---------+---------+---------+---------+---------+
|以太网首部 | ip首部 | udp首部 | 应用数据 |以太网尾部 |
+---------+---------+---------+---------+---------+
| 14 20 8 4 |
| -> 以太网帧 <- |

数据的封装和tcp是一样,应用层的数据加上udp首部,构成udp数据报,再加上ip首部构成ip数据报,最后加上以太网首部和尾部构成以太网帧,经过网卡发送出去。


Golang udp实践


实践出真知,编程就需要多实践,才能体会其中的奥妙。


echo客户端和服务端


echo服务,实现数据包的回显,这是很多人网络编程起点,因为这个服务足够简单,但又把网络的数据流都过了一遍,这里也用go udp实现一个echo服务。

实现客户端发送一个“hello”,服务端接收消息并原封不动的返回给客户度。


server.go


package main

import (
"flag"
"fmt"
"log"
"net"
)

var addr = flag.String("addr", ":10000", "udp server bing address")

func init() {
log.SetFlags(log.LstdFlags | log.Lshortfile)
flag.Parse()
}

func main() {
//Resolving address
udpAddr, err := net.ResolveUDPAddr("udp", *addr)
if err != nil {
log.Fatalln("Error: ", err)
}

// Build listining connections
conn, err := net.ListenUDP("udp", udpAddr)
if err != nil {
log.Fatalln("Error: ", err)
}
defer conn.Close()

// Interacting with one client at a time
recvBuff := make([]byte, 1024)
for {
log.Println("Ready to receive packets!")
// Receiving a message
rn, rmAddr, err := conn.ReadFromUDP(recvBuff)
if err != nil {
log.Println("Error:", err)
return
}

fmt.Printf("<<< Packet received from: %s, data: %s\n", rmAddr.String(), string(recvBuff[:rn]))
// Sending the same message back to current client
_, err = conn.WriteToUDP(recvBuff[:rn], rmAddr)
if err != nil {
log.Println("Error:", err)
return
}
fmt.Println(">>> Sent packet to: ", rmAddr.String())
}
}

client1.go


package main

import (
"flag"
"fmt"
"log"
"net"
)

var raddr = flag.String("raddr", "127.0.0.1:10000", "remote server address")

func init() {
log.SetFlags(log.LstdFlags | log.Lshortfile)
flag.Parse()
}

func main() {
// Resolving Address
remoteAddr, err := net.ResolveUDPAddr("udp", *raddr)
if err != nil {
log.Fatalln("Error: ", err)
}

// Make a connection
tmpAddr := &net.UDPAddr{
IP: net.ParseIP("127.0.0.1"),
Port: 0,
}

conn, err := net.DialUDP("udp", tmpAddr, remoteAddr)
// Exit if some error occured
if err != nil {
log.Fatalln("Error: ", err)
}
defer conn.Close()

// write a message to server
_, err = conn.Write([]byte("hello"))
if err != nil {
log.Println(err)
} else {
fmt.Println(">>> Packet sent to: ", *raddr)
}

// Receive response from server
buf := make([]byte, 1024)
rn, rmAddr, err := conn.ReadFromUDP(buf)
if err != nil {
log.Println(err)
} else {
fmt.Printf("<<< %d bytes received from: %v, data: %s\n", rn, rmAddr, string(buf[:rn]))
}
}

client2.go


package main

import (
"flag"
"fmt"
"log"
"net"
)

var (
laddr = flag.String("laddr", "127.0.0.1:9000", "local server address")
raddr = flag.String("raddr", "127.0.0.1:10000", "remote server address")
)

func init() {
log.SetFlags(log.LstdFlags | log.Lshortfile)
flag.Parse()
}

func main() {
// Resolving Address
localAddr, err := net.ResolveUDPAddr("udp", *laddr)
if err != nil {
log.Fatalln("Error: ", err)
}

remoteAddr, err := net.ResolveUDPAddr("udp", *raddr)
if err != nil {
log.Fatalln("Error: ", err)
}

// Build listening connections
conn, err := net.ListenUDP("udp", localAddr)
// Exit if some error occured
if err != nil {
log.Fatalln("Error: ", err)
}
defer conn.Close()

// write a message to server
_, err = conn.WriteToUDP([]byte("hello"), remoteAddr)
if err != nil {
log.Println(err)
} else {
fmt.Println(">>> Packet sent to: ", *raddr)
}

// Receive response from server
buf := make([]byte, 1024)
rn, remAddr, err := conn.ReadFromUDP(buf)
if err != nil {
log.Println(err)
} else {
fmt.Printf("<<< %d bytes received from: %v, data: %s\n", rn, remAddr, string(buf[:rn]))
}
}

这里实现echo的服务端和客户端,和tcp的差不多,但是有一些小细节需要注意。

对于server端,先net.ListenUDP建立udp一个监听,返回一个udp连接,这里需要注意udp不像tcp,建立tcp监听后返回的是一个Listener,然后阻塞等待接收一个新的连接,这样区别是因为udp一个非面向连接的协议,它没有会话管理。同时也因为udp是非面向连接的协议,当接收到消息后,想把消息返回给当前的客户端时,是不能像tcp一样,直接往conn里写的,而是需要指定远端地址。

对于client端,类似tcp先Dial,返回一个连接,对于发送消息用Write,接收消息用Read,当然udp也可以用ReadFromUDP,这样可以知道从哪得到的消息。但其实client也可以用另一种方式写,如client2.go程序,先建立一个监听,返回一个连接,用这个连接发送消息给服务端和从服务器接收消息,这种方式和tcp倒是有很大的不同。


参考


golang pkg

GoCN每日新闻(2017-06-14)

回复

astaxie 发起了问题 • 1 人关注 • 0 个回复 • 644 次浏览 • 2017-06-14 10:58 • 来自相关话题