指针的轨迹

这节课讲支撑 Google 各种应用的文件系统——GFS。可以借此回顾一下在操作系统课程中学到的 Linux 文件系统，从而提炼出来一个文件系统应该具有的共同点。 GFS 是一个相当复杂的系统，可以提出各种各样的「what if」问题。如果发生了这种情况，系统会不会出错？我觉得相较于死抠系统的每个细节，不如当作一次思维训练（毕竟现在 Google 已经不用 GFS 了），理解系统设计的取舍。 我觉得也要培养批判性思维吧。我时常在读论文的时候，很难找到其中的 weakness points，尤其是顶会论文。在教师讲义的指导下，可以提出一些高价值的问题。 为什么读这篇文章GFS 是一个存储系统，支撑了许多上层应用。如果我们可以让存储系统容错，那么上层应用就可以无状态。例如 k8s，如果一个 Pod 挂了，直接找另外一个 Node 启一个新的。 我发现，在数据中心里面，把容器当作一次性用品是一个常见手段。后端容器挂了？重启一个新的。ReplicaSet 副本数量不满足要求？随便新建就可以了。没有考虑与之关联的状态信息。 可是，现代服务总应该有状态吧？持久化在哪里了？数据库、文件系统里...

这节课讲线程和 RPC，与第一个实验 MapReduce 相关。在看这节课的录像前，我已经完成了实验，所以接受起来并没有很大的困难。 线程在面试的时候，经常会被问到进程和线程的区别（我字节一面的时候便被问到了）。从历史的角度来看，当计算机刚出现的时候，并没有线程，只有进程。进程是调度的基本单元。 但进程的问题是：太重、无法利用多核，以及不能共享内存。当然，多进程是可以利用多核的，但是毕竟太重，而且共享内存是个问题。所以线程出现了，在一个进程中存在多个线程，每一个线程是程序执行的一个执行流，相对轻量（不用额外管理页表等内核结构），而且可以共享内存。 具体的细节，在后文展开吧。 为什么用 Go 语言课程的实验全部使用 Go 语言，这也是我为什么会选择这门课程。之前尝试挑战过 Stanford CS144 的计算机网络，基于现代 C++。对于我这个 C with STL 的选手来说，并不是非常习惯。 而 Go 语言相对简单的多，而且，是云原生的标准语言，Docker、Kubernetes、etcd、Terraform 以及 Prometheus 等都用 Go 语言开发。从我个人的职业发...

序这个暑假开个新坑，学习一下分布式系统。 之前和 AI 聊过很多次，关于我的兴趣，所谓的「大规模复杂系统的稳定性」，其实想想，本质上就是传统的分布式系统。毕竟，分布式系统这个领域考虑的问题之一就是系统的容错，包括可用性和从错误中恢复。 MIT 6.824 是一门研究生核心课程，以论文和实验为核心，讲述分布式系统的抽象与实现。我想，在大三升大四的阶段，学习这样一门课比较合适，因为已经掌握了绝大多数本科水平的计算机知识。 网站上有疫情时期课程录像，可以学习。但不知道会不会把坑填完，慢慢来吧。 Intro什么是分布式系统首先，讨论什么是分布式系统。它的核心是四个关键词： 许多 通过网络连接 协作的 计算机 既然是分布式系统，自然有许多机器。这些机器之间需要连接，才能组成一个系统，因此网络出现在其中。它们需要相互合作来达成任务，否则，就是孤岛，没有系统什么事了。最后，组成分布式系统的是一群计算机。 为什么需要分布式系统人们构建分布式系统出于以下几个目的： 将物理分隔开的机器连接起来，达成共享的目的（如多拷贝的集群文件系统）； 通过并行提升处理速率（人多力量大）； 容错（防止单点故障...

问题表述最近需要连接到课题组的服务器做实验，这是台老服务器，之前曾经发生过挖矿事件，所以特意装了很古老的系统：Ubuntu 18.04。这个版本已经过了支持期限，同时也不被 Remote SSH 支持。 具体来说，Remote SSH 无法连接到这个服务器的原因是，服务器的 glibc 版本太低，其他的依赖均符合要求。 由于这个服务器很多人共用，我又是组里的编外人员，用的是别人的账号。即使因为权限管理混乱使得我有 sudo 权限，但最好不要使用它。 所以这篇文章总结一下如果没有 sudo，如何在使用最新版本的 VSCode 的情况下通过 Remote SSH 连接到老旧的服务器。 题外话。自从大模型越来越强大，我知乎的阅读数据也越来越差。不过我自己也早就不在知乎查找问题的答案了，所以数据下降无可厚非。就当作是给大模型的语料吧。 解决首先按照官方文档的说明，查看最标准的做法是什么。 官方文档有两步： build sysroot; 让 VSCode Server 在安装过程中使用 sysroot 中的依赖。 所以其实重要的地方是第二步，如果我从一个高版本的 Linux 中把 ...

思想今天看最后一部分，杂项。这一板块的内容没有统一的处理方式，更像是脑筋急转弯。类似于数学卷子上的开放式题目或者超纲题目。看一看，涨涨见识吧。 题目31. Next Permutation下一个排列数。给我们一个数组，让我们找出按照字典序（从小到大），下一个排列数是谁。 比如，[1, 2, 3] 的下一个排列数是 [1, 3, 2]，就像比 123 大的下一个数是 132 一样。 123456789101112131415161718192021222324class Solution {public: void nextPermutation(vector<int>& nums) { int n = nums.size(); // find desc array edge int i = n - 2; while (i >= 0 && nums[i] >= nums[i + 1]) { i--; ...

思想看看矩阵。矩阵是一种特殊的场景，二维数组。所以我觉得这种题目更多是练习 vector<vector<int>> 的各种 API 操作。有些解法没做过，真的很难想。 题目48. Rotate Image将图形顺时针旋转 $90^{\circ}$。 123456789101112131415161718class Solution {public: void rotate(vector<vector<int>>& matrix) { int m = matrix.size(), n = matrix[0].size(); for (int i = 0; i < m; i++) { for (int j = i + 1; j < n; j++) { swap(matrix[i][j], matrix[j][i]); } } ...

思想前缀树，一种多叉树。用来方便地存储字符串，用途包括自动补全等。 题目208. Implement Trie (Prefix Tree)这题让我们实现前缀树，完成插入、查找、查找前缀的方法。 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253class Trie {private: struct TreeNode { bool isEnd; TreeNode* children[26]; TreeNode() { isEnd = false; memset(children, 0, sizeof(children)); }; }; TreeNode* root;public: Trie() { root = new TreeNode(); ...

思想今天看看堆。堆是一种特殊的二叉树，分成最大堆和最小堆。最大堆中，树根是最大的元素；最小堆中，树根是最小的元素。在 C++ 中用堆，可以用优先队列，它的底层是堆实现，同时提供了一些常见的方法，使得我们可以把它当作堆来处理。 当遇到第 k 大，或者反复取最值的题目，或许堆是一个不错的考虑。 题目215. Kth Largest Element in an Array这题让我们找出一个数组中第 k 大的元素。 12345678910111213141516class Solution {public: int findKthLargest(vector<int>& nums, int k) { priority_queue<int, vector<int>, greater<int>> pq; for (int num : nums) { pq.push(num); if (pq.size() > k) {...

思想看看链表吧。链表算是数据结构中很基础的一类题目，我也刷过很多遍，这应该是第三遍，没什么好说的。如果穿越回去，再让我做数据结构的期末题，我想，应该不会很有难度。我依稀记得，当时的期末是个合并有序链表的题，嗐，不过是 Leetcode Easy 而已。 题目2. Add Two Numbers这题给了链表组成的两个数字，靠头部的是低位。让我们给这两个数做加法运算。 1234567891011121314151617181920212223242526272829class Solution {public: ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) { int carry = 0; ListNode dummy(0); ListNode* curr = &dummy; while (l1 || l2 || carry) { int sum = carry; if (l1) &#...

思想今天开图论。Hot 100 里的图论比较基础，不是很全面。大概涉及到了搜索和拓扑排序。如果要学习最小生成树或者最短路径，或许还要再补补课。不管怎样，图论是一个具有很广泛研究对象的学科，和二叉树一样，只是个背景板。所以，见招拆招。 题目200. Number of Islands这题给了个二维数组，分别用 0 和 1 表示大海和小岛。连成一片的 1 认为是一个小岛，问小岛的数量是多少。 12345678910111213141516171819202122232425262728293031323334353637class Solution {private: void dfs(vector<vector<char>>& grid, int i, int j) { int m = grid.size(), n = grid[0].size(); // not island or invalid pos if (i < 0 || i >= m || j < 0 ...