6.824ShardKV实现
概述这也是 6.824 的最后一个 lab，即在之前 raft 和 RSM 的基础上，实现一个multi raft 的分片存储来提高性能，整个集群的性能会随着分片数量的增加而线性提高 整体架构对于这个集群，主要是分为三部分，shardctrler、shardGroup 以及 shardClient，每个 shardGroup 由一个 client 和 raft server集群组成，shardctrler负责对整体集群分片存储的配置，shardClient由用户进行使用，shardctrler和shardClient都只能和 shardGroup 进行交互，如图 shardctrler会将配置的信息存入到 kvsrv 中，通过 RPC 与shardGroup进行交互，进行碎片迁移 shardClient每次操作先获取 kvsrv 中的信息得到每个分片对应的shardGroup，再和shardGroup进行交互 实现思路我们从初始状态开始实现，首先实现shardctrler的 InitConfig 和...
6.824-实现 raft_kv
整体架构这里实现的总体架构大致是 server-rsm-raft，server 主要提供对外的 API 服务，rsm 负责将任务进行提交并调用 server 的 do_op()将日志进行应用后返回，raft 负责分布式一致性和分区容错性的保证。请求处理逻辑如下 初始化时 rsm 会开启一个reader后台线程 client 多线程发送请求 一个请求到达server 时，server 调用rsm.submit()对请求进行提交 rsm 将请求通过 raft.start()提交给 raft，开始睡眠等待 raft将请求apply，reader 读取到 apply 的请求，执行 do_op()，然后唤醒提交线程 调用rsm.submit()的线程将请求返回给 server server将结果返回给 client RSM按照上述处理逻辑实现即可，唯一需要注意的点是我们的Submit 和 Reader 都应当是与 op 的格式无关，因此在设计op -> channel的map 时，应该把 key 设计为 Raft Start取得的 Term 和 Index，然后如果...
raft实现
Lab3 Raft实现Raft的原理是通过一个日期机制和日志复制以及持久化保证一致性，每台服务器都有一个 Term，每个 Term 只会有一个 Leader，每次操作由 Leader 先追加日志再将日志同步给其他 follower，只要有多数确认了日志，则可以提交日志，即操作成功。我们通过在选举 leader 时增加对日志的限制即可保证被提交的日志一定不会被覆盖。 3A3A 主要是不考虑状态机的情况下，实现 Raft Leader选举和心跳机制，确保选举出单一 Leader，如果没有故障就保持 Leader，如果 Leader 故障或者包丢失，则选举新的 Leader ticker实现我们需要实现超时机制，在一定时间后没有心跳，则我们需要进行选举 选举实现状态转移API 参考具体实现参照原论文中状态转移和 API 定义即可，需要注意的点如下 在向其他服务器发送 RequestVote 时，需要将锁释放，不然有可能出现多个 Candidater相互要票却无法投票的情况，因为投票也需要加锁，所以会产生死锁 在一台服务器决定是否投票时，如果收到的 Term 大于自身...
TCP Receiver Sender实现
CS144 TCP Receiver & Sender 实现笔记这是我做CS144的TCP实现部分的一些记录，主要是为了以后复习的时候能快速回忆起当时的思路。 StreamReassembler 实现在搞TCP Receiver之前得先把StreamReassembler搞定，这个东西就是用来把乱序的数据包重新排好序的。 我的实现思路我用了一个set来存放所有的segment，按照起始位置排序。最关键的是要保证一个规律：set里面的所有segment都不能重叠。 每次来新的segment的时候： 先找出所有和它重叠的segment 把这些重叠的都删掉 然后把它们全部合并成一个大的segment 再把这个合并后的segment放回set 这样搞的好处是，后面往ByteStream里写数据的时候就很简单了，直接从头开始写，碰到第一个不连续的地方就停。 TCP通信流程TCP就是靠两对(Receiver, Sender)来搞双向通信的： 发送端：Sender.send() → 网络 → Receiver.receive()接收端：Receiver.send() → 网络 →...
Google File System设计阅读
背景在 Google 早期，随着其搜索引擎和各项服务数据量的爆炸式增长，传统的文件系统已经无法满足其日益严苛的需求。为了应对海量数据的存储和处理挑战，Google 内部设计并实现了一个高度可扩展、高可用且容错的分布式文件系统——Google 文件系统 (GFS)。GFS 的设计理念和技术实践深刻影响了后续 Hadoop HDFS 等一系列大数据存储系统。 GFS 的设计基于以下核心需求和假设： 硬件不可靠性常态化： 系统由大量廉价的商用硬件构建，这些组件的故障是常态，而非异常。因此，系统必须具备强大的故障监控、检测和自动恢复能力。 存储重心在大文件： GFS 主要面向大文件（GB 乃至 TB 级别）存储进行优化，例如 Web 爬虫数据、搜索引擎索引、视频文件等。虽然支持小文件，但并非其优化重点。 工作负载特性鲜明： 读取模式： 以大型流式读取（一次性读取大量连续数据）为主，也支持小型的随机读取。 写入模式： 大型追加写入（将数据追加到文件末尾）是主要场景，文件写入后很少被修改。小写入也支持，但效率不高。 高并发追加需求：...
6.824Lab1-Mapreduce设计
概述用户传递给我们 n 个 files，map 和 reduce 函数，以及一个 nreduce，我们要做的就是把这 n 个 files 经过 map 和 reduce后输出 nreduce 的 output 还给用户 框架以及我们需要做的事情这个 lab 为我们提供了 coordinator 和 worker，我们通过coordinator 去控制多个 worker 来并行处理 map 操作或者 reduce 操作。 思路首先考虑 coordinator 和 worker 之间的交互过程，我这里的实现方案是让 worker 去不断的轮询coordinator，这样的话我们的 coordiantor 不需要知道有多少个 worker，它只需要当有请求来的时候，把任务分给 worker 去操作就可以了，我们想搞几个 worker 搞几个 worker，然后大致流程是这样的 worker 询问 master 请求分配任务 master 返回请求的任务，worker 开始运行任务(这里如果没有任务要退出，或者还在等其他 map 任务的话可以考虑睡眠) worker 完成任务后告诉...
MapReduce学习
背景Google需要处理大量的数据，在这些数据的基础上进行海量的计算，或者去分析整个网络的链接结构，这个过程本质上是对整个网络的内容去进行排序，这是非常耗费资源的一件事，使用单台计算机需要相当长的时间，于是Google希望能在成千上万台机器上去并行处理这些事情以缩短处理的时间，尽管如此，工程师们还是需要去手动的将任务分配给每台机器，这也是很费劲的事情，因此我们需要一个框架，能够让工程师只编写一个任务的核心部分，或者说能让非分布式专业的程序员也能够在分布式的系统上设计应用，于是便有了MapReduce。 运行过程用户上传需要处理的文件，框架会对这些Input...
Hello World
Welcome to Hexo! This is your very first post. Check documentation for more info. If you get any problems when using Hexo, you can find the answer in troubleshooting or you can ask me on GitHub. Quick StartCreate a new post1$ hexo new "My New Post" More info: Writing Run server1$ hexo server More info: Server Generate static files1$ hexo generate More info: Generating Deploy to remote sites1$ hexo deploy More info: Deployment
Java 内存模型 (JMM) 深入解析 —— 内存屏障、volatile 与 synchronized 原理
Java 内存模型 (JMM) 深入解析 —— 内存屏障、volatile 与 synchronized 原理 从 Java 内存模型出发，详细剖析 volatile 和 synchronized 如何通过内存屏障保障可见性与有序性，彻底掌握 CPU 与编译器优化下的并发底层原理。 目录 1. 什么是 JMM？ 2. 重排序问题简述 3. 内存屏障概念 3.1 内存屏障分类 4. volatile 与内存屏障 4.1 内存语义 4.2 JVM 对 volatile 插入的屏障 4.3 示例分析 5. synchronized 与内存屏障 5.1 内存语义 5.2 字节码 monitorenter/monitorexit 对应屏障 5.3 示例分析 6. 内存屏障总结 7. volatile 与 synchronized 屏障对比 8. happens-before 规则详解 1. 什么是 JMM？Java 内存模型（JMM, Java Memory Model）定义了 多线程之间可见性、有序性、原子性 的规则，主要解决 CPU...
JUC-多线程锁原理详解
Java 多线程锁原理详解 —— 从字节码到 JVM 实现全解Java 并发编程离不开对“锁”机制的理解与掌握。无论是最基础的 synchronized，还是功能丰富的 ReentrantLock，亦或是高效提升读操作性能的 ReadWriteLock，它们背后蕴含的实现原理和适用场景各有千秋。 本文将从为什么需要锁讲起，结合 字节码、JVM 实现，一步步剖析各类锁的底层机制，帮助你彻底掌握多线程锁的原理。 目录 1. 为什么需要锁？ 2. 可重入锁是什么？ 3. synchronized 详解 3.1 基本用法 3.2 字节码与 JVM 实现 3.3 优缺点总结 4. wait/notify 机制详解 5. ReentrantLock 详解 5.1 基本用法 5.2 公平锁与非公平锁 5.3 tryLock 与中断 5.4 Condition 精准唤醒 5.5 Condition vs wait/notify 对比 6. 读写锁 ReadWriteLock 6.1 原理与用法 6.2 适用场景 7. StampedLock 简介 8....
