Oldposts

2021-07-27-etcd应用场景 etcd Kubernetes [转载]etcd 应用场景 转载信息 作者：TonyDeng 时间：2015-10-19 原始链接：ETCD 应用场景 etcd 是什么？ 很多人对这个问题的第一反应可能是，它是一个键值存储仓库，却没有重视官方定义的后半句，用于配置共享和服务发现。 A highly-available key value store for shared configuration and service discovery. 实际上，etcd 作为一个受到 Zookeeper 和 doozer 启发而催生的项目，除了拥有与之类似的功能外，更具有以下 4 个特点。（引自etcd 官方文档） 简单： 基于 HTTP+JSON 的 API 让你可以用 CURL 命令就可以轻松使用。 安全： 可以选择 SSL 客户认证机制。 快速： 每个实例每秒支持一千次写操作。 可信： 使用 RAFT 算法充分实现了分布式。 应用场景 场景一： 服务发现 服务发现（Service Discovery）要解决的是分布式系统中最常见的问题之一，即在同一个分布式集群中的进程或服务如何才能找到对方并建立连接。 从本质上说，服务发现就是要了解集群中是否有进程在监听 udp 或者 tcp 端口，并且通过名字就可以进行查找和连接。 要解决服务发现的问题，需要下面三大支柱，缺一不可。 一个强一致性、高可用的服务存储目录。 基于 Ralf 算法的 etcd 天生就是这样一个强一致性、高可用的服务存储目录。 一种注册服务和健康服务健康状况的机制。 用户可以在 etcd 中注册服务，并且对注册的服务配置 key TTL，定时保持服务的心跳以达到监控健康状态的效果。 一种查找和连接服务的机制。 通过在 etcd 指定的主题下注册的服务业能在对应的主题下查找到。 为了确保连接，我们可以在每个服务机器上都部署一个 proxy 模式的 etcd，这样就可以确保访问 etcd 集群的服务都能够互相连接。 ...

2021-07-26-etcd入门 [[etcd]] [[Kubernetes]] etcd 入门 etcd（读作 et-see-dee）是一种开源的分布式统一键值存储，用于分布式系统或计算机集群的共享配置、服务发现和的调度协调。etcd 有助于促进更加安全的自动更新，协调向主机调度的工作，并帮助设置容器的覆盖网络。 etcd 是许多其他项目的核心组件。最值得注意的是，它是 Kubernetes 的首要数据存储，也是容器编排的实际标准系统。使用 etcd， 云原生应用可以保持更为一致的运行时间，而且在个别服务器发生故障时也能正常工作。应用从 etcd 读取数据并写入到其中；通过分散配置数据，为节点配置提供冗余和弹性。 一种键值对分布式数据库。 通过 raft 共识机制，使得 etcd 具备高可用性。 raft visualization 安装并启动 etcd 作为 k8s 的常见组建，使用 Go 开发，可以方便的构建并安装到大多数的系统中。在 Linux 中只需要一个二进制程序即可启动。 cd /tmp wget https://github.com/etcd-io/etcd/releases/download/v3.5.2/etcd-v3.5.2-linux-amd64.tar.gz tar -zxvf etcd-v3.5.2-linux-amd64.tar.gz -C etcd cd etcd/ ./etcd ## 下面就是启动日志 对于 etcd 集群的启动，通过环境变量的方式进行参数配置并启动。 官方也提供了单机集群的方案，需要用到 goreman，然后修改 Procfile 文件，把 etcd 执行路径修改为真实路径以及网络配置的变动，通过 goreman -f Procfile start 即可启动一个 etcd 集群。 使用 常见两种方式： 命令行通过 etcdctl 进行使用 程序包调用 增删改查 # put etcdctl --endpoints=$ENDPOINTS put foo "Hello World!" # get etcdctl --endpoints=$ENDPOINTS get foo etcdctl --endpoints=$ENDPOINTS --write-out="json" get foo # get keys by prefix etcdctl --endpoints=$ENDPOINTS put web1 value1 etcdctl --endpoints=$ENDPOINTS put web2 value2 etcdctl --endpoints=$ENDPOINTS put web3 value3 etcdctl --endpoints=$ENDPOINTS get web --prefix # delete keys etcdctl --endpoints=$ENDPOINTS put key myvalue etcdctl --endpoints=$ENDPOINTS del key # delete keys by prefix etcdctl --endpoints=$ENDPOINTS put k1 value1 etcdctl --endpoints=$ENDPOINTS put k2 value2 etcdctl --endpoints=$ENDPOINTS del k --prefix 事务 # use transaction # etcd transaction mode # if compare # then op # else op # commit etcdctl --endpoints=$ENDPOINTS put user1 bad etcdctl --endpoints=$ENDPOINTS txn --interactive compares: value("user1") = "bad" success requests (get, put, delete): del user1 failure requests (get, put, delete): put user1 good SUCCESS 1 # in this case, key:user1 could be delete 监测 key # watch keys # in this case,you should open two terminal # terminal 1, create a watcher, wait key:stock1 appear etcdctl --endpoints=$ENDPOINTS watch stock1 # after terminal2 put stock1,could happen: PUT stock1 1000 # terminal 2, put stock1 etcdctl --endpoints=$ENDPOINTS put stock1 1000 # watch keys by prefix # terminal 1,wait etcdctl --endpoints=$ENDPOINTS watch stock --prefix # after terminal2 put keys,could happen: PUT stock1 10 PUT stock2 20 # terminal 2,put keys etcdctl --endpoints=$ENDPOINTS put stock1 10 etcdctl --endpoints=$ENDPOINTS put stock2 20 # or watch keys history etcdctl --endpoints=$ENDPOINTS watch --rev=1 foo 租约 # lease ## create a lease etcdctl --endpoints=$ENDPOINTS lease grant 300 lease 49527f598bbfe014 granted with TTL(300s) ## key binding to lease etcdctl --endpoints=$ENDPOINTS put sample value --lease=49527f598bbfe014 etcdctl --endpoints=$ENDPOINTS get sample sample value ## if set keep-alive, than the lease could never timeout etcdctl --endpoints=$ENDPOINTS lease keep-alive 49527f598bbfe014 ## revoke lease manual etcdctl --endpoints=$ENDPOINTS lease revoke 49527f598bbfe014 lease 49527f598bbfe014 revoked # or after 300 seconds,could get null data etcdctl --endpoints=$ENDPOINTS get sample 分布式锁 # create lock # in this case,you should open two terminal # terminal 1, etcdctl --endpoints=$ENDPOINTS lock mutex1 mutex1/49527f598bbfe018 # interrupt this lock ^C # terminal 2, wait terminal 1 release lock etcdctl --endpoints=$ENDPOINTS lock mutex1 # will get lock after terminal 1 interrupt mutex1/49527f598bbfe01b 领导选举 # How to conduct leader election in etcd cluster # but i can't unserstand # tips: need think more 查看集群状态 # check cluster status ─ ~ ──────────────────────────────────────────────────────── INT ✘ ╰─ etcdctl --write-out=table --endpoints=$ENDPOINTS endpoint status +--------------------+------------------+---------+---------+-----------+------------+-----------+------------+--------------------+--------+ | ENDPOINT | ID | VERSION | DB SIZE | IS LEADER | IS LEARNER | RAFT TERM | RAFT INDEX | RAFT APPLIED INDEX | ERRORS | +--------------------+------------------+---------+---------+-----------+------------+-----------+------------+--------------------+--------+ | 172.16.242.3:2379 | 45d97e7a24a2c952 | 3.5.2 | 20 kB | false | false | 2 | 31 | 31 | | | 172.16.242.3:22379 | 1803770bd57fe7f5 | 3.5.2 | 20 kB | false | false | 2 | 31 | 31 | | | 172.16.242.3:32379 | 180470dceeda2be0 | 3.5.2 | 20 kB | true | false | 2 | 31 | 31 | | +--------------------+------------------+---------+---------+-----------+------------+-----------+------------+--------------------+--------+ ╭─ ~ ──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────── ✔ ╰─ etcdctl --write-out=table --endpoints=$ENDPOINTS endpoint health +--------------------+--------+-------------+-------+ | ENDPOINT | HEALTH | TOOK | ERROR | +--------------------+--------+-------------+-------+ | 172.16.242.3:2379 | true | 10.182483ms | | | 172.16.242.3:32379 | true | 11.098445ms | | | 172.16.242.3:22379 | true | 13.308361ms | | +--------------------+--------+-------------+-------+ 快照 # save the database # must set endpoint to one host ENDPOINTS=$HOST_1:2379 etcdctl --endpoints=$ENDPOINTS snapshot save my.db {"level":"info","ts":1646487341.2083359,"caller":"snapshot/v3_snapshot.go:119","msg":"created temporary db file","path":"my.db.part"} {"level":"info","ts":"2022-03-05T21:35:41.210+0800","caller":"clientv3/maintenance.go:200","msg":"opened snapshot stream; downloading"} {"level":"info","ts":1646487341.211041,"caller":"snapshot/v3_snapshot.go:127","msg":"fetching snapshot","endpoint":"172.16.242.3:2379"} {"level":"info","ts":"2022-03-05T21:35:42.438+0800","caller":"clientv3/maintenance.go:208","msg":"completed snapshot read; closing"} {"level":"info","ts":1646487342.465489,"caller":"snapshot/v3_snapshot.go:142","msg":"fetched snapshot","endpoint":"172.16.242.3:2379","size":"44 MB","took":1.257066939} {"level":"info","ts":1646487342.4674938,"caller":"snapshot/v3_snapshot.go:152","msg":"saved","path":"my.db"} Snapshot saved at my.db etcdctl --write-out=table --endpoints=$ENDPOINTS snapshot status my.db +----------+----------+------------+------------+ | HASH | REVISION | TOTAL KEYS | TOTAL SIZE | +----------+----------+------------+------------+ | 79ec4d35 | 18024 | 36026 | 44 MB | +----------+----------+------------+------------+ # in this case, I found keys is too much and revision too high. Because I use `ectdctl --endpoints=$ENDPOINTS check perf`.Every perfomance check could raise too much keys and revision. 合并v2到v3 # how to migrate etcd from v2 to v3 # let it pass # write key in etcd version 2 store export ETCDCTL_API=2 etcdctl --endpoints=http://$ENDPOINT set foo bar # read key in etcd v2 etcdctl --endpoints=$ENDPOINTS --output="json" get foo # stop etcd node to migrate, one by one # migrate v2 data export ETCDCTL_API=3 etcdctl --endpoints=$ENDPOINT migrate --data-dir="default.etcd" --wal-dir="default.etcd/member/wal" # restart etcd node after migrate, one by one # confirm that the key got migrated etcdctl --endpoints=$ENDPOINTS get /foo 增减集群节点 # deal with membership https://etcd.io/docs/v3.5/tutorials/how-to-deal-with-membership/ 权限、用户与角色 # create role etcdctl --endpoints=${ENDPOINTS} role add root Role root created ## can be grant to every key,need use / to replace foo etcdctl --endpoints=${ENDPOINTS} role grant-permission root readwrite foo Role root updated etcdctl --endpoints=${ENDPOINTS} role get root Role root KV Read: foo KV Write: foo # create user and grant role ## set password is 123 etcdctl --endpoints=${ENDPOINTS} user add root Password of root: Type password of root again for confirmation: User root created etcdctl --endpoints=${ENDPOINTS} user grant-role root root Role root is granted to user root etcdctl --endpoints=${ENDPOINTS} user get root User: root Roles: root # enable auth etcdctl --endpoints=${ENDPOINTS} auth enable Authentication Enabled # now all client requests go through auth etcdctl --endpoints=${ENDPOINTS} --user=root:123 put foo bar OK etcdctl --endpoints=${ENDPOINTS} get foo {"level":"warn","ts":"2022-03-05T22:19:54.108+0800","caller":"clientv3/retry_interceptor.go:62","msg":"retrying of unary invoker failed","target":"endpoint://client-7b0e89ed-5f03-4f6d-b44c-ce59520a4c07/172.16.242.3:2379","attempt":0,"error":"rpc error: code = InvalidArgument desc = etcdserver: user name is empty"} Error: etcdserver: user name is empty etcdctl --endpoints=${ENDPOINTS} --user=root:123 get foo foo bar etcdctl --endpoints=${ENDPOINTS} --user=root:123 get foo1 tips: root 在内部可能有独立定义（或者uid很高），除非先关闭auth，否则无法直接删除该用户 ...

2021-07-25-共识机制 Block Chain 区块链共识机制 由于加密货币多数采用去中心化的区块链设计，节点是各处分散且平行的，所以必须设计一套制度，来维护系统的运作顺序与公平性，统一区块链的版本，并奖励提供资源维护区块链的使用者，以及惩罚恶意的危害者。这样的制度，必须依赖某种方式来证明，是由谁取得了一个区块链的打包权（或称记账权），并且可以获取打包这一个区块的奖励；又或者是谁意图进行危害，就会获得一定的惩罚，这就是共识机制。 PoW 工作量证明 代表：比特币 一般要求用户进行一些耗时适当的复杂运算，并且答案能被服务方快速验算，以此耗用的时间、设备与能源做为担保成本，以确保服务与资源是被真正的需求所使用。 由于加密货币多由区块链所建构，而区块链本来就要依赖散列函数来做为资料正确无误的担保，所以在加密货币上使用工作量证明，是非常简明的设计。由分散在各处的计算机，竞赛谁能最早找出，搭配原本要打包的资料的穷举猜测值（nonce），谁就等同获得该区块的打包权（记账权）。此猜测值被找出后，与资料、散列值一起打包成块后广播，经多数节点确认与承认，打包者就能获得打包该区块所提供的奖励。[3]一般采用工作量证明的加密货币，好比比特币，会设置成随着参与竞赛的算力增减，而调整找寻猜测值的难度，以维持合理的运作速度。 优点 架构简明扼要、有效可靠。 由于要获得多数节点承认，那攻击者必须投入超过总体一半的运算量（51%攻击），才能保证篡改结果。这使得攻击成功的成本变得非常高昂，难以实现。 某种程度上是公平的，你投入越多的算力，你获得打包权的几率也等比增加。 缺点 非常浪费能源。投入在一种加密货币上的能源，可能会超过一个小型国家的总使用量。 由于加密货币在世界上已成为一种投资标的，所以技术人员开发出了由ASIC组成的特制计算设备（矿机），垄断算力。这与加密货币的去中心化思想背道而驰。 也因此，后期开发的加密货币有针对抗ASIC的算法设计，例如以太坊采用的Ethash（Dagger-Hashimoto）算法。 后期开发的加密货币陆续使用了POS机制（例如以太坊）或DPOS机制（例如比特股﹑EOS）。 从长远来看，POW不太适合作为共识机制。 PoS 权益证明 代表：以太坊 权益证明的问题是，大多数的持币人没有足够的专业知识或足够的预算，无法达到高性能节点所需的计算机硬件和软件要求，难以产生区块，因此持币量大的少数账户便能支配区块的生成，获取大部分的奖励。 代理持有量证明（又称代理权益证明，英语：Delegated Proof of Stake或DPOS）的出现旨在解决以上的问题。DPOS与POS原理相同，主要分别在于每位持币人有权投票选出代理节点，由得票最多的若干节点负责生成区块。DPOS引入了民主机制，持币量少的人亦能参与投票，决定之后能生成区块获取奖励的节点，以实现去中心化的目的。 优点：通过缩小选举节点的数量，能够在不增加计算资源的前提下有效减少网络压力。 缺点：选举固定数量的节点未必能完全实现去中心化；如参选的节点数量少或者投票人数低，选出的节点代点代表性不足。 DPoS 股份授权证明 代表：EOS Proof-of-Spacetime (PoSt) 时空证明 代表：filecoin 用空间保持的时间作为算力，获得打包权从而出块。

2021-07-24-各种排序 Algorithm 排序算法 排序算法有很多种，在大部分时候只需要调用语言中封装好的排序算法（大部分都是快速排序）即可，但这些排序方法都可以尝试理解下，也是算法的基础，下文不会给出每个算法的具体实现，而只给出理解总结以及相关的链接。 冒泡排序：多次遍历，每次遍历交换相邻元素 选择排序：多次遍历，每次寻找最小值然后交换到左侧 插入排序：多次遍历，取出某个数，和它左侧的数分别比较，插入到合适的位置 合并排序：多次排序，每次对定量且相邻的元素进行排序，也是分而治之 计数排序：适用于大量且分散在指定范围内的元素，例如10000个数据，但是每个数据都在0-10之间，这样只需要做11次计数就可以完成排序 桶排序：类似于计数排序，只是多个计数整合成一个桶，桶内的排序任务就减轻了很多 基数排序：类似于桶排序，但根据键值的每位数字来分配桶，对于十进制来说无论多少数据都是十个桶（0-9），但需要多次的排序 随机快速排序：随机获得基准值，然后和快速排序一致 快速排序：寻找一个基准值，然后分而治之，最后直接顺序完成 func quickSort(arr []int) []int { return _quickSort(arr, 0, len(arr)-1) } func _quickSort(arr []int, left, right int) []int { if left < right { partitionIndex := partition(arr, left, right) _quickSort(arr, left, partitionIndex-1) _quickSort(arr, partitionIndex+1, right) } return arr } func partition(arr []int, left, right int) int { pivot := left index := pivot + 1 for i := index; i <= right; i++ { if arr[i] < arr[pivot] { swap(arr, i, index) index += 1 } } swap(arr, pivot, index-1) return index - 1 } func swap(arr []int, i, j int) { arr[i], arr[j] = arr[j], arr[i] } 参考链接 visualgo.Net/Sort 快速排序 十大经典排序算法 算法导论-排序（二）快速排序、随机化快速排序

2021-07-21-Redis专题：万字长文详解持久化原理 database Redis [转载]Redis 专题：万字长文详解持久化原理 转载信息 作者：码路印记 时间：2021-02-13 原始链接：Redis 专题：万字长文详解持久化原理 本文将从以下几个方面介绍 Redis 持久化机制： 写在前面 本文从整体上详细介绍 Redis 的两种持久化方式，包含工作原理、持久化流程及实践策略，以及背后的一些理论知识。上一篇文章仅介绍了 RDB 持久化，但是 Redis 持久化是一个整体，单独介绍不成体系，故重新整理。 Redis 是一个内存数据库，所有的数据将保存在内存中，这与传统的 MySQL、Oracle、SqlServer 等关系型数据库直接把数据保存到硬盘相比，Redis 的读写效率非常高。但是保存在内存中也有一个很大的缺陷，一旦断电或者宕机，内存数据库中的内容将会全部丢失。为了弥补这一缺陷，Redis 提供了把内存数据持久化到硬盘文件，以及通过备份文件来恢复数据的功能，即 Redis 持久化机制。 Redis 支持两种方式的持久化：RDB 快照和 AOF。 RDB 持久化 RDB 快照用官方的话来说：RDB 持久化方案是按照指定时间间隔对你的数据集生成的时间点快照（point-to-time snapshot）。它以紧缩的二进制文件保存 Redis 数据库某一时刻所有数据对象的内存快照，可用于 Redis 的数据备份、转移与恢复。到目前为止，仍是官方的默认支持方案。 RDB 工作原理 既然说 RDB 是 Redis 中数据集的时间点快照，那我们先简单了解一下 Redis 内的数据对象在内存中是如何存储与组织的。 默认情况下，Redis 中有 16 个数据库，编号从 0-15，每个 Redis 数据库使用一个 redisDb 对象来表示，redisDb 使用 hashtable 存储 K-V 对象。为方便理解，我以其中一个 db 为例绘制 Redis 内部数据的存储结构示意图。 ...

2021-07-20-Redis为什么变慢了？一文讲透如何排查Redis性能问题 database Redis Redis为什么变慢了？一文讲透如何排查Redis性能问题 因为版权原因，这里只贴链接。 Redis为什么变慢了？一文讲透如何排查Redis性能问题 | 万字长文

2021-07-19-MySQL索引原理及慢查询优化 database MySQL [转载]MySQL 索引原理及慢查询优化 转载信息 作者：NeverMore 原始链接：MySQL 索引原理及慢查询优化 时间：2014 年 06 月 30 日 其他: 6290 字 13 分钟阅读 背景 MySQL 凭借着出色的性能、低廉的成本、丰富的资源，已经成为绝大多数互联网公司的首选关系型数据库。虽然性能出色，但所谓“好马配好鞍”，如何能够更好的使用它，已经成为开发工程师的必修课，我们经常会从职位描述上看到诸如“精通 MySQL”、“SQL 语句优化”、“了解数据库原理”等要求。我们知道一般的应用系统，读写比例在 10:1 左右，而且插入操作和一般的更新操作很少出现性能问题，遇到最多的，也是最容易出问题的，还是一些复杂的查询操作，所以查询语句的优化显然是重中之重。 本人从 2013 年 7 月份起，一直在美团核心业务系统部做慢查询的优化工作，共计十余个系统，累计解决和积累了上百个慢查询案例。随着业务的复杂性提升，遇到的问题千奇百怪，五花八门，匪夷所思。本文旨在以开发工程师的角度来解释数据库索引的原理和如何优化慢查询。 一个慢查询引发的思考 select count(*) from task where status=2 and operator_id=20839 and operate_time>1371169729 and operate_time<1371174603 and type=2; 系统使用者反应有一个功能越来越慢，于是工程师找到了上面的 SQL。 并且兴致冲冲的找到了我，“这个 SQL 需要优化，给我把每个字段都加上索引”。 我很惊讶，问道：“为什么需要每个字段都加上索引？” “把查询的字段都加上索引会更快”，工程师信心满满。 “这种情况完全可以建一个联合索引，因为是最左前缀匹配，所以 operate_time 需要放到最后，而且还需要把其他相关的查询都拿来，需要做一个综合评估。” “联合索引？最左前缀匹配？综合评估？”工程师不禁陷入了沉思。 多数情况下，我们知道索引能够提高查询效率，但应该如何建立索引？索引的顺序如何？许多人却只知道大概。其实理解这些概念并不难，而且索引的原理远没有想象的那么复杂。 MySQL 索引原理 索引目的 索引的目的在于提高查询效率，可以类比字典，如果要查“MySQL”这个单词，我们肯定需要定位到 m 字母，然后从下往下找到 y 字母，再找到剩下的 sql。如果没有索引，那么你可能需要把所有单词看一遍才能找到你想要的，如果我想找到 m 开头的单词呢？或者 ze 开头的单词呢？是不是觉得如果没有索引，这个事情根本无法完成？ ...

2021-07-18-树 Data Structure 各种树 [TOC] 二叉查找树 BST 二叉查找树（英语：Binary Search Tree），也称为二叉查找树、有序二叉树（ordered binary tree）或排序二叉树（sorted binary tree），是指一棵空树或者具有下列性质的二叉树： 若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值； 若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值； 任意节点的左、右子树也分别为二叉查找树； 二叉查找树相比于其他数据结构的优势在于查找、插入的时间复杂度较低。为{\displaystyle O(\log n)}O(\log n)。二叉查找树是基础性数据结构，用于构建更为抽象的数据结构，如集合、多重集、关联数组等。 二叉查找树的查找过程和次优二叉树类似，通常采取二叉链表作为二叉查找树的存储结构。中序遍历二叉查找树可得到一个关键字的有序序列，一个无序序列可以透过建构一棵二叉查找树变成一个有序序列，建构树的过程即为对无序序列进行查找的过程。每次插入的新的结点都是二叉查找树上新的叶子结点，在进行插入操作时，不必移动其它结点，只需改动某个结点的指针，由空变为非空即可。搜索、插入、删除的复杂度等于树高，期望{\displaystyle O(\log n)}O(\log n)，最坏退化为偏斜二叉树{\displaystyle O(n)}O(n)。对于可能形成偏斜二叉树的问题可以经由树高改良后的平衡树将搜索、插入、删除的时间复杂度都维持在{\displaystyle O(\log n)}O(\log n)，如AVL树、红黑树等。 二叉搜索树 B+ 树 B+ 树是一种树数据结构，通常用于数据库和操作系统的文件系统中。B+ 树的特点是能够保持数据稳定有序，其插入与修改拥有较稳定的对数时间复杂度。B+ 树元素自底向上插入，这与二叉树恰好相反。 B+ 树在节点访问时间远远超过节点内部访问时间的时候，比可作为替代的实现有着实在的优势。这通常在多数节点在次级存储比如硬盘中的时候出现。通过最大化在每个内部节点内的子节点的数目减少树的高度，平衡操作不经常发生，而且效率增加了。这种价值得以确立通常需要每个节点在次级存储中占据完整的磁盘块或近似的大小。 B+ 背后的想法是内部节点可以有在预定范围内的可变量目的子节点。因此，B+ 树不需要像其他自平衡二叉查找树那样经常的重新平衡。对于特定的实现在子节点数目上的低和高边界是固定的。例如，在 2-3 B 树（常简称为2-3 树）中，每个内部节点只可能有 2 或 3 个子节点。如果节点有无效数目的子节点则被当作处于违规状态。 B+树 平衡二叉树、B树、B+树、B*树 理解其中一种你就都明白了

2021-07-17-slice是完美的引用传递吗 [[Go]] slice是完美的引用传递吗 发现问题 首先说明go中只有值传递，这里的引用传递只是一个相对概念。 问题起源于新生群的讨论，大家说到 go 时有人问 slice 是不是指针传递，我说是，有位学长说他曾经写过一段和 slice 有关的代码，很怪，怀疑不是引用传递。故事就这样开始了。 代码如下： func main() { sliceA := []int{1, 2, 3, 4, 5} fmt.Println(sliceA) changeSlice(sliceA) fmt.Println(sliceA) } func changeSlice(slicePass []int) { slicePass = slicePass[0:3] } // Output /* [1 2 3 4 5] [1 2 3 4 5] */ 看完这串代码我也惊了，在我曾经的想法里，slice 是会变的，但在这里却还是原样输出。我怀疑是 slice 的问题，于是上网搜寻信息，原来已经有人碰到同样的坑了。 过程有点艰难，看到一些说是 slice 扩容新指针导致的，又有一些说是 len 未被改变导致的，于是研究了一会儿才整理起来。 一些思考 main 中的 slice 没变化有两种情况 cap 够，slice 没扩容 slice 只是引用类型而非“完美”的引用传递。slice 本身是一个结构体 // runtime/slice.go type slice struct { array unsafe.Pointer len int cap int } 底层数组的确用指针表示，但是 slice 中的 len 与 cap 却是 int 类型。 ...

2021-07-08-Linux 标准退出状态码 Linux Linux 标准退出状态码 在Linux中，当程序中断后，会返回一个退出码。如果是正常退出，那么这个码将会是零，任何非零的情况都意味着有错误产生。 退出码在我们自己的程序中是可以任意选择并指定的，但有些约定俗成的规矩，部分退出码有明确的含义，尽量不要使用。 我们一般在shell里通过 exit number，像是 exit 42，的方式指定退出码，在标准的输出时是隐藏的，可以通过 echo $? 的方式查询上一条指令的运行状态，这也常常作用在 shell 脚本中对某个指令运行状况的检测。 特殊的退出码 General Error: 1 This is the most used exit code and should be used as a catch-all value for miscellaneous errors. Misuse of Shell Built-in: 2 Exit code 2 signifies invalid usage of some shell built-in command. Examples of built-in commands include alias, echo, and printf. Cannot Execute: 126 In this case, the command invoked can’t be executed. This will most likely occur when there’s a permission problem or the command isn’t executable. Command Not Found: 127 A command couldn’t be found. This may happen, for example, because there was a typo or an issue with our PATH. Invalid Argument To Exit: 128 The exit command only takes a positive integer as its argument. This means any negative, fractional, or non-numeric values aren’t allowed. Fatal Error Signal ‘n‘: 128+n In Linux, programs might send one of 33 different signals. When a program terminates after receiving one of these signals, it will return an error code equal to 128 + signal-number. For example, when we terminate a program by typing Control-C, we’re effectively sending it a SIGINT signal. This signal has a value of 2, therefore, the program will stop its execution and return an exit code with a value 128 + 2 = 130. Exit Status Out of Range: 255 Depending on our shell, exit code 255 might mean that the returned exit code is outside of the 0-255 range. 不要使用255以上的退出码。