- 博客(381)
- 收藏
- 关注
RSS订阅原创 CMU15-445-Spring-2023-分布式DBMS初探（lec21-24）
分布式 DBMS 将单个逻辑数据库划分为多个物理资源。应用程序（通常）并不知道数据被分割在不同的硬件上。系统依靠单节点 DBMS 的技术和算法来支持分布式环境中的事务处理和查询执行。设计分布式 DBMS 的一个重要目标是容错（即避免单个节点故障导致整个系统瘫痪）。
2024-01-18 12:23:49
1170
原创 CMU15-445-Spring-2023-Project #4 - Concurrency Control
通过添加一个锁管理器在 BusTub 中支持事务，然后将其用于并发查询执行。锁管理器将支持五种锁模式下的表锁和元组锁：intention-shared、intention-exclusive、shared-intention-exclusive、shared、exclusive。锁管理器将处理来自事务的锁请求，向事务授予锁，并根据事务的隔离级别检查锁是否被适当释放。
2024-01-17 07:15:00
880
原创 CMU15-445-Spring-2023-Project #4 - 前置知识（lec15-20）
并发控制：如何避免同时更新记录时出现race？耐久性问题（恢复）：断电时如何确保状态正确？
2024-01-17 04:15:00
1753
原创 CMU15-445-Spring-2023-Project #3 - Query Execution
为 BusTub 添加新的运算符执行器和查询优化。BusTub 使用迭代查询处理模型（火山模型），其中每个执行器都实现了一个 Next 函数，用于获取下一个元组结果。当 DBMS 调用执行器的 Next 函数时，执行器会返回 (1) 一个元组或 (2) 一个没有更多元组的指示符。通过这种方法，每个执行器都实现了一个循环，不断调用其子执行器的 Next 来检索元组并逐个处理。在 BusTub 的迭代器模型实现中，每个执行器的 Next 函数除了返回一个元组外，还会返回一个记录标识符（RID）。
2024-01-16 22:22:05
1056
原创 CMU15-445-Spring-2023-Project #3 - 前置知识（lec10-14）
数据库系统会将 SQL 编译成查询计划。查询计划是一棵运算符树。
2024-01-16 22:17:34
3350
原创 CMU15-445-Spring-2023-Project #2 - B+Tree
实现三个page class来存储B+树的数据。每个 B+Tree 的leaf/internal page都与缓冲池获取的内存页的内容（即 data_ 部分）相对应。每次读取或写入leaf/internal page时，必须先从缓冲池中获取该页（使用其唯一的 page_id），然后 reinterpret cast 成leaf/internal page，并在读取或写入该页后将其unpin。
2024-01-10 22:46:15
567
原创 CMU15-445-Spring-2023-Project #2 - 前置知识（lec07-09）
哈希表将键映射到值。它提供平均 O (1) 的操作复杂度（最坏情况下为 O (n)）和 O (n) 的存储复杂度。由两部分组成： Hash Function和Hashing Scheme（发生冲突后的处理）
2024-01-10 22:44:58
998
原创 CMU15-445-Spring-2023-Project #1 - Buffer Pool
在存储管理器中实现缓冲池。缓冲池负责将物理页从主内存来回移动到磁盘。它允许 DBMS 支持大于系统可用内存量的数据库。缓冲池的操作对系统中的其他部分是透明的。例如，系统使用page唯一标识符（page_id_t）向缓冲池请求一个页面，但系统并不知道该页面是否已在内存中，也不知道系统是否需要从磁盘中获取该页面。实现必须是线程安全的。
2024-01-06 22:21:07
491
原创 CMU15-445-Spring-2023-Project #1 - 前置知识（lec01-06）
数据库是相互关联的数据的有组织集合，对现实世界的某些方面进行建模。区别于DBMS（MySQL、Oracle）。
2024-01-06 18:01:11
978
原创 ZooKeeper Client API 安装及使用指北
Zookeeper实际上运行在Zab协议（ZooKeeper Atomic Broadcast）之上，Zab几乎与Raft是一样的。从Raft说起，Raft实际上就是一个库。你可以在一些更大的多副本系统中使用Raft库。但是Raft不是一个你可以直接交互的独立的服务，你必须要设计你自己的应用程序来与Raft库交互。所以这里有一个有趣的问题：是否有一些有用的，独立的，通用的系统可以帮助人们构建分布式系统？是否有这样的服务可以包装成一个任何人都可以使用的独立服务，并且极大的减轻构建分布式应用的痛苦？
2023-12-25 00:05:07
653
原创 MIT6.5840-2023-Lab4B: Sharded K/V Service-Sharded K/V Server
实现一个分片 k/v 存储系统，分片指如所有以“a”开头的键可能是一个分片，所有以 “b”开头的键可能是另一个分片。每个副本组仅处理几个分片的 Put、Append 操作，实现并行操作，系统总吞吐量（单位时间的放入和获取）与组的数量成正比。分片 k/v 存储系统由多个副本组和一个分片控制器组成，分片控制器管理配置信息，决定哪个副本组为哪个分片服务。某些组的负载可能远高于其他组，实现在多个副本组之间转移分片，以达到负载均衡。
2023-12-22 01:49:45
794
原创 MIT6.5840-2023-Lab4A: Sharded K/V Service-The Shard controller
实现一个分片 k/v 存储系统，分片指如所有以“a”开头的键可能是一个分片，所有以 “b”开头的键可能是另一个分片。每个副本组仅处理几个分片的 Put、Append 操作，实现并行操作，系统总吞吐量（单位时间的放入和获取）与组的数量成正比。分片 k/v 存储系统由多个副本组和一个分片控制器组成，分片控制器管理配置信息，决定哪个副本组为哪个分片服务。某些组的负载可能远高于其他组，实现在多个副本组之间转移分片，以达到负载均衡。
2023-12-20 01:44:47
372
原创 MIT6.5840-2023-Lab3B: Fault-tolerant K/V Service-Key/value service with snapshots
使用 lab2 中的 Raft 库构建 Fault-tolerant K/V Service，即维护一个简单的键/值对数据库，其中键和值都是字符串。具体来说，该服务是一个复制状态机，由多个使用 Raft 进行复制的键/值服务器组成，只要大多数服务器处于活动状态并且可以通信，该服务就应该继续处理客户端请求。
2023-12-19 02:03:58
358
原创 MIT6.5840-2023-Lab3A: Fault-tolerant K/V Service-Key/value service without snapshots
线性一致（强一致）：对于整个请求历史记录，只存在一个序列，不允许不同的客户端看见不同的序列；或者说对于多个请求可以构造一个带环的图，那就证明不是线性一致的请求记录。线性一致不是有关系统设计的定义，这是有关系统行为的定义。Zookeeper 的确允许客户端将读请求发送给任意副本，并由副本根据自己的状态来响应读请求。副本的 Log 可能并没有拥有最新的条目，所以尽管系统中可能有一些更新的数据，这个副本可能还是。
2023-12-18 15:53:32
800
原创 MIT6.5840-2023-Lab2A: Raft-leader election
所以，新的Leader必然知道旧Leader使用的任期号（term number），因为新Leader的过半服务器必然与旧Leader的过半服务器有重叠，而旧Leader的过半服务器中的每一个必然都知道旧Leader的任期号。类似的，任何旧Leader提交的操作，必然存在于过半的Raft服务器中，而任何新Leader的过半服务器中，必然有至少一个服务器包含了旧Leader的所有操作。跟随者只响应来自其他服务器的请求。避免脑裂：奇数个服务器，在任何时候为了完成任何操作，必须凑够过半的服务器来批准相应的操作。
2023-12-11 02:13:49
945
原创 MIT6.5840-2023-Lab1: MapReduce
MapReduce：Master 将一个 Map 任务或 Reduce 任务分配给一个空闲的 worker。：被分配了 map 任务的 worker 程序读取相关的输入数据片段，生成并输出中间 k/v 对，并缓存在内存中。：所有 map 任务结束，reduce 程序使用 RPC 从 map worker 所在主机的磁盘上读取缓存数据，通过对 key 进行排序后使得具有相同 key 值的数据聚合在一起，reduce 进行操作后输出为文件。
2023-12-06 19:11:47
991
原创 Linux高性能服务器编程——ch16笔记
作为守护进程运行的服务器程序就应该总是关闭标准输入、标准输出和标准错误这3个文件描述符。两个层次的限制：用户级限制和系统级限制。
2023-10-31 16:35:48
74
原创 Linux高性能服务器编程——ch15笔记
两者相似。进程池是由服务器预先创建的一组子进程，代码相同，属性相同。主进程选择为新任务服务的子进程：1）主动选择：随机和Round Robin（轮流选取）。2）主进程和所有子进程通过一个共享的工作队列来同步。选择完后，传递数据：在父进程和子进程之间预先建立好一条管道，然后通过该管道来实现所有的进程间通信（当然，要预先定义好一套协议来规范管道的使用）。在父线程和子线程之间传递数据就要简单得多，因为可以把这些数据定义为全局的，那么它们本身就是被所有线程共享的。
2023-10-31 16:35:05
148
原创 Linux高性能服务器编程——ch14笔记
线程是程序中完成一个独立任务的完整执行序列，即一个可调度的实体。内核线程：轻量级线程，运行在内核空间，由内核调度；用户线程：运行在用户空间，由线程库调度；当进程的一个内核线程获得CPU的使用权时，就加载并运行一个用户线程。一个进程拥有固定比例的内核线程和用户线程，M
2023-10-31 16:34:23
64
原创 Linux高性能服务器编程——ch13笔记
::tips:::每次调用返回两次，在父进程中返回子进程的PID，在子进程中返回0。用来判断当前进程是父进程还是子进程。fork函数复制当前进程，在内核进程表中创建一个新的进程表项。该进程的PPID被设置成原进程的PID，信号位图被清除（原进程设置的信号处理函数不再对新进程起作用）。数据的复制采用写时复制（即只有在任一进程（父进程或子进程）对数据执行了写操作时，复制才会发生（先是缺页中断，然后操作系统给子进程分配内存并复制父进程的数据））。
2023-10-31 16:33:45
54
原创 Linux高性能服务器编程——ch12笔记
外链图片转存中…(img-VrkMkNau-1698741179220)]基于Reactor模式的I/O框架库包含：1）句柄：与事件源绑定（I/O事件、信号和定时事件）。当内核检测到就绪事件时，通过句柄来通知应用程序这一事件。I/O事件对应的句柄是文件描述符，信号事件对应的句柄就是信号值。2）事件多路分发器：等待事件使用I/O复用实现， I/O框架库一般将系统支持的各种I/O复用系统调用封装成统一的接口。核心函数：demultiplex。事件循环：循环等待并处理事件。
2023-10-31 16:33:07
55
原创 Linux高性能服务器编程——ch10笔记
::tips:::kill函数：一个进程给其他进程发送信号的API。sig一般大于0，如果设为0则表示不发送信号，可以用来检测进程或进程组是否存在。由于进程PID的回绕（当进程被启动的时候，系统将按照顺序选择下一个没有被使用的数字作为它的PID（2~32768），当数字已经回绕一圈的时候，新的PID重新从2开始），可能导致被检测的PID不是我们期望的；另一方面，这种检测方法不是原子操作。:::tips:::信号处理函数是可重入的，避免引发竞态条件。
2023-10-31 16:31:56
47
原创 Linux高性能服务器编程——ch8笔记
服务器启动后，首先创建一个（或多个）监听socket，并调用bind函数将其绑定到服务器感兴趣的端口，然后调用listen函数等待客户连接。服务器稳定运行之后，客户端就可以调用connect函数向服务器发起连接。由于客户连接请求是随机到达的异步事件，版务器需要使用某种I/O模型来监听这一事件。下图服务器使用的是I/O复用技术之一的select系统调用。当监听到连接请求后，服务器就调用accept函数接受它，并分配一个逻辑单元为新的连接服务。
2023-10-27 17:35:30
185
原创 Linux高性能服务器编程——ch7笔记
Linux提供rsyslogd守护进程接收用户进程输出的日志和内核日志。应用程序使用syslog函数与rsyslogd守护进程通信。openlog函数：改变syslog的默认输出方式。setlogmask函数：设置syslog的日志掩码（日志过滤，使日志级别大于日志掩码的日志信息被系统忽略）。closelog函数：关闭日志功能。
2023-10-22 21:03:35
279
原创 Linux高性能服务器编程——ch6笔记
用于创建一个管道，以实现进程间通信。读端文件描述符fd[0]和写端文件描述符fd[1]构成管道的两端，默认是阻塞的，fd[0]读出数据，fd[1]写入数据。管道内部传输的数据是字节流。如果fd[1]的引用计数减少至0，即没有任何进程需要往管道中写入数据，则针对f[0]的read操作将返回0，即读取到了文件结束标记（EOF）；反之，如果fd[0]计数减少至 0，即没有任何进程需要从管道读取数据，则针对fd[1]的write操作将失败，并引发SIGPIPE信号。
2023-10-22 21:02:37
481
1
原创 Linux高性能服务器编程——ch5笔记
主机字节序（小端字节序）：整数的高位字节存储在内存的高地址处，而低位字节则存储在内存的低地址处。网络字节序（大端字节序）：相反。主机字节序和网络字节序之间的转换：发送端总是把要发送的数据转化成大端字节序数据后发送。（函数：htonl、htons、ntohl、ntohs）host to network long(short)
2023-10-20 11:29:26
325
原创 Linux高性能服务器编程——ch4笔记
客户端和目标服务器之间可能存在多个代理服务器。正向代理：要求客户端自己设置代理服务器的地址。反向代理：设置在服务器端。透明代理：设置在网关上，可以看作正向代理的特殊情况。192.168.1.0/24：CIDR（无类域间路由）表示法，前面是IP地址，后面是子网掩码中1的位数，等价于192.168.1.0/255.255.255.0。通过squid部署代理服务器。
2023-10-19 11:40:44
664
原创 Linux高性能服务器编程——ch3笔记
面向连接：在数据读写前必须先建立连接，并分配内核资源。全双工（读写可以通过一个连接进行）。数据交换后必须断开连接，释放系统资源。一对一的，基于广播和多播（目标是多个主机地址）的应用程序不能使用TCP。字节流：发送端执行的写操作次数和接收端执行的读操作次数之间没有任何数量关系，应用程序对数据的发送和接收是没有边界限制的，在TCP发送（接收）缓冲区封装（读出）。
2023-10-18 16:29:36
228
原创 Linux高性能服务器编程——ch2笔记
无状态：IP通信双方不同步传输数据的状态信息。IP数据报相互独立，缺点是无法处理乱序和重复的IP数据报。上层协议如果是面向连接的协议（TCP），能够自己处理乱序和重复的报文段。IP数据报头部的标识字段是被用来处理IP分片和重组的，不是指接收顺序。优点是简单高效。UDP和HTTP也是无状态的。无连接：IP通信双方都不长久地维持对方的任何信息。不可靠：IP协议不能保证IP数据报准确地到达接收端。通知上层协议发送失败，但不重传，使用IP的上层协议需要自己实现数据确认、超时重传。
2023-10-18 16:28:53
253
原创 Linux高性能服务器编程——ch1笔记
网卡接口的网络驱动程序，以处理数据在物理媒介（比如以太网、令牌环等）上的传输。协议：ARP、RARP，实现IP地址和机器物理地址之间的转换。数据包的选路和转发。WAN使用路由器（中间节点）连接分散的主机或LAN。协议：IP，逐跳确定通信路径；ICMP，补充，检测网络连接，如ping。为两台主机上的应用程序提供端到端的通信。数据链路层（驱动程序）封装了物理网络的电气细节；网络层封装了网络连接的细节；传输层则为应用程序封装了一条端到端的逻辑通信链路，它负责数据的收发、链路的超时重连等。
2023-10-18 16:26:58
251
原创 GO-SLAM——论文简析
消费级深度传感器容易产生噪声，这就导致 RGB-D SLAM 会丢失一些几何细节，导致过度平滑。使用轻量级的相机传感器是一种趋势，然而，它们的 representations（点云、曲面、volume）在形状提取时缺乏灵活性，重建的准确度就会下降。基于 NeRF 的视觉 SLAM 可以在小尺度场景中实现精确的三维重建和相机位姿估计。然而目前的工作由于缺乏全局在线优化，如 loop closure 和 全局 BA，会导致随着帧数的增加，相机偏移误差累积，三维重建会迅速崩溃。
2023-10-14 20:20:56
856
原创 NICE-SLAM——论文简析
传统的适用于构建稠密图的视觉 SLAM，无法对未观察到的区域进行估计。另一类基于学习的方法通常是在特定任务的数据集上进行训练，因此能达到一定的预测能力。此外，基于学习的方法往往能更好地处理噪声和异常值，但是只适用于有几个物体的小场景。iMAP 应用了神经隐式表征，在房间大小的数据集上显示了不错的跟踪和建图结果。但是当扩展到更大的场景（如由多个房间组成的公寓）时，稠密图重建和相机跟踪精度都出现了明显的性能下降。其限制在于只用了一个 MLP 来表示场景，且只能根据新的局部数据进行全局更新。
2023-10-08 17:15:06
219
原创 iMAP——论文解析
理想的 3D 表征应该具备高效性（内存方面）、可预测性（未观察区域）、灵活性（复用性）。隐式神经表征（implict neural representation， INR）之前大多数用于离线重建，它使用 MLP 将 3D 点映射为空间中的颜色和不透明度，并从头开始进行优化，以适应特定场景。MLP 能对为观察到的区域进行重建。iMAP 的网络权重不需要 pre-train，追踪上用 MLP 渲染的深度和颜色调整相机的观察结果，建图上用一组关键帧训练和改进 MLP，并优化关键帧的位姿。
2023-09-24 22:38:22
352
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人