NX の 博客

双端队列 简介 普通的 BFS 每一步的代价都是相同的，而双端队列是专门用来处理代价可以为 1 和 0 两种的这种特殊情况：遇到无代价的直接插队到队首，有代价的插到队尾 当然，你也可以使用优先队列，甚至是各种图遍历算法，但是我感觉解决这种问题还是使用双端队列比较简单 例题 最经典的还是 Acwing175 电路维修 点击查看题目 题目描述 达达是来自异世界的魔女，她在漫无目的地四处漂流的时候，遇到了善良的少女翰翰，从而被收留在地球上。翰翰的家里有一辆飞行车。有一天飞行车的电路板突然出现了故障，导致无法启动。电路板的整体结构是一个 RRR 行 CCC 列的网格，如下图所示。 每个格点都是电线的接点，每个格子都包含一个电子元件。电子元件的主要部分是一个可旋转的、连接一条对角线上的两个接点的短电缆。在旋转之后，它就可以连接另一条对角线的两个接点。电路板左上角的接点接入直流电源，右下角的接点接入飞行车的发动装置。达达发现因为某些元件的方向不小心发生了改变，电路板可能处于断路的状态。她准备通过计算，旋转最少数量的元件，使电源与发动装置通过若干条短缆相连。不过，电路的规模实在是太大了，达达并不擅长编程，希望你能够帮她解决这个问题。 注意：只能走斜向的线段，水平和竖直线段不能走。 输入格式 输入文件包含多组测试数据。 第一行包含一个整数 TTT，表示测试数据的数目。 对于每组测试数据，第一行包含正整数 RRR 和 CCC，表示电路板的行数和列数。 之后 RRR 行，每行 CCC 个字符，字符是 / 和 \ 中的一个，表示标准件的方向。 输出格式 对于每组测试数据，在单独的一...

正文 最近，我发现我的评论系统加载不出来，观察了一下，发现是域名被墙了 但是解决方法也很简单——准备一个新域名，然后把这个域名指过去 首先先来到 vercel 控制台，点进去你的实例 然后找到 Setting -> Domain 之后手动添加你的域名进去 然后他会给出解析配置，你就去改你的域名解析就好了 搞定之后，访问看看 （我的这个域名本来是备用的） 最后去主题配置文件里更新这个新地址就行 2022年09月12日更 发现子域名也可以，如果你已经有一个域名的话，就没必要另外搞一个域名了（

嗯…如你所见，我最近停更了好久，因为暑假发生了一堆的事情，让我的心态很差 而且，我也没能完成我的暑假开始立的 Flag 我本来写了很长一段话想说明情况，但是最后还是删掉了，还是不提了吧 已经浪费了太多时间，就更要抓紧现在的时间，赶紧让生活步入正轨，去做更多有意义的事情 来聊些轻松些的吧！比如最近还发生了哪些正面的事情呢？ 最近的好事情 考试顺利通过 暑假的时候，得知自己六级裸考过了，还是挺高兴的 六级的话，不要太焦虑就行了，我四六级一张卷子都没做过，就考前 B 站上找些视频看看就去考了 这东西越早考越好，其实高考一考完就去考，我不相信有人过不了，毕竟我的英语水平也好不到哪里去，这东西越往后拖越难考 另外一个就是驾照了，我把科目三考过了 科目三就是好好记路线+不要紧张就行了，考试前一晚自己在脑海里过一边路线，看看有没有地方没记住的 把每个细节都拿捏住了，基本就没有什么大问题 青训营顺利结营 第四届字节跳动青训营顺利结束了，虽然没有拿到大项目的奖，但是也能拿到结营证书，这也算是一件好事情 至少有个交代嘛，而且这东西最后也就大概 50 个人拿到了 而且前几天，我也拿到上一届的证书和纪念品了 这东西在我放暑假回家了才送到学校，所以只能放同学那里，等开学再过来拿（ 重装了系统 细心的你肯定已经发现了，我现在用的不是 Windows 了 那是 Mac OS 嘛？其实不是，只是我的 Ubuntu 装了个 Mac 的主题 最近我装了个 Windows + Linux 双系统，并开始把 Linux 作为主力使用，只有打游戏的时候才用 Windows Windows 和 Linux...

本篇总结于 Go + Redis 实现分布式锁 鄙人最近在参加分布式存储的项目时学习了本内容，特此记录 为什么要用到分布式锁 先从本地的锁开始吧，在 Golang 中可以对本地的某一资源进行加锁（如变量等），以保证你在使用该资源的时候不会被其他协程更改 而在分布式系统中，若各个节点要同时使用某一个公共资源（比如说交易要修改用户存款，进程修改日志文件等），很容易就会有读写冲突、写写冲突。这时就需要一种抢占资源的机制，在你使用的时候锁住资源，保证你在使用的时候其他人不会捣乱，确保并发安全 而一种简单的实现方法就是使用 Redis 搭建分布式锁 简单的原理 这东西听上去很高大上，但是其实非常简单 就是你在访问资源前，先尝试在 Redis 处做个标记 例如你欲编辑 /file/hello.txt ，就尝试将 ["/file/hello.txt"] = 1 写入 Redis 而其他人也想做标记的时候，就会发现你已经做过了，就知道你已经抢占了资源，要等你释放 项目实践 本人的项目地址：https://github.com/tiktok-dfs/dfs 首先肯定要初始化 Redis ，因为项目是本地单机测试的，所以就以单机服务为例 1234567891011var RedisDB *redis.Client// InitRedis 初始化redis，用于分布式锁func InitRedis() { RedisDB = redis.NewClient(&redis.Options{ Addr: "localhost:63...

鄙人最近在参加青训营的项目，要完成一个分布式存储系统，里面就用到了 gRPC 框架，学习之后有所收获，所以特此记录 理论知识 什么是 RPC 要知道什么是 gRPC ，先要了解 RPC（Remote Procedure Call，远程过程调用） 什么叫做远程过程调用捏？比如说，你在写程序的时候，可以很方便地调用你本地写的函数，但是，如果你想调用其他程序的函数，那该怎么办呢？ 答案是使用 RPC ，它做到这一点，即使目标函数的程序跑在地球的另一边，都没有问题 什么是 gRPC gRPC 是一个出名的 RPC 框架，它速度很快，而且支持多种语言，它允许你可以在 Go 中调用 Java 乃至 Python 中的函数 多语言支持是怎么做到的呢？那中间必然是要借助某种通用介质，在这里就是 Protocol Buffers 什么是 Protocol Buffers Protocol Buffers 是谷歌搞的一种数据交换格式（就类似于 JSON ，XML 之类的），常被简写成 protobuf 但是与 JSON 之类不同的是，Protocol Buffers 不是明文存储的，而是压缩打包成二进制的，这也就是 gRPC 选择 Protocol Buffers 的原因，毕竟传输起来方便 你要先通过 .proto 文件定义好你的数据结构和调用函数，然后用编译器编译出 xxxxx.pb.go 文件（里边有一堆打包和解包相关的函数方法）和 xxxxx_grpc.pb.go （里边是关于 RPC 的函数方法），之后在你的项目里调用就好了 上手实践 准备环境 根据官网上的教程，你有两件事要做：...

相关链接🎶 学员手册：【大数据专场 学习资料七】第四届字节跳动青训营 - 掘金 定义 什么是可视化 什么是数据可视化 静态/不可交互 -> 动态/可交互 数据可视化作用 拿破仑进攻/撤退图，粗细表示军队人数，与下面的温度图表有很强的关联性 统计学特征 原理 数据 定义 数据和数据集 表格 多维表格 网络图和树图 场 几何数据 属性分类 编码 认知 图元 通道 编码 举例 编码有效性 交互 分类 （几个gif） 案例 这个太经典了 这个也经典，后面销量其实是下降的 历史上的传染病人口死亡规模 很多人没有达到预测年龄就被枪击死亡了（动图） 学习 综合 理论 编程 前沿 实践 我们在做的事情 课程总结

相关链接🎶 学员手册：【大数据专场 学习资料七】第四届字节跳动青训营 - 掘金 P1：基础篇 为什么要做用户数据分析 数据分析的各个环节 数据分析全景图 指标体系和指标分级 手游业务指标体系示意 口径：你怎么算出来的 搭建指标体系的价值 数据分析的各个环节 埋点简介 常见的分析工具 维度：分组项（日期和操作系统），指标：设备去重数 聚和，最大最小… 可以，但一般会先划分 数据可视化 选择合适的 数据分析的流程和案例 分析流程 案例 获取 激活 思考各个环节，哪些是要重点改进的地方 留存 收入 可以得出结论，这个游戏就是靠头部用户来维持运营的，来指导产品经营 数据分析常见的问题 总结&思考 P2：进阶篇 机器学习概览 为什么要机器学习 什么是机器学习 例：垃圾邮件过滤程序 开发者自己从现有的样本提取特性信息，对于新的样本又要手动增加过滤规则 使用机器学习，自动总结、添加规律 机器学习算法有哪些 机器学习的挑战有哪些 特征工程 概述 流程 数据理解 结构化/非结构化 定量/定性 数据预处理 衡量数据质量 准确性 完整性 一致性 时效性 可信性 解释性 主要步骤 数据清洗 缺失值 异常值 噪声 数据集成 实体识别 冗余 数据值冲突 数据规约 维度规约 维度变换 数据交换 规范化 离散化 稀疏化 特征构造 聚合 转换 特征选择 Filter 方法（过滤式） Wrapper方法（封装式） Embedded方法（嵌入式） （这些在学...

相关链接🎶 学员手册：【大数据专场 学习资料六】第四届字节跳动青训营 - 掘金 企业数据架构 数据集成 业务数据收集 CDC Log 系统间同步传输 数据生产 - 离线&实时 数据服务 数据中心案例 核心业务指标 数据查询要求 实时数据生产 数据分析 数据产出目标 数据生产可行性 计算分析 目标 计算架构 - Lambda 数据产出 查询的时候把离线和实时合并后返回 问题 过去的离线数据在今天发生变更，这是一个问题 计算架构 - 全量计算 问题解决 全量计算问题 计算架构 - 架构选择 计算难点 全量数据获取 - Hybrid Source 准确 - 处理去重&更新 准确 - Join 乱序问题场景 效率 - 聚合 效率 - Join 数据质量 任务稳定性 数据持续正确性 计算总结 数仓建设 数据组织方案 元数据管理 数据服务 查询快 引擎选择 怎么做 列存的重要性 筛选 分区 主键构建 主键查找 原始信息关联 计算向量化 执行计划 应用优化 宽表构建 提升信息密度 稳定 数据管理 课程总结

相关链接🎶 学员手册：【大数据专场 学习资料六】第四届字节跳动青训营 - 掘金 Kubernetes 简介 为什么要 k8s k8s 是什么 k8s 核心概念 Pod spec：pod的核心配置，可以配置多个 containers Volume/PV/PVC/StrorageClass Volume 太老了直接跳过 Deployment template 就是一个 pod 的声明 StatefulSet Node k8s 设计准则 声明式而不是命令式：告诉 k8s 最终想要什么状态，而不是具体要做什么做什么 控制循环：怎么生成中间步骤呢？通过控制循环 简单 模块化 向下兼容 开放 k8s 架构 k8s 核心通信机制 List-Watch 这里老师讲得真的很清楚，而且认为这个机制是 k8s 最大的特色 k8s 核心功能 资源管理 资源上报 节点资源样例 资源分配 状态维护 资源回收 调度 资源申请 request和limits：底线和上限 调度流程 示例 MySQL WordPress 优化实践 k8s 还可以更好 字节的一些工作 资源管理 功能增强 性能优化 调度质量 k8s 和 Yarn 的一些不同 k8s：拿着应用找节点 yarn：拿着节点找应用 k8s的调度质量高，但是性能差 课程总结

相关链接🎶 学员手册：【大数据专场 学习资料六】第四届字节跳动青训营 - 掘金 YARN 概述 初识调度系统 场景导入 一种简易分配模型 优化的分配模型 调度系统演进 调度系统发展的背景 调度系统解决的问题 调度系统预达的目标 调度系统模型 主要是前两者用的比较多 YARN 设计思想 演化背景 离线生态 面临挑战 YARN 整体架构 系统架构 任务运行生命周期核心流程 这里视频里讲得很清楚 Client 把任务提交到 Resource Manager，然后 RM 会拉起 AM AM 再用心跳交互资源的申请和分配，再去拉起对应的节点 运行中，AM 会监控，运行结束后 AM 会向 RM 注销 核心模块 Resource Manager 整体架构 主要职责 状态机管理 RMApp 状态机 RMAppAttempt RMContainer RMNode 调度器分析 任务/资源组织 调度流程 典型调度器 Node Manager 整体架构 主要职责 状态机管理 Application Container LocalizedResource 节点健康检测机制 重要机制 调度策略 Fair Share 调度策略背景 Instantaneous Fair Share 定义 Instantaneous Fair Share 计算逻辑 DRF 调度策略 DRF 调查策略描述 DRF 调度策略计算逻辑 事件机制 状态机管理 事件处理模型 容错机制 公司实践 Gang 调度器 为什么要开发 Gang 调...

相关链接🎶 学员手册：【大数据专场 学习资料六】第四届字节跳动青训营 - 掘金 分布式系统 分布式系统面临的挑战 理想中的分布式系统 从 HDFS 开始 案例 - KV 小结 一致性与共识算法 从复制开始 最好不要都接受请求，应设置一个主一个从 如何复制 两种策略，但是第一种的代价太高了 关于读操作 什么是一致性 复制协议 当失效发生 小结 共识算法 小结 从 Raft 入手 Paxos Raft 复制状态机（RSM） Raft 角色 客户端向 s2 发送请求 s2 把请求转成 log ，然后发送给 follower 多数完成，就回复客户 旧 leader 无响应后，发现的节点发起投票，获得半数投票即成为新 leader Raft 日志复制 小箭头：确认已经提交了的 log Raft 从节点失效 没有真正对比 log 的内容，只需要对比 term 和 index Raft Term Raft 主节点失效 Raft Leader failure 格子上面的数字是几号 term 为什么第一个状态 s1 的 term 都是 1 ？可以想象之前 s1 是 leader，然后突然卡死了，选了 s2 是新 leader 此时 s2 挂了，然后 s3 请求成为 leader ，s1 的 term 后面也变成了 3 状态是怎么复制的呢？一直往前检查，如果有冲突就从节点服从主节点 Raft 安全性 同 Term 跨 Term 小结 实现细节以及未来 案例 - KV 为什么读操作不能直接读的问题 ...

相关链接🎶 学员手册：juejin.cn LSMT 与存储引擎介绍 LSMT 的历史 LSMT 是什么 存储引擎是什么 LSMT 存储引擎的优势与实现 LSMT 与 B+ Tree 的异同 但 LSMT 是追加写，然后后台择机合并 二者在逻辑上实际是等价的 为什么要采用 LSMT 模型？ LSMT 存储引擎的实现 Write Snapshot & Supervision Get & BloomFilter 又是熟悉的 BloomFilter（ Compact 用读放大的增加换取写放大的减小 LSMT 模型理论分析 云原生的 LSMT 存储引擎 - HBase LSMT 模型算法复杂度分析 Level 这个失效率的推导非常复杂 Tier 思考题 这里建议看原视频，鄙人一直在听天书（ 总结 LSMT 存储引擎调优案例与展望 TerarkDB TerarkDB& Abase & ByteGraph Flink 新硬件 新模型 新参数 / 新工况 这个是最复杂的 总结

相关链接🎶 学员手册：【大数据专场 学习资料五】第四届字节跳动青训营 - 掘金 列存 vs 行存 数据格式层概述 分层视角下的数据形态 两种数据查询分析场景：OLTP vs OLAP OLTP：行式存储格式 OLAP：列式存储格式 总结 Parquet 原理解释 Parquet 简介 Parquet in Action DDL Spark Parquet vs Text Format 做了压缩，而且性能反而还会有提升 Dremel 数据模型 数据布局 编码 Encoding 列基数不大：去重后的数据不多 压缩 Compression 索引 Index 这东西在第一节课也出现了 排序 Ordering 过滤下推 Predicate PushDown Spark 集成 - 向量化读 深入 Dremel 数据模型 老师说听不懂没关系，哈哈哈 小结 ORC 详解和对比 ORC 简介 数据模型 数据布局 ACID 特性简介 AliORC 索引增强 小列聚合 异步读取 思考 Parquet vs ORC 性能 选择 小结 列存演进 数仓中的列存 存储侧下推 Column Family 支持 总结

相关链接🎶 学员手册：【大数据专场 学习资料四】第四届字节跳动青训营 - 掘金 消息队列概述 消息队列的应用场景 上下游解耦 MQ 消息通道 Eventbridge 数据总线 Data Platform 流数据平台 主流消息队列的相关介绍 Kafka 详解 架构介绍 Zookeeper Broker Controller 选举 作用 Coordinator 高可用 副本 ISR 机制 写入 ACK 机制 如何保证消息不丢 ACK = -1 并且 最少 ISR = 2 先看左下角，只有一个 leader 而没有 follwer 的情况，然后再看上面 结合右侧概念解释理解 第一个策略更注重一致性 第二个更注重可用性 集群扩缩容 扩容步骤 扩缩容问题 未来演进之路 运维/调优经验介绍 单机吞吐 in_sync_replica 看业务重要性，2或3 集群参数配置 扩缩容优化 指标可视化 Pulsar 详解 Pulsar 架构介绍 Pulsar Proxy 非必须，但是作用很大 Pulsar Broker Pulsar Storage Pulsar IO Pulsar Function Bookkeeper 介绍 整体架构 基本概念 Bookkeeper Ledger Bookkeeper 新建 Ledger Quorum 写：副本之间没有主从概念，例如 3 副本同时写，2 副本完成就算完成 Bookkeeper Ledger 分布 写一致性 读一致性 读写分离 Bookkeeper wit...

相关链接🎶 学员手册：【大数据专场 学习资料四】第四届字节跳动青训营 - 掘金 发展历史 数据湖发展阶段1 - Hadoop 数据湖发展阶段2 - Hive 数据湖发展阶段3 - 湖仓一体 存储计算不分离、结构化数据 业界三大数据湖 关于“数据湖” 核心技术 文件结构 Time travel Transaction 原子性 事务隔离 Schema Evolution 各有所长 Iceberg Well-designed Metadata Layer s1 比 s0 多的就是最右边的一个 manifest file，而对应的就是最右边的 data files Data File Filter Hidden Partition Hudi Timeline Service & Upsert & Incremental 这里建议看原视频，讲的还是很清楚的 Copy On Write 更新的时候把所有列读到内存，改完再塞回去 Merge On Read 更新的时候把变动放到旁边，然后读的时候再合并 Delta Lake 流批一体 总结场景 三个数据湖的异同 三个数据湖的热度 技术选型 字节场景举例 课程总结

相关链接🎶 学员手册：【大数据专场 学习资料四】第四届字节跳动青训营 - 掘金https://juejin.cn/post/7124948585614934029#heading-0) HBase 适用场景 什么是 HBase HBase 和关系型数据库的区别 HBase 数据模型 这种类 JSON 的格式看上去也是很清晰的 使用场景 典型应用 半结构化 / 字典序有序索引的数据 “近在线” 海量分布式 KV / 宽表存储 写密集的高吞吐场景 HBase 数据模型的优缺点 架构设计 HBase 架构设计 HMaster 主要职责 RegionServer 主要职责 ZooKeeper 主要职责 ThriftServer 主要职责 大数据支撑 HBase 在大数据生态的定位 水平扩展能力 Region 热点切分 切分点选取 切分过程 流量设计 Region 碎片整合 流程设计 Region 负载均衡 调度策略 其他策略 故障恢复机制 HMaster RegionServer Distributed Log Split 原理 具体流程 优化空间 最佳实践 Rowkey 设计策略 Column Family 设计策略 参数调优经验 ByteTable - 字节跳动自研分布式表格存储系统 总结