• 还在篮子里

    acl 权限控制 · 语雀

    ACL 权限控制

    项目简介

    TL;DR;

    ACL is a lightweight ACL manager for Go.

    Features

    • Design simple & reusable roles to empower your application.
    • Acquire the rights of other roles to build a powerful set of permissions.
    • Resolve possible roles by examine them in an unified way.

    Example

    type User struct {
        isAdmin bool
    }
    
    func main() {
        // first of all: create a new manager instance to register all your roles in one place
        manager := acl.NewManager()
    
        // now you can use `Ensure` to guarantee that the role with the passed identifier is present
        user := manager.Ensure("user").Grant("profile.edit")
        // use `Grant`, `Revoke` and `AcquireFrom` to extend the right stack
        editor := manager.Ensure("editor").Grant("news.list", "news.create", "news.edit").AcquireFrom(user)
    
        // you can also use NewRole to create a Role manually
        admin := acl.NewRole("admin").Grant("news.delete").AcquireFrom(editor)
        // note, that you have to register the role by yourself
        manager.Register(admin)
    
        // to check if a right was granted to a role you can use:
        var hasAccess bool
        hasAccess = admin.Has("some.right")
    
        // to check if at least one of the expected rights is present:
        hasAccess = admin.HasOneOf("news.list", "news.create")
    
        // ... and finally, to check that all the expected rights are present, use:
        hasAccess = admin.HasAllOf("news.delete", "news.list")
    
        // a role can be extended with an examiner to determine whether a role can be added
        // to a `ResultSet`
        admin.SetExaminer(func (payload interface{}) bool {
            user := payload.(User)
            return user.isAdmin
        })
    
        // to get a result set you can use the managers `Examine` function
        rs := manager.Examine(User{isAdmin: true})
    
        // a result set contains "Has", "HasOneOf" and "HasAllOf" as described above and...
        // `GetRole` to grab specific roles from the result set
        expectedRole := rs.GetRole("admin")
    
        // you can also check if a role was added to a result set using:
        if rs.HasRole("admin") {
            // ...
        }
    }

    ##Blueprint

    来源: acl 权限控制 · 语雀

  • 还在篮子里

    使用Go进行集成测试的MySQL Docker容器 · 语雀

    使用Go进行集成测试的MySQL Docker容器

    原文链接                                                                                     作者:Mitesh

    翻译整理                                                                                     翻译整理:Abser

    Overview

    Bug 在实际生产中常常代价高昂。我们可以使用测试用例来在开发过程中捕获它们,以降低我们的成本。测试在所有软件中都非常重要。这有助于确保代码的正确性并有助于防止恶化。单元测试有助于隔离测试组件,而无需任何外部依赖。但是单元测试不足以确保我们能够拥有经过良好测试的稳定系统。实际上,在集成不同组件的过程中会发生故障。如果我们不在真实的环境上测试数据库后端的应用程序将面临的问题,我们可能永远不会注意到由于事务未提交,数据库的错误版本等问题。集成测试在端到端测试中扮演了重要角色。

    在当今世界,我们编写了许多软件应用程序,其中包含数据库作为存储后端。模拟这些数据库调用以进行单元测试可能很麻烦。在纲要中进行小的更改可能会导致重写部分或全部。因为查询不会连接到实际的数据库引擎,因此不会验证查询的语法或约束。模拟每个查询都可能导致重复工作。为避免这种情况,我们应该测试一个真正的数据库,在测试完成后可以将其销毁。Docker 非常适合运行测试用例,因为我们可以在几秒钟内运行容器并在完成后终止它们。

    安装docker

    让我们了解如何启动 MySQL docker 容器并使用它来使用 go 代码进行测试。我们首先需要确保运行我们的测试用例的系统安装了 docker,可以通过运行命令“ docker ps ” 来检查。如果未安装docker,请从此处安装 docker 。

    func(d * Docker)isInstalled()bool { 
      command:= exec.Command(“docker”,“ps”)
      err:= command.Run()
      if err!= nil { 
        return false 
      } 
      return true 
    }

    运行容器

    安装 docker 之后,我们需要使用用户和密码运行 MySQL 容器,该用户和密码可用于连接 MySQL 服务器。

    docker run --name our-mysql-container -e MYSQL_ROOT_PASSWORD = root -e MYSQL_USER = gouser -e MYSQL_PASSWORD = gopassword -e MYSQL_DATABASE = godb -p 3306:3306 --tmpfs / var / lib / mysql mysql:5.7

    这将运行 MySQL 版本 5.7 的 docker 镜像,其容器名称为 “our-mysql-container”。“-e” 指定我们需要为 MySQL docker 容器设置的运行时变量。我们将 root 设置为 root 密码。使用密码“gopassword” 创建用户 “gouser”,我们用它来连接到我们的应用程序中的 MySQL 服务器。我们正在暴露 Docker 容器的 3306 端口,所以我们可以连接到在 docker 容器内运行的 mysql 服务器。我们使用的是 tmpfs mount,它只将数据存储在主机的内存中。当容器停止时,将删除 tmpfs 挂载。因为我们只是进行测试,所以不需要永久存。

    type ContainerOption struct {
      Name              string
      ContainerFileName string
      Options           map[string]string
      MountVolumePath   string
      PortExpose        string
    }
    
    func (d *Docker) getDockerRunOptions(c ContainerOption) []string {
      portExpose := fmt.Sprintf("%s:%s", c.PortExpose, c.PortExpose)
      var args []string
      for key, value := range c.Options {
        args = append(args, []string{"-e", fmt.Sprintf("%s=%s", key, value)}...)
      }
      
      args = append(args, []string{"--tmpfs", c.MountVolumePath, c.ContainerFileName}...)
      
      dockerArgs := append([]string{"run", "-d", "--name", c.Name, "-p", portExpose}, args...)
      return dockerArgs
    }
    
    func (d *Docker) Start(c ContainerOption) (string, error) {
      dockerArgs := d.getDockerRunOptions(c)
      command := exec.Command("docker", dockerArgs...)
      command.Stderr = os.Stderr
      
      result, err := command.Output()
      if err != nil {
        return "", err
      }
      
      d.ContainerID = strings.TrimSpace(string(result))
      d.ContainerName = c.Name
      
      command = exec.Command("docker", "inspect", d.ContainerID)
      result, err = command.Output()
      if err != nil {
        d.Stop()
        return "", err
      }
      return string(result), nil
    }
    
    func (m *MysqlDocker) StartMysqlDocker() {
      mysqlOptions := map[string]string{
        "MYSQL_ROOT_PASSWORD": "root",
        "MYSQL_USER":          "gouser",
        "MYSQL_PASSWORD":      "gopassword",
        "MYSQL_DATABASE":      "godb",
      }
      containerOption := ContainerOption{
        Name:              "our-mysql-container",
        Options:           mysqlOptions,
        MountVolumePath:   "/var/lib/mysql",
        PortExpose:        "3306",
        ContainerFileName: "mysql:5.7",
      }
      
      m.Docker = Docker{}
      m.Docker.Start(containerOption)
    }

    我们可以通过 containerId 检查容器以获取容器的详细信息。

    docker inspect containerId

    一旦我们运行 Docker 容器,我们需要等到我们的 docker 容器启动并运行。我们可以使用以下命令检查这个。

    docker ps -a

    使用实例

    一旦 docker 启动并运行,我们就可以开始在我们的应用程序中使用它来运行真实数据库的集成测试用例。

    func (d *Docker) WaitForStartOrKill(timeout int) error {
      for tick := 0; tick < timeout; tick++ {
        containerStatus := d.getContainerStatus()
        if containerStatus == dockerStatusRunning {
         return nil
        }
        
        if containerStatus == dockerStatusExited {
         return nil
        }
        time.Sleep(time.Second)
      }
      
      d.Stop()
      return errors.New("Docker faile to start in given time period so stopped")
    }
    
    func (d *Docker) getContainerStatus() string {
      command := exec.Command("docker", "ps", "-a", "--format", "{{.ID}}|{{.Status}}|{{.Ports}}|{{.Names}}")
      output, err := command.CombinedOutput()
      if err != nil {
        d.Stop()
        return dockerStatusExited
      }
      
      outputString := string(output)
      outputString = strings.TrimSpace(outputString)
      dockerPsResponse := strings.Split(outputString, "\n")
      
      for _, response := range dockerPsResponse {
        containerStatusData := strings.Split(response, "|")
        containerStatus := containerStatusData[1]
        containerName := containerStatusData[3]
        
        if containerName == d.ContainerName {
          if strings.HasPrefix(containerStatus, "Up ") {
            return dockerStatusRunning
          }
        }
      }
      return dockerStatusStarting
    }

    我们可以使用下面的连接字符串从 go 代码连接到 docker 中运行的 MySQL服 务器。

    gouser:gopassword@tcp(localhost:3306)/godb?charset=utf8&parseTime=True&loc=Local

    结束

    这些可以在每次运行时重新创建来模拟使用真实数据库运行集成测试。这有助于确保我们的应用程序已准备好进行生产发布。

    完整的代码可以在这个git存储库中找到:https//github.com/MiteshSharma/DockerMysqlGo

    来源: 使用Go进行集成测试的MySQL Docker容器 · 语雀

  • 还在篮子里

    HyperLogLog · 语雀

    HyperLogLog

    基数计数基本概念

    基数计数(cardinality counting)通常用来统计一个集合中不重复的元素个数,例如统计某个网站的UV,或者用户搜索网站的关键词数量。数据分析、网络监控及数据库优化等领域都会涉及到基数计数的需求。 要实现基数计数,最简单的做法是记录集合中所有不重复的元素集合,当新来一个元素,若中不包含元素,则将加入,否则不加入,计数值就是的元素数量。这种做法存在两个问题:

    1. 当统计的数据量变大时,相应的存储内存也会线性增长
    1. 当集合变大,判断其是否包含新加入元素的成本变大

    概率算法

    实际上目前还没有发现更好的在大数据场景中准确计算基数的高效算法,因此在不追求绝对准确的情况下,使用概率算法算是一个不错的解决方案。概率算法不直接存储数据集合本身,通过一定的概率统计方法预估基数值,这种方法可以大大节省内存,同时保证误差控制在一定范围内。目前用于基数计数的概率算法包括:

    • Linear Counting(LC):早期的基数估计算法,LC在空间复杂度方面并不算优秀,实际上LC的空间复杂度与简单bitmap方法是一样的(但是有个常数项级别的降低),都是O(Nmax);
    • LogLog Counting(LLC):LogLog Counting相比于LC更加节省内存,空间复杂度只有O(log2(log2(Nmax)))
    • HyperLogLog Counting(HLL):HyperLogLog Counting是基于LLC的优化和改进,在同样空间复杂度情况下,能够比LLC的基数估计误差更小。

    HLL

    直观演示

    HLLDEMO

    HLL的实际步骤

    1. 通过hash函数计算输入值对应的比特串
    1. 比特串的低 位对应的数字用来找到数组S中对应的位置 i
    1. t+1位开始找到第一个1出现的位置 k,将 k 记入数组位置
    1. 基于数组S记录的所有数据的统计值,计算整体的基数值,计算公式可以简单表示为:

    HLLLLC的误差改进,实际是基于LLC

    算法来源(N次伯努利过程)

    下面非正式的从直观角度描述LLC算法的思想来源。

    a为待估集合(哈希后)中的一个元素,由上面对H的定义可知,a可以看做一个长度固定的比特串(也就是a的二进制表示),设H哈希后的结果长度为L比特,我们将这L个比特位从左到右分别编号为1、2、…、L

    又因为a是从服从均与分布的样本空间中随机抽取的一个样本,因此a每个比特位服从如下分布且相互独立。

    通俗说就是a的每个比特位为0和1的概率各为0.5,且相互之间是独立的。

    ρ(a)为a的比特串中第一个“1”出现的位置,显然1≤ρ(a)≤L,这里我们忽略比特串全为0的情况(概率为)。如果我们遍历集合中所有元素的比特串,取为所有ρ(a)的最大值。

    此时我们可以将作为基数的一个粗糙估计,即:

    解释

    注意如下事实:

    由于比特串每个比特都独立且服从0-1分布,因此从左到右扫描上述某个比特串寻找第一个“1”的过程从统计学角度看是一个伯努利过程,例如,可以等价看作不断投掷一个硬币(每次投掷正反面概率皆为0.5),直到得到一个正面的过程。在一次这样的过程中,投掷一次就得到正面的概率为1/2,投掷两次得到正面的概率是,投掷k次才得到第一个正面的概率为

    现在考虑如下两个问题:

    1、进行n次伯努利过程,所有投掷次数都不大于k的概率是多少?

    2、进行n次伯努利过程,至少有一次投掷次数等于k的概率是多少?

    首先看第一个问题,在一次伯努利过程中,投掷次数大于k的概率为,即连续掷出k个反面的概率。因此,在一次过程中投掷次数不大于k的概率为。因此,n次伯努利过程投掷次数均不大于k的概率为:

    显然第二个问题的答案是:

    从以上分析可以看出,当时,Pn(X≥k)的概率几乎为0,同时,当时,Pn(X≤k)的概率也几乎为0。用自然语言概括上述结论就是:当伯努利过程次数远远小于时,至少有一次过程投掷次数等于k的概率几乎为0;当伯努利过程次数远远大于时,没有一次过程投掷次数大于k的概率也几乎为0。

    如果将上面描述做一个对应:一次伯努利过程对应一个元素的比特串,反面对应0,正面对应1,投掷次数k对应第一个“1”出现的位置,我们就得到了下面结论:

    设一个集合的基数为n,为所有元素中首个“1”的位置最大的那个元素的“1”的位置,如果n远远小于,则我们得到为当前值的概率几乎为0(它应该更小),同样的,如果n远远大于,则我们得到为当前值的概率也几乎为0(它应该更大),因此可以作为基数n的一个粗糙估计。

    以上结论可以总结为:进行了n次进行抛硬币实验,每次分别记录下第一次抛到正面的抛掷次数kk,那么可以用n次实验中最大的抛掷次数来预估实验组数量n: 

    回到基数统计的问题,我们需要统计一组数据中不重复元素的个数,集合中每个元素的经过hash函数后可以表示成0和1构成的二进制数串,一个二进制串可以类比为一次抛硬币实验,1是抛到正面,0是反面。二进制串中从低位开始第一个1出现的位置可以理解为抛硬币试验中第一次出现正面的抛掷次数k,那么基于上面的结论,我们可以通过多次抛硬币实验的最大抛到正面的次数来预估总共进行了多少次实验,同样可以可以通过第一个1出现位置的最大值来预估总共有多少个不同的数字(整体基数)。

    LogLogCounting

    均匀随机化

    与LC一样,在使用LLC之前需要选取一个哈希函数H应用于所有元素,然后对哈希值进行基数估计。H必须满足如下条件(定性的):

    1、H的结果具有很好的均匀性,也就是说无论原始集合元素的值分布如何,其哈希结果的值几乎服从均匀分布(完全服从均匀分布是不可能的,D. Knuth已经证明不可能通过一个哈希函数将一组不服从均匀分布的数据映射为绝对均匀分布,但是很多哈希函数可以生成几乎服从均匀分布的结果,这里我们忽略这种理论上的差异,认为哈希结果就是服从均匀分布)。

    2、H的碰撞几乎可以忽略不计。也就是说我们认为对于不同的原始值,其哈希结果相同的概率非常小以至于可以忽略不计。

    3、H的哈希结果是固定长度的。

    以上对哈希函数的要求是随机化和后续概率分析的基础。后面的分析均认为是针对哈希后的均匀分布数据进行。

    分桶平均

    上述分析给出了LLC的基本思想,不过如果直接使用上面的单一估计量进行基数估计会由于偶然性而存在较大误差。因此,LLC采用了分桶平均的思想来消减误差。具体来说,就是将哈希空间平均分成m份,每份称之为一个桶(bucket)。对于每一个元素,其哈希值的前k比特作为桶编号,其中,而后L-k个比特作为真正用于基数估计的比特串。桶编号相同的元素被分配到同一个桶,在进行基数估计时,首先计算每个桶内元素最大的第一个“1”的位置,设为M[i],然后对这m个值取平均后再进行估计,即:

    这相当于物理试验中经常使用的多次试验取平均的做法,可以有效消减因偶然性带来的误差。

    下面举一个例子说明分桶平均怎么做。

    假设H的哈希长度为16bit,分桶数m定为32。设一个元素哈希值的比特串为“0001001010001010”,由于m为32,因此前5个bit为桶编号,所以这个元素应该归入“00010”即2号桶(桶编号从0开始,最大编号为m-1),而剩下部分是“01010001010”且显然ρ(01010001010)=2,所以桶编号为“00010”的元素最大的ρ即为M[2]的值。

    偏差修正

    上述经过分桶平均后的估计量看似已经很不错了,不过通过数学分析可以知道这并不是基数n的无偏估计。因此需要修正成无偏估计。这部分的具体数学分析在“Loglog Counting of Large Cardinalities”中,过程过于艰涩这里不再具体详述,有兴趣的朋友可以参考原论文。这里只简要提一下分析框架:

    首先上文已经得出:

    因此:

    这是一个未知通项公式的递推数列,研究这种问题的常用方法是使用生成函数(generating function)。通过运用指数生成函数和poissonization得到上述估计量的Poisson期望和方差为:

    其中不超过

    最后通过depoissonization得到一个渐进无偏估计量:

    其中:

    其中m是分桶数。这就是LLC最终使用的估计量。

    误差分析

    不加证明给出如下结论:

    算法应用

    误差控制

    在应用LLC时,主要需要考虑的是分桶数m,而这个m主要取决于误差。根据上面的误差分析,如果要将误差控制在ϵ之内,则:

    内存使用分析

    内存使用与m的大小及哈希值得长度(或说基数上限)有关。假设H的值为32bit,由于,因此每个桶需要5bit空间存储这个桶的,m个桶就是5×m/8字节。例如基数上限为一亿(约),当分桶数m为1024时,每个桶的基数上限约为,而,因此每个桶需要5bit,需要字节数就是5×1024/8=640,误差为,也就是约为4%。

    合并

    LC不同,LLC的合并是以桶为单位而不是bit为单位,由于LLC只需记录桶的,因此合并时取相同桶编号数值最大者为合并后此桶的数值即可。

    HyperLogLog Counting

    HyperLogLog Counting(以下简称HLLC)的基本思想也是在LLC的基础上做改进,具体细节请参考“HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm”这篇论文。

    基本算法

    HLLC的第一个改进是使用调和平均数替代几何平均数。注意LLC是对各个桶取算数平均数,而算数平均数最终被应用到2的指数上,所以总体来看LLC取得是几何平均数。由于几何平均数对于离群值(例如这里的0)特别敏感,因此当存在离群值时,LLC的偏差就会很大,这也从另一个角度解释了为什么n不太大时LLC的效果不太好。这是因为n较小时,可能存在较多空桶,而这些特殊的离群值强烈干扰了几何平均数的稳定性。

    因此,HLLC使用调和平均数来代替几何平均数,调和平均数的定义如下:

    调和平均数可以有效抵抗离群值的扰动。使用调和平均数代替几何平均数后,估计公式变为如下:

    其中:

    偏差分析

    根据论文中的分析结论,与LLC一样HLLC是渐近无偏估计,且其渐近标准差为:

    因此在存储空间相同的情况下,HLLC比LLC具有更高的精度。例如,对于分桶数m为2^13(8k字节)时,LLC的标准误差为1.4%,而HLLC为1.1%。

    分段偏差修正

    在HLLC的论文中,作者在实现建议部分还给出了在n相对于m较小或较大时的偏差修正方案。具体来说,设E为估计值:

    时,使用LC进行估计。

    是,使用上面给出的HLLC公式进行估计。

    时,估计公式如为

    关于分段偏差修正效果分析也可以在原论文中找到。

    结论

    并行化

    这些基数估计算法的一个好处就是非常容易并行化。对于相同分桶数和相同哈希函数的情况,多台机器节点可以独立并行的执行这个算法;最后只要将各个节点计算的同一个桶的最大值做一个简单的合并就可以得到这个桶最终的值。而且这种并行计算的结果和单机计算结果是完全一致的,所需的额外消耗仅仅是小于1k的字节在不同节点间的传输。

    应用场景

    基数估计算法使用很少的资源给出数据集基数的一个良好估计,一般只要使用少于1k的空间存储状态。这个方法和数据本身的特征无关,而且可以高效的进行分布式并行计算。估计结果可以用于很多方面,例如流量监控(多少不同IP访问过一个服务器)以及数据库查询优化(例如我们是否需要排序和合并,或者是否需要构建哈希表)。

    参考阅读

    Redis new data structure: the HyperLogLog

    HyperLogLog — Cornerstone of a Big Data Infrastructure

    来源: HyperLogLog · 语雀

  • 还在篮子里

    TokenBucket · 语雀

    TokenBucket

    Overview

    • 每秒会有 Limit个令牌放入桶中,或者说,每过 1/Limit 秒桶中增加一个令牌
    • 桶中最多存放 burst 个令牌,如果桶满了,新放入的令牌会被丢弃
    • 当一个 n 单元的数据包到达时,消耗 n 个令牌,然后发送该数据包
    • 如果桶中可用令牌小于 n,则该数据包将被缓存或丢弃

    令牌桶算法

    令牌桶算法是网络流量整形(Traffic Shaping)和速率限制(Rate Limiting)中最常使用的一种算法。典型情况下,令牌桶算法用来控制发送到网络上的数据的数目,并允许突发数据的发送。

    RateLimiter 中的令牌桶算法

    简介

    该包基于令牌桶算法(Token Bucket)来完成限流,非常易于使用.RateLimiter经常用于限制对一些物理资源或者逻辑资源的访问速率.它支持三种方式,:

    ·AllowN()是如果拿不到立刻返回。

    ·WaitN() 是暂时排队,等到足够的令牌再出发,中途可能因为context的cancel而cancel,同时归还占位。

    ·ReserveN()是直接出发,但是前人挖坑后人填,下一次请求将为此付出代价,一直等到令牌亏空补上,并且桶中有足够本次请求使用的令牌为止。

    工作实例

    假设正在工作的一个RateLimiter

    allow和wait

    对一个每秒产生一个令牌的RateLimiter,每有一个没有使用令牌的一秒,我们就将tokens加 1 ,如果RateLimiter在 10 秒都没有使用,则tokens变成10.0.这个时候,一个请求到来并请求三个令牌,我们将从RateLimiter中的令牌为其服务,tokens变为7.0.这个请求之后立马又有一个请求到来并请求10个令牌,我们将从RateLimiter剩余的 7 个令牌给这个请求,剩下还需要三个令牌,我们将从RateLimiter新产生的令牌中获取.我们已经知道,RateLimiter每秒新产生 1 个令牌,就是说上面这个请求还需要的 3 个令牌就要求其等待 3 秒.

    reserve

    想象一个RateLimiter每秒产生一个令牌,现在完全没有使用(处于初始状态),如果一个昂贵的请求要求 100 个令牌.如果我们选择让这个请求等待100秒再允许其执行,这显然很荒谬.我们为什么什么也不做而只是傻傻的等待100秒,一个更好的做法是允许这个请求立即执行(和allow没有区别),然后将随后到来的请求推迟到正确的时间点.这种策略,我们允许这个昂贵的任务立即执行,并将随后到来的请求推迟100秒.这种策略就是让任务的执行和等待同时进行.

    关于 timeToAct

    一个重要的结论:RateLimiter不会记最后一个请求,而是即下一个请求允许执行的时间.这也可以很直白的告诉我们到达下一个调度时间点的时间间隔.然后定一个一段时间未使用的Ratelimiter也很简单:下一个调度时间点已经过去,这个时间点和现在时间的差就是Ratelimiter多久没有被使用,我们会将这一段时间翻译成tokens.所有,如果每秒钟产生一个令牌(Limit==1),并且正好每秒来一个请求,那么tokens就不会增长.

    burst

    RateLimiter有一个桶容量,当请求大于这个桶容量时,直接丢弃。

    链接

    · Golang实现RateLimiter源码导航

    · RateLimiter语雀阅读

    来源: TokenBucket · 语雀

  • 还在篮子里

    《HTTP 权威指南》阅读 · 语雀

    《HTTP 权威指南》阅读

    Overview

    说实话,看这本书的时候是2019年,我认为她的部分信息已经过时了,或者说是完全没有意义了。

    但是作为现在网络传输信息的核心,总有一些东西是一直贯彻了几十年直到今日的。所以在这里写下读后感。

    包括有哪些是我认为还能读的以及我的感受

    Part One

    这是关于 HTTP 的概述,是现在web的基础,只要现在还是使用这个协议,那么这一块一定是有价值的。只是说这部分有价值的东西其实日常的网络工程中能了解到,或者在一些百科上也能知道

    • 关于URL的定义
      • 资源定位
    • 关于TCP/IP的使用
      • 链接的建立
    • 关于Web使用的组件
      • 代理
      • 缓存
      • 网关
      • 隧道
      • Agent代理
    • 关于报文的组成结构和C/S模式下的报文交互
      • 方法
      • 状态码

    Part Two

    这一部分是关于HTTP的结构,关于HTTP各种情况下是怎样交互的–使用不同的组件是什么情况

    主要用一些网络知识的拓扑图让你理解了你从客户端发出的请求是经历的怎样的过程到达服务端又是怎样回来的。这对理解网络之间的文件传输概念提供了很好的构建方式。

    Part Three

    这一部分讲了怎样在交互中保证隐私,即安全。实际上是怎样在HTTP传输的时候能够识别出来谁是谁来保护信息。

    讲到了Cookie和基本认证和摘要认证、HTTPS。

    其中最重要的应为Cookies和HTTPS。Cookies实际上就是存储一些信息来帮助认证客户端属性。而HTTPS则是在HTTP和TCP两层之间加了一层SSL加密,使得信息通过加密传输

    Part Four

    这部分是关于协议和标准的事情,我个人认为有些过时同时也是我们现在不需要了解的一段。正如图灵图书上写的

    站在巨人的肩膀上

    我们不应该注重于已经规范好的细枝末节上的实现,而是根据认真的使用他们,整合他们或者创新出的新的方式。

    当然建立新标准也是很重要的事情

    Part Five

    这是关于网页内容方面的部分。

    从这里你可以了解到网络上经常说到的重定向,DNS ,CDN 等各种名词其含义和起源,它们为什么要被这样设定,希望达到的是什么效果。

    和日志监控,用来分析网站–实际上现在我们只需要用别人的网站分析服务就好,没有必要和精力去自己耗力。


    最后附录里说明了一些规定

    如什么状态码代表什么情况,首部即header中的信息通常可以从名字判断出他们的信息是用来做什么的,然后是一些编码,语言和认证标识

    拓展

    HTTP或许以后会被取代,或者说被分掉大量的市场份额,比如这个

    星际文件传输网络:https://achainofblocks.com/2018/10/05/ipfs-interplanetary-file-system-simply-explained/

    来源: 《HTTP 权威指南》阅读 · 语雀

  • 还在篮子里

    My TechStack

    The way to TechStack

    Deepin

    go,caddy,grpc,boltdb(kv)

    Achive

    Language

    Go,javascript, python,c++,dart,next.js,react,julia,schema,rust, GDScript ,Bosque,Reason,StoryScript

    Database

    Redis/Mysql/mongoDB/etcd/postageSQL/laravelDB/TiDB/Vitess/ArangoDB/CRUX/Digraph/RethinkDB/CockroachDB/Prometheus/bboltdb/goleveldb

    Web Develop

    odoo,hugo,hexo,Wordpress,homeland,flutter webant design, landingpage,,mason,uplab,codepen,svelte

    Cloud Service

    Heroku

    ServiceMesh

    kubernetesistioprotobufgRPC,docker,docker-compose

    Proxy:

    envoy/trafic

    configure:

    kubeEdge/pulumi/openStack

    Grafana/IRONdb,elastic/fluentd/logstash.

    Security

    teleport/vault

    MQ

    Nats/kafka/RabbitMQ/streamSets

    Math

    模糊数学,离散数学,范畴学,线性代数。

    APP

    flutter,wepy,微信小程序,electron,mattermost,slack bot,telegram bot etc

    Serverless

    zeit,lamda,OpenFaas,fn(JS)

    Network

    netstack,http,tcp/ip,ssl,webRTC,telegram mtg

    BlockChain

    move,IPFS,libp2p

    Linux

    0.12内核源码,ssh,centOS

    Google

    fuchsia,ChromeOS

    Design

    photoshop,flash,ppt,sketch

    IDE & TOOL

    vscode,goland,clion,postman,Godot

    Communicate

    佛理,哲学,冥想‍♂️

    miscs

    json,xml,yaml,toml,slack,tokenbucket

  • 还在篮子里

    BoltDB Page Layout · 语雀

    BoltDB Page Layout

    尝试在尽量简洁的语言中讲解清楚,boltdb 的存储过程,分页算法。结合图片。同时,讲清楚这个,整个 boltdb 就完全清楚了,剩下的不过是 把数据 key value 放在 每一个 page 中。其他 boltdb 的部分可以自己看源码和看别人的博客了解

    BoltDB 作为无临时文件,只在内存中写的数据库,是如何通过页面分配支持完整的事务特性(ACID)使用 MVCC并发控制。

    首先是一点概念,BoltDB 是一个 K/V 数据库,他把数据都储存在文件系统的一个文件上,都是以字节切片的格式存储的,在运行中,文件在内存中组织成 B+ 树,K/V 数据储存在 名叫 Bucket 的桶中,每一个 Bucket 都是一个完整的 B+ 树。B+ 树的每一个 node 存储着数据,对应着文件中的一个(或多个连续) page,而 page 是由操作系统的页面大小决定的,一般为 4k。

    page.svg

    page-allocate.svg

    Refer

    存储结构和并发事务特性解析:https://youjiali1995.github.io/storage/boltdb/

    源代码详细内在逻辑流程:https://www.jianshu.com/p/b86a69892990

    来源: BoltDB Page Layout · 语雀

  • 还在篮子里

    BoltDB 事务流程 · 语雀

    BoltDB 事务流程

    分析的 etcd-io/bbolt 的代码,同时基本不会改动了。

    文章不会写上详细的信息,但是会留下链接供自己深入研究。

    结构

    Wiki-事务

    首先看事务的结构体 Tx

    // txid represents the internal transaction identifier.
    type txid uint64
    
    // Tx represents a read-only or read/write transaction on the database.
    // Read-only transactions can be used for retrieving values for keys and creating cursors.
    // Read/write transactions can create and remove buckets and create and remove keys.
    type Tx struct {
        writable       bool
        managed        bool
        db             *DB
        meta           *meta
        root           Bucket
        pages          map[pgid]*page
        stats          TxStats
        commitHandlers []func()
    
        // WriteFlag specifies the flag for write-related methods like WriteTo().
        // Tx opens the database file with the specified flag to copy the data.
        WriteFlag int
    }

    Update

    通常使用 db.Update 开启事务

    // Update executes a function within the context of a read-write managed transaction.
    // If no error is returned from the function then the transaction is committed.
    // If an error is returned then the entire transaction is rolled back.
    // Any error that is returned from the function or returned from the commit is
    // returned from the Update() method.
    //
    // Attempting to manually commit or rollback within the function will cause a panic.
    func (db *DB) Update(fn func(*Tx) error) error {
        t, err := db.Begin(true)
        if err != nil {
            return err
        }
    
        // Make sure the transaction rolls back in the event of a panic.
        defer func() {
            if t.db != nil {
                t.rollback()
            }
        }()
    
        // Mark as a managed tx so that the inner function cannot manually commit.
        t.managed = true
    
        // If an error is returned from the function then rollback and return error.
        err = fn(t)
        t.managed = false
        if err != nil {
            _ = t.Rollback()
            return err
        }
    
        return t.Commit()
    }

    注意到 Rollback()Commit()

    Begin

    事务可以使用

    • db.Update()db.View()) 开启。(包装的 db.Begin())
    • 手动使用 db.Begin() 开启。传入参数控制是否写事务。
    // Begin starts a new transaction.
    // Multiple read-only transactions can be used concurrently but only one
    // write transaction can be used at a time. Starting multiple write transactions
    // will cause the calls to block and be serialized until the current write
    // transaction finishes.
    func (db *DB) Begin(writable bool) (*Tx, error) {
        if writable {
            return db.beginRWTx()
        }
        return db.beginTx()
    }

    写事务的 beginRWTx()

    beginRWTx()

    写事务会上锁控制单写,这里的 rwlock 不是真的读写锁,是一个互斥锁,不然文件锁上啥事也做不了。

    // Obtain writer lock. This is released by the transaction when it closes.
    // This enforces only one writer transaction at a time.
    db.rwlock.Lock()

    注意到 init 函数初始化了事务

    t.init(db)

    读事务的 beginTx()

    beginTx()

    读事务中会上 内存 mmap 的锁,这会阻塞需要 remmap 的写事务。写事务在 Commit 时需要 更多的 page 映射在 内存里就会 remmap。

    // Obtain a read-only lock on the mmap. When the mmap is remapped it will
    // obtain a write lock so all transactions must finish before it can be
    // remapped.
    db.mmaplock.RLock()

    这意味着,耗时的读操作会降低性能,同时应尽量避免写事务频繁 remmap,

    参数

    可以通过设置初始化最初 map 的大小避免最开始的 mmap 内存映射操作。

    mmap 的 remmap 的增长逻辑是翻倍,直到内存中 mmap 大于 1g 时,每次 remmap 申请 1g

    由此可以看出, BoltDB 只适合少写多读的场景。

    Init

    detail:事务初始化信息

    // init initializes the transaction.
    func (tx *Tx) init(db *DB) {
        tx.db = db
        tx.pages = nil
    
        // Copy the meta page since it can be changed by the writer.
        tx.meta = &meta{}
        db.meta().copy(tx.meta)
    
        // Copy over the root bucket.
        tx.root = newBucket(tx)
        tx.root.bucket = &bucket{}
        *tx.root.bucket = tx.meta.root
    
        // Increment the transaction id and add a page cache for writable transactions.
        if tx.writable {
            tx.pages = make(map[pgid]*page)
            tx.meta.txid += txid(1)
        }
    }

    这里拷贝了 db.meta 实现了写事务的版本控制,每一次写事务会更新 两个 metapage 之一,同时版本号 加一

    Commit

    • B+

    commit 的过程中才会发生 b+ 树的分裂,平衡等操作。

    完成在内存中对 数据库信息 的操作之后提交。

    // Commit writes all changes to disk and updates the meta page.
    // Returns an error if a disk write error occurs, or if Commit is
    // called on a read-only transaction.
    func (tx *Tx) Commit() error {
        _assert(!tx.managed, "managed tx commit not allowed")
        if tx.db == nil {
            return ErrTxClosed
        } else if !tx.writable {
            return ErrTxNotWritable
        }
    
        // Rebalance nodes which have had deletions.
        var startTime = time.Now()
        tx.root.rebalance()
        if tx.stats.Rebalance > 0 {
            tx.stats.RebalanceTime += time.Since(startTime)
        }
    
        // spill data onto dirty pages.
        startTime = time.Now()
        if err := tx.root.spill(); err != nil {
            tx.rollback()
            return err
        }
        tx.stats.SpillTime += time.Since(startTime)
    
        // Free the old root bucket.
        tx.meta.root.root = tx.root.root
    
        // Free the old freelist because commit writes out a fresh freelist.
        if tx.meta.freelist != pgidNoFreelist {
            tx.db.freelist.free(tx.meta.txid, tx.db.page(tx.meta.freelist))
        }
    
        if !tx.db.NoFreelistSync {
            err := tx.commitFreelist()
            if err != nil {
                return err
            }
        } else {
            tx.meta.freelist = pgidNoFreelist
        }
    
        // Write dirty pages to disk.
        startTime = time.Now()
        if err := tx.write(); err != nil {
            tx.rollback()
            return err
        }
    
        // If strict mode is enabled then perform a consistency check.
        // Only the first consistency error is reported in the panic.
        if tx.db.StrictMode {
            ch := tx.Check()
            var errs []string
            for {
                err, ok := <-ch
                if !ok {
                    break
                }
                errs = append(errs, err.Error())
            }
            if len(errs) > 0 {
                panic("check fail: " + strings.Join(errs, "\n"))
            }
        }
    
        // Write meta to disk.
        if err := tx.writeMeta(); err != nil {
            tx.rollback()
            return err
        }
        tx.stats.WriteTime += time.Since(startTime)
    
        // Finalize the transaction.
        tx.close()
    
        // Execute commit handlers now that the locks have been removed.
        for _, fn := range tx.commitHandlers {
            fn()
        }
    
        return nil
    }

    Transaction Commit 的全部过程,主要包括:

    1. root Bucket 开始,对访问过的 Bucket 进行转换与分裂,让进行过插入与删除操作的 B+Tree 重新达到平衡状态;
    2. 更新freeList页;
    3. 将由当前 transaction 分配的页缓存写入磁盘,
    4. metapage写入磁盘;
    • 事务原子性的实现
      • 若事务未提交时出错,因为 boltdb 的操作都是在内存中进行,不会对数据库造成影响。
      • 若是在commit的过程中出错,如写入文件失败或机器崩溃,boltdb写入文件的顺序也保证了不会造成影响:
      • 只需要保证 metapage 写入不会出错,用 checksum 和 两个版本 保证出错时会使用前一个正确的版本。
    • 版本控制的实现
        1. 每一次写事务修改已有的数据的时候,回写磁盘不会覆盖
        2. 即 BoltDB 同时保持着两个版本的视图
        3. 看上篇文章可以看到图image.png
    此处为语雀文档,点击链接查看:https://www.yuque.com/techcats/database/bolt-page-layout

    总结

    着重看 txid 、 metapage 和 mmap,这就是 BoltDB MVCC机制的核心

    来源: BoltDB 事务流程 · 语雀

  • 还在篮子里

    国内加速 GitHub 访问方法

    国内加速 GitHub 访问方法
    Q:为什么访问速度会很慢?
    A:GitHub的CDN域名遭到DNS污染。
    GitHub在中国大陆访问速度慢的问题原因有很多,但最直接和最主要的原因是GitHub的分发加速网络的域名遭到DNS污染。
    由于GitHub的加速分发CDN域名assets-cdn.github.com遭到DNS污染,导致无法连接使用GitHub的加速分发服务器,才使得中国大陆访问速度很慢。
    Q:如何解决DNS污染?
    A:通过修改Hosts解决污染问题。
    一般的DNS问题都可以通过修改Hosts文件来解决,GitHub的CDN域名被污染问题也不例外,同样可以通过修改Hosts文件解决。
    将域名解析直接指向IP地址来绕过DNS的解析,以此解决污染问题。
    解决方法:
    1、打开网站: https://www.ipaddress.com
    2、查询下面3个网址的IP
    github.com
    assets-cdn.github.com
    github.global.ssl.fastly.net
    3、修改系统 Host 加入
    vim etc/hosts140.82.114.3 github.com
    185.199.108.153 assets-cdn.github.com
    185.199.109.153 assets-cdn.github.com
    185.199.110.153 assets-cdn.github.com
    185.199.111.153 assets-cdn.github.com
    199.232.5.194 github.global.ssl.fastly.net
    4、刷新 DNS 缓存,就可以了
    mac
    sudo killall -HUP mDNSResponder && echo macOS DNS Cache Reset
    centOS
    nscd -i hosts
    service nscd restart

    来源: 国内加速 GitHub 访问方法

  • 还在篮子里

    How boltdb Write its Data? · 语雀

    How boltdb Write its Data?

    A Ha!

    Here’re three questions during reading the source code of BoltDB. I’ll explain our testing procedure to dive into the core of BoltDB writing machanism?

    Code link: yhyddr/quicksilver

    First

    • First, mentor asked me :”Did BoltDB have a temporary file when starting a read/write transaction”

    Following the quickstart, all data is stored in a file on disk.

    so have this question , what happened when we store or view data on this file.

    mentor meaned that some methods to change file like tempory file method ,have a copy file to update. When some operations end , it file would replace origin file to realize store/commit.

    Let’s check if boltdb use this method.

    FileSystem Notify

    I heard it from my mentor about how to watch files or diretories by simple go file.

    use this package fsnotify/fsnotify on github.

    I write a small go binary file to log current directory’s file’s change.

    package main
    
    import (
      "log"
    
      "github.com/fsnotify/fsnotify"
    )
    
    func main() {
      hang := make(chan bool)
      watcher, err := fsnotify.NewWatcher()
      if err != nil {
        log.Fatal(err)
      }
    
      watcher.Add("./")
    
      go func() {
        for {
          select {
          case e := <-watcher.Events:
            log.Println(e.Op.String(), e.Name)
          case err := <-watcher.Errors:
            log.Println(err)
          }
        }
      }()
    
      <-hang
    }
    

    use upon code and go build then we have fsnotify (I rename my binary file this name)

    it could tell us what happened on current directory.If you know how to wirte go code , you could change it to watch any file or directory you like by yoursely.

    I’ll show how it works

    Update Boltdb file

    then we need write code to store some data.This way we update boltdb file and know if there has a tempory file to replace origin file. Because it’s obviously that boltdb as simple kv database seems do not have access on system directory but just current directory and the database file.

    We Write code below to insert data :

    package main
    
    import (
      "encoding/binary"
      "log"
      "os"
      "time"
    
      bolt "go.etcd.io/bbolt"
    )
    
    var InsertNum int = 15000
    
    func main() {
      hang := make(chan bool)
      db, err := bolt.Open("./data.db", 0600, nil)
      if err != nil {
        log.Fatal(err)
      }
    
      go func() {
        times := time.Now()
        for {
          db.Update(func(tx *bolt.Tx) error {
            b, err := tx.CreateBucketIfNotExists([]byte("cats"))
            if err != nil {
              return err
            }
    
            num, err := b.NextSequence()
            log.Println(num)
            byteid := make([]byte, 8)
            binary.BigEndian.PutUint64(byteid, num)
    
            b.Put(byteid, byteid)
    
            if num == InsertNum {
              log.Println(time.Now().Sub(times))
              os.Exit(0)
            }
            return nil
          })
        }
    
      }()
    
      <-hang
    }

    attention I use variable InsertNum controll how many data could be inserted.

    then we run it.(sure you need run fsnotify first.)

    image.png

    we inserted 900 data and it cost us 20s.find that it’s just write data.db file. It means that we seems to have anwser to the first question : No!

    In addition , we also could get the answer by source code.

    Second

    We have known the first question’s answer, mentor quickly asked me the second.

    • How much data or Which size could a boltdb file store ?

    we want know how much.

    let’s find it from source code. BoltDB declare these sizes on the head of go file

    image.png

    and we got the miniFillPercent and maxFillPercent are 0.1 and 1.0, in db.go we also know about boltdb page size is determined by OS page size.

    image.png

    It means a page may be used some part.

    important that maxMmanpstep = 1 <<30 is 1 GB for remapping.

    we have know there’s no temporary file that means BoltDB use memory or called Mmap to host temporary data.

    use Mmap means , your BoltDB File should not bigger than your assignable memory space.

    Third

    From upon questions , we know a lot about bolddb. But mentor still have a question:

    • in a node , author set 50% capcity limit otherwise spill it to two nodes.Do our datafile just use 50% space what a boltdb database file hold?

    image.png

    It’s because the stragecy about node spill method to controll size of node do not overflow OS page size.

    that question need we know about the disk layout of BoltDB file . I’ll detailed explanation in my next article. Of course, we know the space ratio should not over 0.5.

    and now I just give some data for you.

    I first insert 100000 data which is auto increment key and the same value.

    1 -> 100000 total 977784 b because of BoltDB store in file as bytes.

    and we found our data file use 8.5m space.

    then I insert 100000 again.

    image.png

    100000 -> 200000 and file expand to 25.2m when I insert nearly 110000th data.

    And at last file is 25.2m when hosted 200000 data.

    image.png

    来源: How boltdb Write its Data? · 语雀