索引

1 前言随着得物业务规模的一直减少，举荐业务也越来越简单，对举荐零碎也提出了更高的要求。咱们于2022年下半年启动了DGraph的研发，DGraph是一个C++我的项目，指标是打造一个高效易用的举荐引擎。举荐场景的特点是表多、数据更新频繁、单次查问会波及多张表。理解这些特点，对于举荐引擎的设计十分重要。通过浏览本文，心愿能对大家理解举荐引擎有肯定帮忙。为什么叫DGraph？因为举荐场景次要是用x2i(KVV)表举荐为主，而x2i数据是图(Graph)的边，所以咱们给得物的举荐引擎取名DGraph。 2 注释2.1 整体架构DGraph能够划分为索引层&服务层。索引层实现了索引的增删改查。服务层则蕴含Graph算子框架、对外服务、Query解析、输入编码、排序框架等偏业务的模块。 图1 2.2 索引框架在DGraph外面参考图1，索引的治理被形象成5个模块：Reader 索引查问、Writer 索引写入、Compaction 增量全量合并、LifeCycle 索引生命周期治理、Schema 索引配置信息。 不同类型的索引只须要实现下面的5个类即可，不同类型的索引只须要关注索引自身的实现形式，而不须要关怀索引的治理问题，通过这种模式，索引治理模块实现了索引的形象治理，如果业务须要，能够疾速在DGraph面退出一种新的索引。 DGraph数据的治理都是按表(table)进行的(图2)，简单的索引会应用到DGraph的内存分配器D-Allocator，比方KVV/KV的增量局部 & 倒排索引 & 向量索引等。在DGraph所有数据更新都是DUMP(耗时)->索引构建(耗时)->引擎更新(图3)，索引平台会依据DGraph引擎的内存状况主动抉择在线更新还是分批重启更新。这种形式让DGraph引擎的索引更新速度&服务的稳定性失去了很大的晋升。 图2图3 2.3 索引数据一致性 相比订单、交易等对于数据一致性要求十分严格的场景。在搜推场景，数据不须要严格的一致性，只须要最终一致性。若一个集群有N个引擎，通过增量向集群写入一条数据，每个引擎是独立更新这条数据的，因为是独立的，所以有些机器会更新快一点，有些机器会更新慢一点，这个时间尺度在毫秒级左近，实践上在某一时刻，不同引擎上的数据是不统一的，但这对业务影响不大，因为最终这些数据会保持一致。 最终一致性这个个性十分重要，因为实现严格的一致性很简单，2PC&3PC等操作在分布式场景下，代价很高。所以事件就变得简略了很多，引擎的读写模型只须要满足最终一致性即可。这能够让咱们的零碎，更偏差于提供更高的读性能。这个前提也是DGraph目前很多设计的根因。 读写模型 举荐场景须要反对在线服务更新数据，因而引擎有读也有写，所以它也存在读写问题。另外引擎还须要对索引的空间进行治理，相似于JAVA零碎外面JVM的内存管理工作，不过引擎做的简略很多。读写问题常见的解决方案是数据加锁。数据库和大部分业务代码外面都能够这么做，这些场景加锁是解决读写问题最靠谱的抉择。然而在举荐引擎外面，对于读取的性能要求十分高，外围数据的拜访如果引入锁，会让引擎的查问性能受到很大的限度。 举荐引擎是一个读多写少的场景，因而咱们在技术路线上抉择的是无锁数据结构RCU。RCU在很多软件系统外面有利用，比方Linux 内核外面的kfifo。大部分RCU的实现都是基于硬件提供的CAS机制，反对无锁下的单写单读、单写多读、多写单读等。DGraph抉择的是单写多读+提早开释类型的无锁机制。效率上比基于CAS机制的RCU构造好一点，因为CAS尽管无锁，然而CAS会锁CPU缓存总线，这在肯定水平上会影响CPU的吞吐率。 如果简略形容DGraph的索引构造，能够了解为实现了RcuDoc(正排)、RcuRoaringBitMap(倒排)、RcuList、RcuArray、RcuList、RcuHashMap等。用举荐场景可推池来举一个例子，可推池表的存储构造能够形象成RcuHashMap<Key, RcuDoc> table。这里用RcuList来举例子，能够用来了解DGraph的RCU机制。其中MEMORY_BARRIER是为了禁止编译器对代码重排，避免乱序执行。 图4 图5 图5是删除的例子，简略讲一下，在RcuList外面，删除一个元素的时候，比方Node19，因为删除期间可能有其余线程在拜访数据，所以对List的操作和惯例的操作有些不同，首先将Node11的Next节点指向Node29，保障前面进来的线程不会拜访Node19，而后把Node19的Next指向Null，因为这个时候可能还有线程在拜访Node19，因而咱们不能立刻把Node19删除，而是把Node19放入删除队列，提早15秒之后再删除，另外删除的动作不是被动的，而是由下一个须要申请内存的操作触发，因而删除是延时且Lazy的。 数据长久化 在DGraph外面咱们构建了一个内存分配器D-Allocator(每个索引只能申请一个/可选)，用于存储增量或者倒排索引等简单数据结构。采纳了相似TcMalloc按大小分类的管理模式。D-Allocator利用Linux零碎的mmap办法每次从固定的空间申请128M ~ 1GB大小，而后再按块划分&组织。由零碎的文件同步机制保证数据的长久化。目前64位x86 CPU理论寻址空间只有48位，而在Linux下无效的地址区间是 0x00000000 00000000 ~ 0x00007FFF FFFFFFFF 和 0xFFFF8000 00000000 ~ 0xFFFFFFFF FFFFFFFF 两个地址区间。而每个地址区间都有128TB的地址空间能够应用，所以总共是256TB的可用空间。在Linux下，堆的增长方向是从下往上，栈的增长方向是从上往下，为了尽可能保证系统运行的安全性，咱们把0x0000 1000 0000 0000 到 0x0000 6fff ffff ffff调配给索引空间，一共96TB，每个内存分配器能够最大应用100GB空间。为了方便管理，咱们引入了表keyID，用于固定地址寻址，表地址 = 0x0000 1000 0000 0000 + keyId * 100GB, 引擎治理平台会对立治理每个集群的keyId，偶数位调配给表，奇数位保留作为表切换时应用。keyId 0 - 600 调配给集群独享表，keyId 600-960调配给全局表。因而单个集群能够最多加载300个独享表+最多180共享表(备注：不是所有表都须要D-Allocator，目前没有增量的KVV/KV表不受这个规定限度)。 ...

作者：杨涛涛 资深数据库专家，专研 MySQL 十余年。善于 MySQL、PostgreSQL、MongoDB 等开源数据库相干的备份复原、SQL 调优、监控运维、高可用架构设计等。目前任职于爱可生，为各大运营商及银行金融企业提供 MySQL 相干技术支持、MySQL 相干课程培训等工作。 本文起源：原创投稿 *爱可生开源社区出品，原创内容未经受权不得随便应用，转载请分割小编并注明起源。 OceanBase 从索引和主表的关系来讲，有两种索引：部分索引和全局索引。 部分索引等价于咱们通常说的本地索引，与主表的数据结构放弃一对一的关系。部分索引没有独自分区的概念，一般来讲，主表的分区形式决定部分索引的分区形式，也就是说假如主表有10个分区，那么对于每个分区来讲，都有一个对应的部分索引。 全局索引区别于部分索引，与主表数据结构放弃一对多、多对多的关系，全局索引次要利用于分区表。对于分区表来讲，一个非分区全局索引对应主表的多个分区；一个分区全局索引也对应主表的多个分区，同时主表每个分区也对应多个全局索引的索引分区。 引入全局索引的指标就是补救部分索引在数据过滤上的一些有余，比方防止分区表的全分区扫描，把过滤条件下压到匹配的表分区中。 针对查问过滤条件来讲，部分索引和全局索引的简略应用场景总结如下：1. 带分区键的查问，适宜用部分索引。这也是分区表设计的初衷，以过滤条件来反推分区表的设计。比方语句：select * from p1 where id = 9; id 为分区键，能够间接定位到具体的表分区partitions(p9)，仅需扫描一行记录。 <mysql:5.6.25:ytt>explain select * from p1 where id = 9\G*************************** 1. row ***************************Query Plan: ==================================|ID|OPERATOR |NAME|EST. ROWS|COST|----------------------------------|0 |TABLE GET|p1 |1 |46 |==================================Outputs & filters: -------------------------------------0 - output([p1.id], [p1.r1], [p1.r2]), filter(nil), access([p1.id], [p1.r1], [p1.r2]), partitions(p9)1 row in set (0.005 sec)2. 不带分区键的查问有两个思考方向，次要在于是否克服全局索引的毛病：全局索引势必会带来查问的分布式执行！（1）表的并发写不大，能够思考用全局索引。 （2）表的并发写很大，用全局索引与否就有待商讨， 能够依据以后的业务模型做个压力测试，取一个折中点。 ...

作者： 京东物流 康睿 1.重建索引需要背景1.1 集群版本升级ES版本兼容性同一大版本范畴内降级，索引读写兼容不同大版本升级，索引读写不兼容，须要重建索引 1.2 集群迁徙集群索引迁徙集群迁徙，索引服务不停机，数据提前迁徙1.3 索引分片数量调整分片数量变更原有分片数量太少，重建变多原有分片数量太多，重建变少ES索引分片，一旦创立，原索引是不能批改分片数量的 1.4 索引文档构造变更文档构造变更字段类型变更，已有索引字段类型是不能够批改的字段属性变更，历史数据的字段属性是不会刷新的文档对象构造变更 2.罕用重建索引形式2.1 Reindex初识索引重建阐明重建是创立新索引，原有索引保留原有索引_source必须开启，否则找不到原始数据索引重建倡议，严格业务场景，指标索引mapping构造倡议先创立好，不应用es动静揣测字段类型的形式。POST_reindex{  "source": {    "index": "原始索引" },  "dest": {    "index": "新指标索引" }}2.2 Url参数解读URL参数refresh，指标索引是否立刻刷新waif\_for\_active_shards, 重建索引分片响应设置Scroll, 快照查问工夫slicing, 重建并行任务切片Max_docs , 单次最大数据量，条数requests\_per\_second . 单次执行的重建文档数据量2.3 Request body参数解读申请参数confilicts, 索引数据抵触如何解决，间接笼罩还是中断source: 原索引配置信息dest，新索引配置信息script，脚本解决，批改原索引信息后再写入新索引 2.4 Response 参数解读响应参数胜利数更新数新增数失败数 2.5 重建索引工作管控工作管控必要性重建索引是一个异步工作，由ES后盾过程实现调度执行，集群可能有并行其余异步工作，有时须要中断进行或查看进度工作管控API_tasks，服务端API 3.高级索引重建形式3.1 单秒数据量阈值管制单秒数据量管制requests\_per\_second默认1000，设置-1则不限度生产重建时，倡议管制范畴500-1000左右管制重建速度，避免集群霎时IO过大 3.2人工切片数据切片利用人为指定切片数量，并行任务用于升高索引redinx速度POST_reindex{  "source": {    "index": "my-index-000001",    "slice": {      "id": 0,  // 执行下标，从0开始，即0切第一批数据做迁徙，1切第二批数据做迁徙      "max": 2  // 切分分片数   } },  "dest": {    "index": "my-new-index-000001" }} ...

作者：京东物流 郎元辉背景Promise时效控单零碎作为时效域的控制系统，在用户下单前、下单后等多个节点均提供服务，是用户下单黄金链路上的重要节点；控单零碎次要逻辑是针对用户申请从规定库中找出符合条件的最优规定，并将该规定的时效管制后果返回客户端，比方因为长期疫情等起因针对仓、配、商家、客户四级地址等不同维度进行精密粒度的时效管制。 该零碎也是Promise侧并发量最大的零碎，双11顶峰集群流量TPS在百万级别，对系统的性能要求十分高，SLA要求在5ms以内，因而对海量申请在规定库(几十万)中如何疾速正确匹配规定是该零碎的技术挑战点。 奢侈的解决方案依照奢侈的思维，在工程建设上，通过异步形式将规定库逐行缓存到Redis，Key为规定条件,Value为规定对应后果；当用户申请过去时，对申请Request(a,b,c,d..)中的参数做全组合，依据全组合出的Key尝试找出所有可能命中的规定，再从中筛选出最优的规定。如下图所示 该计划面临的问题是全组合的工夫复杂度是2n,n≈12；算法的工夫复杂度高且算法稳定性差**，最差状况一次申请须要4096次计算和读取操作。当然在工程上咱们能够应用本地缓存做一些优化，然而无奈解决最基本的性能问题。架构简图如下所示： ![]() 新的解决方案下面计划是从行的角度对待匹配定位的，可能命中的行的每一列必然也是符合条件的，这外面存在某种隐约的内在联系。是否反过来思考这个问题，为此咱们尝试进行新的计划，当然架构简图仍然如上图所示，外围优化的是命中算法。 新的计划整体采纳列的倒排索引和倒排索引位运算的形式，使得计算复杂度由原来的2n降至n**，且算法稳定性有十分好的保障。其中列的倒排索引是对每列的值和所散布的行ID(即Posting List)建设KV关系，倒排索引位运算是对符合条件的列倒排索引进行列间的位运算，即通过联结查问以便疾速找到符合条件的规定行。 算法具体设计1.预计算生成列的倒排索引和位图通过对每列的值进行分组合并生成Posting List，建设列值和Posting List的KV关系。以下图为例,列A可生成的倒排索引为：301={1},201={2,3,4,5}等，须要阐明的一点，空值也是一种候选项，也须要生成KV关系，如nil={7}。 2.生成列的倒排索引对应位图将步骤1的倒排索引转成成位图，不便后续的位图计算，转换规则为行ID对应位图的下标位（步骤1、2能够合并操作）。 3.依据用户申请查找列位图，通过位图计算生成候选规定集将用户申请中的入参作为Key，查找符合条件的位图，对每一列进行列内和空值做||运算，最初列间位图做&运算，失去的后果是候选规定集，如下图所示： ![]() 4.从候选规定库中，依据业务优先级排序，查找最优的规定以候选规定为基点，依照业务优先级排序，进行逐级位运算&，当遍历完或位运算为0时，找到最初不为空的即为最优规定，该过程是从候选规定库逐步放大最优范畴的过程。须要阐明某列当用户申请位图不存在时，须要应用对应的空位图进行参加，以B列为例，入参B_1102不存在，须要应用B_nil参加&。 复杂度剖析通过下面的例子咱们能够看到，在工夫复杂度方面查找候选规定集时，进行一轮||运算，一轮&运算；在查找最优规定时进行一轮&运算，所以整体复杂度是3n≈n。 在空间复杂度方面，相比原来的行式存储，倒排索引的存储形式，每列都须要存储行ID，相当于多了 (n-1)*Posting List存储空间，当然这是粗略计算，因为实际上行ID的存储最终转换为位图存储，在空间上有十分大的压缩空间。 工程问题-压缩位图如果倒排索引位图十分稠密，零碎会存在十分大的空间节约。咱们举一个极其case，若千万规定库中命中的行ID是第1000万位，依照传统形式BitSet进行存储，须要耗费1.2MB空间，在内存中占用存在重大节约，有没有压缩优化计划，在RoaringBitMap压缩位图计划中咱们找到，雷同场景在压缩位图形式下仅占144bytes；即便在1000万的位图空间，咱们随机存储1万个值，两者比也是在31K vs 2MB，近100倍的差距，总的来说RoaringBitMap压缩率十分大。 RoaringBitMap实质上是将大块的bitmap拆分成各个小块，其中每个小块在须要存储数据的时候才会存在，所以当进行交加或并集运算的时候，RoaringBitMap只须要去计算存在的块而不须要像bitmap那样对整个大块进行计算，既做到了压缩的存储又做到计算性能的晋升。 以下图821697800为例，对应的16进制数为30FA1D08， 其中高16 位为30FA，低16位为1D08。先用二分查找从一级索引（即Container Array）中找到数值为 30FA 的容器，该容器是一个Bitmap容器,而后在该容器查找低16位的数值1D08，即十进制下7432，在Bitmap中找到相应的地位，将其置为1即可。 实用场景剖析回顾下面的设计方案咱们能够看到，这种形式仅实用于PostingList简略如行ID的模式，如果是简单对象就不适宜用位图来存储。另外仅实用于等值查问，不适用于like、in的范畴查问，为什么有这种局限性？因为这种形式依赖于搜寻条件的空间，在计划中咱们将值的条件作为搜寻的Key，值的条件空间心愿尽可能是一个无限的、不便穷举的、小的空间。而范畴查问导致这个空间变成难以穷举、近乎有限扩张的、所以不实用。 其余优化形式除了应用位运算的形式对倒排索引减速，思考到Posting List的有序性，还有其余的形式比方应用跳表、Hash表等形式，以ES中采纳的跳表为例，进行&运算理论就是在查找两个有序Posting List公共局部，以互相二分查找的模式，将工夫复杂度管制在log(n)的级别。 具体参见工业界如何利用跳表、哈希表、位图进行倒排索引减速？

索引设计—高并发场景微服务实战（六）你好，我是程序员Alan. 我在上一篇文章《 表结构设计—高并发场景微服务实战（五）》中，具体的写了如何抉择适合的类型创立一张表，但表结构设计只是设计数据库最后的环节之一，咱们还短少数据库设计中最为重要的一个环节——索引设计，只有正确设计索引，业务能力达到上线的初步规范。 索引如果开展来讲有很多须要关注的中央，例如索引设计、业务利用与调优等等，本篇文章我会重点讲一下索引设计相干常识。 索引是什么？索引是一门排序的艺术，索引是晋升查问速度的一种数据结构。无效的设计并创立索引，会晋升数据库系统的整体性能。索引之所以能晋升查问速度，在于它在插入时对数据进行了排序（不言而喻，它的毛病是影响插入或者更新的性能）。索引是对记录进行排序。 在目前的 MySQL 8.0 版本中，InnoDB 存储引擎反对的索引有 B+ 树索引、全文索引、R 树索引。这里咱们先关注应用最为宽泛的 B+ 树索引。 B+树索引构造B+ 树索引是数据库系统中最为常见的一种索引数据结构，简直所有的关系型数据库都反对它。 那你晓得为什么关系型数据库都热衷反对 B+树索引吗？因为B+数是目前为止排序最有效率的数据结构。 B+树索引的特点是： 基于磁盘的均衡树，但树十分矮，通常为 3~4 层，能寄存千万到上亿的排序数据。树矮意味着拜访效率高，从千万或上亿数据里查问一条数据，只用 3、4 次 I/O。 又因为当初的固态硬盘每秒能执行至多 10000 次 I/O ，所以查问一条数据，哪怕全副在磁盘上，也只须要 0.003 ~ 0.004 秒。另外，因为 B+ 树矮，在做排序时，也只须要比拟 3~4 次就能定位数据须要插入的地位，排序效率十分不错。 优化 B+ 树索引的插入性能B+ 树在插入时就对要对数据进行排序，但排序的开销其实并没有你设想得那么大，因为排序是 CPU 操作（以后一个时钟周期 CPU 能解决上亿指令）。 真正的开销在于 B+ 树索引的保护，保证数据排序，这里存在两种不同数据类型的插入状况。 数据程序（或逆序）插入： B+ 树索引的保护代价十分小，叶子节点都是从左往右进行插入，比拟典型的是自增 ID 的插入、工夫的插入（若在自增 ID 上创立索引，工夫列上创立索引，则 B+ 树插入通常是比拟快的）。数据无序插入： B+ 树为了保护排序，须要对页进行决裂、旋转等开销较大的操作，另外，即使对于固态硬盘，随机写的性能也不如程序写，所以磁盘性能也会收到较大影响。你不可能要求所有插入的数据都是有序的，因为索引的自身就是用于数据的排序，插入数据都曾经是排序的，那么你就不须要 B+ 树索引进行数据查问了。 所以对于 B+ 树索引，在 MySQL 数据库设计中，仅要求主键的索引设计为程序，比方应用自增，或应用排序的 UUID，而不必无序值做主键。 ...

9月29日，咱们邀请到开务数据库研发工程师邹彤老师与大家一起研读大咖论文，主题为《学习型索引在数据库中的利用实际》。 索引是数据库引擎的重要组成部分，在当下数据井喷式暴发的阶段，如何高效精确地在海量数据中疾速检索某条或某个特定范畴的数据就显得尤为要害。 通用的数据库系统为不同的利用需要与数据类型提供了对立的解决形式，在获得了巨大成功的同时，也暴露出肯定的局限性：因为没有联合具体利用的数据分布与工作负载，零碎往往难以保障性能的最优。 为了解决这一问题，“学习式数据库系统”成为了目前数据库畛域的钻研热点，它利用机器学习技术无效捕捉负载与数据的个性，从而对数据库系统进行优化。 学习式数据库系统当中，呈现了一个对数据库索引构造产生颠覆性影响的畛域—学习型索引构造 Learned Index。 论文重点回顾012018 年 Jeff Dean 等人在 SIGMOD 发表了《The Case for Learned Index Structures》，成为 Learned Index 的开山之作。近年来，SIGMOD 每年都有肯定数目的论文聚焦此畛域，论证学习型索引在各种存储构造中的合理性和可行性，也逐步拓宽了学习型索引的实用场景，反对增删改操作、多维索引、数据歪斜负载等。 索引是实现数据高效拜访的重要途径，有助于疾速失去键的相干信息，如地址、存在与否等。学习型索引应用机器学习中的回归模型建设起键值与数据之间的对应关系，或建设分类模型判断键值是否存在，从而利用数据分布或特色对索引构造进行优化，使索引变得专用。 在 《The Case for Learned Index Structures》论文中，咱们解读了机器学习模型如何与传统的 B 树、布隆过滤器等构造联合，优化索引构造。该文章的根本观点：索引就是模型。 Range Index（以 B-Tree 为代表）能够看做是从给定 key 到一个排序数组 position 的预测过程；Point Index（以 Hash 为代表）能够看做是从给定 key 到一个未排序数组的 position 的预测过程；Existence Index（Bloom Filter）能够看做是预测一个给定 key 是否存在。因而，索引零碎是能够用机器学习模型去替换的。 索引个别是通用构造，对数据分布不做任何假如，也没有利用利用负载中实在数据的模式。形容数据分布的连续函数，能够用来构建更无效的数据结构或算法（机器学习模型）。假如用于 Range Index 的 key 的范畴是 1-100M，那么能够用非凡的函数或者模型（间接把 key 自身当成是 offset）做索引而不用再用 B-Tree。 以 B-Tree 为例，它能够被看做 Regression Tree。B-Tree 的建设过程也是依赖数据的，只不过它不是通过梯度降落失去，而是依赖事后定义的法令。查问时给定一个 key，B-Tree 会索引到蕴含该 key 的对应范畴的叶子节点，在叶子节点内对 key 进行搜寻。 ...

索引简介索引是一种数据结构，索引的呈现是为了进步数据查问的效率。查问效率个别能够从等值查问和范畴查问两个方面进行评判。 索引的模型哈希表哈希表是一种以键 - 值（key-value）存储数据的构造，哈希的思路很简略，把值放在数组里，用一个哈希函数把 key 换算成一个确定的地位，而后把 value 放在数组的这个地位。 不同的key 值通过哈希函数的换算，会呈现同一个值的状况。解决这种状况的一种办法是，拉出一个链表。 假如，当初保护着一个身份证信息和姓名的表，须要依据身份证号查找对应的名字，这时对应的哈希索引的示意图如下所示： 哈希表因为能够疾速的找到数据的地位，等值查问效率十分高，但哈希表中的值因为不保障程序，如果要查问某个范畴内的数据，就须要把整个哈希表中的值进行扫描判断。所以哈希表这种数据结构适宜比拟适宜等值查问，不适宜范畴查问的场景。 有序数组有序数组保障了数组中的元素的值是依照肯定顺序存储的，还是下面的例子，假如身份证是不反复的，如下图：如果要查 ID_card_n2 对应的名字，用二分法就能够疾速失去，这个工夫复杂度是 O(log(N))。 同时，这个索引构造反对范畴查问。要查身份证号[ID_card_X, ID_card_Y]区间的 User，能够先用二分法找到 ID_card_X（如果不存在 ID_card_X，就找到大于 ID_card_X 的第一个 User），而后向右遍历，直到查到第一个大于 ID_card_Y 的身份证号，退出循环。 如果仅仅看查问效率，有序数组就是比拟好的数据结构了。然而，在须要更新数据的时候就比拟麻烦了，往两头插入一个记录就必须得移动前面所有的记录，老本太高。所以，有序数组索引只实用于动态存储引擎。 二叉树还是下面依据身份证号查名字的例子，如果咱们用二叉搜寻树来实现的话，示意图如下所示：二叉搜寻树的特点是：父节点左子树所有结点的值小于父节点的值，右子树所有结点的值大于父节点的值。这样如果要查 ID_card_n2 的话，依照图中的搜寻程序就是依照 UserA -> UserC -> UserF -> User2 这个门路失去。这个工夫复杂度是 O(log(N))。 当然为了维持 O(log(N)) 的查问复杂度，你就须要放弃这棵树是均衡二叉树。为了做这个保障，更新的工夫复杂度也是 O(log(N))。 树能够有二叉，也能够有多叉。多叉树就是每个节点有多个儿子，儿子之间的大小保障从左到右递增，如图： 二叉树是搜寻效率最高的，然而实际上大多数的数据库存储却并不应用二叉树。其起因是，索引不止存在内存中，还要写到磁盘上。 如果数据库存储应用二叉树，那么树的高度就比拟大，设想一下一棵 100 万节点的均衡二叉树，树高 20。一次查问可能须要拜访 20 个数据块。在机械硬盘时代，从磁盘随机读一个数据块须要 10 ms 左右的寻址工夫。也就是说，对于一个 100 万行的表，如果应用二叉树来存储，独自拜访一个行可能须要 20 个 10 ms 的工夫。 为了让一个查问尽量少地读磁盘，就必须让查问过程拜访尽量少的数据块。那么，就不应该应用二叉树，而是要应用“N 叉”树来实现缩小树的高度。这里，“N 叉”树中的“N”取决于数据块的大小。 对于雷同个数的数据构建 N 叉树索引，N 叉树中的 N 越大，那树的高度就越小，那 N 叉树中的 N 是不是越大越好呢？到底多大才最合适呢？ ...

通过后面一些对于索引设计的相干介绍与示例，置信大家曾经对索引设计这块有了一些系统的意识，那本篇来做下总结，给出一个索引设计的具体标准。 索引命名标准：单值索引，倡议以 idx_ 为结尾，字母全副小写。 例如：alter table t1 add key idx_r1(r1)；组合索引，倡议以 dx_multi_ 结尾，字母全副小写。 例如：alter table t1 add key idx_multi_1(r1,r2,r3) ;惟一索引，倡议以 udx_ 为结尾，字母全副小写；如果是多值惟一索引，则命名形式相似 udx_multi_1 等。 例如：alter table t1 add unique key udx_f1(r1)；或者alter table t1 add key udx_multi_1(r1,r2,r3);全文索引，倡议以 ft_ 结尾，字母全副小写，并且倡议默认用 ngram 插件。 例如：alter table t1 add fulltext ft_r1(r1) with parser ngram;前缀索引，倡议以 idx_ 结尾，以 _prefix 结尾。 例如： alter table t1 add key idx_r1_prefix(r1(10));函数索引，倡议以 idx_func_ 结尾，字母全副小写。 例如： alter table t1 add key idx_func_r1((mod(r1,4)));索引列抉择标准：##### 索引列的字段类型： ...

作者：姚远 MySQL ACE，华为云 MVP ，专一于 Oracle、MySQL 数据库多年，Oracle 10G 和 12C OCM，MySQL 5.6，5.7，8.0 OCP。当初鼎甲科技任技术顾问，为共事和客户提供数据库培训和技术支持服务。 本文起源：原创投稿 *爱可生开源社区出品，原创内容未经受权不得随便应用，转载请分割小编并注明起源。 当在很长的字符串的字段上创立索引时，索引会变得很大而且低效，一个解决办法是 crc32 或 md5 函数对长字符串进行哈希计算，而后在计算的后果上创立索引。在 MySQL 5.7 当前的版本，能够创立一个主动生成的字段，例如能够创立上面一个表： create table website(id int unsigned not null,web varchar(100) not null,webcrc int unsigned generated always as (crc32(web)) not null,primary key (id));向这个表中插入记录： mysql> insert into website(id,web) values(1,"https://www.scutech.com");Query OK, 1 row affected (0.07 sec)mysql> select * from website;+----+-------------------------+-----------+| id | web | webcrc |+----+-------------------------+-----------+| 1 | https://www.scutech.com | 851176738 |+----+-------------------------+-----------+1 row in set (0.00 sec)能够看到字段 webcrc 中主动生成了 web 字段的循环冗余校验值，在这个字段上创立索引，能够失去一个占用空间少，而且高效的索引。 ...

个别提到索引，大家都只关注索引的长处，一个优良的索引确实会让查问申请的效率大幅晋升、亦或是大幅晋升带有索引键进行过滤的写入申请（update、delete)效率。 不可否认，索引在这样的场景下带来微小的性能晋升，然而对于整张表的写申请来讲，则刚好相同，索引的存在会在肯定水平上升高写入申请的效率。为了保护索引数据的准实时性而让优化器基于索引做出更优化的执行打算，数据库会自动更新索引数据分布，比方带来索引页的拆分与合并等。 那索引的存在对写入申请影响到底有多大？ 也就是说，索引的数量多少与写申请效率的升高有没有一个对应的关系？这篇我用几个简略的例子看看是否失去一个明确的论断。（简略基于笔记本虚拟机测试，次要是基于 MySQL 单实例。） 我的例子次要针对四类语句：insert、update、delete、load data 。用 mysqlsh 部署一个洁净的实例：(带入端口，近程管理员，report_host 选项) MySQL Py > dba.deploy_sandbox_instance(3500,{"password":"root","allowRootFrom":"%","mysqldOptions":["report_host=debian-ytt1"]})A new MySQL sandbox instance will be created on this host in/home/ytt/mysql-sandboxes/3500...Deploying new MySQL instance...Instance localhost:3500 successfully deployed and started.Use shell.connect('root@localhost:3500') to connect to the instance.这里用来测试索引数量的表有 10 个，别离为 t1 到 t10 ，除了每张表索引数量不一样外，字段定义等都一样：t1 有 1 个索引，t2 有个 2 个，顺次类推，t10 有 10 个索引，字段类型都是整形（索引数量不蕴含主键，只蕴含二级索引）。表 t0 表构造如下： (debian-ytt1:3500)|(ytt)>show create table t0\G*************************** 1. row *************************** Table: t0Create Table: CREATE TABLE `t0` ( `id` int unsigned NOT NULL AUTO_INCREMENT, `r0` int DEFAULT NULL, `r1` int DEFAULT NULL, `r2` int DEFAULT NULL, `r3` int DEFAULT NULL, `r4` int DEFAULT NULL, `r5` int DEFAULT NULL, `r6` int DEFAULT NULL, `r7` int DEFAULT NULL, `r8` int DEFAULT NULL, `r9` int DEFAULT NULL, `r10` int DEFAULT NULL, PRIMARY KEY (`id`)) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4 COLLATE=utf8mb4_0900_ai_ci1 row in set (0.00 sec)在 shell 命令行批量建这 10 张表，并且别离加上对应的索引： ...

摘要：本文章先形容了罕用的索引，并针对B-tree和Psort两种索引具体介绍，上面给出索引的利与弊。除了索引，还介绍了分区、PCK等其余查问提速的伎俩。最初给出各种索引和调优伎俩的应用场景。本文分享自华为云社区《DWS 索引的正确“关上姿态”》，原文作者：hoholy 。 索引能干什么呢，一言以蔽之：查问减速。常见的索引有上面几种： 1. 罕用索引介绍1.1 B-btree索引B-tree存储构造示意如下： B-tree是均衡树，有序存储索引KEY值和TID；对于索引上的过滤条件，通过KEY疾速找到对应的叶子节点，而后再通过TID找到理论记录；索引中的数据以非递加的顺序存储（页之间以及页内都是这种程序），同级的数据页由双向链表连贯；反对单列索引和复合（多列）索引，多列复合索引实用于多列组合查问，B-tree索引对于查问条件的程序有要求；B-tree索引能够解决等值和范畴查问；索引页面不存储事务信息；在数据库外面举个例子，如何创立B-tree索引： 1.2 Psort索引Psort索引数据结构示意如下图所示： Psort索引自身是个列存表，蕴含索引列和tid，在索引列上部分排序，利用MIN/MAX块过滤减速TID获取；Psort索引自身有可见性，但删除、更新数据不会作用到Psort索引；Psort索引更适宜做范畴过滤，点查问速度较差；批量导入场景下无效，对于单条导入有效；横向比照B-tree、Psort如下： 1.3 非凡索引表达式索引比方对于查问“select * from test1 where lower(col1) = ‘value’;”能够建设在Lower表达式之上的索引“create index on test1(lower(col1));”，后续对于相似在lower(col1)表达式上的过滤条件，就能够间接应用这个索引减速，对于其余表达式该索引不会对查问失效。但须要留神的是：索引表达式的保护代价较为低廉，因为在每一个行被插入或更新时都得为它从新计算相应的表达式。 局部索引比方创立一个局部索引“create index idx2 on test1(ip) where not (ip > ’10.185.178.100’ and ip < ’10.185.178.200’);”，应用该缩影减速的典型查问是这样“select from test1 where ip = ’10.185.178.150’”，然而对于查问“select from test1 where ip = ’10.185.178.50’”就不能应用该索引。局部索引用来缩小索引的大小，排除掉查问不感兴趣的数据，同时能够减速索引的检索效率. 惟一索引（1）只有B-tree索引反对惟一索引； （2）当一个索引被申明为惟一时，索引中不容许多个表行具备雷同的索引值； （3）空值被视为不雷同，一个多列惟一索引将会回绝在所有索引列上具备雷同组合值的表行； （4）对于主键列会主动创立一个惟一索引； （5）唯一性查看会影响索引插入性能； 1.4 索引的利与弊索引的长处如下： 点查问提速显著，间接定位到须要的地位，缩小有效IO；多条件组合查问，过滤大量数据，放大扫描范畴；利用倒排索引减速全文检索；利用等值条件索引查问速度快的劣势，联合nestloop进步多表join效率；提供主键和唯一性束缚，满足业务须要；利用btree索引人造有序的特点，优化查问打算；索引的毛病如下： 索引页面占用额定空间，导致肯定的磁盘收缩；每次数据导入同时须要更新索引，影响导入性能；索引页面没有可见性，存在垃圾数据，须要定期清理；索引扫描性能并不总是比程序扫描性能更好，一旦优化器判断有误，可能导致查问性能反向劣化；索引须要记录XLOG，减少日志量；每个索引至多一个文件，减少备份复原、扩容等操作的代价；鉴于索引的应用是一把双刃剑，创立索引要审慎，只给有须要的列创立，不能过滤大量数据的条件列不要创立索引。除了索引能够优化查问效率，存储层还有没有其余优化伎俩呢？上面给大家再介绍几种DWS查问提速的伎俩。 2. DWS查问提速2.1 分区分区是最罕用的提速伎俩之一，而且成果很好，举荐大家联合场景多多应用。 目前反对的分区是range分区，分区反对merge、split、exchange等操作；在工夫维度或者空间维度等具备肯定数据法则的列上创立分区，分区列上的过滤条件会先做分区剪枝，缩小物理扫描量；相比拟索引，分区间接把原始数据物理划分，一旦分区剪枝失效，会极大的缩小IO；应用分区和应用索引并不抵触，能够给分区创立索引；应用分区的注意事项如下： 分区对于导入的影响是减少内存应用（内存不足时会下盘），但不产生额定的磁盘占用；应用分区肯定要留神分区列的抉择和分区数量的管制，分区过多会导致小文件问题，分区数量倡议最多不超过1600个；分区剪枝适宜范畴查问，对于点查问效率晋升无限；上面举个例子，别离创立同样数据类型的分区表和非分区表，导入雷同的数据640万条，用同样的查问会看到分区剪枝对性能进步了7倍多，筹备数据： 分区和非分区查问耗时比照，其中test1是分区表，test2是非分区表，test1的查问scan耗时6ms，test2的查问scan耗时46ms，差距7倍还多： 2.2 PCK(partial cluster key)PCK的实质就是通过排序晋升查问过滤的效率，创立表时指定PCK列，该列上的数据会部分排序，有序的数据带来更好的数据聚簇性，每个数据块的min/max等稠密索引就能更好的发挥作用，粗过滤掉大量的数据，晋升IO效率，默认状况下420万行数据部分排序。 注意事项如下： 只有列存表反对PCK，部分排序对每次导入的批量数据失效，不会做全排序；PCK更实用于范畴查问，点查场景下配套应用PCK和索引能够达到最佳成果；带PCK导入因为排序的起因会应用更多的内存，影响导入速度，须要衡量导入和查问性能；举个例子，对于查问select * from tab where col > 65，如果不应用PCK，很可能一个CU都无奈过滤掉，但如果应用了PCK，下图所示的5个CU就能过滤掉一半还多，晋升查问性能至多50%： ...

简介：近日阿里巴巴开源了其云原生容器镜像减速技术，它推出的 overlaybd 镜像格局，相比于传统的分层 tar 包文件格式，实现了基于网络的按需读取，从而使得容器能够疾速启动。 作者 |陈博 起源 | 阿里巴巴云原生公众号 近日阿里巴巴开源了其云原生容器镜像减速技术，它推出的 overlaybd 镜像格局，相比于传统的分层 tar 包文件格式，实现了基于网络的按需读取，从而使得容器能够疾速启动。 该技术计划本来是阿里云外部 DADI 我的项目的一部分， DADI 是 Data Accelerator for Disaggregated Infrastructure 的缩写，旨在为计算存储拆散架构提供各种可能的数据拜访减速技术。镜像减速是 DADI 架构在容器及云原生畛域的一次突破性尝试，该技术自 2019 年投产以来，已在线上部署了大量机器，累计启动容器次数超过 10 亿，反对了阿里巴巴团体及阿里云的多个业务线，极大进步了利用的公布和扩容效率。2020 年，团队在国内顶级会议发表了论文"DADI: Block-Level Image Service for Agile and Elastic Application Deployment. USENIX ATC'20"[1]，并随后启动了开源我的项目，打算将技术该奉献给社区，通过建设规范并打造生态，吸引更多的开发者投入到容器及云原生性能优化这个畛域上来。 背景简介随着 Kubernetes 和云原生的大暴发，容器在企业外部的大规模利用曾经越来越宽泛。部署启动快是容器的外围劣势之一，这个启动快是指本地镜像实例化的工夫十分短，即“热启动”工夫短。然而对于“冷启动”，即在本地无镜像的状况下，须要先从 Registry 下载镜像能力创立容器。业务的镜像通过长期保护和更新，无论是镜像层数还是整体大小都会达到一个较大的量级，比方可能达到数百 MB 或者几个 GB。因而生产环境中，容器的冷启动往往耗时数分钟，并且随规模扩大会导致 Registry 因集群内网络拥挤而无奈疾速地下载镜像。 例如，在之前某年的双十一流动中，阿里外部一个利用因为容量有余触发紧急扩容，但因并发量过大，整体扩容耗时较长，这期间对局部用户的应用体验造成了影响。而到了 2019 年，随着 DADI 的部署上线，新镜像格局的容器在“镜像拉取+容器启动”上消耗的总工夫比一般容器缩短了 5 倍，且 p99 长尾工夫更是比后者快了 17 倍。 如何解决存储在远端的镜像数据，这是解决容器冷启动慢这个问题的外围点。历史上业界对这一问题做出的尝试有：应用块存储或者NAS保留容器镜像，实现按需读取；应用基于网络的散发技术（如 p2p），将镜像从多个源头下载、或者提前预热到主机上，避免出现网络单点瓶颈。近年来，针对新镜像格局的探讨也逐步被提上议题，依据 Harter 等人的钻研表明，拉取镜像占用了容器启动工夫的 76%，而只有 6.4% 的工夫用来读取数据。因而，反对 On-demand Read 技术的镜像，曾经成为默认的潮流风向。Google 提出的 stargz 格局，其全称是 Seekable tar.gz，顾名思义，能够有选择地从存档中搜查并提取特定的文件，无需扫描或者解压整个镜像。stargz 旨在进步镜像拉取的性能，其提早拉取技术（lazy-pull）不会拉取整个镜像文件，实现了按需读取。为了进一步提高运行时效率，stargz 又推出了一个 containerd 的 snapshotter 插件，在存储层面对 I/O 做了进一步优化。 ...

简介：家喻户晓，QUIC（Quick UDP Internet Connection）是谷歌制订的一种互联网传输层协定，它基于UDP传输层协定，同时兼具TCP、TLS、HTTP/2等协定的可靠性与安全性，能够无效缩小连贯与传输提早，更好地应答以后传输层与应用层的挑战。目前阿里云CDN线上提供GQUIC版本服务，曾经有Tbps级别的流量承载，并对客户来带了显著的提早收益。本文将由低向上分层探讨QUIC协定的特点。家喻户晓，QUIC（Quick UDP Internet Connection）是谷歌制订的一种互联网传输层协定，它基于UDP传输层协定，同时兼具TCP、TLS、HTTP/2等协定的可靠性与安全性，能够无效缩小连贯与传输提早，更好地应答以后传输层与应用层的挑战。目前阿里云CDN线上提供GQUIC版本服务，曾经有Tbps级别的流量承载，并对客户来带了显著的提早收益。本文将由低向上分层探讨QUIC协定的特点。 作者：黎叔 QUIC协定是一系列协定的汇合，次要包含：传输协定（Transport）丢包检测与拥塞管制（Recovery)平安传输协定（TLS)HTTP3协定HTTP头部压缩协定（QPACK)负载平衡协定（Load Balance)本文针对QUIC的系列协定进行科普性简略介绍，细节读者依然须要通读协定原文。本文基于quic的探讨均基于quic-34系列版本。 QUIC协定相似快递公司，在收到用户数据后，将数据打包，传输到对端，再进行拆包，将用户数据交给了最终目标用户。QUIC是基于UDP协定，实现了相似TCP的牢靠传输，并在此基础上，联合HTTP3/QPACK，更好地服务互联网上海量的HTTP Request/Response需要。如其名发音，QUIC(quick)，其指标就是心愿比基于TCP的HTTP交互有更好的体验。 QUIC/HTTP3的特点：有序传输：用stream的概念，确保数据有序。不同的stream或者packet，不保障有序达到。报文压缩，进步荷载比率：比方QUIC引入了variable-length integer encoding。又比方引入QPACK进行头部压缩牢靠传输：反对丢包检测和重传平安传输：TLS 1.3平安协定分层的协定QUIC是在UDP的根底上，构建相似TCP的牢靠传输协定。HTTP3则在QUIC根底上实现HTTP事务。 网络总是分层探讨的，在此咱们由低向上分层探讨quic协定 UDP层: 在UDP层传输的是UDP报文，此处关注的是UDP报文荷载内容是什么，以及如何高效发送UDP报文Connection层: Connection通过CID来确认惟一连贯，connection对packet进行牢靠传输和平安传输Stream层: Stream在相应的Connection中，通过StreamID进行惟一流确认，stream对stream frame进行传输治理HTTP3层：HTTP3建设在QUIC Stream的根底上，绝对于HTTP1.1和HTTP2.0，HTTP3提供更有效率的HTTP事务传输。HTTP3中通过QPACK协定进行头部压缩UDP层本章节探讨QUIC发包的UDP局部的相干问题。 UDP荷载大小荷载大小受限于3个对象：QUIC协定规定；门路MTU；终端承受能力 1、QUIC不能运行在不反对1200字节的单个UDP传输网络门路上 QUIC有规定initial包大小不得小于1200，如果数据自身有余1200（比方initial ack)，那么须要用padding形式至多填充到1200字节 2、QUIC不心愿呈现IP层分片景象本要求意味着udp交给ip层的数据不会大于1个MTU，假如mtu为1500，ipv4场景下，udp的荷载下限为1472字节（1500-20-8），ipv6下，udp荷载下限为1452（1500-40-8)。QUIC倡议应用PMTUD以及DPLPMTUD进行mtu探测。在实战中，咱们倡议设置IPv6的MTU为1280，大于这个值，某些网络会存在丢包景象。 3、终端能承受 transport paraments的max\_udp\_payload\_size(0x03)的是终端承受单个udp包大小的能力，发送端该当听从这一约定。 UDP荷载内容UDP荷载内容即为quic协定中的packet。协定规定，如果不超过荷载大小的限度，那么多个packet能够组成一个udp报文收回去。在quic实现中，如果每个udp报文只蕴含一个quic packet，会更容易呈现乱序问题。 高效发UDP包和tcp不同，quic须要在应用层就实现udp数据组装，且每个udp报文不大于1个mtu，如果不加以优化，比方每个包间接用sendto/sendmsg发送，势必会造成大量的零碎调用，影响吞吐 1、通过sendmmsg接口进行优化，sendmmsg能够将用户态的多个udp quic包通过一次零碎调用发到内核态。内核态对于每个udp quic包独立作为udp包收回去 2、在1.）解决了零碎调用次数问题，开启GSO能够提高一分包提早到发给网卡驱动前一刻，能够进一步提高吞吐，升高CPU耗费 3、在2.）的根底上，当初支流网卡曾经反对硬件GSO offload计划，能够进一步提高吞吐，升高cpu耗费 下面介绍的发送形式，事实上能够了解为udp burst发送形式，这带来了一个问题，拥塞管制须要pacing能力！ Connection层在咱们探讨时，可知1个udp报文里传输的其实是一个或多个quic协定定义的packet。那么在Connection这一层面，其实是以packet为单位进行治理的。一个packet到来，终端须要解析出指标ConnectionID(DCID)字段，并将该packet交给找到对应的quic connection。一个packet是由header加payload两局部组成。 connection id不同于tcp的4元组惟一确认一条连贯的形式，QUIC定义了一个和网络路由无关的ConnectionID来确认惟一连贯的。这带来一个益处，能够在四元组发生变化时（比方nat rebinding或者终端网络切换wifi->4G)，仍然放弃连贯。当然，尽管连贯状态仍然放弃，但因为门路发生变化，拥塞管制也须要可能及时调整。 packet头部IETF的quic header分为两种类型，long header, short header。其中long header有分为 initial, 0rtt, handshake, retry四种类型。类型的定义能够间接参考rfc文档，此处不再赘述。 quic规定packet number始终为自增的，就算某个packet的内容为重传的frame数据，其packet number也必须自增，这绝对于TCP来说，带来一个长处，可能更加准确的采集到门路的RTT属性。 packet number编解码: packet number是一个0~262 -1的取值范畴，quic为了节约空间，在计算packet number时，引入了unacked的概念，通过截断（只保留无效bit位）的形式，只用了1-4个字节，即能够encode/decode出正确的packet number。rfc文档中有附录具体解说了enc/dec的过程。 packet头在平安传输中是被爱护对象，这也意味着在没有ssl信息的状况下，无奈应用wireshake对packet进行时序剖析。两头网络设备也无奈向TCP那样取得packet number进行乱序重组。 ...

原创 https://developer.aliyun.com/... MySQL · 捉虫动静 · order by limit 造成优化器抉择索引谬误简介： 问题形容 bug 触发条件如下： 优化器先抉择了 where 条件中字段的索引，该索引过滤性较好； SQL 中必须有 order by limit 从而疏导优化器尝试应用 order by 字段上的索引进行优化，最终因代价问题没有胜利。 复现case 表构造 create table t 问题形容bug 触发条件如下： 优化器先抉择了 where 条件中字段的索引，该索引过滤性较好；SQL 中必须有 order by limit 从而疏导优化器尝试应用 order by 字段上的索引进行优化，最终因代价问题没有胜利。复现case表构造 create table t1( id int auto_increment primary key, a int, b int, c int, key iabc (a, b, c), key ic (c)) engine = innodb; 结构数据 insert into t1 select null,null,null,null;insert into t1 select null,null,null,null from t1;insert into t1 select null,null,null,null from t1;insert into t1 select null,null,null,null from t1;insert into t1 select null,null,null,null from t1;insert into t1 select null,null,null,null from t1;update t1 set a = id / 2, b = id / 4, c = 6 - id / 8; 触发SQL ...

2014年跨年夜上海外滩人流隐患事件，使得公共安全问题受到了整体社会的宽泛关注。解决这一问题的很重要一项工作就是：如何实时监控和疾速预测城市中每个中央的人流量。当某个中央的人流量超过给定的值或者有超过给定值的趋势时，相干部门能及时地采取相干措施，例如：疏散人群，交通引流等，这样能力避免喜剧的再次发生。 为防止相似公共安全隐患，解决因人流问题造成的交通、社会治安等问题，搭建城市实时人流监控预测零碎势在必行。 ▲图1 上海外滩的踩踏事件 京东城市作为零碎建设中标单位，对整个零碎的需要进行了初步剖析，发现一个区域的人流量与多种数据相干，如图2所示。 比方：（1）手机基站数据。当一个中央的手机信令数据越多时，阐明四周的人也越多； （2）视频监控数据。从视频的画面中，可能辨认出大概有多少人； （3）交通流量数据。某条路的交通流量直观的反映了某个区域的流入流出人数； （4）出行轨迹数据。轨迹数据可能反映出人的流向； （5）天气数据。人的出行受天气的影响，比方下雨天，人们都很少出门，因而天气数据也有助于人流量的预测； （6）不同的地点所能承载的最大人流量是不同的。比方大型火车站，2万的人其实不会造成公共安全威逼，然而如果一个小区忽然有2万人，那就须要留神了。因而，每个区域的修建类型（咱们称之为趣味点或POI）、修建密度、路线构造等都能够帮忙人流的预警； （7）最初，如果当时理解到诸如举办演唱会等事件信息，也有助于人流量的预测。 ▲图2 业务数据 下面说的这些数据，单从一项数据是无奈实时监测和无效预测某个区域的人流量的，因为一项数据仅仅反映某一方面的信息。必须综合利用尽可能多的数据，能力无效地实现人流量的监控与预警，确保公共安全。 通过剖析论证后，确定的大体思路是：（1）利用上述的多种数据计算出某个时间段每个区域的流入、流出的人流量；（2）采纳AI算法模型对城市中每个区域的人流量进行建模；（3）利用建设好的模型，依据最近一段时间各区域的人流量，疾速预测将来一段时间内每个区域的人流量，并给出潜在的预警。 整体解决思路确定之后，最要害的就是钻研数据并敲定建模办法。但问题是：（1）这么多品种的数据须要如何无效治理？（2）如何从各种类型数据中疾速地提取特色指标，例如人流量？（3）如何不便疾速地构建模型，并对模型进行有效性验证？ 如果下面三个问题无奈高效解决，那人流监控及预测根本无法保障实时性。只有疾速监控和预测人流量，能力无效地实施交通管制、人流疏散，避免相似于踩踏事件的公共安全事故产生。 但这个问题要解决并不容易，首先，同类型的不同起源业务数据，数据格式可能不一样，没法对立建表，这样只能为每一份数据独自设计一张表，而且当入库数据量达到1T的时候，MySQL数据库间接解体。即便好不容易能把数据导入到MySQL数据库，往往不足更深刻的MySQL数据库调优教训，一个简略的数据查问过程，耗时费劲。 针对这些窘境，京东城市自研了——时空数据引擎（JUST引擎），通过把带有工夫、空间、地位属性的数据统称为时空数据，并且借助JUST引擎弱小的数据建模能力，将数据归类成6大类时空数据模型，所有的时空数据咱们都能够依照6大类数据模型进行入库治理。这6种数据类型的分类形式为： 一方面，世间万事万物都能够由实体对象以及实体对象之间的关系组成。若实体对象之间不存在关联，咱们称之为点数据；若实体之间存在关联，咱们称之为网数据。 另一方面，依据数据的工夫和空间的动静个性，咱们能够将数据分成4类：时空静态数据、空间动态工夫动态数据、空间动静工夫静态数据、时空动态数据。然而，因为同一物体在同一时刻只能呈现在一个中央，空间动静工夫静态数据不会存在。因而，依据时空动静个性，咱们将时空数据最终分成了3类，即：时空静态数据、空间动态工夫动态数据和时空动态数据。 综上，依据城市数据的时空个性以及实体间的关联性，咱们能够将城市数据划分成(4-1)×2 = 6类,如图4所示。 （1）时空动态点数据：以空间点的模式存在，空间地位和读数都不随工夫变动。上述数据中，趣味点就是这类数据，例如，火车站一旦建好，它的地位、大小、分类等信息将不再随工夫变动； （2）空间动态工夫动静点数据：以空间点的模式存在，其地位信息不随工夫变动，但会连续不断地产生读数。上述数据中，监控视频数据、天气数据就是这类数据； （3）时空动静点数据，以空间点的模式存在，但地位和读数均随工夫变动。下面用到的数据中，事件数据就是典型的时空动静点数据。生存中的打车数据、订单数据也是这类数据； （4）时空动态网数据，以网络的模式存在，地位和读数均不变动。下面用到的数据中，路网数据就属于此类； （5）空间动态工夫动态网数据，是指空间网络上产生的一系列读数。例如交通流量，每条路上每隔一段时间都会产生一条读数； （6）时空动态网数据，以网的模式存在，且空间地位和读数一直变动。下面用到的轨迹数据就是一种非凡的时空动态网数据。 回到人流预测场景，计算某个区域的相对流出人数，就是计算出某个时刻的总人数绝对于上一时刻的总人数的差值。这是典型的时空范畴查问的问题。传统的关系型数据库，例如MySQL、Oracle以及PostGIS，尽管整合了时空数据管理的模块，可能满足小数据量的时空范畴查问。然而一旦数据量很大，零碎就会解体。 针对海量数据，目前采纳的支流办法是分布式非关系型数据库，例如HBase。然而，原生的HBase是一个键值（key-value）数据库，只能依据一维的键值疾速找到记录，没有无效的时空索引（时空数据能够看成是3维的：经度、纬度、工夫），无奈高效实现时空范畴查问等查问剖析。此外，HBase自身没有对时空数据进行优化存储，因而占用的磁盘空间十分大。以轨迹数据为例，传统的存储形式如图5所示，每个GPS点占用一行数据，造成数据条目数与GPS点的数目雷同，导致存储空间开销很大。 ▲图5 传统HBase轨迹数据存储形式 针对这些问题，JUST引擎为HBase创立了多种高效时空索引，将多维的时空信息编码到一维的键当中，可能疾速定位诸如时空范畴查问等查问的数据。以后JUST反对的时空索引如图6所示，别离对应不同的数据查问场景。 这就好比你在图书馆的书架上找书的过程 ，没有创立时空索引的HBase，须要你在书架上一本一本地查找你要的书。而领有时空索引的JUST会通知你，你所须要的书在哪个书架、第几层、第几本中，大大减少你的查找时间。 除此之外，JUST还对6种时空数据类型的每种数据类型设计了最佳的索引存储形式以及数据分析办法。还是以轨迹数据为例，咱们预置了多种开箱即用的轨迹解决办法，包含轨迹异样值过滤、轨迹分段、轨迹地图匹配、轨迹插值等；对于每条分段后的轨迹，咱们将这条轨迹的GPS点存储在同一条数据记录中，并采纳GZip压缩形式，这样可能大大减少数据的条目数和占用空间，如图7所示。通过咱们的试验，采纳JUST的轨迹存储办法与原来传统的非关系型数据库的存储办法相比，磁盘空间放大至1/8。更小的存储空间不仅节约磁盘空间，在无限的网络带宽下还减速了查问效率。好比一扇不大的门，对于瘦子们来说，一次只能一个人穿过，而对于胖子来说，能够容许两个人同时通过。 ▲图7 JUST中轨迹数据存储形式 咱们还提出了更为准确形容轨迹形态的办法。如图8所示。传统的形容轨迹形态的办法是应用一个矩形框，该矩形框很大空间都与轨迹地位无关。因而咱们提出了采纳多个小格子来形容轨迹形态的办法。更准确的轨迹形态形容容许咱们设计出了更好的过滤办法，更进一步的进步了查问效率。 ▲图8 准确形容轨迹形态 正是先进的索引办法和存储办法，使得JUST的计算效率有了微小的晋升。其中，存储和索引效率相较于原生HBase晋升超过7倍，查问效率绝对于其余时空查问框架有了上100倍的晋升，如图9所示。目前相干钻研工作申请了多项国家专利，相干论文也已被国内顶尖会议ICDE 2020接管，受到了国内同行的认可。（TrajMesa: A Distributed NoSQL Storage Engine for Big Trajectory Data.ICDE 2020） ▲图9 性能比照 ...

作者：胡呈清爱可生 DBA 团队成员，善于故障剖析、性能优化，集体博客：https://www.jianshu.com/u/a95...，欢送探讨。 本文起源：原创投稿*爱可生开源社区出品，原创内容未经受权不得随便应用，转载请分割小编并注明起源。 ExtraExtra 是 EXPLAIN 输入中另外一个很重要的列，该列显示 MySQL 在查问过程中的一些详细信息。 Using index应用索引笼罩的状况下，执行打算的 extra 会显示为 "Using index"： 查问的字段都蕴含在应用的索引中；where 子句应用的字段也都蕴含在应用的索引中。比方： 有组合索引：idx_a (first_name,last_name,birth_date) mysql> explain select first_name,last_name,birth_date from employees where \first_name='Mayuri' and last_name like 'Alpay' and birth_date > '1968-01-01'\G*************************** 1. row *************************** id: 1 select_type: SIMPLE table: employees partitions: NULL type: rangepossible_keys: idx_a key: idx_a key_len: 127 ref: NULL rows: 1 filtered: 100.00 Extra: Using where; Using indexUsing index condition查问数据时如果应用 index condition down 索引条件下推就会在执行打算的 extra 字段中呈现 "Using index condition"。 ...

索引的目标是什么？答：数据库增加索引的目标是为了放慢查问速度。 索引的的数据结构是什么？答：（这里的B是balance）B+树来存储索引，B+树相似于二叉树。 B+树是怎么查找数据的？答：B+树索引并不能找到一个给定值的具体行。B+树索引能找到的只是被查问数据行所在的页。而后数据库通过页读入到内存，再在内存中进行查找，最初失去要查找的数据。 什么是B+树答：B+树是为磁盘或其余直接存取辅助设备设计的一种均衡查找树。在B+树中，所以记录点都依照值的大小程序寄存在同一层的叶子节点上，由各叶子节点指针进行链接。 汇集索引的定义（每张表只能有一个汇集索引）答：汇集索引就是依照每张表的主键结构一颗B+树，同时叶子节点中寄存的即为整张表的行记录，也将汇集索引的叶子节点称为数据页。汇集索引的这个个性决定了索引组织表中数据也是索引的一部分（因为存储是依照KEY-VALUE这样存储）。每个数据页都通过双向链表进行链接。 聚簇索引和非聚簇索引答：将数据存储与索引放到了一块，找到索引也就找到了数据。将数据存储于索引离开构造，索引构造的叶子节点指向了数据的对应行，myisam通过key_buffer把索引先缓存到内存中，当须要拜访数据时（通过索引拜访数据），在内存中间接搜寻索引，而后通过索引找到磁盘相应数据，这也就是为什么索引不在key buffer命中时，速度慢的起因 辅助索引（非汇集索引）答：辅助索引，叶子节点并不蕴含行记录的全副数据 联结索引答：就是对表中的多个字段增加索引。联结索引也是一颗B+树，只不过联结索引的叶子节点存储的字段是大于等于2。联结索引的第二个益处是曾经对第二个键值进行了排序解决。 笼罩索引答：辅助索引中就能够失去查问的记录，而不须要查问汇集索引的记录（意思就是不必回表了）。笼罩索引是联结索引的最优状况。 最左前缀准则索引下推

引言明天碰到一个需要：客户有张表，主键自增。因为种种原因，主键值并非间断，两头有空隙。为了使主键间断，反复利用这些空隙，目前是用 MySQL 的非凡语法：INSERT IGNORE。 这种办法非常简单，不过会带来额定的失败重试。比方我上面往表 ytt_t0 插入一条存在的记录，前期须要不停的重试能力保障插入实现。 mysql> insert ignore ytt_t0 (id) values (1);Query OK, 0 rows affected, 1 warning (0.00 sec)mysql> show warnings;+---------+------+----------------------------------------------+| Level | Code | Message |+---------+------+----------------------------------------------+| Warning | 1062 | Duplicate entry '1' for key 'ytt_t0.PRIMARY' |+---------+------+----------------------------------------------+1 row in set (0.00 sec)客户纠结的问题是：那有没有一种从数据库角度来讲疾速找出这些不间断主键值的办法呢？ 一、shell 端的实现办法必定是有，不过我自己还是感觉这一块放在非数据库端会比拟好。 比方思考在 Shell 端来实现这种需要，非常简单，效率又十分高。举个例子： 表 ytt_t0 蕴含以下数据： 最大值为 28，须要返回的后果为：5,6,7,8,9,10,11,16,17,18,20,21,22,23,24,25,26 mysql> select id from ytt_t0;+----+| id |+----+| 1 || 2 || 3 || 4 || 12 || 13 || 14 || 15 || 19 || 27 || 28 |+----+11 rows in set (0.00 sec在 Shell 端用几条常用命令就可拿到这些空缺 ID 串： ...

表的主键指的针对一张表中的一列或者多列，其后果必须能标识表中每行记录的唯一性。InnoDB 表是索引组织表，主键既是数据也是索引。 主键的设计准则对空间占用要小上一篇咱们介绍过 InnoDB 主键的存储形式，主键占用空间越小，每个索引页里寄存的键值越多，这样一次性放入内存的数据也就越多。 最好是有肯定的排序属性如 INT32 类型来做主键，数值有严格的排序，那新记录的插入只有往原先数据页前面增加新记录或者在数据页后新增空页来填充记录即可，这样有严格排序的主键写入速度也会十分快。 数据类型为整形数据类型早就曾经讲过，依照前两点的需要，最现实的当然是抉择整数类型，比方 int32 unsigned。数据程序增长，要么是数据库本人生成，要么是业务主动生成。 一、与业务无关的属性做主键1.1 自增字段做主键这是 MySQL 最举荐的形式。个别用 INT32 能够满足大部分场景，单库单表能够最大保留 42 亿行记录；含有自增字段的新增记录会程序增加到以后索引节点的后续地位直到数据页写满为止，再写新页。这样会极大水平的缩小数据页的随机 IO。用自增字段做主键可能须要留神两个问题：第一个问题：MySQL 原生自增键拆分如果随着数据前期增长，有拆库拆表预期，能够思考用 INT64；MySQL 原生反对拆库拆表的自增主键，通过自增步长与起始值来确定。起码要有 2 个 MySQL 节点，每个节点自增步长为 2，假如 server_id 别离为 1，2，那自增起始值也能够是 1，2。假如上面是第 1 个 MySQL 节点，设置好了步长和起始值后，表 tmp 插入三行，每行严格依照设置的形式插入数据。 mysql> set @@auto_increment_increment=2;Query OK, 0 rows affected (0.00 sec)mysql> set @@auto_increment_offset=1;Query OK, 0 rows affected (0.00 sec)mysql> insert into tmp values(null),(null),(null);Query OK, 3 rows affected (0.01 sec)Records: 3 Duplicates: 0 Warnings: 0mysql> select * from tmp;+----+| id |+----+| 1 || 3 || 5 |+----+3 rows in set (0.00 sec)然而这块 MySQL 并不能保障其余的值不抵触，比方插入一条节点 2 的值，也能胜利插入，MySQL 默认对这块没有什么束缚，最好是数据入库前就校验好。 ...

最艰难的事件就是意识本人！集体网站 ，欢送拜访！前言：想要彻底明确索引该怎么创立，以及怎么创立出最正当的索引，首先须要对一些常识要有所理解； 本文将从以下几方面来进行论述： 索引的相干常识（包含索引数据结构等）；索引创立的准则/根据；学会查看sql执行打算，以及哪些sql执行时会导致索引生效；索引基本知识：1、索引的数据结构：索引的数据机构是 B+Tree，B+Tree 是一个多路均衡查找树。1.1、至于为什么索引应用此数据机构呢？最次要一个起因就是：应用B+Tree这种数据机构的索引，在进行sql查问时只须要较少的几次磁盘IO 即可，所以会大大晋升查问效率；具体起因可参考：【深刻学习MySQL】MySQL的索引构造为什么应用B+树？ 1.2、索引 B+Tree 构造的个性：①、B+Tree 只有叶子节点会存储实在的数据，非叶子节点只会存储索引字段值； ②、B+Tree的叶子节点之间应用 双向链表 链接，所以更加适宜范畴查问和排序； 2、索引的类型：在平时创立的索引中，能够将索引大体分为两类： ①、聚簇索引（主键索引） ②、非聚簇索引（二级索引） 二级索引依据索引中的字段个数能够分为： ①、单字段索引 ②、联结索引 / 复合索引（多个字段组成的索引） 3、不同类型索引在磁盘中的B+Tree的存储构造：3.1、聚簇索引：（主键索引）聚簇索引：当表中创立了主键，默认就会生成主键索引；聚簇索引的B+Tree索引构造中，非叶子节点中存储的是 ID主键值 ，存储在叶子节点中的实在数据是具体的 行记录 ； 结构图如下： 3.2、单字段索引：（二级索引）单字段索引：手动创立的索引，由 一个字段 组成的索引；单字段索引的B+Tree索引构造中，非叶子节点中存储的是 索引字段值，存储在叶子节点中的数据局部是 主键值 。结构图如下： 3.3、联结索引：（二级索引）联结索引：手动创立的索引，由 多个字段 组成的索引；联结索引的B+Tree索引构造中，非叶子节点中存储的是 多个索引字段值，存储在叶子节点中的数据局部是 主键值 。结构图如下： 4、回表：什么是回表？回表 是产生在 二级索引 中的；在应用二级索引查问数据时，如果 select 投影列 中领有 索引字段和主键 之外的字段时，此时就须要 回表；应用在二级索引树中查问到的 主键值 去主键索引树中查问具体的行记录，而后在具体行记录中获得最终的 select 投影列 数据。 4.1、举例说明：数据表：t_user 字 段：id（主键）、name、age、address、sex 索 引：index( name, age ) 测试的这个索引是 联结索引，单字段索引也是一样的原理 ...