tags: Learning English shape ʃeip be in great/good shape stay/keep in (good) shape 英语表示次数范围 five times a month once two weeks 英语表示尺码 loose /luːs/ 松的 tight /tait/ 紧的 what/how about 提议 What/How about some coffee? What/How about you? 穿衣：try on/take off/put on n.: try on sth I’d like to try on the shoes. pron.: try sth. on I’d like to try them on. think of 认为 sth. 怎么样 What do you think of my new shirt? What does she think of me? would like 委婉表示想要 do sth. I’d like to see some casual shirts. ...

tags: Learning English 副词 adv/adverb 是指在句子中表示行为或状态特征的词，用以修饰动词、形容词、其他副词或全句，表示时间、地点、程度、方式等概念。 副词可分为：时间副词、频率副词、地点副词、方式副词、程度副词、疑问副词、连接副词、关系副词、表顺序的副词以及表完成的副词。 频率副词 always usually often sometimes about 表示大约大约修饰数量。 形容词 adj 形容词后缀 -ful helpful useful thankful 形容词后缀 -ed interested excited 形容词后缀 -ing interesting exciting 动词 verb 情态动词 modal verb. can(could)/may(might)/must/need/to/shall(should)/will(would). 动名词 形式 v.-ing 动词的名词化。 语法：名词 语意：动词 形变规则 特殊 1 -e：去 e 加 ing live -> living give -> giving 特殊 2 短元音 + 一辅音：重复最后一个字母加 ing jog -> jogging swim -> swimming 常规：直接加 ing do -> doing study -> studying 词性 I usually go swimming. ...

tags: Learning English 通过动词变化来区分时间 通过动词变化来区分时间。 I am walking in the rain. 正在 I will walk in the rain. 将要 I walk in the rain sometings. 一般状态、重复、常态 一般现在时 表示： 当前的一般状态 重复或习惯动作 am/is/are（be 动词）：是，处于某状态 do/does（实意动词）：具体动作 (X): am/is/are + do/des 一般现在时不能 am/is/are 跟动词实意动词 一般现在时第三人称单音形规则 tags: 英语读音规则 一般现在时第三人称单数动词需要变形，需要注意变形后的读音 清对清 /s/ works helps 非清则浊 /z/ lives sees goes does /dʌz/ 组合 /dz/ /ts/ meets needs 近似音 -es /iz/ introduces fishes 现在进行时 当前正在发生的事情或动作，表示当前正在发生或者近将来。 I’m looking for a shirt. I’m not taking it off. Everyone is wearing the same shirt on the street! 结构 am/is/are doing ...

tags: Linux Linux I/O Linux I/O 演进 阻塞式：read()/write() 非阻塞式：select()/poll()/epoll()，不支持文件 I/O Thread Pool Direct I/O（数据软件）：绕过 page cache 异步 IO（Linux AIO）：早起进支持文件 I/O，近期支持了 epoll 支持非文件 I/O Linux io_uring [译] Linux 异步 I/O 框架 io_uring：基本原理、程序示例与性能压测 对比 Linux AIO： 重新设计实现真正的是不。 支持任何类型的 I/O：cached files、direct-access files 甚至 blocking sockets。 灵活、可扩展：基于 io_uring 能够重写 Linux 的每个系统调用。 原理及核心数据结构：SQ/CQ/SQE/CQE 每个 io_uring 实例都有两个环形队列，在内核和应用程序之间共享： 提交队列：submission queue（SQ） 完成队列：completion queue（CQ） 这两个队列： 都是单生产者、单消费者，size 是 2 的幂次； 提供无锁接口（lock-less access interface），内部使用内存屏障做同步（coordinated with memory barrers）。 使用方式： 请求 应用创建 SQ entries（SQE），更新 SQ tail； 内核消费 SQE，更新 SQ head 完成 内核为完成一个或多个请求创建 CQ enries（CQE），更新 CQ tail； 应用消费 CQE，更新 CQ head 完成事件（completion events）可能以任意顺序到达，到总是与特定的 SQE 相关联的。 消费 CQE 过程无需切换到内核态 带来的好处 支持批处理 支持文件 I/O 系统调用：read、write、send、recv、accept、opentat、stat、专用的一些系统调用，如 fallocate 不再局限于数据库应用 应对现在硬件架构：将硬件架构本身作为一个网络（多核多 CPU 是一个基础网络、CPU 之间是一个网络、CPU 和磁盘 I/O 之间又是一个网络） 三种工作模式 中断驱动模式（interrupt driven）：默认模式。可通过 io_uring_enter() 提交 I/O 请求，然后直接检查 CQ 状态判断是否完成。 ...

tags: Emacs,LSP 如果无法正常补全三方库，应该是 bloop 服务没有正常启动： 创建 ~/Library/Caches/org.scalameta.metals/bsp.trace.json 开启跟踪 查看项目目录下 metals.log

tags: DDD,《领域驱动设计》读书笔记 领域基础模式 模式：UBIQUITOUS LANGUAGE 在同领域专家、开发人员和项目管理沟通的过程中建立并使用 UBIQUITOUS LANGUAGE，，并在模型实现时依然使用 UBIQUITOUS LANGUAGE 来让设计与沟通相一致（中文语境下稍显困难），UBIQUITOUS LANGUAGE 让知识消化后直接驱动变更模型。 应用 UBIQUITOUS LANGUAGE 需要大声的建模。 模式：MODEL-DRIVEN DESIGN 严格按照模型来编写代码，让模型与实际系统相结合。 不再分离「分析模型」和程序设计，而是寻求一种能够满足这两方面需求的单一模型。 工具：面向对象编程语言、UML等。 更好的支持 UBIQUITOUS LANGUAGE. 模式：HANDS-ON MODELER 开发设计和模型设计紧密合作，避免模型设计者不参与编写和程序设计者不参与模型设计。 每一个开发人员都必须不同程度的参与模型讨论并且与领域专家保持联系，模型设计者及时通过 UBIQUITOUS LANGUAGE 与接触代码的人及时交换关于模型的想法。 领域模式构造块 模式：LAYERED ARCHITECTURE 分层架构是实现 DDD 的基础，分层架构将不同的层次的实现分开，自上倒下应分为： 用户界面层 应用层 领域层（模型的精髓） 基础设施层 核心在于要将领域层单独出来实现 MODEL-DRIVEN DESIGN，对业务进行建模封装业务规则。调用规则也只能自上而下的调用，不能反向调用。 领域层（或模型层）分离出来之后使得模型足够丰富，结构足够清晰，可以捕捉到基本的业务知识，并有效的使用这些知识。 模式：ENTITY 用于跟踪对象的状态，有唯一标识符，在系统中是可变的，两个对象是否一个通过唯一标识来判断，不是靠它们的属性定义。 模式：VALUE OBJECT 区别与 ENTITY ，没有唯一标识，仅记录状态，一般设计为不可变用于共享 VALUE OBJECT，两个对象是否一个通过对象属性的值来判断。 模式：SERVICE 没有状态，但又需要建模的对象，只包含动作。用于一些不适合建模为对象的领域概念。 与领域概念相关的操作不是 ENTITY 或 VALUE OBJECT 的一个自然组成部署 接口是根据领域模型的其他元素定义的。 操作是无状态的 模式：MODULE（或 PACKAGE） 根据对象的意义划分领域模型，低耦合高内聚。按照模式或者对象生命周期或者其他方式划分都是错误的。 模式：AGGREGATE 划分模型边界，统一对关联模型的创建、修改、复制和销毁。一般选定一个 ENTITY 对象作为 AGGREGATE 的「根」，同时对事务应用一组规则： ...

案例 Airflow powers AI。 Airflow SSO 接入 公司 SSO 系统不是基于开源标准，而是一套自定义的方式，目前网上没有成熟的解决方案，通过查看 Flask-AppBuilder 和 Airflow 的代码发现可以扩展 flask_appbuilder.security.views.AuthRemoteUserView 并通过自定义的 SecurityManager 指定 authremoteuserview 来实现，去掉具体 SSO 逻辑后的代码如下： from urllib.parse import urlencode from urllib.parse import urljoin import requests from flask import flash from flask import redirect from flask import request from flask_appbuilder.baseviews import expose from flask_appbuilder.security.views import AuthRemoteUserView try: from airflow.www.security import AirflowSecurityManager except ImportError: AirflowSecurityManager = None __version__ = "0.1.0" AUTHORIZE_URL = "https://example.com/sso/login" ACCESS_TOKEN_URL = "https://example.com/sso/check" class AuthComCasView(AuthRemoteUserView): def _get_redirect_uri(self): return urljoin(request.host_url, self.appbuilder.get_url_for_login) def get_authorize_params(self): return { "callback": self._get_redirect_uri(), } @expose("/login/") def login(self): token = request.args.get("token") if not token: params = self.get_authorize_params() redirect_uri = u"{}?{}".format( AUTHORIZE_URL, urlencode(params), ) return redirect(redirect_uri) data = self.exchange_token(token) if data["status"] < 0: flash("Invalid Token", "info") return "Invalid token" # Set REMOTE_USER to let user login request.environ["REMOTE_USER"] = data["username"] return super().login() @staticmethod def get_token_params(token): return { "token": token, } def exchange_token(self, token): data = self.get_token_params(token) return requests.get(ACCESS_TOKEN_URL, params=data).json() if AirflowSecurityManager is not None: class ComCasAirflowSecurityManager(AirflowSecurityManager): authremoteuserview = AuthComCasView 然后在 Airflow 的 webserver_config.py 中应用就行: ...

tags: Bigdata Spark 编程语言选择 毋庸置疑，Python 应该是最简单也是大部分的选择，但是如果有依赖那么将要付出额外的心智负担（Spark 管理 Python 依赖）。 JVM 语言的依赖组织方式则具有天然的优势，可以将依赖（排除 Spark 生态之后）都 bundle 进 Jar 包里。 其中 Scala 兼具简单和 JVM 的优势，但是它「不流行」。 Spark Driver & Executor Driver 执行 spark-commit 客户端，创建 SparkContext 执行 main 函数。 Executor Spark Worker 上的线程 See also: Understanding the working of Spark Driver and Executor Cluster Mode Overview Spark 代码执行 我在配置 Spark 的时候就在好奇，从观察上看部分代码应该是执行在 Driver 上部分代码会执行在 Executer，这让我很好奇。 但是我通过学习 Spark RDD 学习到了一些知识。 以下代码是在 Executor 上执行的： Transformations 和 Actions 是执行在 Spark 集群的。 传递给 Transformations 和 Actions 的闭包函数也是执行在 Spark 集群上的。 其他额外的代码都是执行在 Driver 上的，所以想要在 Driver 打印日志需要上使用 collect： ...

tags: Programming Language Scala 学习资源 Scala Book Scala 这么好的语言为什么不流行 HN：Scala 为什么不流行 Reddit：Scala 为什么不流行 结论：Java 人才更多且成本更低。 Scala 工具 sbt sbt new 无法处理替换过的 SSH 会导致 Auth fail，一个 workaround 就是手动 clone 项目然后： sbt new file:///path/to/template.g8 sbt 国内加速 ~/.sbt/repositories: [repositories] local nexus-aliyun:https://maven.aliyun.com/nexus/content/groups/public nexus-aliyun-ivy:https://maven.aliyun.com/nexus/content/groups/public/, [organization]/[module]/(scala_[scalaVersion]/)(sbt_[sbtVersion]/)[revision]/[type]s/[artifact](-[classifier]).[ext] typesafe: https://repo.typesafe.com/typesafe/ivy-releases/, [organization]/[module]/(scala_[scalaVersion]/)(sbt_[sbtVersion]/)[revision]/[type]s/[artifact](-[classifier]).[ext], bootOnly Unique Scala Rust from Scala Rust 和 Scala 有很多想通的地方，Rust 应该从 Scala 借鉴了很多： 可变量和不可变量 模式匹配 Trait 内置类型 val b: Byte = 1 val x: Int = 1 val l: Long = 1 val s: Short = 1 val d: Double = 2.0 val f: Float = 3.0 字符串拼接 Python 也支持类似的 f-string 语法，在 Scala 中是 s-string 语法。 ...

https://inkscape.org/

SVG SVG 绘制工具

Graphviz 教程 https://www2.eecs.berkeley.edu/Pubs/TechRpts/2013/EECS-2013-176.pdf Graphviz Examples https://graphviz.org/gallery/ Graphviz 绘制思维导图 Graphviz Online Tools 一个手绘风格的在线绘图工具：https://sketchviz.com/new Gaphviz Playground：http://magjac.com/graphviz-visual-editor/

tags: LeetCode https://leetcode.com/problems/validate-binary-search-tree/ /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: bool isValidBST(TreeNode* root) { if (root == nullptr || (root->left == nullptr && root->right == nullptr)) { return true; } if (root->left != nullptr && root->right != nullptr) { if (root->left->val >= root->val || root->right->val <= root->val) { return false; } return isValidBST(root->left) && isValidBST(root->right); } if (root->left != nullptr) { if (root->left->val >= root->val) { return false; } return isValidBST(root->left); } if (root->right != nullptr) { if (root->right->val <= root->val) { return false; } return isValidBST(root->right) ; } return true; } }; 无法处理子树元素大于上一层的问题。中序遍历排序： ...

tags: LeetCode,backtracking https://leetcode.com/problems/path-sum-ii/ /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: vector<vector<int>> pathSum(TreeNode* root, int targetSum) { vector<vector<int>> r; if (root == nullptr) { return r; } if (root->left != nullptr) { auto left = pathSumSide(root-> left, root->val, targetSum); if (left.size() > 0) { left.insert(left.begin(), root->val); r.push_back(left); } } if (root->right != nullptr) { auto right = pathSumSide(root->right, root->val, targetSum); if (right.size() > 0) { right.insert(right.begin(), root->val); r.push_back(right); } } return r; } vector<int> pathSumSide(TreeNode* node, int sum, int targetSum) { vector<int> r; sum += node->val; if (node->left == nullptr && node->right == nullptr) { if (sum == targetSum) { r.push_back(node->val); return r; } } if (node->left != nullptr) { auto ret = pathSumSide(node->left, sum, targetSum); if (ret.size() > 0) { ret.insert(ret.begin(), node->val); return ret; } } if (node->right != nullptr) { auto ret = pathSumSide(node->right, sum, targetSum); if (ret.size() > 0) { ret.insert(ret.begin(), node->val); return ret; } } return r; } }; 失败的错误用例: ...

tags: LeetCode https://leetcode.com/problems/path-sum/ 递归版 /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: bool hasPathSum(TreeNode* root, int targetSum) { if (root == nullptr) { return false; } return pathSum(root, 0, targetSum); } bool pathSum(TreeNode* node, int sum, int targetSum) { sum += node->val; if (node->left == nullptr && node->right == nullptr) { if (sum == targetSum) { return true; } } if (node->left != nullptr) { if (pathSum(node->left, sum, targetSum)) { return true; } } if (node->right != nullptr) { if (pathSum(node->right, sum, targetSum)) { return true; } } return false; } }; 测试用例 ...

tags: LeetCode 79. Word Search class Solution { public: bool exist(vector<vector<char>>& board, string word) { backtracking(board, word, 0, 0); return res; } private: string track; bool res = false; enum Direction { right, down, up, left, }; /** * @param dir: 0: right, 1: down, 2: up, 3: left */ void backtracking(vector<vector<char>>& board, string word, int row, int col) { if (track == word || res) { res = true; return; } for (int i = row; i < board.size(); i++) { for (int j = col; j < board[i].size(); j++) { auto directions = get_next_directions(board, i, j); if (directions.size() == 0) { return; } for (auto d: directions) { int r, c; track.push_back(board[i][j]); std::tie(r, c) = next_char_pos(board, row, col, d); if (word.find(track) == 0) { backtracking(board, word, r, c); } track.pop_back(); } } } } vector<Direction> get_next_directions(vector<vector<char>>& board, int row, int col) { vector<Direction> r; if (col < board[row].size() - 1) { r.push_back(right); } if (row < board.size() - 1) { r.push_back(down); } if (row > 0) { r.push_back(up); } if (col > 0) { r.push_back(left); } return r; } tuple<int, int> next_char_pos(vector<vector<char>>& board, int row, int col, Direction dir) { switch(dir) { case right: col++; break; case left: col--; break; case up: row--; break; case down: row++; break; } tuple<int, int>r(row, col); return r; } }; 失败的用例： ...

《领域驱动设计》读书笔记

tags: 计划读的书,HTTP,High Performance,Network 在线： https://hpbn.co/ source: Grigorik, Ilya. High-Performance Browser Networking. Beijing ; Sebastopol, CA: O’Reilly, 2013. “Good developers know how things work. Great developers know why things work.”

预写日志（write-ahead log，WAL），也称为重做日志。 一个仅支持追加修改的文件，每个 B-tree 的修改必须先更新 WAL 然后再修改数本身的页。 当数据库在崩溃后恢复时，该日志用于将 B-tree 恢复到最近一致的状态。

AMQP/JMS 风格的消息代理 将单个消息分配给消费者，消费者在成功处理后确认每条消息。消息被确认后从代理中删除。 适合作为一种异步 RPC。 RabbitMQ ActiveMQ HornetQ Qpid TIBCO Enterprise MEssage Service IBM MQ Azure Service Bus Google Cloud Pub/Sub 多个消费者 负载均衡式 每一条消息都只被传递给其中一个消费者。 扇出式 每条消息都被传递给所有消费者。 确认和重新传递 为了确保消息不会丢失，消息代理使用确认：客户端必须在处理完消息后显式的告诉代理，以便代理可以将其从队列中移除。 如果客户端的连接关闭或超时，而代理没有收到确认，则认为消息未处理，因此它将消息重新传递给另一个消费者。 消息顺序性 即使消息代理试图保留消息顺序（标准要求），负载均衡与重新传递的组合也不可避免地导致消息被重新排序。 基于日志的消息代理 代理将分区中的所有消息分配给相同的消费者节点，并始终以相同的顺序发送消息。 通过分区机制来实现并行（写在多个磁盘上突破磁盘带宽），消费者通过检查他们处理的最后一条消息的偏移量来跟踪进度。 代理将消息保存在磁盘上，因此如果有必要，可以回退并重新读取旧消息。 代表性的有： Kafka Amazon Kinesis Streams Twitter DistributedLog 基于日志的消息存储 参照 LSM-Tree 和 B-tree 的 WAL，可以使用相同的结构来实现消息代理： 生产者通过将消息追加到日志的末尾来发送消息，消费者通过依次读取日志来接收消息。 如果消费者读到日志的末尾，它就开始等待新消息被追加的通知。 通过对日志进行分区突破单个磁盘所能体能的带宽吞吐上线。 代理为每个消息分区分配了一个单调递增的序列号或偏移量，保证了分区内的消息完全有序。 消费者偏移量：记录哪些消息已经被处理，减少 ACK 开销 磁盘空间：分段，定期删除 消费者跟不上生产者：增加 LAG 报警 重新处理消息：重置偏移量

tags: TCP,High Performance Browser Networking 原文链接：https://hpbn.co/building-blocks-of-tcp/。 Overview The 4th version of RFC 675, and final two seperate RFCs: RFC 791 - Internet Protocol(IPv4) RFC 793 - Transmission Control Protocol TCP provides: Effective abstraction. A reliable network running over unreliable channel. Hiding most the complexity of network communication: retransmission of lost data, in-order delivery, congestion control and avoidance, data integrity, and more. Three-Way Handhsake Sequence numbers are important for keep in-order delivery, and they are picked randomly from both sides for security reasons. ...

tags: Network

阻止生产者发送更多的消息。使用背压的场景： Unix 管道 TCP

发送事件流 消息系统 生产者速度比消费者快：丢弃消息、将消息缓存在队列、激活背压。 节点崩溃或者暂时历险，是否会有消息丢失？ 生产者与消息系统之间的直接消息传递 UDP 组播：广泛应用于金融股票 无代理消息库：ZerroMQ 和 nanomsg StatsD 和 Brubeck 使用 UDP 传递消息 HTTP、RPC 接口 消息代理 参见：AMQP/JMS 风格的消息代理。 也称消息队列。 消息对比与数据库对比 多个消费者 确认和重传机制 分区日志 参见： 基于日志的消息代理。 数据库与流 保持系统同步 变更数据捕获 变更数据捕获（Change Data Capture，CDC）记录了写入数据库的所有更改，并以可复制到其他系统的形式来提取数据。 如果在写入时立即将更改作为一种流来发布，那么 CDC 就更有趣来。 实现变更数据捕获 解析复制日志，并将解析的内容发送到事件流中进行 replay。 初始快照 replay 日志占用空间过大，需要进行截断，截断之前的进行初始快照保存。 日志压缩 参考哈希索引。 对变更流的 API 支持 数据库开始支持将变更流作为标准接口。 事件溯源 一种在领域驱动设计社区中开发的技术，与 CDC 最大的区别在于事件溯源在不同抽象层次上应用了将所有对应用程序状态的更改保存为更改事件日志： CDC 中：应用程序以数据可变方式来操纵数据库，从数据库中提取较低级的变更日志，从而确保从数据库提取写入顺序与实际写入顺序相匹配。写入数据库的程序不需要知道 CDC 正在发生。 事件溯源中：应用程序的写入逻辑是基于写入事件日志的不可变事件构建的。事件存储仅支持追加，不鼓励甚至禁止更新或删除操作。事件旨在反映在应用程序级别所发生的事情，而不是低级别的状态改变。 专门的数据库 Event Store 来支持使用事件溯源的应用程序。 从事件中导出当前状态：真正对用户有意义 命令和事件 命令经过校验后转化为事件。 状态，流与不可变性 流处理 事件中的数据写入数据库、缓存、搜索索引或类似的存储系统，提供给客户端查询。 通过某种方式将事件推送给用户，如电子邮件、短信等。 处理一个或多个输入流产生过一个或多个输出流。 流处理适用场景 复杂事件处理 复杂事件处理（Complex Event Processing，CEP）尤其适用需要搜索特定的事件模式。 实现：Esper、IBM Info Sphere Streams、Apama、TIBCO StreamBase 和 SQLstream。 ...

原文链接：Why MapReduce is making a comeback。

tags: Rust 原文：When Zero Cost Abstractions Aren’t Zero Cost

基于 Hadoop 分布式文件系统使用 SSTables 和 LSM-Tree 实现随机访问的 OLTP 数据库。

MPP 数据库 Gamma 数据库机器 Teradata Tandem NonStop SQL

tags: 分布式,一致性,Clock Synchronization,Multicast source: https://signalsandthreads.com/clock-synchronization/ Electronic Oscillator: Computer itself to Dervie its Notion of Time Computer’s clock are based on a 1 MHz electronic oscillator circuit, that is oscillating at some frequency, and driving an interrupt. So the operating system can use it to derive its notion of time. It helps computer to keep the time correct. But a bad oscillator could be influenced by the heat of CPU, like compiling Linux kernel, etc. A really high-quality oscillator would be really expensive. So most computers come with fairly bad oscillators. ...

tags: Bigdata bucketed map join

tags: Bigdata Hadoop Distributed File System MapReduce MapReduce shuffle 按照 reducer 分区，排序和将数据分区从 mapper 复制到 reducer。（令人困惑的术语，并不完全与洗牌一样，在 MapReduce 中其实没有随机性）。 MapReduce 的分布式执行 Hadoop MapReduce 并行化基于数据分区实现： 输入：通常是 HDFS 中的一个目录。 分区：每个文件或文件块都被视为一个单独的分区。 处理：每个分区由单独的 map 任务来处理。 每个 mapper 都会尽量实现计算靠近数据。 代码复制：JAR 文件。 Reduce 任务的计算也被分隔成块，可以不必与 mapper 任务数量相同，MapReduce 框架使用关键字的哈希值来确保具有相同关键字的键值对都在相同的 reduce 任务中处理。 键值对必须进行排序，排序是分阶段进行的： 每个 map 任务都基于关键字哈希值，按照 reducer 对输出进行分块。 每个分区都被写入 mapper 程序所在的本地磁盘上的已排序文件，参见 SSTables 和 LSM-Tree。 reducer 与每个 mapper 相连接：MapReduce 调度器会在 mapper 写入经过排序的输出文件后，通知 reducer 开始从 mapper 中获取输出文件，框架进行 MapReduce shuffle。 reducer 任务从 mapper 中获取文件并将它们合并在一起，同时保持数据的排序。不同 mapper 使用相同的关键字生成记录，会在合并后的 reducer 输入中位于相邻的位置。 reducer 可以使用任意逻辑来处理这些记录，并且生成任意数量的输出记录。记录被写入分布式文件系统中的文件。 MapReduce 工作流调度器 Oozie Azkaban Luigi Airflow Pinball 对比分布式数据库 MapReduce 中的并行处理和并行 join 算法已经在十多年前所谓的大规模并行处理（MPP）数据库中实现了。 ...

tags: Rust

tags: 分布式

tags: Bigdata,分布式文件系统 与网络连接存储（NAS）和 存储区域网络（SAN）架构相比，HDFS 基于无共享原则，无需定制硬件和特殊网络基础设施（光纤）。 HDFS 创建了一个庞大的文件系统，来充分利用每个守护进程机器上的磁盘资源。 HDFS 包含一个在每台机器上运行的守护进程，并会开放一个网络服务以允许其他节点访问存储在该机器上的文件。 名为 NameNode 的中央服务器会跟踪哪个文件块存储在哪个服务器上。 考虑容错，文件快块复制到多台机器上，或者像 Reed-Solomon 代码中这样的纠删码方案（类似 RAID，但无需特殊硬件）。 提供很好的扩展性，配合商业硬件和开源软件，可以运行在上万台机器，容量达几百 PB。 计算靠近数据 只要有足够的空闲内存和 CPU 资源，MapReduce 调度器会尝试在输入文件的副本的某台机器上运行 mapper 任务。

tags: Emacs M-x life RET 康威生命游戏（Conway’s Game of Life）

tags: 技术 数据库作为一个长期发展的技术，但是在中国相对处于一个起步阶段，相关人才比较少。近年能够看得到的技术： TiDB 分布式关系型数据库 TDengine 面向 IoT 的 OLAP 数据库 相关创业公司： 神策 https://zhuanlan.zhihu.com/p/396433354

MapReduce MapReduce 与分布式文件系统 MapReduce 就像分布在上千台机器上的 Unix 工具。 MapReduce 作业通常不会修改输入，除了输出外没有任何副作用。 MapReduce 作业在分布式文件系统上读写。（Unix 工具 stdin、stdout），如 HDFS（Hadoop Distributed File System)等（GlusterFS、QFS、Amazon S3、Azure Blob 和 OpenStack Swift）。 MapReduce 作业执行 MapReduce 是一个编程框架，可以使用它编写代码处理 HDFS 等分布式文件系统中的大型数据集。 要创建 MapReduce 作业需要实现两个回调函数： mapper 和 reducer （另请参阅 MapReduce 查询）: Mapper: 每个输入记录都会调用一次，从输入记录提取任意数量的关键字和值（可以为空），不保留任何状态，可以独立处理。 Reducer: MapReduce 框架使用 Mapper 生成的键值对，收集同一个关键字的所有值，并使用迭代器调用 reducer 以使用该值的集合。 Reducer 可以生成输出记录。 MapReduce 分布式执行 参见 Hadoop 的 MapReduce 的分布式执行。 MapReduce 工作流 将 MapReduce 作业链接到工作流是非常普遍的，作业的输出作为下一个作业的输入。通过目录名隐式的完成： 第一个作业必须配置将其输出写入 HDFS 中指定目录； 第二个作业必须配置读取相同的目录名作为输入。 目前已经开发了处理依赖管理的 MapReduce 工作流调度器。 Reduce 端的 join 与分组 批处理的背景下讨论 join，主要解决数据集内存在关联的所有事件。 假设 join 两张表：用户和活动事件。 ...

tags: LeetCode

tags: LeetCode https://leetcode.com/problems/valid-sudoku/ <- high -- low -> +------------------- wow(row(i):0,col(j):0) 0 -> [ 0010, 0010 ] | 1 -> [ 0000, 0000 ] | 2 -> [ 0000, 0000 ] | | +--------------- wow(row(i):0,col(j):1) 0 -> [ 0010 | 1 = 0011, 0010 ] | | 1 -> [ 0000, 0000 | 1 = 0001 ] | | 2 -> [ 0000, 0000 ] | | | | +----------- wow(row(i):0,col(j):2) 0 -> [ 0011 | 3 = 0100, 0010 ] | | | 1 -> [ 0000, 0001 ] | | | 2 -> [ 0000, 0000 | 3 = 0100 ] +---+---+---+ | 2 | 1 | 3 | +---+---+---+ ----| 3 | 2 | 1 | | +---+---+---+ | | 1 | 3 | 2 | | +---+---+---+ |- wow(row(i):1,col(j):0) 0 -> [0010 | 3 = 0110, 0010] +---------------------+ 1 -> [0000, 0001 | 3 = 0101] 2 -> [0000, 0100] class Solution { public: bool isValidSudoku(vector<vector<char>>& board) { vector<int> wow(9,0); int mux1; int mux2; int mux3; int box_index; for(int i=0;i<9;i++){ for(int j=0;j<9;j++){ if(board[i][j] == '.'){ continue; } mux1 = 0x01 << (board[i][j] - '1'); mux2 = 0x01 << 9 << (board[i][j] - '1'); mux3 = 0x01 << 9 << 9 << (board[i][j] - '1'); box_index = (i/3) * 3 + j/3; if((wow[i]&mux1) != mux1 && (wow[j]&mux2) != mux2 && (wow[box_index]&mux3) != mux3){ wow[i] = wow[i]|mux1; wow[j] = wow[j]|mux2; wow[box_index] = wow[box_index]|mux3; } else{ return false; } } } return true; } };

tags: 分布式共识,技术概念

tags: LeetCode source: https://leetcode.com/problems/combination-sum-ii/ LeetCode: 39. Combination Sum 的进阶。元素不在唯一且每一个元素只能出现一次。对结果进行排序然后通过 set 对结果进行去重： class Solution { public: vector<vector<int>> combinationSum2(vector<int>& candidates, int target) { sort(candidates.begin(), candidates.end()); backtracking(candidates, 0, 0, target); vector<vector<int>> r; for (auto t : res) { r.push_back(t); } return r; } private: set<vector<int>> res; vector<int> track; map<int, bool> visited; void backtracking(vector<int>& condidates, int start, int n, int target) { if (n == target) { res.insert(track); return; } if (n > target) { return; } int c = 0; int sz = condidates.size(); for (int i = start; i < sz; i++) { c = condidates[i]; track.push_back(c); backtracking(condidates, i + 1, n + c, target); track.pop_back(); } } }; 以下测试用例无法通过： ...

tags: LeetCode source: https://leetcode.com/problems/combination-sum/ class Solution { public: vector<vector<int>> combinationSum(vector<int>& candidates, int target) { backtracking(candidates, 0, target); return res; } private: vector<vector<int>> res; vector<int> track; void backtracking(vector<int> & candidates, int n, int target) { if (n == target) { res.push_back(track); return; } // this is new if (n > target) { return; } for (auto c : candidates) { track.push_back(c); backtracking(candidates, n + c, target); track.pop_back(); } } }; 问题：会有不同顺序但是元素相同的数组，如何快速高效的进行过滤？ ...

tags: LeetCode,backtracking source: https://leetcode.com/problems/n-queens-ii/ 参见：LeetCode: 51. N-Queens

tags: Algorithm,Brute Force Approach