月梦の技术博客

ymdb 是我开源的一款简易的分布式键值存储系统，适用于分布式系统初学者练手或者应届生写上简历，这篇文章将对 ymdb 做一个全面的介绍（建议仅用作学习用途，应用于生产是危险的，因为 ymdb 尚不完善）。 ymdb 使用 Go 语言开发，从面试情况来看，面试官还是很喜欢问这个项目的，并且有几个面试官表示这样的项目比较抓眼球，因为它是一个偏底层的并且不是一个千篇一律（俗称“烂大街”）的项目，因此写在简历上不失为一个好的选择。 技术选型要做一个分布式存储系统，需要考虑以下三个点： 存储 分区 复制 存储是设计一个存储系统必须要考虑的，而分区和复制则是设计一个分布式系统需要考虑的。 在存储部分，当前的键值存储有三种技术方案，一种是 RocksDB 采用的 LSMT(Log Structured Merge Tree) 方案；一种是 RoseDB 采用的 Bitcask 方案；一种是 Redis 的方案。考虑到我想做一个持久的键值存储系统，所以 Redis 这种基于内存的方式首先排除，Redis 的持久化仅用作备份以及主从复制，并不会从磁盘去拿数据。LSMT 实现 ...

ReentrantLock 是 Java JUC(java.util.concurrent) 包下的一个锁工具，它实现了 Lock 接口，与 synchronized 锁不同， ReentrantLock 除了用来做线程间互斥之外，还提供了很多高级的特性，例如公平锁 & 非公平锁以及可中断。 本文将从 JDK17 源码角度介绍一下 ReentrantLock 的底层实现原理，这部分是 Java 面试的常考知识点。（目前看到的博客都是基于 JDK8 源码分析的，而鲜有基于 JDK17 源码进行分析的） 2024美团暑期实习后端开发一面：公平锁与非公平锁是如何实现的？ 看完这篇文章你就明白了！ AQSAQS 的全称为 AbstractQueueSynchronizer ，即抽象队列同步器，通俗来讲，AQS 的作用就是来定义线程如何获得锁、线程未获得锁如何等待以及线程如何释放锁。 ReentrantLock 的底层实现是高度依赖 AQS 的，这一点从源码中就可以看得出来： public class ReentrantLock implements Lock, java.io. ...

拓扑排序（Topological Sorting）是一种针对有向无环图（DAG）的排序算法。在拓扑排序中，图中的顶点被安排成一个线性序列，使得如果图中存在一条从顶点 u 到顶点 v 的有向边，则在序列中顶点 u 出现在顶点 v 之前。 拓扑排序通常用于描述一组任务或事件之间的依赖关系，其中每个任务都有一些前置任务，必须在它们完成后才能执行。通过拓扑排序，我们可以确定一种合理的执行顺序，以确保所有任务都按照其依赖关系得到正确执行。 在实现上，拓扑排序可以根据下面的步骤实现： 找到入度为 0 的顶点，把这些节点加入到排序结果中，这些节点没有前置任务 将已经加入到排序结果中的节点及其相连的边删去，更改图中其他节点的入度 重复 1，2 步，直到图中没有入度为 0 的节点 如果被拓扑排序的图是一个有向无环图，那么所有顶点都会被排序；而如果图中有环，则拓扑排序只会得到一部分的节点序列。 因此，拓扑排序也常被用来检测一个图中是否有环。 下面是拓扑排序入门的一个经典案例及其代码实现（ 2024春招字节跳动暑期实习一面代码题 ）： 题目描述: 一共有 n 门课你可以选， ...

Spring 是 Java 生态中一个举足轻重的框架，大大简化了开发，它的主要核心特性包括两个，分别是 控制反转 以及 依赖注入。 控制反转Inversion of control ，简写为 IoC ，译为 控制反转，是一种设计思想，它将对象的 创建 和 管理 交给了 Spring 来管理，更具体地说，是交给了 IoC 容器来管理。 IoC 容器是控制反转的一个实现，它存放着开发者交给 Spring 管理的对象，其底层是一个 Map。 IoC 的好处是可以帮我们管理对象间的依赖关系，隐藏了对象的创建逻辑，当我们需要一个对象实例时直接去问 Spring 要就行了。这样降低了依赖，减小了耦合。比方说 A 类中依赖了 B 类，如果没有 控制反转 ， A 类需要自己去在代码中创建对象 B 的实例，倘若对象 B 的构造函数或者说具体实现在之后有改变，那么所有依赖了 B 类的地方代码都需要重新改，依赖关系比较简单还好，如果依赖关系错综复杂，那简直无处下手。 常常与 控制反转 一起出现的一个概念叫做 依赖注入 ，即 Dependency Injection ，简称 DI 。 依赖注入 指 ...

Raft 算法是目前应用广泛的分布式共识算法，在许多知名的开源项目比如 etcd 中，都有 Raft 的身影。同时，随着 MIT6.824 课程的普及，_Raft_ 俨然成为了最广为人知的分布式共识算法。 Raft 的设计动机之一就是为解决 Paxos 算法的难以理解性，因此 Raft 的一个大的特性就是易于理解。 直接啃论文是困难的，本文旨在以简洁的文字总结 Raft 算法，让第一次认识 Raft 算法的同学也可以很快有一个整体上的理解。 Raft is a consensus algorithm for managing a replicated log. 上面这句话引自 Raft 论文，即 Raft 是一个用于管理复制式日志的共识算法。 这里有两个问题，什么是复制式日志？什么是共识？ 复制式日志（ replicated log ） 与复制式日志紧密相关的一个概念是 复制式状态机（ Replicated state machines ） 复制式状态机 用于解决分布式系统中的 容错（ fault tolerance ） 问题，通常采用 复制式日志 实现， ...

今天看了The Google File System的论文， 我们简称其为GFS。 GFS是谷歌的分布式文件存储系统， 这篇论文是现代分布式软件系统入门的经典论文， 并由此诞生了Hadoop生态中HDFS的开源实现。 我不会一字一句地翻译这篇论文， 因为我并不是想实现这样一个系统， 我打算将一些关键点提炼出来以供学习。 介绍 GFS shares many of the same goals as previous distributed file systems such as performance, scalability, reliability, and availability. GFS与之前的分布式文件系统有着许多共同的目标， 比如性能、可扩展性、可靠性和可用性。 但是， Google在实践中提出了与早期分布式文件系统不同的设计。 首先， 组件失效是常态而不是例外。 因此， 持续监控(constant monitoring)、错误检测(error detection)、容错( faulttolerance)和自动恢复(automatic re ...

IO，即Input/Output，指的是程序从外部设备或者网络读取数据到用户态内存/从用户态内存写数据到外部设备或者网络的过程。 普通的IO过程一般的IO，其流程为， Java进程调用read() write()系统调用函数，进入内核态； 内核中的相关程序将数据从设备缓冲区拷贝到内核缓冲区中； 把数据从内核缓冲区拷贝到进程的地址空间中去 这就完成了一次Input，Output反之。 以磁盘IO为例，一次普通IO的流程如下： 这里有两个耗时的操作，一是从设备拷贝数据到内核缓冲区（磁盘准备数据慢，这里的设备缓冲区就是磁盘控制器的缓冲区，内核缓冲区就是PageCache），二是从内核缓冲区拷贝数据到进程的用户态内存空间（涉及到内核态到用户态CPU上下文的切换）。 内核缓冲区的作用是解决第二个问题，一次性拷贝一批数据，从而避免频繁且缓慢的磁盘IO或者与其他设备的IO。 字节缓冲流诸如BufferedInputStream作用是解决第一个问题，一次性从内核缓冲区拷贝一批数据到进程的缓冲区中，这个缓冲区位于进程的地址空间，之后接着取数据，如果缓冲区中 ...

RPC，是Remote Procedure Call的缩写，意为远程过程调用，使得调用远程服务的方法，就像我们调用本地方法一样简单，并且我们不需要关心整个过程底层的细节。 RPC协议被广泛应用于分布式系统节点间的通信，我所接触的分布式存储Curve就广泛使用了RPC协议. 关于RPC协议的实现，有很多RPC框架可以为我们所用，比如gRPC dubbo等，因此我们一般不需要去自己实现RPC。 RPC架构 整个RPC架构可以看做五个部分： 客户端，调用远程方法 客户端 stub：把客户端调用的方法以及参数等信息传往服务端 网络传输：在客户端stub以及服务端stub之间传递信息，可以是基于TCP也可以是基于UDP 服务端stub：接收客户端的方法调用请求，调用方法，向客户端stub返回执行结果 服务端：提供远程方法 一次RPC调用一次RPC调用的流程如下： 客户端调用方法（就像调用本地方法一样） 客户端stub将调用的方法及参数信息打包为RpcRequest并序列化 客户端stub得到远程服务地址，将消息发送给服务端 服务端stu ...

IO也就是Input/Output ，数据拿到计算机内存中的过程即为输入，反之，数据从内存输出到外部存储（可以是远程主机、磁盘、数据库等）的过程即为输出。数据传输过程类似于水流，因此称作IO流。IO流在Java中分为输出流和输入流，根据数据的处理方式又分为字节流和字符流。（这里的输入输出是以程序为中心的，输入指程序接收输入，输出指程序把数据输出到外部存储） Java IO流Java IO流有四个基类，分别是输入流InputStream（字节输入流），Reader（字符输入流），OutputStream（字节输出流），Writer（字符输出流），其余的IO相关类都是派生于这四个抽象基类。 字节流与字符流字节流： 以字节为单位处理数据，适用于处理二进制数据 直接操作字节，不涉及编码转换，可以处理任何类型的数据 字符流： 以字符为单位处理数据，适合处理文本数据 自动处理字符编码和解码（将字节传为字符） 性能逊于字节流处理，因为还有编解码消耗 对于不知道编码类型的数据，使用字节流处理会带来乱码问题，而使用字符流就不会出现这样的问题 字节流InputStr ...

一致性哈希是一种哈希算法，主要用于分布式系统中数据的分片和负载均衡，一致性哈希算法解决了传统哈希算法在节点动态增减时可能导致数据迁移量过大的问题，能够提供更好的扩展性和性能。 普通的哈希算法众所周知，哈希算法用于将字符串映射到固定长度的哈希值上，应用广泛，譬如Java中的HashMap，C++中的unordered_map，都是用到了哈希算法。 在分布式缓存中，数据被缓存到了不同的节点上，那么具体到一个数据的缓存或者访问，分布式缓存系统应该如何选择节点呢？这里会遇到一个问题，即： 如果随机选择节点，那么比如第一次查询选择将数据缓存在A节点，第二次查询的时候有很大概率会选择其他缓存节点，那么则缓存失效，需要重新进行数据查询，这显然是不合理的！ 另外，此举还会造成不同的节点缓存相同的数据，带来空间的浪费！ 我们应该让相同的数据的缓存和查找落在同一个节点上，这样才可以充分发挥缓存带来的性能提升。 如何使得相同的数据的缓存和访问落在同一个节点上呢？ 使用哈希算法可以很好地完成这样的工作—— 现假设拥有5个节点，编号为0~4，可以首先将待查询key的信息映射到 ...