XIAOSUO 记录个人学习的足迹

摘要：channels 是一种类型安全的消息队列，充当两个 goroutine 之间的管道，将通过它同步的进行任意资源的交换。chan 控制 goroutines 交互的能力从而创建了 Go 同步机制。当创建的 chan 没有容量时，称为无缓冲通道。反过来，使用容量创建的 chan 称为缓冲通道。 要了解通过 chan 交互的 goroutine 的同步行为是什么，我们需要知道通道的类型和状态。根据我们使用的是无缓冲通道还是缓冲通道，场景会有所不同，所以让我们单独讨论每个场景。 Unbuffered Channels ch := make(chan struct{}) 无缓冲 chan 没有容量，因此进行任何交换前需要两个 goroutine 同时准备好。当 goroutine 试图将一个资源发送到一个无缓冲的通道并且没有goroutine 等待接收该资源时，该通道将锁住发送 goroutine 并使其等待。当 goroutine 尝试从无缓冲通道接收，并且没有 goroutine 等待发送资源时，该通道将锁住接收 goroutine 并使其等待。 无缓冲信道的本质是保证同步。 func main() { c:= make(chan string) var wg sync.WaitGroup wg.Add(2) go func() { defer wg.Done() c - `foo` } go func() { defer wg.Done() time.Sleep(time.Second * 1) printIn(`Message` + -c) }() wg.Wait() } 第一个 goroutine 在发送消息 foo 之后被阻塞，因为还没有接收者准备好。规范中对这种行为进行了很好的解释： Receive 先于 Send 发生。 好处: 100% 保证能收到。 代价: 延迟时间未知。 Buffered Channels buffered channel 具有容量，因此其行为可能有点不同。当 goroutine 试图将资源发送到缓冲通道，而该通道已满时，该通道将锁住 goroutine并使其等待缓冲区可用。如果通道中有空间，发送可以立即进行，goroutine 可以继续。当goroutine 试图从缓冲通道接收数…… 阅读全文

摘要：Share Memory By Communicating 传统的线程模型(通常在编写 Java、C++ 和Python 程序时使用)程序员在线程之间通信需要使用共享内存。通常，共享数据结构由锁保护，线程将争用这些锁来访问数据。在某些情况下，通过使用线程安全的数据结构(如Python的Queue)，这会变得更容易。 Go 的并发原语 goroutines 和 channels 为构造并发软件提供了一种优雅而独特的方法。Go 没有显式地使用锁来协调对共享数据的访问，而是鼓励使用 chan 在 goroutine 之间传递对数据的引用。这种方法确保在给定的时间只有一个goroutine 可以访问数据。 Do not communicate by sharing memory; instead, share memory by communicating. Detecting Race Conditions With Go data race 是两个或多个 goroutine 访问同一个资源(如变量或数据结构)，并尝试对该资源进行读写而不考虑其他 goroutine。这种类型的代码可以创建您见过的最疯狂和最随机的 bug。通常需要大量的日志记录和运气才能找到这些类型的bug。 早在6月份的Go 1.1中，Go 工具引入了一个 race detector。竞争检测器是在构建过程中内置到程序中的代码。然后，一旦你的程序运行，它就能够检测并报告它发现的任何竞争条件。它非常酷，并且在识别罪魁祸首的代码方面做了令人难以置信的工作。 var Wait sync.WaitGroup var Counter int = 0 func main() { for routine := 1; routine = 2; routine++ { Wait.Add(1) go Rountine(rountine) } Wait.Wait() fmt.Print(Final Counter: %d\n, Counter) } func Rountine(id int) { for count := 0; count 2; count++ { value := Counter value++ Counter = value } Wait.Done() }…… 阅读全文

摘要：需要阅读https://golang.org/ref/mem 如何保证在一个 goroutine 中看到在另一个 goroutine 修改的变量的值，如果程序中修改数据时有其他 goroutine 同时读取，那么必须将读取串行化。为了串行化访问，请使用 channel 或其他同步原语，例如 sync 和 sync/atomic 来保护数据。 在一个 goroutine 中，读和写一定是按照程序中的顺序执行的。即编译器和处理器只有在不会改变这个 goroutine 的行为时才可能修改读和写的执行顺序。由于重排，不同的goroutine 可能会看到不同的执行顺序。例如，一个goroutine 执行 a = 1;b = 2;，另一个 goroutine 可能看到 b 在 a 之前更新。 Memory Reordering 用户写下的代码，先要编译成汇编代码，也就是各种指令，包括读写内存的指令。CPU 的设计者们，为了榨干 CPU 的性能，无所不用其极，各种手段都用上了，你可能听过不少，像流水线、分支预测等等。其中，为了提高读写内存的效率，会对读写指令进行重新排列，这就是所谓的 内存重排，英文为 MemoryReordering。 这一部分说的是 CPU 重排，其实还有编译器重排。比如: 但是，如果这时有另外一个线程同时干了这么一件事：x=0 在多核心场景下,没有办法轻易地判断两段程序是“等价”的。 现代 CPU 为了“抚平” 内核、内存、硬盘之间的速度差异，搞出了各种策略，例如三级缓存等。为了让 (2) 不必等待 (1) 的执行“效果”可见之后才能执行，我们可以把 (1) 的效果保存到 store buffer： 先执行 (1) 和 (3)，将他们直接写入 store buffer，接着执行 (2) 和 (4)。“奇迹”要发生了：(2) 看了下 store buffer，并没有发现有 B 的值，于是从 Memory 读出了 0，(4) 同样从 Memory 读出了 0。最后，打印出了 00。 因此，对于多线程的程序，所有的 CPU 都会提供“锁”支持，称之为 barrier，或者 fence。它要求：barrier 指令要求所有对内存的操作都必须要“扩散”到 memory 之后才能继续执行其他对 memory 的操作。因此，我们可以用高级点的 atomic com…… 阅读全文

摘要：Processes and Threads 操作系统会为该应用程序创建一个进程。作为一个应用程序，它像一个为所有资源而运行的容器。这些资源包括内存地址空间、文件句柄、设备和线程。 线程是操作系统调度的一种执行路径，用于在处理器执行我们在函数中编写的代码。一个进程从一个线程开始，即主线程，当该线程终止时，进程终止。这是因为主线程是应用程序的原点。然后，主线程可以依次启动更多的线程，而这些线程可以启动更多的线程。 无论线程属于哪个进程，操作系统都会安排线程在可用处理器上运行。每个操作系统都有自己的算法来做出这些决定。 Goroutines and Parallelism Go 语言层面支持的 go 关键字，可以快速的让一个函数创建为 goroutine，我们可以认为 main 函数就是作为 goroutine 执行的。操作系统调度线程在可用处理器上运行，Go运行时调度 goroutines 在绑定到单个操作系统线程的逻辑处理器中运行(P)。即使使用这个单一的逻辑处理器和操作系统线程，也可以调度数十万 goroutine 以惊人的效率和性能并发运行。 并发不是并行。并行是指两个或多个线程同时在不同的处理器执行代码。如果将运行时配置为使用多个逻辑处理器，则调度程序将在这些逻辑处理器之间分配 goroutine，这将导致 goroutine 在不同的操作系统线程上运行。但是，要获得真正的并行性，您需要在具有多个物理处理器的计算机上运行程序。否则，goroutines 将针对单个物理处理器并发运行，即使 Go 运行时使用多个逻辑处理器。 Keep yourself busy or do the work yourself 比如我们想监听一个端口，但并不知道它什么时候返回，我们可能会使用一个select来永远阻塞，如下代码： func main() { http.HandleFunc(/, func(w http.ResponseWriter, r *http.Request)) { fmt.FprintIn(w, Hello, GrpherCon SG) } go func() { if(err := http.listenAndServe(:8080, nil); err != nil) { log.Fatal(err) } }() sele…… 阅读全文

摘要：Error error类型是go语言的一种内置类型，使用的时候不用特定去import,他本质上是一个接口 //http://golang.org/pkg/builtin/#error type error interface{ Error() string //Error()是每一个订制的error对象需要填充的错误消息,可以理解成是一个字段Error } 我们经常使用 errors.New() 来返回一个 error 对象。 //http://golang.org/src/pkg/errors/errors.go type errorString struct { s String } func (e *errorString) Error() string { return e.s } 基础库中有大量自定义的error，如bufio //http://golang.org/src/pkg/bufio/bufio.go var { ErrInvalidUnreadByte = errors.New(bufio: invalid use of UnreadByte) ErrInvalidUnreadRune = errors.New(bufio: invalid use of UnreadRune) ErrBufferFull = errors.New(bufio: Buffer full) ErrNegativeCount = errors.New(bufio: negative count) } errors.New()返回的是内部errorString对象的指针 //http://golang.org/src/pkg/errors/errors.go //New returns an error that formats as the given text func New(text string) error { return errorString{text} } Error vs Exception 各个语言的演进历史： C：单返回值，一般通过传递指针作为入参，返回值为 int 表示成功还是失败。 C++：引入了 exception，但是无法知道被调用方会抛出什么异常 Java：引入了 checked exception…… 阅读全文

摘要：Go语言GC算法主要是基于Mark and Sweep (标记清除)算法，在此基础上进行改进和优化。 1). Mark and Sweep(标记清除)算法主要是以下2个步骤： 标记(Mark): 找出所有不可达对象，然后做上标记 清除(Sweep): 回收标记好的对象 标记清除具体步骤如下： a). 开始标记，程序暂停 b). 找到所有可达对象，并做上标记 c). 标记完成后开始清除未标记的对象 d). 清除完成 2). 标记清除算法存在以下几个问题 a). STW (stop the world) 标记对象的时候程序需要暂停，导致程序出现卡顿 (最主要的问题) b). 标记需要扫描整个堆 c). 清除对象会产生堆碎片 STW指的是runtime把所有的协程都冻结了，意味着用户逻辑是暂停的，这样所有的对象都不会被修改，这个时候去扫描是绝对安全的。 3). Tri-color Marking 为了解决标记清除算法带来的问题，Go在标记清除算法基础上提出来Tri-color Marking(三色标记法)算法来优化GC过程，大体流程如下： a). 最开始所有的对象都是白色的 b). GC开始，扫描所有可达的对象，标记为灰色 c). 从灰色对象中找到其引用对象并标记为灰色，自己标记为黑色 d). 监控对象修改，循环上一步骤，直到没有任何灰色对象 e). GC回收白色对象 f). 最后把所有黑色对象变成白色 4). 三色标记法通过2点来优化STW问题 a). 标记操作和用户逻辑并行: 用户逻辑经常会生成或改变对象引用，那如何保证标记和用户逻辑并行呢？Go为了解决这个问题引入了写屏障机制，在GC的过程中会监控对象的内存修改，并对对象进行重新标记，这个时候用户逻辑也可以执行 (实际上是很短暂的STW，然后对对象重新标记)，所以标记操作可以做到一定程度和用户逻辑并行。 b). 清除操作和用户逻辑并行: 三色标记法中最后只剩下的黑白两种对象，黑色对象是程序恢复后接着使用的对象，如果不碰触黑色对象，只清除白色的对象，肯定不会影响程序逻辑，所以清除白色对象和用户逻辑可以并行。 通过允许用户逻辑在标记和清除操作上做到并行处理来缩短STW的时间，提升整体GC的性能。 阅读全文

摘要：什么是哈希算法 定义 将任意长度的二进制值串映射成固定长度的二进制值串，这个映射的规则就是哈希算法，而通过原始数据映射之后得到的二进制值串就是哈希值。 如何设计一个优秀的哈希算法 单向哈希： 从哈希值不能反向推导出哈希值（所以哈希算法也叫单向哈希算法）。 篡改无效： 对输入敏感，哪怕原始数据只修改一个Bit，最后得到的哈希值也大不相同。 散列冲突： 散列冲突的概率要很小，对于不同的原始数据，哈希值相同的概率非常小。 执行效率： 哈希算法的执行效率要尽量高效，针对较长的文本，也能快速计算哈希值。 哈希算法的常见应用 安全加密 常用于加密的哈希算法： MD5：MD5 Message-Digest Algorithm，MD5消息摘要算法 SHA：Secure Hash Algorithm，安全散列算法 DES：Data Encryption Standard，数据加密标准 AES：Advanced Encryption Standard，高级加密标准 对用于加密的哈希算法，有两点格外重要，第一点是很难根据哈希值反向推导出原始数据，第二点是散列冲突的概率要小。 在实际开发中要权衡破解难度和计算时间来决定究竟使用哪种加密算法。 唯一标识 通过哈希算法计算出数据的唯一标识，从而用于高效检索数据。 数据校验 利用哈希算法对输入数据敏感的特点，可以对数据取哈希值，从而高效校验数据是否被篡改过。 散列函数 散列函数中用到的哈希算法更加关注散列后的值能不能平均分布，以及散列函数的执行快慢。 负载均衡 需求 如何实现一个会话粘滞（session sticky）的负载均衡算法？也就是说，在一次会话中的所有请求都路由到同一个服务器上。 解决方案 通过哈希算法对客户端IP或会话ID计算哈希值，将取得的哈希值与服务器列表的大小进行取模运算，最终得到的值就是应该被路由到的服务器编号。这样，就可以把同一个IP过来的请求都路由到同一个后端服务器上。 数据分片 如何统计“搜索关键词”出现的次数？ ①需求描述 假如我们有1T的日志文件，这里面记录了用户的搜索关键词，我们想要快速统计出每个关键词被搜索的次数，该怎么做呢？ ②问题分析 这个问题有两个难点，第一个是搜索的日子很大，没办法放到一台机器的内存中。第二个是只用一台机器来处理这么巨大的数据，处理时间会很长。 ③解决方案 先对数据进行分…… 阅读全文

摘要：什么是跳表 为一个值有序的链表建立多级索引，比如每2个节点提取一个节点到上一级，我们把抽出来的那一级叫做索引或索引层。如下图所示，其中down表示down指针，指向下一级节点。以此类推，对于节点数为n的链表，大约可以建立log2n-1级索引。像这种为链表建立多级索引的数据结构就称为跳表。 跳表的时间复杂度 计算跳表的高度 如果链表有n个节点，每2个节点抽取抽出一个节点作为上一级索引的节点，那第1级索引的节点个数大约是n/2，第2级索引的节点个数大约是n/4，依次类推，第k级索引的节点个数就是n/(2^k)。假设索引有h级别，最高级的索引有2个节点，则有n/(2^h)=2，得出h=log2n-1，包含原始链表这一层，整个跳表的高度就是log2n。 计算跳表的时间复杂度 假设我们在跳表中查询某个数据的时候，如果每一层都遍历m个节点，那在跳表中查询一个数据的时间复杂度就是O(m*logn)。那这个m是多少呢？假设我们要查找的数据是x，在第k级索引中，我们遍历到y节点之后，发现x大于y，小于后面的节点z，所以我们通过y的down指针，从第k级下降到第k-1级索引。在第k-1级索引中，y和z之间只有3个节点（包含y和z），所以，我们在k-1级索引中最多只需要遍历3个节点，以此类推，每一级索引都最多只需要遍历3个节点。所以m=3。因此在跳表中查询某个数据的时间复杂度就是O(logn)。 跳表的空间复杂度及如何优化 计算索引的节点总数 如果链表有n个节点，每2个节点抽取抽出一个节点作为上一级索引的节点，那每一级索引的节点数分别为：n/2，n/4，n/8，…，8，4，2，等比数列求和n-1，所以跳表的空间复杂度为O(n)。 如何优化时间复杂度 如果链表有n个节点，每3或5个节点抽取抽出一个节点作为上一级索引的节点，那每一级索引的节点数分别为（以3为例）：n/3，n/9，n/27，…，27，9，3，1，等比数列求和n/2，所以跳表的空间复杂度为O(n)，和每2个节点抽取一次相比，时间复杂度要低不少呢。 高效的动态插入和删除 跳表本质上就是链表，所以仅插作，插入和删除操时间复杂度就为O(1)，但在实际情况中，要插入或删除某个节点，需要先查找到指定位置，而这个查找操作比较费时，但在跳表中这个查找操作的时间复杂度是O(logn)，所以，跳表的插入和删除操作的是时间复杂度也是O…… 阅读全文

摘要：什么是二分查找 二分查找针对的是一个有序的数据集合，每次通过跟区间中间的元素对比，将待查找的区间缩小为之前的一半，直到找到要查找的元素，或者区间缩小为0。 时间复杂度分析 时间复杂度 假设数据大小是n，每次查找后数据都会缩小为原来的一半，最坏的情况下，直到查找区间被缩小为空，才停止。所以，每次查找的数据大小是：n，n/2，n/4，…，n/(2^k)，…，这是一个等比数列。当n/(2^k)=1时，k的值就是总共缩小的次数，也是查找的总次数。而每次缩小操作只涉及两个数据的大小比较，所以，经过k次区间缩小操作，时间复杂度就是O(k)。通过n/(2^k)=1，可求得k=log2n，所以时间复杂度是O(logn)。 认识O(logn) 这是一种极其高效的时间复杂度，有时甚至比O(1)的算法还要高效。为什么？ 因为logn是一个非常“恐怖“的数量级，即便n非常大，对应的logn也很小。比如n等于2的32次方，也就是42亿，而logn才32。 由此可见，O(logn)有时就是比O(1000)，O(10000)快很多。 如何实现二分查找 循环实现 func binarySearch1([]int a, val int) int { start := 0 end := len(a) - 1 for start = end { // 不要使用（start + end）/ 2 防止超出边界 mid := start + (end - start) / 2 if a[mid] val { end = mid - 1 } else if a[mid] val { start = mid + 1 } else { return mid } } return -1 } 注意事项： 循环退出条件是：start=end，而不是startend。 mid的取值，使用mid=start + (end - start) / 2，而不用mid=(start + end)/2，因为如果start和end比较大的话，求和可能会发生int类型的值超出最大范围。为了把性能优化到极致，可以将除以2转换成位运算，即start + ((end - start) 1)，因为相比除法运算来说，计算机处理位运算要快得多。 start和end的更新：sta…… 阅读全文

摘要：一、如何选择合适的排序算法？ 排序算法一览表 时间复杂度 是稳定排序？ 是原地排序？ 冒泡排序 O(n^2) 是 是 插入排序 O(n^2) 是 是 选择排序 O(n^2) 否 是 快速排序 O(nlogn) 否 是 归并排序 O(nlogn) 是 否 桶排序 O(n) 是 否 计数排序 O(n+k)，k是数据范围 是 否 基数排序 O(dn)，d是纬度 是 否 为什选择快速排序？ 线性排序时间复杂度很低但使用场景特殊，如果要写一个通用排序函数，不能选择线性排序。 为了兼顾任意规模数据的排序，一般会首选时间复杂度为O(nlogn)的排序算法来实现排序函数。 同为O(nlogn)的快排和归并排序相比，归并排序不是原地排序算法，所以最优的选择是快排。 二、如何优化快速排序？ 导致快排时间复杂度降为O(n)的原因是分区点选择不合理，最理想的分区点是：被分区点分开的两个分区中，数据的数量差不多。如何优化分区点的选择？有2种常用方法，如下： 三数取中法 从区间的首、中、尾分别取一个数，然后比较大小，取中间值作为分区点。 如果要排序的数组比较大，那“三数取中”可能就不够用了，可能要“5数取中”或者“10数取中”。 随机法：每次从要排序的区间中，随机选择一个元素作为分区点。 警惕快排的递归发生堆栈溢出，有2中解决方法，如下： 限制递归深度，一旦递归超过了设置的阈值就停止递归。 在堆上模拟实现一个函数调用栈，手动模拟递归压栈、出栈过程，这样就没有系统栈大小的限制。 三、通用排序函数实现技巧 数据量不大时，可以采取用时间换空间的思路 数据量大时，优化快排分区点的选择 防止堆栈溢出，可以选择在堆上手动模拟调用栈解决 在排序区间中，当元素个数小于某个常数是，可以考虑使用O(n^2)级别的插入排序 用哨兵简化代码，每次排序都减少一次判断，尽可能把性能优化到极致 四、Go语言排序函数的实现 golang标准库中的Sort用的是快排+希尔排序+插排，数据量大于12时用快排，小于等于12时用6作为gap做一次希尔排序，然后走一遍普通的插排（插排对有序度高的序列效率高）。其中快排pivot的选择做了很多工作，是基于首中尾中值的很复杂的变种 func quickSort(data Interface, a, b, maxDepth int) { for b-a 12 …… 阅读全文