记录一个拷贝文件到GlusterFS卡住的解决过程

houyy668 回复了问题 • 3 人关注 • 2 个回复 • 471 次浏览 • 2017-11-03 16:32 • 来自相关话题

Gorush 輕量級手機訊息發送服務

appleboy 发表了文章 • 6 个评论 • 304 次浏览 • 2017-11-01 10:21 • 来自相关话题

文章轉錄自: Gorush 輕量級手機訊息發送服務


68747470733a2f2f7261772e6769746875622e636f6d2f676f6c616e672d73616d706c65732f676f706865722d766563746f722f6d61737465722f676f706865722e706e67


今年第一次參加濁水溪以南最大研討會 Mopcon,給了一場議程叫『用 Go 語言打造輕量級 Push Notification 服務』,身為南部人一定要參加 Mopcon,剛好透過此議程順便發佈新版 Gorush,其實今年投稿 Mopcon 最主要是回家鄉宣傳 Google 所推出的 Go 語言,藉由實際案例來跟大家分享如何入門 Go 語言,以及用 Go 語言最大好的好處有哪些。底下是此議程大綱:



  • 為什麼建立 Gorush 專案

  • 如何用 Go 語言實作

  • Drone 自動化測試及部署

  • Kubernetes 上跑 Gorush


什麼是 Gorush


Gorush 是一套輕量級的 Push Notification 服務,此服務只做一件事情,就是發送訊息給 Google Andriod 或 Apple iOS 手機,啟動時預設跑在 8088 port,可以透過 Docker 或直接用 Command line 執行,對於 App 開發者,可以直接下載執行檔,在自己電腦端發送訊息給手機測試。藉由這次投稿順便發佈了新版本。底下來說明新版本多了哪些功能。


支援 RPC 協定


在此之前 Gorush 只有支援 REST API 方式,也就是透過 JSON 方式來通知伺服器來發送訊息,新版了多了 RPC 方式,這邊我是使用 gRPC 來實作,Gorush 預設是不啟動 gRPC 服務,你必須要透過參數方式才可以啟動,詳細可以參考此文件,底下是 Go 語言客戶端範例:


package main

import (
"log"

pb "github.com/appleboy/gorush/rpc/proto"
"golang.org/x/net/context"
"google.golang.org/grpc"
)

const (
address = "localhost:9000"
)

func main() {
// Set up a connection to the server.
conn, err := grpc.Dial(address, grpc.WithInsecure())
if err != nil {
log.Fatalf("did not connect: %v", err)
}
defer conn.Close()
c := pb.NewGorushClient(conn)

r, err := c.Send(context.Background(), &pb.NotificationRequest{
Platform: 2,
Tokens: []string{"1234567890"},
Message: "test message",
})
if err != nil {
log.Fatalf("could not greet: %v", err)
}
log.Printf("Success: %t\n", r.Success)
log.Printf("Count: %d\n", r.Counts)
}

支援 ARM64 Docker 映像檔


目前已經支援 ARM64 的 Docker 版本,所以可以在 ARM64 板子內用 Docker 來執行,可以直接在 Docker Hub 找到相對應的標籤


支援全域變數


Gorush 本身支援 Yaml 設定檔,但是每次想要改設定,都要重新修改檔案,這不是很方便,所以我透過 Viper 套件來讓 Gorush 同時支援 Yaml 設定,或 Global 變數,也就是以後都可以透過變數方式來動態調整,有了這方式就可以讓 Docker 透過環境變數來設定。底下是範例讓開發者動態調整 HTTP 服務 Port。請注意所有變數的前置符號為 GORUSH_


$ GORUSH_CORE_PORT=8089 gorush

支援 Kubernetes


此版增加了 Kubernetes 設定方式,有了上述的全域變數支援,這時候設定 Kubernetes 就更方便了,請直接參考 k8s 目錄,詳細安裝步驟請參考此說明,底下是透過 ENV 動態設定 Gorush


env:
- name: GORUSH_STAT_ENGINE
valueFrom:
configMapKeyRef:
name: gorush-config
key: stat.engine
- name: GORUSH_STAT_REDIS_ADDR
valueFrom:
configMapKeyRef:
name: gorush-config
key: stat.redis.host

iOS 支援動態發送到開發或正式環境


在此之前發送訊息到 iOS 手機,都必須在啟動伺服器前將 iOS 環境設定好,現在可以動態調整 JSON 參數。


{
"notifications": [
{
"tokens": ["token_a", "token_b"],
"platform": 1,
"message": "Hello World iOS!"
}
]
}

可以加上 developmentproduction 布林參數,底下是將訊息傳給 iOS 開發伺服器


{
"notifications": [
{
"tokens": ["token_a", "token_b"],
"platform": 1,
"development": true,
"message": "Hello World iOS!"
}
]
}

投影片


底下是議程投影片,有興趣的參考看看


https://www.slideshare.net/appleboy/gorush-a-push-notification-server-written-in-go


最後有講到如何部署及測試 Go 語言,這邊講了一下 Drone 這套自動化測試工具。如果大家有興趣可以參考我在 Udemy 開設的課程,目前特價 1600 元。Drone 幫忙開發者自動化測試,部署到 Docker Hub 或編譯出執行檔,這些在 Drone 裡面都可以透過 YAML 來設定,開發者只需要專注於寫程式就可以了。

不得不知道的golang知识点之nil

qiangmzsx 发表了文章 • 2 个评论 • 972 次浏览 • 2017-10-30 17:43 • 来自相关话题

golang中的nil,很多人都误以为与Java、PHP等编程语言中的null一样。但是实际上Golang的niu复杂得多了,如果不信,那我们继续往下阅读。

nil 为预声明的标示符,... 查看全部

golang中的nil,很多人都误以为与Java、PHP等编程语言中的null一样。但是实际上Golang的niu复杂得多了,如果不信,那我们继续往下阅读。


nil 为预声明的标示符,定义在builtin/builtin.go


// nil is a predeclared identifier representing the zero value for a
// pointer, channel, func, interface, map, or slice type.
// Type must be a pointer, channel, func, interface, map, or slice type
var nil Type

// Type is here for the purposes of documentation only. It is a stand-in
// for any Go type, but represents the same type for any given function
// invocation.
type Type int

nil的零值


按照Go语言规范,任何类型在未初始化时都对应一个零值:布尔类型是false,整型是0,字符串是"",而指针、函数、interface、slice、channel和map的零值都是nil。


PS:这里没有说结构体struct的零值为nil,因为struct的零值与其属性有关


nil没有默认的类型,尽管它是多个类型的零值,必须显式或隐式指定每个nil用法的明确类型。


package main

func main() {

// 明确.
_ = (*struct{})(nil)
_ = []int(nil)
_ = map[int]bool(nil)
_ = chan string(nil)
_ = (func())(nil)
_ = interface{}(nil)

// 隐式.
var _ *struct{} = nil
var _ []int = nil
var _ map[int]bool = nil
var _ chan string = nil
var _ func() = nil
var _ interface{} = nil
}

如果关注过golang关键字的同学就会发现,里面并没有nil,也就是说nil并不是关键字,那么就可以在代码中定义nil,那么nil就会被隐藏。


package main

import "fmt"

func main() {
nil := 123
fmt.Println(nil) // 123
var _ map[string]int = nil //cannot use nil (type int) as type map[string]int in assignment
}

nil类型的地址和值大小


nil类型的所有值的内存布局始终相同,换一句话说就是:不同类型nil的内存地址是一样的。


package main
import (
"fmt"
)
func main() {
var m map[int]string
var ptr *int
var sl []int
fmt.Printf("%p\n", m) //0x0
fmt.Printf("%p\n", ptr ) //0x0
fmt.Printf("%p\n", sl ) //0x0
}

业务中一般将nil值表示为异常。nil值的大小始终与其类型与nil值相同的non-nil值大小相同。因此, 表示不同零值的nil标识符可能具有不同的大小。


package main

import (
"fmt"
"unsafe"
)

func main() {
var p *struct{} = nil
fmt.Println( unsafe.Sizeof( p ) ) // 8

var s []int = nil
fmt.Println( unsafe.Sizeof( s ) ) // 24

var m map[int]bool = nil
fmt.Println( unsafe.Sizeof( m ) ) // 8

var c chan string = nil
fmt.Println( unsafe.Sizeof( c ) ) // 8

var f func() = nil
fmt.Println( unsafe.Sizeof( f ) ) // 8

var i interface{} = nil
fmt.Println( unsafe.Sizeof( i ) ) // 16
}

大小是编译器和体系结构所依赖的。以上打印结果为64位体系结构和正式 Go 编译器。对于32位体系结构, 打印的大小将是一半。


对于正式 Go 编译器, 同一种类的不同类型的两个nil值的大小始终相同。例如, 两个不同的切片类型 ( []int和[]string) 的两个nil值始终相同。


nil值比较


1.不同类型的nil是不能比较的。


package main
import (
"fmt"
)
func main() {
var m map[int]string
var ptr *int
fmt.Printf(m == ptr) //invalid operation: m == ptr (mismatched types map[int]string and *int)
}

在 Go 中, 两个不同可比较类型的两个值只能在一个值可以隐式转换为另一种类型的情况下进行比较。具体来说, 有两个案例两个不同的值可以比较:



  • 两个值之一的类型是另一个的基础类型。

  • 两个值之一的类型实现了另一个值的类型 (必须是接口类型)。


nil值比较并没有脱离上述规则。


package main
import (
"fmt"
)
func main() {
type IntPtr *int
fmt.Println(IntPtr(nil) == (*int)(nil)) //true
fmt.Println((interface{})(nil) == (*int)(nil)) //false
}

2.同一类型的两个nil值可能无法比较
因为golang中存在map、slice和函数类型是不可比较类型,它们有一个别称为不可比拟的类型,所以比较它们的nil亦是非法的。


package main
import (
"fmt"
)
func main() {
var v1 []int = nil
var v2 []int = nil
fmt.Println(v1 == v2)
fmt.Println((map[string]int)(nil) == (map[string]int)(nil))
fmt.Println((func())(nil) == (func())(nil))
}

不可比拟的类型的值缺是可以与“纯nil”进行比较。


package main
import (
"fmt"
)
func main() {
fmt.Println((map[string]int)(nil) == nil) //true
fmt.Println((func())(nil) == nil) //true
}

3.两nil值可能不相等


如果两个比较的nil值之一是一个接口值, 而另一个不是, 假设它们是可比较的, 则比较结果总是 false。原因是在进行比较之前, 接口值将转换为接口值的类型。转换后的接口值具有具体的动态类型, 但其他接口值没有。这就是为什么比较结果总是错误的。


package main
import (
"fmt"
)
func main() {
fmt.Println( (interface{})(nil) == (*int)(nil) ) // false
}

常见问题


1.函数返回


func nilReturn() (string,error)  {

return nil,nil //cannot use nil as type string in return argument
}

因为error是接口类型所以error类型没有报错。


2.map的nil key
map的key为指针、函数、interface、slice、channel和map,则key可以为nil。


package main
import (
"fmt"
)
func main() {
mmap := make(map[*string]int,4)
a:="a"
mmap[&a] = 1
mmap[nil] = 99
fmt.Println(mmap) //map[0xc042008220:1 <nil>:99]
}

总结


nil之所以比较难以理解因为我们经常混淆了nil值和nil类型,希望各位同学细细品味其中区别。

软件开发过程中值不值得写单元测试?

voidint 发表了文章 • 2 个评论 • 331 次浏览 • 2017-10-27 23:14 • 来自相关话题


原文链接: https://voidint.github.io/post/2017/10/24/ut/



一、不写单元测试的理由


工作几年,遇到过不少抗拒写单元测试的人,总结一下大致有以下这么几个理由:


首先,写单元测试所支出的时间可能比实现功能本身所花费的时间还多。言外之意,在实现完所有功能之前不值得写单元测试。如果现阶段功能开发大致完毕,可能也不会去补上亏欠的单元测试,理由大致有这么几点:



  • 需求总是无穷尽的,还有下阶段功能需求要实现,没空补单元测试。

  • 要补的单元测试太多,无从下手,主观上抗拒。

  • 单元测试编写难度大。一方面原因可能是功能函数实现上不够合理,另一方面是没有(或者不知道)好用的单元测试框架和mock框架。

  • 单元测试不算入工作量内。


其次,功能需求还不稳定,写单元测试的性价比不高。换句话说,万一明天需求一变,那不光功能代码废了,单元测试也废了。如果不写单元测试,那这部分工夫就不会白费。


二、写单元测试的投入产出比


投入产出比作为这个问题的判断依据,我觉得是所有理性人都会做出的选择。而既然引入了投入产出比这个经济学上的概念,那么应该也能接受另一个经济学上的普世规律——边际收益递减。以及资源(主要指时间和精力)具有稀缺性这一规律。


下面的分析都将是建立在以上这些共识的基础之上,如果你并不认同这些规律同样可以用来分析软件开发过程中值不值得写单元测试这个问题,那么阅读以下内容仅仅是在浪费你宝贵的时间。如果你继续往下阅读,那么,我将假设你已经和我达成了这些共识。


虽然要为这个问题做精确的投入产出比定量分析比较困难,但并不妨碍我们通过定性分析来得出自己心中的答案。


成本(投入)



  • 编写单元测试用例所额外付出的时间,短期内会拖慢项目进度。


收益(产出)




  • 提升代码质量。监督开发人员写出更加易于测试和可维护的代码。




  • 提升开发团队内部的协作效率。其他开发人员可以通过阅读单元测试用例来理解代码原作者的意图。




  • 保证功能实现的长期稳定。代码一旦发生与原功能意图不相符的变化,通过跑单元测试可以体现出来,即可以防止功能被无意识地破坏。



  • 提高自动化测试占比,降低其他测试方式上的投入。


从上面我所罗列的成本/收益数量上说,收益的数量远大于成本。但是,分析投入产出比并不是掰手指数数量就能得出答案的,特此说明。


首先,短期项目不写单元测试是划算的选择。至于到底多长时间算作短期,并无定论。我选择将一个月作为划分的界限,一月以内为短期,多于一月是中期或者长期,至于中长期的界限在哪儿,这个无关紧要,暂且不论。


短期项目的典型代表就是演示用demo项目。这类项目的共性是时间紧迫,项目生命周期短,无需后续的维护,使用一次性(或者接近一次性)。如果说中长期项目的使用周期(区别于开发周期)是时间段的话,那么短期项目的使用周期就是一个时间点或者几个时间点。这种情况下将有限的资源投入到单元测试中,所获得的收益并不明显。如果继续追加投入,由于收益增幅平缓,投入产出比极低,甚至为负。索性零投入零产出,虽然略显保守,但也不失为一个好的选择。


其次,中长期项目不写单元测试绝对不是划算的选择。请注意,这里我并没有说中长期项目写单元测试是划算的选择这样的话。因为写单元测试这个说法太宽泛。很明显,单元测试覆盖率1%99%是有巨大区别的,而这两者都属于写单元测试这个范畴。


对于中长期项目,将资源投入到单元测试上所获得的收益曲线会是这样(不太会画图,暂且用文字描述):




  • 横坐标为投入,纵坐标为产出。




  • 开始阶段,随着投入的增加,收益(产出)增幅明显,曲线比较陡峭。




  • 当投入到达某一临界值,单位投入所获得的收益最大。



  • 当投入继续追加并超过临界值,收益的增幅明显放缓,曲线开始变得平缓,单位投入所获得的收益越来越少,即边际收益递减。


如果你也认可以上的投入产出比曲线,那么不难推出以下几个结论:




  • 不写单元测试一定不是最佳选择。不写单元测试可以理解为是零投入/零成本,那么必然的也会是零收益。




  • 写单元测试并且单元测试的覆盖率接近100%也一定不是最佳选择。由于边际收益递减,投入一旦越过临界值,那么继续追加投入所带来的收益将越来越少。



  • 临界值才是理论上的最佳选择。


上面提到的临界值是属于写单元测试的范畴,并且单元测试覆盖率在0%~100%之间的某个点。所以说,软件开发过程中值不值得写单元测试这个问题的答案应该无需再多言了。


文章一开始提到的那些不写单元测试的理由,往往是抱着一个非黑即白的观点,认为不写单元测试的反面就是写单元测试且覆盖率近100%。因而会过分夸大写单元测试的成本(单元覆盖率100%的代价当然大),选择短期利益。


三、个人的做法


下面以个人的小开源项目gbb为例,啰嗦几句我自己写单元测试的习惯。




  • 开源项目一定要写单元测试!开源项目一定要写单元测试!开源项目一定要写单元测试!按照规定,重要的事情得说三遍。除了上文提到的单元测试的好处外,单元测试也是开源项目负责任的一种体现。我花了时间去构思各种情况下的测试用例,我能为开源项目质量负责。




  • 不是非得写完一个函数就必须立马写单元测试或者TDD。关于写单元测试的时机,我一般选择在完成一个基本功能后写单元测试,优先覆盖功能的主体逻辑,一些边界条件逻辑不会体现在这个阶段的单元测试当中。我觉得这个阶段也是投入产出比最大的阶段。




  • 等功能相对稳定后,再把一些边界条件逻辑纳入到单元测试当中。这是单元测试覆盖率提升较大的阶段。



  • 最后一个阶段是刷数据阶段(gbb项目单元测试覆盖率曲线)。所谓的刷数据阶段的主要目标就是为了让覆盖率尽可能提高。刷数据并不是在某个功能成熟稳定后开始,我是选择在开源项目进入成熟阶段后开始刷单元测试覆盖率,为的就是使其更加好看。对于非开源项目,建议选择跳过这个抠细节的阶段。


四、参考


在写这篇博客时,我并没有查阅相关的这类文章。为的就是防止他人的观点在不知不觉中掺入其中,影响了我的原始观点。

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

redstorm 发表了文章 • 1 个评论 • 510 次浏览 • 2017-10-18 20:23 • 来自相关话题

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
}

链表以及golang介入式链表的实现

sheepbao 发表了文章 • 4 个评论 • 483 次浏览 • 2017-10-14 21:47 • 来自相关话题

链表以及golang介入式链表的实现

今天看tcp/ip协议栈的代码时看到一个双向链表,链表吗?听过它的顶顶大名,知道它是由节点构成的,每个节点还有个指针指向下一个节点,但是从来没自己实现过一个,没有实践就不能深刻理解,遂有此文。查看全部

链表以及golang介入式链表的实现


今天看tcp/ip协议栈的代码时看到一个双向链表,链表吗?听过它的顶顶大名,知道它是由节点构成的,每个节点还有个指针指向下一个节点,但是从来没自己实现过一个,没有实践就不能深刻理解,遂有此文。

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


何为链表?


链表(Linked list)是一种常见的基础数据结构,是一种线性表,但是并不会按线性的顺序存储数据,而是在每一个节点里存到下一个节点的指针(Pointer)。由于不必须按顺序存储,链表在插入的时候可以达到O(1)的复杂度,比另一种线性表顺序表快得多,但是查找一个节点或者访问特定编号的节点则需要O(n)的时间,而顺序表相应的时间复杂度分别是O(logn)和O(1)。

简单的说链表是一个具有逻辑顺序的线性表,每一个节点里存到下一个节点的指针。


图示


单链表


list1


双向链表


list2


链表有啥用?


因为链表插入很快,而且具有动态性,想添加几个元素就添加几个(内存空间足够),不像数组一样那么死板,正因为链表的灵活性,所有链表的用处是大大的有啊。

链表最适合用于频繁更新变化的数据,比如一个需要异步执行并且不可丢失的命令序列、一个需要进行实时加载与卸载的驱动,无序且数量未知,这个时候就需要链表结构来协助完成数据的管理。如果不需要过度关注数据的顺序,还可以用链表方便快捷地在任意一个地方插入或删除一个元素,并且不会影响到其它的元素。

又或者我在今天看tcp/ip源码中,链表用来构造队列,作为数据段的队列。我想链表用于队列应该是最多的。如果你看过linux内核源码,应该会发现linux内核中多处使用链表这种结构。


go标准库的双向链表


golang的标准库中实现了一个双向链表,该链表可以存储任何数据,先看看使用标准库链表的例子:


package list_test

import (
"container/list"
"fmt"
"testing"
)

func TestList(t *testing.T) {
// Create a new list and put some numbers in it.
l := list.New()
e4 := l.PushBack(4)
e1 := l.PushFront(1)
l.InsertBefore(3, e4)
l.InsertAfter(2, e1)

// Iterate through list and print its contents.
for e := l.Front(); e != nil; e = e.Next() {
fmt.Println(e.Value)
}
}
// output
// 1
// 2
// 3
// 4

该链表实现了链表所有的功能,链表的增删查改。


实现该链表的数据结构


// List represents a doubly linked list.
// The zero value for List is an empty list ready to use.
type List struct {
root Element // sentinel list element, only &root, root.prev, and root.next are used
len int // current list length excluding (this) sentinel element
}

// Element is an element of a linked list.
type Element struct {
// Next and previous pointers in the doubly-linked list of elements.
// To simplify the implementation, internally a list l is implemented
// as a ring, such that &l.root is both the next element of the last
// list element (l.Back()) and the previous element of the first list
// element (l.Front()).
next, prev *Element

// The list to which this element belongs.
list *List

// The value stored with this element.
Value interface{}
}

可以看到Element结构体看到了链表的结构,next,prev分别指向下一个和前一个元素的指针。Value就是链表中的数据段,可以理解为上图中的object。


介入式链表(intrusive list)


前面的链表都是普通链表,记得<<c语言程序设计>>上讲的链表也是一样,就是链表的节点指针和数据段是放在同一个struct,每实现一个不同的struct就得重新实现一遍链表的功能,这对于“懒惰”的程序员来说是不可忍受的,所以就出来了介入式链表,将数据段和链表的功能区别开来。最经典的例子莫过于linux内核的list_head,详情请看链接klist or Linked List in Linux Kernel,linux中是用c实现的,我想用go实现一个介入式链表。


实现代码


package list

type Intrusive interface {
Next() Intrusive
Prev() Intrusive
AddNext(Intrusive)
AddPrev(Intrusive)
}

// List provides the implementation of intrusive linked lists
type List struct {
prev Intrusive
next Intrusive
}

func (l *List) Next() Intrusive {
return l.next
}

func (l *List) Prev() Intrusive {
return l.prev
}

func (l *List) AddNext(i Intrusive) {
l.next = i
}

func (l *List) AddPrev(i Intrusive) {
l.prev = i
}

func (l *List) Reset() {
l.prev = nil
l.next = nil
}

func (l *List) Empty() bool {
return l.prev == nil
}

// Front returns the first element of list l or nil.
func (l *List) Front() Intrusive {
return l.prev
}

// Back returns the last element of list l or nil.
func (l *List) Back() Intrusive {
return l.next
}

// PushFront inserts the element e at the front of list l.
func (l *List) PushFront(e Intrusive) {
e.AddPrev(nil)
e.AddNext(l.prev)

if l.prev != nil {
l.prev.AddPrev(e)
} else {
l.next = e
}
l.prev = e
}

// PushBack inserts the element e at the back of list l.
func (l *List) PushBack(e Intrusive) {
e.AddNext(nil)
e.AddPrev(l.next)

if l.next != nil {
l.next.AddNext(e)
} else {
l.prev = e
}
l.next = e
}

// InsertAfter inserts e after b.
func (l *List) InsertAfter(e, b Intrusive) {
a := b.Next()
e.AddNext(a)
e.AddPrev(b)
b.AddNext(e)

if a != nil {
a.AddPrev(e)
} else {
l.next = e
}
}

// InsertBefore inserts e before a.
func (l *List) InsertBefore(e, a Intrusive) {
b := a.Prev()
e.AddNext(a)
e.AddPrev(b)
a.AddPrev(e)

if b != nil {
b.AddNext(e)
} else {
l.prev = e
}
}

// Remove removes e from l.
func (l *List) Remove(e Intrusive) {
prev := e.Prev()
next := e.Next()

if prev != nil {
prev.AddNext(next)
} else {
l.prev = next
}

if next != nil {
next.AddPrev(prev)
} else {
l.next = prev
}
}

我们这里用List表示实现了Intrusive接口,也实现了链表的基本功能,所以任何实现了Intrusive接口的对象都是可以作为链表的节点,利用这个介入式链表就很简单了,只要在现有的struct嵌入List这个结构体即可,在举个例子:


package list

import (
"container/list"
"fmt"
"testing"
)

func TestIntrusiveList(t *testing.T) {
type E struct {
List
data int
}
// Create a new list and put some numbers in it.
l := List{}
e4 := &E{data: 4}
e1 := &E{data: 1}
l.PushBack(e4)
l.PushFront(e1)
l.InsertBefore(&E{data: 3}, e4)
l.InsertAfter(&E{data: 2}, e1)

for e := l.Front(); e != nil; e = e.Next() {
fmt.Printf("e: %#v\n", e)
fmt.Printf("data: %#v\n", e.(*E).data)
}
}

E里嵌入List即可作为链表的节点,是不是很方便,其实当我写完介入式链表的栗子后,发现其实标准库的链表更方便,哈哈。。因为golang有interface{}


参考


https://blog.goquxiao.com/posts/2013/07/06/intrusive-list/

http://blog.nlogn.cn/linked-list-in-linux-kernel/

【翻译】使用 sync.ErrGroup 实现并发搜索文件

crazyvv 回复了问题 • 6 人关注 • 2 个回复 • 1812 次浏览 • 2017-10-11 15:11 • 来自相关话题

Go并发机制

simple 发表了文章 • 0 个评论 • 619 次浏览 • 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 发表了文章 • 2 个评论 • 594 次浏览 • 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,性能好很多。


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

為什麼我用 Drone 取代 Jenkins 及 GitLab CI

appleboy 回复了问题 • 5 人关注 • 4 个回复 • 788 次浏览 • 2017-09-27 10:38 • 来自相关话题

分享下一点创业小心得以及创业项目运营情况

qixinghaitang 发表了文章 • 3 个评论 • 454 次浏览 • 2017-09-22 13:16 • 来自相关话题

之前发过一个文章介绍我的创业小项目,但是可能还是有部分同学没有看到,所以在分享运营情况之前还是重新介绍下我的创业项目:

小专栏:一个专业人士的创作知识社区,旨在为一些在某个领域有深度研究的小伙伴提供的写作平台。后续小专栏会推出新功能,我们愿... 查看全部

之前发过一个文章介绍我的创业小项目,但是可能还是有部分同学没有看到,所以在分享运营情况之前还是重新介绍下我的创业项目:


小专栏:一个专业人士的创作知识社区,旨在为一些在某个领域有深度研究的小伙伴提供的写作平台。后续小专栏会推出新功能,我们愿景就是要改变技术人购买实体技术书的传统方式。


小专栏地址:https://xiaozhuanlan.com/


小专栏从8月1号开始内测到现在一共50天:


1、截止今天通过申请的专栏有将近130个,大多数专栏作者都是来自小米、腾讯、华为、阿里巴巴、百度、亚马逊、今日头条、欢聚时代、网易的技术产品设计牛人,也有如网易UEDC设计团队、又拍云技术团队、Ucloud 技术团队开设的团队专栏。


2、截止今天一共有1717次付费订阅共33691元,付费订阅次数最高的专栏如下:



还有剩下几十个两三百块钱订阅的专栏不一一罗列......


3、通过微信、Github、微博授权登录的用户是11067人,小专栏平台公众号也获得了超过7000人的订阅,希望大家可以多多支持,微信搜索“小专栏平台”关注支持一下哈。


4、成本:小专栏是我在今年四月份辞职之后全职做的,主要成本除了注册公司、各种认证花费将近一万元之外,其余都是人力成本,比如我接近6个月没有工资,薪资损失大概就18万了,还有一些设计费用等等加起来大约在二十六七万吧。


创业心得:


1、之前总结的一句话,那就是“如果看到一个平时还蛮骄傲的人哪怕再忙都跟每一个人/每一个群很有耐心聊天说话,那这个人肯定刚刚创业”。像小专栏这样的平台需要很多优秀的作者,需要不断邀请各类大牛加入平台,经常会遭受到各种拒绝,被拒绝其实也是需要一颗强大内心承受的。


2、每天想着如何能够让小专栏这个项目坚持20-24个月;在我钱少人少如何做到最好;后续的一些产品规划;等等。


3、在50天内测期间,我对小专栏付费率还是满意的吧,但是也时常会想做小专栏我怎么赚钱啊?万一20个月过去之后,我无法做到维持盈亏的话怎么办呢?


最后对自己说一句话:


坚持吧,少年!加油吧,少年!


也欢迎大家给建议、提意见,么么哒

使用bcc分析函数耗时

lrita 发表了文章 • 2 个评论 • 249 次浏览 • 2017-09-22 13:15 • 来自相关话题

golang自带的pprof工具只能分析定性分析哪些代码时最热(最占用CPU)的代码,通常低调用次数+高耗时的方法会被高调用次数的方法淹没掉。因此我们需要一些方法能够比较准确的... 查看全部

golang自带的pprof工具只能分析定性分析哪些代码时最热(最占用CPU)的代码,通常低调用次数+高耗时的方法会被高调用次数的方法淹没掉。因此我们需要一些方法能够比较准确的获知某个函数具体消耗的多少时间。
https://lrita.github.io/2017/09/16/get-function-elapse/

看到一个用Go语言编程的众筹机器人项目

Comdex 发表了文章 • 2 个评论 • 462 次浏览 • 2017-09-20 21:39 • 来自相关话题

https://z.jd.com/project/details/89271.html

好像还不错,大家怎么看

https://z.jd.com/project/details/89271.html


好像还不错,大家怎么看

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

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

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

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

因为之... 查看全部

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


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


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


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

go 语言操作数据库 CRUD

leyafo 发表了文章 • 2 个评论 • 678 次浏览 • 2017-09-07 18:38 • 来自相关话题

文章原链:http://www.leyafo.com/post/2017-09-07-go-db-crud/


go 语言标准库已经提供数据库访问通用接口,不同数据库需搭配相应连接 Driver。标准库里面 database/sql 实现基本数据类型 Scan, 基本的 Transaction 以及 sql 参数化。用这些东西去操作数据库完全够用,只是随着项目代码增长,sql string 会蔓延到项目的各个角落。若要修改数据库表结构,这些 sql string 就是噩梦一般存在。流行做法是使用 ORM(Object Relational Mapping) 去解决这个问题。ORM 封装好一些 CRUD 基本操作,可以避免大量手写 sql string.


go 编译型语言,无法做到像 Ruby 里面的 Method Missing 这样动态特性,可以为一个复合类型的 struct 随时添加一个 field. go 社区使用的 ORM 还是需要事先手动添加好 Field. 这样做需要对数据库和 struct 的成员做很多约定,写好对应的访问 tag。这些仍然无法避免修改数据库表时要一齐修改 go 代码。


我们可以仔细想想 ORM 真的是唯一的选择吗?ORM 实际上无法完美操作数据库,它做的事情无非就是这些事情:



  1. 参数化 sql string。

  2. 封装一些简单的 CRUD 操作。

  3. 序列化 sql 查询结果。


对于一些复杂的数据库查询语句,任何强大的 ORM 库,灵活的动态语言特性都无法解决。况且 ORM 也未必是好东西,它简化了操作,却间接隐藏了数据库的一些功能。如果不脱离 ORM 依赖我们无法去更好的操作数据库,去自己优化查询语句。以 go 语言目前的特性来看,这个社区永远也不可能会做出能像动态语言那样灵活的 ORM。关于 ORM 与 go 语言更详细的吐槽请见这里


如果不用 ORM 我们碰到的无非是上面提到的 3 个问题而已。把这个三个问题掰开处理,第一个问题是不存在的。参数化 sql string 这件事情我们只需要小心的处理就能防止 sql 注入这样的安全问题。剩下的就是 2 和 3 的问题,而第二个问题我们暂时也不需要解决,我们一开始就去写一些重复代码好了。而问题 3 我们可以手动自己去序列化,也可以用社区的一些库去解决这个问题。社区已经有了不错的解决方案,我用的就是 sqlx 去解决的这个问题。


当初项目开始时我考察不少 ORM 库后,果断抛弃使用 ORM。项目经过一段时间迭代后,不用 ORM 没有特别明显的不便。唯一的问题就是我需要手动为每一张表做好 table 到 go struct 之间的映射。需要写非常多重复性的 CRUD 操作代码。这些代码很难使用统一方法减少重复,只好任其膨胀。直到有一天我看到这篇文章,原来 go 语言需要写重复代码这个问题在其他问题领域也存在,而社区老司机们解决这个问题的方式是使用机器生成代码。社区大范围这么做的原因是 go 语言的语法非常简单,很容易用 go 生成 go 代码。


写 CRUD 生成器思路很简单,只需要去数据库里查询 table 的详细信息,为不同的 column 数据类型映射 go 数据类型。最后用 go 的 template 实现一些简单的 CRUD 方法。对于一般的 select 查询语句我这里没有去做实现,因为不同的表查询条件是不一样的,这种差异用函数传参解决会更好。生成器做 column 映射和拼接查询语句是极好的。


最后在项目里面把生成器生成的代码和手写的数据库相关代码分离开来,以方便数据库表结构变动后可以让生成器重新生成代码。这里是我写的这个简单的生成器,参照了一部分 xo 项目的代码,由于我只支持 Postgresql, 没有去支持 join 和 has_many 这样的操作,代码相对他们要简单很多。


事情到这里并没有完,我们还需要序列化后的查询结果做一些反序列化的工作,go 语言的 struct tag 对这方面有很好的支持。可是我们用机器生成的代码是无法控制外界需要的各种反序列化的字段。下面以序列化 json 为例,我们并不想把数据库的 ID 字段暴露给外界。如果用生成器去控制这些配置,生成器需要做更多的配置,数据库表字段需要更多约定,这无疑会增加生成器的难度。我们必须要为每一张表手动单独做一个 Export 的结构体与方法,以满足各种其他序列化的要求。


type UserExport struct {
Name string `json:"name"`
Email string `json:"email"`
UpdatedAt string `json:"updated_at"`
}

func (u User) Export() UserExport {
return UserExport{
Name: u.Name,
Email: u.Email,
UpdatedAt: u.UpdatedAt,
}
}

func (u User) MarshalJSON() ([]byte, error) {
return json.Marshal(u.Export())
}

如上所示,我们可以为 User 表配置不同 field 和 tag。可以单独为不同的序列化数据类型写一个 Marshal 方法,这些都是手动可以控制。为了灵活我们还可以把 Export 这个结构体直接嵌入到其他结构体中,不用担心 Marshal 会继承式覆盖后面 Marshal 方法。