分布式唯一 ID 生成算法笔记
雪花算法
格式(64bit)
1bit 不用:因为二进制中最高位是符号位,1 表示负数,0 表示正数,生成的 id 一般都是用整数,所以最高位固定为 0
41bit 时间戳:这里采用的就是当前系统的具体时间,单位为毫秒
10bit 工作机器 ID(workerId):每台机器分配一个 id,这样可以标示不同的机器,但是上限为 1024,标示一个集群某个业务最多部署的机器个数上限
12bit 序列号(自增域):表示在某一毫秒下,这个自增域最大可以分配的 bit 个数,在当前这种配置下,每一毫秒可以分配 2^12 = 4096 个数据
特点
全局唯一性:雪花算法可以保证集群系统的 ID 全局唯一
趋势递增:由于强依赖时间戳,所以整体趋势会随着时间递增
单调递增(×):不满足单调递增,在不考虑时间回拨的情况下,虽然在单机中可以保持单调递增,但在分布式集群中无法做到单调递增,只能保证总体趋势递增
信息安全指的是 ID 生成不规则,无法猜测下一个
时间回拨
简单说就是时间被调整回到了之前的时间,由于雪花算法重度依赖机器的当前时间,所以一旦发生时间回拨,将有可能导致生成的 ID ...
data-engineer
不同岗位、不同公司、不同面试官问的内容是不一样的。大数据开发包括 Hadoop(ETL,Mapreduce),Spark(SparkSql 和 SparkStreaming),Python 等,看你偏向的技术了。另外大数据开发看是否偏向数仓开发和数据分析,又会不一样。不同的面试官和公司用到的技术栈也不一样,问的问题也会有很大差别的。
我说说我面试大数据开发岗面试官常问的问题吧。因为我简历项目项目经验注重实时流处理这方面,在面试时,面试会在这些方面问的比较深,我前后梳理一遍吧。
一般上来就是自我介绍,谈下工作经历和项目经验,面试官会根据你的项目经验对你进行技术面试。
Java 是必问的,不过问的不深,把 Javase 部分吃透,足以应付 Java 部分的面试。
Hadoop 生态,Yarn、Zookeeper、HDFS 这些底层原理要懂,面试经常被问。
Mapreduce 的 shuffle 过程这个也是面试被常问的。
Hbase 和 HIve,搞大数据这些不懂真的说不过去。
Mysql、Oracle 和 Postgres 数据库操作要回,Sql 要会写。
linux 操作系统,这个简 ...
计算机网络串记
名词解释
ARQ(Automatic Repeat reQuest,自动重传请求)
ARQ 是一种用于数据通信中的错误控制方法,旨在保证数据传输的可靠性。ARQ 协议通过在发送端和接收端之间引入确认机制来检测并纠正传输过程中出现的数据丢失或损坏问题。
停等式 ARQ(Stop-and-Wait ARQ):最简单的形式,每发送一个数据包后就停止并等待确认。只有在收到 ACK 之后才会发送下一个数据包。这种方法效率较低,因为发送方在等待确认时处于空闲状态。
回退 N 步 ARQ(Go-Back-N ARQ):允许发送方连续发送多个数据包而不需要立即等待每个数据包的确认。如果某个数据包未被正确接收,发送方需要重传从那个数据包开始到当前的所有后续数据包。
选择性重传 ARQ(Selective Repeat ARQ):类似于回退 N 步 ARQ,但更高效。它只需要重传那些确实丢失或损坏的数据包,而不是从出错点开始的所有后续数据包。这减少了不必要的重传,提高了效率。
TCP
三次握手与四次挥手
滑动窗口确认机制
拥塞控制算法
慢启动(Slow Start):在连接开始时或网络出 ...
GC 算法笔记
标记清除法
标记清除法主要包含两个步骤:
标记
清除
示例如下:
开启 STW,停止程序的运行,图中是本次 GC 涉及到的 root 节点和相关对象。
从根节点出发,标记所有可达对象。
停止 STW,然后回收所有未被标记的对象
标记清除法的最大弊端就是在整个 GC 期间需要 STW,将整个程序暂停。因为如果不进行 STW 的话,会出现已经被标记的对象 A,引用了新的未被标记的对象 B,但由于对象 A 已经标记过了,不会再重新扫描 A 对 B 的可达性,从而将 B 对象当做垃圾回收掉。
三色标记法
三色标记法将对象用三种颜色表示,分别是白色、灰色和黑色。
最开始所有对象都是白色的,然后把其中全局变量和函数栈里的对象置为灰色。第二步把灰色的对象全部置为黑色,然后把原先灰色对象指向的变量都置为灰色,以此类推。等发现没有对象可以被置为灰色时,所有的白色变量就一定是需要被清理的垃圾了。
初始标记阶段,指的是标记 GCRoots 直接引用的节点,将它们标记为灰色,这个阶段需要「Stop the World」。
并发标记阶段,指的是从灰色节点开始,去扫描整个引用链,然后将它们标记 ...
C++ 面经杂文
STL,C++11
move 相关
这里需要构造一个方便指明不同对象的 class A,下面的实现是不符合复制、移动构造函数的语义的,请不要模仿:
12345678910111213141516171819202122#include <iostream>using std::cout, std::endl;class A {public: int id = 0; A() { cout << "Construct A" << endl; } A(A &a) { this->id = a.id + 1; cout << "Copy A(" << a.id << ") to A(" << this->id << ");"; } A(A &&a) { this->id = a.id + ...
Mysql 锁机制笔记
行级锁与表级锁
行级锁由存储引擎实现,而表级锁则是服务器端实现。所以不同的存储引擎有不同的行级锁(说到底似乎只有 Innodb 有这个锁),但带伙的表级锁则是共用的。
网上存在大量博客在解说表级锁的时候每一句都要强调这个功能 Innodb 有,MyISAM 也有,这不是废话吗。。
隔离级别
Mysql 有四个隔离级别,应当这样说明:
隔离级别
特点
实现思路
Read Uncommited(读未提交)
《高性能 Mysql》自己说的就算改成 RU 级别也不能让数据库变快多少,所以废物一个路边一条,无需在意
把数据库写出来就默认是这个状态
Read Commited(读已提交)
RC 相较于 RU 主要是不至于会读到无效的、回滚的、不清楚来源的数据了,但参考实现思路,这种当然不能保证事务全程读到的数据是一致的。一个简单的场景,A 事务先读了一下 col a,A 还没结束时,B 事务以迅雷不及掩耳之势改好了 col a,标志位自然是先被标记然后又复原,A 事务再次读 col a 就没办法了,两次读的就不一致了。
只需加个标志位,所有事务正在改的行设置一下,看到别人 ...
原始面经存档
字节后端日常实习一二三面面经
一面(40 分钟)
1,自我介绍,主要介绍了一下一个 go 写的基础项目,强调了一下高并发环境下数据库/消息队列/微服务在里面的作用,后面基本都是围绕这个项目来提问的。
2,你提到了高并发,那么对于高并发环境下数据库的优化都有哪些(说了缓存/分库分表/悲观锁乐观锁和队列)
3,说说乐观锁和悲观锁的区别
4,如果我现在做一个电商下单,比如说抢购的情景,你会用什么方法实现数据库(说了乐观锁,面试官反问乐观锁合适么,我陷入思考)
5,面试官又说,比如现在有两个场景,一个是只有一件商品,有比如十万个人抢购;另一个场景是有一千个商品,还是有十万个人抢购。你都会怎么设计策略。(思考了一会,如果一件商品直接乐观锁,适用于读多写少的场景,如果一千件商品就用一个队列强行把请求变成单线程,只放一千个请求过去,其他全部返回抢购失败)
6,开始问消息队列,有什么作用(异步解耦,说了一个例子)
7,如果使用消息队列怎么解决返回消息同步性的问题(有点记不清了,这个问题想了有点久,和面试官讨论了很久,因为不知道答案说了消息队列的原理/回调,但是感觉都不是正解,后面面试官就跳过这个问 ...
一片荒芜的面经
Mysql
Mysql 的事务隔离级别有哪些?
给定 MYSQL 的情景:通过非主键列更新数据时加锁的流程。
一列主键 a,一列 b,一列 c,通过 b 读出五行 c 的数据需要进行几次磁盘 IO?
索引用什么数据结构?
索引设计原则及优化手段有哪些?
B+ 树的优势是什么?为什么不用 B 树?
三大引擎(MyISAM, InnoDB 等)讲一下,各自的优势和区别是什么?
NoSQL 与 SQL 的区别?
数据库优化
对于高并发环境下数据库的优化都有哪些?
缓存、分库分表、悲观锁乐观锁和队列
为什么会引起索引失效?最左前缀法则?
从 b+ 树的角度去讲一讲,如果插入节点的时候达到了页上限,树结构怎么调整的?
乐观锁和悲观锁的区别是什么?
数据库的锁都有什么类型?
介绍一下行级锁和表级锁。
给出一个使用表级锁的场景例子。
在更新没有索引的非主键列时,加锁的流程是什么?
MySQL 聚簇与非聚簇索引的区别是什么?
联合索引的具体结构是什么?给定一个 SQL 语句,能否命中联合索引 (a,b,c)?
1select * from order whe ...
关于 PVE 你不得不做的几件事(雾)
记载一下笔者在自己的 PVE 上做了什么防止忘记。
PVE 版本
123456789101112131415161718192021root@pve:~# neofetch .://:` `://:. root@pve `hMMMMMMd/ /dMMMMMMh` -------- `sMMMMMMMd: :mMMMMMMMs` OS: Proxmox VE 8.2.2 x86_64 `-/+oo+/:`.yMMMMMMMh- -hMMMMMMMy.`:/+oo+/-` Kernel: 6.8.4-2-pve `:oooooooo/`-hMMMMMMMyyMMMMMMMh-`/oooooooo:` Uptime: 14 mins `/oooooooo:`:mMMMMMMMMMMMMm:`:oooooooo/` Packages: 792 (dpkg) ./ooooooo+- +NMMMMMMMMN+ ...
OSPP 2024 经验分享
简单版简历
Github: feathercyc
邮箱:feathercyc@163.com
教育经历:
2023-现今:硕士,计算机科学与技术,华中科技大学
项目基本信息
项目名称:图数据库 NebulaGraph 对接数据访问层 OpenDAL
项目导师:Suyan
项目描述:OpenDAL 是一个数据访问层,允许用户以统一的方式轻松有效地从各种存储服务中检索数据。目前 OpenDAL 尚未对接图数据库 NebulaGraph,希望通过这个项目完成 NebulaGraph 和 OpenDAL 的对接,让 OpenDAL 能直接访问 NebulaGraph 存储的数据。
项目链接:https://summer-ospp.ac.cn/org/prodetail/241190422
关于 OpenDAL 社区
OpenDAL 是一个数据访问层,其支持以相同的方式访问多种存储后端,旨在减轻开发人员要为每个服务重新实现访问各种存储后端的工作量。
关于 NebulaGraph 社区
NebulaGraph 是图数据库,其以 vertex,edge 和 tag 的形式 ...