NX の 博客

相关链接🎶 学员手册：【大数据专场 学习资料三】第四届字节跳动青训营 - 掘金 元数据高可用 高可用的需求 服务高可用的需求 高可用的衡量 故障度量的指标 MTTR（Mean Time To Repair）：平均修复时间，系统能多快恢复。 MTTF（Mean Time To Failure）：平均失效时间，运行到故障间的时间，一般用于不可修复的系统（制造业） MTBF（Mean Time Between Failures）：平均无故障时间，两次故障间的间隔，一般用于可修复的系统（软件） 可用性的年化 高可用的形式 HDFS 主备同步实现 HDFS NameNode 高可用架构 理论基础 - 状态机复制和日志 NameNode 操作日志的生产消费 NameNode 块状态维护 HDFS 自动主备切换 分布式协调组件 - ZooKeeper 自动主备切换流程 - Server 侧 脑裂问题：多个节点都认为自己是 active，都会去写日志 Fence 机制：会阻止多个节点同时写日志 自动主备切换流程 - Client 侧 过去，只存一个 ND 的地址，但现在会存一组，然后依次轮询，如果是 Standby 就一直往后找，直到找到一个 active 日志系统 BookKeeper 简介 BookKeeper 架构 Quorum 机制 BookKeeper Quorum BookKeeper Ensemble 数据存储高可用 单机存储的数据高可用机制 RAID RAID 方案讲解 （梦回中学时代了属于是，之前 B 站见过讲了所有 RAID ...

相关链接🎶 学员手册：【大数据专场 学习资料三】第四届字节跳动青训营 - 掘金 HDFS 基本介绍 HDFS: Hadoop Distribute File System，是 Hadoop 的一个组件 Windows 单机文件系统 Linux 单机文件系统 分布式文件系统 分布式存储系统 HDFS 功能特性 演示环境 前面两个组件是为了高可用的，本节课主要放在 NameNode 和 DataNode 上 （一个演示视频） 架构原理 HDFS 组件 Client 写流程 Client 读流程 元数据节点 NameNode 知道 NameNode 很重要就可以了（ 数据节点 DataNode 关键设计 NameNode 目录树维护 思考题：为什么不直接在硬盘上修改 fsimage ？ NameNode 数据放置 （一个关于 block 的演示视频） DataNode 后面两个绿框里面的编号是通过哈希算出来的 HDFS 写异常处理 Lease Recovery 租约（Lease）就是一个锁 Pipeline Recovery 这是非常复杂的一部分 Client 读异常处理 旁路系统 异步地解决积累的问题 控制面建设 应用场景 使用 HDFS 的公司 初窥大数据生态 演示：PySpark 读写 HDFS 文件 （一个演示视频） ETL OLAP 查询引擎 查询引擎很多种，但是都是要对 HDHS 提供支持 HBase 机器学习 通过存储应用

相关链接🎶 学员手册：【大数据专场 学习资料三】第四届字节跳动青训营 - 掘金 概述 大数据与 OLAP 的演进 廉价机器：可以做到成本与性能的线性增长 存算分离：存储节点和计算节点可以不在一台物理机上 预计算：用空间换时间 Presto 设计思想 小结 Presto 架构原理与优化介绍 基础概念介绍 服务相关 黄色：数据源 绿色（深和浅）：服务 蓝色：用户 数据源相关 Query 相关 数据传输相关 核心组件架构介绍 服务发现 通信协议 代表了我想要关闭（当前手上还有东西，设置为此状态时，不会再安排新 task ，设定一个超时时间，过后关闭） 小结 Presto 重要机制 多租户资源管理 Case 介绍 Resource Group （这里在解读代码） 多租户下的任务调度 物理计划生成 Stage 调度 Task 调度 实际使用中 90% 都是第3种 Split 调度 内存计算 Pipeline 化数据处理 反压机制 多数据源联邦查询 小结 性能优化实战 常用性能分析工具 阿里巴巴开源的一个线上查询工具 万物皆可火焰图（ 具体案例分析 Case 1 每一段上去都有一个 copy 方法 说白了就是这个函数有问题 Case 2 某些情况下，正则表达式的匹配是非常耗时的 字节内部优化实践 Multi Coordinator History Server Support Remote UDF Raptor X 的多级缓存 小结

相关链接🎶 学员手册：【大数据专场 学习资料二】第四届字节跳动青训营 讲真，这节课大概都听不懂（ Shuffle 概述 MapReduce 概述 Map 三张 gif Shuffle 本质：通过哈希区别不同类型数据 Reduce 为什么 Shuffle 对性能非常重要 总结 批式计算的发展流程 Shuffle 算子 算子分类与应用 这个例子中，把一个 txt 按行分割，然后统计每个单词的个数 reduceByKey 产生 Shuffle，做的是 A + B 的操作（有很多机器） 最后 collect，返回结果 Spark 中对 Shuffle 的抽象 - 宽依赖、窄依赖 Shuffle Dependency Shuffle 过程 Hash Shuffle 写数据 写数据优化 把每个 Partition 映射到某个文件的片段 Sort Shuffle 写数据 每个 task 只用一个文件存储真实数据 读数据 Shuffle 过程的触发流程 前 5 行只是记录计算过程，在 Collect 的时候才会进行计算 Shuffle Handle 的创建 Shuttle Handed 与 Shuffle Writer 的对应关系 Writer 实现 BypassMergeShuffleWriter 仅适用于Partition较少的情况 UnsafeShuffleWriter SortShuffleWriter Reader 实现 网络时序图 ShuffleBlockFetchIterator External Shuffle ...

相关链接🎶 学员手册：【大数据专场 学习资料二】第四届字节跳动青训营 大数据处理引擎 Spark 大数据处理技术栈 常见大数据处理链路 开源大数据处理引擎 什么是 Spark？ 用于大规模数据处理的统一分析引擎 Spark 版本演进 Spark 生态 & 特点 Spark 特点 多语言支持 丰富数据源 丰富的 API/算子 Spark 运行架构 Spark 下载编译 Spark 包概览 Spark 提交命令 提交一个简单任务 Spark UI Spark 性能 benchmark SparkCore 原理解析 SparkCore 什么是 RDD 一个容错的可以并行执行的分布式处理集 如何创建 RDD RDD 算子 RDD 依赖 RDD 执行流程 调度器 内存管理 多任务间内存分配 Shuffle SortShuffleManager External Shuffle Service SparkSQL 原理解析 这里就是第一节课的内容了 Catalyst 优化器 RBO 语法树遍历->模式匹配->等价转换 CBO Adaptive Query Excution Coalescing Shuffle Partition 先设置比较大的 Partition 个数，然后后面再动态合并 Switch Join Strategies Optimizing Skew Joins Runtime Filter 这个和第一课里面讲的一样 Bloom Runtime Filter Codg...

相关链接🎶 学员手册：【大数据专场 学习资料二】第四届字节跳动青训营https://juejin.cn/post/7122754431371706404#heading-36) 概述 流式计算 VS 批式计算 资源模型：批式跑完资源就释放了，流式是必须一直都占用的 批处理 T+1：加 1 天 处理时间窗口 处理时间 VS 时间时间 事件事件窗口 有些数据会有延迟 Watermark 小结 （感觉有点没听懂😂） Watermark 什么是 Watermark 如何产生 Watermark 如何传递 Watermark 每个算子根据上游输入的最小值 如何通过 Flink UI 观察 Watermark 典型问题一 典型问题二 部分的分区断流（故障、晚上业务少等）的问题 典型问题三 Window Window 分类 Window 使用 滚动窗口 滑动窗口 会话窗口 迟到数据 增量 VS 全量计算 EMIT 触发 小结 优化机制 Mini-batch 优化 让算子攒一小批，然后再处理，避免高频读写 但是这样也会增加延迟，所以实际上会进行全局的协调 倾斜优化 local-global Distinct 计算状态复用 （听得不是很懂，还是建议看原视频） Pane 优化 在滑动窗口里，每一条数据可能属于多个窗口 小结 案例分析 （基于真实场景的抽象） 需求一 需求二 课程总结

相关链接🎶 学员手册：【大数据专场 学习资料一】第四届字节跳动青训营 - 掘金 数据流和动态表 随处可见的流式数据 传统 SQL 和流处理 数据流和动态图转换 先转换为动态表，再执行 SQL，再转为流 连续查询 查询产生仅追加数据的动态表 两个连续查询对比 Retract 消息的产生 对之前的结果进行回撤 状态 数据流和动态表转换回顾 不同数据处理保证的语义 Exactly-Once 和 Checkpoint 状态快照与恢复 一个源源不断的数字流，分布对奇数和偶数进行累加和 现在要备份，需要记录现在消费的位点（Source 算子）与目前的和（两个 sum 算子） 保存这 3 个状态，发生故障后就可以通过最近的保存点恢复 制作快照的时间点 不能在任意时间点保存，必须等待下游数据全部处理完成 因为恢复时上游不会重复下发数据，而下游可能在快照时还没处理或收到 可见这种方法需要停止业务消费，有没有更好的方法？ Chandy - Lamport 算法 更复杂一点的场景，有两个数据流并行处理 快照制作的开始 Source 收到 JM 发送的 Checkpoint Barrier 标识 Source 算子的处理 Source 短暂地停止处理，保存当前状态，然后继续向下游传递 Checkpoint Barrier 标识，然后就恢复数据的处理，不需要管下游 Barrier Alignment 对于下游节点，两个 Source 的 Checkpoint Barrier 不一定是同时到的（例如对于这里的 Sum even，Source 1 的 Chec...

相关链接🎶 学员手册：【大数据专场 学习资料一】第四届字节跳动青训营 - 掘金 Flink 概述 Apache Flink 的诞生背景 什么是大数据 大数据计算架构发展历史 Hadoop 那里就是谷歌发的 3 篇论文，GFS， Map-Reduce 等 为什么需要流式计算 简单地说，就是业内需要流式计算，然后就有了 Flink 为什么 Apache Flink 会脱颖而出 流式计算引擎发展历程 流式计算引擎对比 At Least Once ：能保证数据至少能被处理一次 At Most Once ：数据最多被处理一次（可能没处理到） StateFul：不再依赖外部系统存储状态 Why Flink 牛啤一体可还行（ Apache Flink 开源生态 最左边：Flink 可以高性能地使用很多存储引擎 中间框：内部架构设计，下面会说 下面：部署模式 上面：基于 Flink 的其他框架 Flink 整体架构 Flink 分层架构 最上面： SDK SQL 相关 API Stream 相关 API python 的 API 中间：执行引擎层 Flink 总体架构 这张图很重要，必须要熟悉 首先你的代码会在客户端转为一张 DAG 图（逻辑执行图），然后发给 JM ，JM 转为物理执行图，并且根据这个图把不同的 task 调度到各个的 TM 中执行 slot：插槽 Flink 作业示例 这个示例就是一个 hello world 类示例 每个 Slot 是单独的一个线程在执行 Flink 如何做到流批一体 为什么需要流批一体 流批一体的挑...

相关链接🎶 学员手册：【大数据专场 学习资料一】第四届字节跳动青训营 - 掘金 大数据体系和 SQL 大数据体系 其中消息队列用于解耦存储与计算，本次青训营会从分析引擎开始展开，然后是存储、消息队列与资源调度 那么，为什么要把 SQL 优化器放在第一节课讲呢？ 首先，SQL 是非常流行的，而且简单，包括数据分析师和挖掘师都在用，他们可能不会使用 Python之类的通用语言，但是他们可以很方便地使用一条 SQL 去处理数据，得到他们想要的结果 并且，SQL 是很多系统都支持的接口，而且 SQL 已经成为了大数据方面的通用接口。很多分析引擎一开始并不支持 SQL ，但现在都渐渐地提供了 SQL 接口 也就是说， One SQL rules big data all （通过 SQL 处理所有的大数据） 所以 SQL 在大数据中是非常重要的，下面将介绍 SQL 的处理流程 SQL 的处理流程 首先，先通过 Parser 变成抽象语法树（Abstract Syntax Tree，AST），之后通过 Analyzer 变成逻辑计划（Logical Plan），再通过 Optimizer 变成物理计划（Physical Plan），最后交给 Executor 来执行 Parser 死去的编译原理突然开始攻击我（bushi Analyzer 逻辑地：只是说明了要干什么，但是没有确定用什么算法实现（例如排序） Optimizer Executor 小结 常规的查询优化器 查询优化器分类 两种分类方法 按遍历树的方向分 按优化方法分 RBO（基于规则的优化）...

启发式搜索 还是从最简单的走网格开始吧，现在有一个包含障碍的方形网格，你需要求出从 S 点到 T 点的最短步数 很简单，不是吗？使用 BFS 就可以办到 但是，BFS 是一种盲目的搜索技术，它只会不断遍历周围的点，如果 T 点在 S 点的右上方，作为人的话肯定会把更多的精力放在往右上方搜索，一般这样能更快地找到路径，但是 BFS 并没有这种智能，那么能不能把这种智能交给程序呢？这就是启发式搜索，A*算法是比较简单的一种，可以认为是BFS和贪心的结合 尝试贪心思想 运用贪心法可进行如下处理：在处理队列中的点时，始终选取与终点的曼哈顿距离最短的点优先处理，这样循环往复，就能不断向终点逼近，而那些南辕北辙的点自然会在队列中被挤到后面去，不会浪费搜索资源 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102#include <bits/stdc++.h>using namespace std;const int M = 8, N = 10, INF = 0x3f3f3f3f;const int dx[] = {0, 1, 0, -1};const int dy[] = {1, 0, -1, 0
...

简述 康托展开可以求出一个全排列在所有全排列中的字典序 也可以逆操作，通过元素个数和字典序，求出第 xxx 个全排序状态 例如，对于 {1,2,3} 3 个数的全排列，共有 3!=63!=63!=6 种状态 1234560: 1 2 31: 1 3 22: 2 1 33: 2 3 14: 3 1 25: 3 2 1 使用康托展开可以通过 2 3 1 求得值 3 ，逆康托展开可以通过值 4 来求得 3 1 2 核心算法 X=A1⋅(n−1)!+A2⋅(n−2)!+…+An⋅0!X = A_{1}\cdot(n-1)! + A_{2}\cdot(n-2)! + \ldots + A_{n}\cdot0! X=A1​⋅(n−1)!+A2​⋅(n−2)!+…+An​⋅0! XXX ：康托展开值，指此排列前面还有多少种排列 nnn ：总共有多少数字 aia_{i}ai​ ：第 iii 位上的数字 AiA_{i}Ai​ ：在第 iii 位后面的数中，比 aia_{i}ai​ 小的数的个数 这个式子鄙人为了理解方便，稍微改动了一下 举例 康托展开 例一 求 2143 是 {1,2,3,4} 的全排列中第几大的数 第一位是 2 ，后面比 2 小的有 1 个数，故写成 1×3!1\times3!1×3! 第二位是 1 ，后面没有比 1 小的数，故写成 0×2!0\times2!0×2! 第三位是 4 ，后面比 4 小的有 1 个数，故写成 1×1!1\times1!1×1! 第四位是 3 ，后面没有数了，故写成 0×0!0\times0!...

经典题目：八数码 广搜处理的对象不仅可以是一个数，还可以是一种状态，这里最经典的题目就是八数码 先来道基础的题目 点击查看题目 题目描述 在3×3的棋盘上，摆有八个棋子，每个棋子上标有1至8的某一数字。棋盘中留有一个空格，空格用0来表示。空格周围的棋子可以移到空格中。要求解的问题是：给出一种初始布局（初始状态）和目标布局（为了使题目简单,设目标状态为123804765），找到一种最少步骤的移动方法，实现从初始布局到目标布局的转变。 输入格式 输入初始状态，一行九个数字，空格用0表示 输出格式 只有一行，该行只有一个数字，表示从初始状态到目标状态需要的最少移动次数(测试数据中无特殊无法到达目标状态数据) 样例 #1 样例输入 #1 1283104765 样例输出 #1 14 对于这道题，我们需要从给定的初始状态变化到目标状态，当我们在搜索的时候，可以直接将生成的子状态加入到队列中，每次再取出状态来处理，这就是所谓的状态图搜索 确定了思路，就有两个主要问题 怎么表示状态 怎么去重 朴素做法 因为洛谷上的这道题比较简单，对于第一个问题，可以直接将 3x3 的数组转换为一个 9 位的数字，使用 int 来保存 而去重的话，可以直接借助于 STL 中的 map 或者 set 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717...

前言 搜索一般来说主要分两种：深度优先搜索（DFS）和广度优先搜索（BFS） 比如说走迷宫，DFS 简单地说就是使用函数递归，先一条路走到底然后再考虑下一条，而 BFS 是从一点出发使用队列并行的往四面八方出发，所有方向是一起走的 正文 用一道例题来理解：hdu 1312 Red and Black 点击查看题目 Problem Description There is a rectangular room, covered with square tiles. Each tile is colored either red or black. A man is standing on a black tile. From a tile, he can move to one of four adjacent tiles. But he can’t move on red tiles, he can move only on black tiles. Write a program to count the number of black tiles which he can reach by repeating the moves described above. Input The input consists of multiple data sets. A data set starts with a line containing two positive integers W and H; W and H are the numbers of tile...

排列 求 n 个元素的全排列 使用 STL 这东西最先想到的必然是直接使用 STL 中的 next_permutation() 了，每执行一次都会把数组内的序列改为下一个排列，最后会输出 -1 123456int data[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12};int sum = 0;do{ sum++; // 得到一个结果}while(next_permutation(data,data+12)); 使用递归（法一，不推荐） 这个方法应该是我高中的时候自己手搓出来的，性能很差劲，放在这里只是为了凑个数（ 12345678910111213141516171819202122232425262728#include <iostream>using namespace std;int a[1000], v[1000], n, k; //A (n,k)void dfs(int cnt, int num){ for (int i = 1; i <= n; i++) //组合 for(int i = num+1; i <= n ;i++) if (!v[i]) { a[cnt] = i; v[i] = 1; if (cnt == k) // 边界条件 {// 得到一个结果// ...

B 站上讲得真的清楚，暂时没时间整理了，先贴个链接在这里 【python】对迭代器一知半解？看完这个视频就会了。涉及的每个概念，都给你讲清楚！ 【python】生成器是什么？怎么用？能干啥？一期视频解决你所有疑问！

模块 基本概念 模块的定义 一般情况下，模块（module）是一个以 .py 为后缀的文件，其他可作为 module 的文件类型还有 .pyo 、.pyc 、.pyd 、.so 、.dll ，但初学者几乎用不到 在模块中能定义函数、类、变量，也能包含可执行的代码，在导入的时候会把模块完整地先执行一遍 模块的作用 隐藏代码细节，提高可维护性 模块的分类 Python 的官方标准库（直接 import 就能开用） 第三方模块（用 pip 下载的包里面的模块等） 自己写的模块（下面来试一试） 初尝模块 首先，在当前目录新建一个 calc.py ，再在里面保存一些函数 1234567891011def add(a,b): return a+bdef sub(a,b): return a-bdef mul(a,b): return a*bdef div(a,b): return a/b 现在我们在其他文件中引用它，在同一目录新建一个 .py 文件 import … 导入整个模块 12345import calcresult = calc.add(10, 20)print(result) # 30 使用这种方法，在调用其中的函数或类时，必须加上模块名的前缀 from … import … 导入特定的内容，使用时不用前缀 12345from calc import add, sub # 可以导入任意个result = add(10, 20)print(result) # 30 from … import * 这会把模块中的所有函数、类、变量等全部导进来，虽...