- 博客(117)
- 收藏
- 关注
RSS订阅原创 LevelDB源码解析(5) WriteBatch
你也可以通过我的独立博客 —— www.huliujia.com 获取本篇文章简介LevelDB的官方注释是这么介绍WriteBatch的：WriteBatch holds a collection of updates to apply atomically to a DB如何保证原子性可能需要看完对WriteBatch的使用才能理清楚，这里只能确定一个WriteBatch对象可以包含多条更新记录（插入/删除），支持批量写入。WriteBatch的很多操作是通过辅助类来实现的，辅助类会直.
2021-10-02 09:18:04
496
1
原创 LevelDB源码解析(4) MemTable
原文作者：胡刘郏原文链接：https://www.huliujia.com/blog/c5e8646cb4765da867b3936b2bae62843bded7e5简介MemTable是LevelDB在内存中的缓存库。用户写入数据时，LevelDB会先把数据写入到MemTable中。如果MemTable写满了，就会新建一个MemTable进行写入。后台再异步把旧的MemTable压缩写到磁盘上。因为旧的MemTable不允许写入了，所以也被称为Immutable MemTmable。MemTa.
2021-10-02 09:09:25
334
原创 LevelDB源码解析(3) 变长编码
你也可以通过我的独立博客 —— www.huliujia.com 获取本篇文章背景LevelDB在内存中存储key、value时，最后是以单值形式存储到一个跳跃表中的，跳跃表我们在上一篇文章LevelDB源码解析之SkipList(跳跃表）聊过了。这里主要想谈一下，LevelDB是如何把key、value编码到一个单值里面的，顺带分析一下为什么要这样做。思考题如何把一对key、value编码到一个单值中呢？很自然的一个想法是用冒号做分割，存储成key:value这种格式。但是如果key或者val.
2021-04-18 21:59:20
902
原创 LevelDB源码解析(2) SkipList(跳跃表)
你也可以通过我的独立博客 —— www.huliujia.com 获取本篇文章背景SkipList是LevelDB的MemTable使用的底层存储结构，LevelDB实现了一个支持泛型的跳跃表。本文不会具体介绍跳跃表的数据结构，如果读者不了解跳跃表的原理、实现，可以先看一下跳跃表（Skiplist）从原理到实现SkipList的对外接口Level对外只提供了3个接口，构造、插入、查找。没有提供删除接口，这个主要是因为LevelDB不会对SkipList的元素进行删除操作，整个SkipList的存.
2021-04-18 21:40:11
520
原创 跳跃表（SkipList）从原理到实现
你也可以通过我的独立博客 —— www.huliujia.com 获取本篇文章数组与链表数组和链表是非常基础的两种数据结构，链表每次查找都需要从头结点开始线性遍历，时间复杂度是O(n)。而数组通过维护元素顺序可以使用二分查找，查找的时间复杂度是O(lg(n))。查找效率方面数组完胜链表。但是由于数组插入或删除元素时必须要移动所有受影响的节点，所以时间复杂度是O(n).并且数组的长度是固定的，当空间不够时需要重新分配内存。而链表插入和删除元素只需要改动少量指针即可，时间复杂度是O(1)。但是因为插入.
2021-04-12 08:44:17
624
原创 LevelDB源码解析(1) Arena内存分配器
你也可以通过我的独立博客 —— www.huliujia.com 获取本篇文章背景LevelDB中需要频繁申请和释放内存，如果直接使用系统的new/delete或者malloc/free接口申请和释放内存，会产生大量内存碎片，进而拖累系统的性能表现。所以LevelDB实现了一个Area内存分配器来对内存进行管理，以保证性能。Arena的核心思想LevelDB本身不再直接申请和释放内存，需要内存时，向Arena申请。内存释放由Arena负责，LevelDB不再关心内存释放问题。Arena从系统申.
2021-04-12 08:39:49
709
原创 C/C++中的断言(assert与static_assert)
你也可以通过我的独立博客 —— www.huliujia.com 获取本篇文章assert简介assert被C/C++用来判断某些条件是否成立，比如判断指针类型的大小sizeof(void*)是否大于8,或者判断malloc返回的指针是否为null。assert的函数申明如下：void assert( int expression );如果expression为0，即false，assert就会把函数名，源代码文件名、当前行号发送给标准错误stderr，然后调用abort()终止执行。什么.
2021-04-06 09:27:17
3733
原创 内存乱序与C++内存模型详解
你也可以通过我的独立博客 —— www.huliujia.com 获取本篇文章内存乱序内存乱序指的是内存操作出现乱序，CPU缓存、编译器优化、处理器指令优化等都会改变内存顺序，造成内存乱序。学习内存顺序容易陷入了一个误区，因为内存顺序是和CPU架构、编译器息息相关的，想要去深入理解CPU缓存怎么导致内存乱序的，编译器优化和处理器指令又是怎么导致内存乱序的，很容易陷入一个又一个填不了的坑。要去了解各种编译器优化技术、了解各种CPU的指令集，甚至连ARM的v7和v8区别都去看了一下。鲁迅说过，学海无.
2021-04-06 09:25:40
893
1
原创 聊一聊原子操作
你也可以通过我的独立博客 —— www.huliujia.com 获取本篇文章先举个栗子下面的C++代码编译执行后，v的输出是多少呢？每个线程都执行了10000次v++，总共2个线程，那么v的最终结果应该是20000，结果是这样吗？#include <iostream> // std::cout#include <thread> // std::threadint v = 0;void plus(){ for(int i=0; i.
2021-04-06 09:23:46
544
原创 简易编译器实现（二）使用Bison创建语法分析器
你也可以通过我的独立博客 —— www.huliujia.com 获取本篇文章简易编译器实现（一）使用Flex创建词法分析器一文介绍了编译器的概念和七个阶段，并说明了如何使用Flex创建词法分析器。本篇文章介绍如何使用Bison创建语法分析器，并实现基本的运算能力。本文继续使用简易编译器实现（一）使用Flex创建词法分析器中提出的集合运算语言AlphaGun作为演示的例子。语法分析语法分析器使用词法分析器输出的token流作为输入，把token流转换成树状的中间表示，通常会转换成语法树，本文中使用.
2021-03-28 22:54:17
4835
1
原创 简易编译器实现（一）使用Flex创建词法分析器
你也可以通过我的独立博客 —— www.huliujia.com 获取本篇文章编译器简介编程语言是人和计算机交流的媒介，但是计算机只能理解二进制语言，编译器的工作就是把人可以理解的编程语言翻译成机器可以理解的二进制语言，即可执行文件。编译过程可以细分为7个阶段词法分析语法分析语义分析中间代码生成机器无关的代码优化代码生成机器相关的代码优化每个阶段都以上一个阶段的输出为输入，其中词法分析的输入是源代码，第7阶段的输出为最终的可执行文件。编译器使用符号表来存储和程序相关的信息，比如.
2021-03-28 22:52:43
2579
原创 内联函数(inline Function)浅析
你也可以通过我的独立博客 —— www.huliujia.com 获取本篇文章什么是内联函数内联函数(inline function)是C和C++都支持的一种语言特性，简单来说，就是在编译阶段在调用内联函数的地方直接展开函数代码，避免函数调用的开销。内联函数的优点内联函数的主要作用是避免函数调用开销，那就必须要讨论一下函数调用有哪些开销。一次函数调用的开销主要有保存和恢复现场参数传递跳转到被调用函数，以及完成执行后返回函数内部执行中产生的开销内联函数的主要优点是避免上面1、2、3.
2021-03-28 22:50:45
932
原创 学习笔记：相似度度量与协同过滤
你也可以通过我的独立博客 —— www.huliujia.com 获取本篇文章相似度度量相似度度量关注的是两个对象是否相似，相似程度是多少？比如两张图片、两篇文章、两句话、两个人的喜好的相抵程度等。为了度量相似度，首先需要将比较对象转换成实数向量，这样计算机才能够理解。对象类型不同，转换方式也不同，最终目的都是将比较对象转换成实数向量。转换成实数向量之后就可以通过计算两个实数向量的相似度来作为对象的相似度。相似度的计算方法有很多种，常见的有余弦相似度、皮尔森相关系数。余弦相似度CosineS.
2021-03-28 22:48:53
592
原创 学习笔记：信息熵与决策树
你也可以通过我的独立博客 —— www.huliujia.com 获取本篇文章信息熵什么是信息熵信息熵用于度量”预测随机变量Y的取值“的难度。信息熵越大说明Y的取值的不确定性越大，即预测难度越大。本文用H(Y)表示预测Y值的信息熵。下表为两只球队的虚拟的胜、负、平历史记录，显然预测恒大比赛结果的难度要远小于绿城。因为恒大90%都是胜场，预测恒大胜就可以了。而绿城胜、平、负的概率都是三分之一，很难预测绿城的比赛结果。这里随便变量Y就是比赛结果，显然预测恒大比赛结果（即Y的取值为胜、平或者负）的信息.
2021-03-28 22:43:54
1143
原创 [译] Linux定时任务工具crontab入门教程
你也可以通过我的独立博客—— www.huliujia.com 获取本篇文章crontab是类Unix系统最好用的工具之一，用来设置定时任务，这些定时任务也被称为“Cron Jobs”。Cron通常被用于运行定时备份、监控磁盘使用情况、定期删除不需要的文件（比如日志文件）、运行系统维护任务等。本文主要介绍crontab的基础使用，基本能覆盖大部分使用场景。crontab的基本用法 分钟(0-59) 小时(0-24) 日(1-31) 月(1-12）星期（0-7） <要执行的命令>.
2021-01-30 12:09:29
898
1
原创 Pyhon+lxml+xpath快速实现网页爬虫（比BeautifulSoup好用）
你也可以通过我的独立博客—— www.huliujia.com 获取本篇文章背景最近因为工作需要写爬虫，以前用过BeautifulSoup，所以很自然的无脑上BeautifulSoup了，不过使用过程中发现BeautifulSoup有一个致命的缺陷，就是不能支持XPath。XPath可以快速在结构化的文档（如XML，HTML）中查找、访问元素的语言，语法比正则表达式还要简单，非常容易使用。在浏览器中其中可以方便地获取任何目标元素的XPath，简单来说XPath和文件路径很像，通过文件路径可以快速定.
2021-01-30 12:04:42
776
1
原创 使用lxml.etree解析中文网页时出现乱码问题的解决办法
吐槽不得不说网络这个东西害死人，一群只会复制粘贴的瓜皮儿。 没一点有用的答案，还要写的像模像样装x这个问题折腾了一个晚上，晚上找了各种方案，都是相互抄，然而都不能解决问题，找的过程中看到一个博主发出了这样的感慨，真的深表赞同啊，鱼目混杂的内容太多了。lxml.etree.tostring 乱码的解决方案话不多说，直接show code，很简单的一个示例代码。这里的关键是to string时用utf-8编码，然后用utf-8解码。#!env python3from urllib.request
2021-01-30 12:01:28
3890
5
原创 版本控制：Git与Svn的命令对应关系
导言作为一个只用过git的童鞋，因为工作需要遇见了svn。初次见面时还很羞涩，经过了一段时间的交往，我们之间的关系突飞猛进，也成功地收到了svn的“好人卡”（这是个悲伤的故事）。所以为了让和我一样的svn新童鞋能够快速收获好人卡，整理了一下git和svn各种操作的对应关系，希望可以帮助到大家。svn简介从使用的角度来说，svn和git的最大区别是svn是集中式版本控制，svn是分布式版本控制...
2019-08-24 17:29:24
2648
原创 云服务器+Github Pages双节点托管解决博客访问速度和百度收录问题
Github Pages + Hugo 搭建静态博客介绍了如何使用Github Pages托管静态网站。使用双仓库+多路解析解决Github Pages无法被百度搜索收录的问题介绍了如何使用Coding Pages和Github Pages双仓库托管静态网站。使用云服务器+Nginx配置静态Web服务器介绍了如何使用云服务器和Nginx搭建静态web服务器托管静态网站。这三种都属于静态网...
2019-08-20 23:13:40
862
原创 使用云服务器+Nginx搭建静态Web服务器
这篇文章介绍如何使用Nginx搭建静态Web服务器（比如静态博客），并实现HTTPS访问（可选）以及Github Pages双节点托管（可选）。Nginx是一款轻量级Web服务器，也可以用作反向代理，负载平衡器 和 HTTP缓存。域名和云服务器准备本文假定你已经拥有一个域名和云服务器实例，并且域名解析已经指向了你的云服务器IP地址。如果没有的话需要购买和注册。域名注册推荐腾讯云：腾讯云-域名...
2019-05-24 09:38:43
2013
原创 Linux/MacOS批量删除文件中的^M符号
title: “Linux/MacOS批量删除文件中的^M符号”date: 2019-03-15T15:39:15+08:00draft: falsecategories: [“Linux”]tags: [“换行符”,"^M"]slug: 003841a593bc4a2741d273eb8f98e872af6cb63a在Windows系统下编辑过的文本文件通常都会在行尾留下"^M"符...
2019-05-05 22:40:43
3853
原创 VSCode查找和替换正则表达式转义字符整理
使用VSCode进行查找、替换时，经常需要用到正则表达式，一段时间不用就忘了，每次要用的时候都要耽误很多时间去查找，所以整理了一份很全的放在这里。这个其实是.NET使用的正则表达式，VSCode也是一样的，微软系的产品（比如Visual Studio等）应该都是使用这个标准的。本文只列举和翻译了常用的一些，完整内容请参照https://docs.microsoft.com/en-us/dotne...
2019-05-05 22:32:12
19851
原创 使用双仓库+多路解析解决Github Pages无法被百度搜索收录的问题
背景介绍在Github Pages + Hugo 搭建静态博客一文中，介绍了如何使用Github pages搭建个人博客。搭建博客后发现Google已经收录了，但是百度却迟迟没有收录，使用百度的“搜索资源平台-抓取诊断”功能对网站进行抓取测试发现抓取失败了，结果为403 Forbidden。出现这个错误的原因是Github屏蔽了百度爬虫的抓取。这个该怎么解决呢可选的解决方案**当百度不...
2019-05-05 21:49:49
2268
原创 Github pages + Hugo 搭建静态博客
前景提要阮一峰总结了喜欢写Blog的人，会经历三个阶段。第一阶段，刚接触Blog，觉得很新鲜，试着选择一个免费空间来写。第二阶段，发现免费空间限制太多，就自己购买域名和空间，搭建独立博客。第三阶段，觉得独立博客的管理太麻烦，最好在保留控制权的前提下，让别人来管，自己只负责写文章。在过去，进入第三阶段需要付出巨大的资金成本（要花钱请人啊。。。），Github Pages的出现，极大地...
2019-02-23 17:50:44
2486
原创 Docker基础使用
本文镜像地址本文使用的运行环境Ubuntu 16.04.5 LTS全新安装docker参考：https://docs.docker.com/install/linux/docker-ce/ubuntu/安装依赖包sudo apt-get updatesudo apt-get install apt-transport-https ca-certificates curl ...
2018-11-30 19:06:41
518
原创 使用iconv对文件批量转码
本文镜像地址Windows下中文使用的编码一般默认为GB18030，git无法识别里面的中文，在Linux和Mac上打开会出现乱码问题iconv可以对单个文件进行转码,使用方式如下：显示支持的编码iconv -l将GB18030码转为UTF-8码,并重定向到new.file中.iconv -f GB18030 -t UTF-8 old.file &amp;amp;amp;amp;amp;amp;gt; new.file-f 原编码...
2018-11-22 16:10:32
1837
原创 Linux内核学习笔记（十一）内核同步方法（自旋锁，信号量，互斥锁，完成变量，顺序锁，禁止抢占）
原子操作Linux内核提供了多种同步机制，这些机制本质上都是通过原子操作来实现的。原子操作可以保证指令以原子方式执行，不会被中途打断（中断也不会打断一个指令，处理器只有在当前指令完成后才会去处理中断）。内核提供了两套原子操作的接口，一套用于整数原子操作，一套用于进行位原子操作。这些接口的实现是和架构相关的，Linux系统支持的所有架构都实现了这些接口。大部分架构为简单的算术运算提供了原子版本的...
2018-06-09 02:18:34
2809
1
原创 Linux内核学习笔记（十）中断处理的下半部（Bottom Halve）
为什么需要下半部中断处理程序有如下局限性：中断处理程序是异步中断，被其中断执行的代码（包括别的中断处理程序）可能正在执行非常重要的任务，为了避免被中断进程停止过长时间，中断处理程序的执行应该越快越好。中断处理程序会禁用其服务的中断线（没有设置IRQF_DISABLE），这是最好的情况。最坏的情况下会禁用当前处理器上所有中断（设置了IRQF_DISABLED）。禁用中断期间，硬件设备无法...
2018-06-06 23:06:58
1726
原创 Linux内核学习笔记（九）中断和中断处理程序
中断为了对计算机的硬件（键盘，硬盘，鼠标等）进行管理，内核需要和这些硬件通信。一种方式是使用轮训（polling）的方式，这种方式周期性地查看所有硬件设备的状态并做相应处理，这会造成很多不必要的系统开销。Linux内核使用中断的方式来管理硬件设备，中断本质上是一种电信号，设备通过和中断控制器引脚相连的总线发出电信号来发出中断。中断控制器是一种控制芯片，多个设备的中断请求线同时连接到中断控制器上...
2018-06-04 23:35:49
2130
1
原创 Linux内核学习笔记（八）Page Cache与Page回写
综述Page cache是通过将磁盘中的数据缓存到内存中，从而减少磁盘I/O操作，从而提高性能。此外，还要确保在page cache中的数据更改时能够被同步到磁盘上，后者被称为page回写（page writeback）。一个inode对应一个page cache对象，一个page cache对象包含多个物理page。对磁盘的数据进行缓存从而提高性能主要是基于两个因素：第一，磁盘访问的速度...
2018-06-02 23:38:19
26500
3
原创 Linux内核学习笔记（七）系统调用
综述用户空间进程通过内核提供的一套接口和系统进行交互，这些接口让用户空间进程能够受控地访问系统资源、创建新的进程以及和其他进程通信等。受控表示用户进程不能不受限制地做任何想做的事情，这对保证系统的稳定非常关键。在Linux系统中，系统调用是除了exception和trap之外用户空间和内核交互的唯一方式。API，POSIX 和 C LibraryAPI（Application Pr...
2018-05-30 23:05:51
1376
原创 Linux内核学习笔记（六）进程调度
综述内核调度子系统负责进程调度，调度程序决定让哪个进程运行、什么时候运行、运行多久。调度程序的目标有两个：一个是最大化系统资源的利用率，一个是减少和用户的交互延迟，让用户觉得多个进程在同时运行。这两个目标是冲突的，需要做trade-off。多任务操作系统多任务操作系统指的是指可以多个进程同时交错执行的操作系统。在单处理器机器上，用户会产生有多个进程同时在不同的处理器上在同时执行的错...
2018-05-29 13:16:55
2000
原创 Linux内核学习笔记（五）进程地址空间
**# 进程地址空间简介Linux是一个虚拟内存操作系统，系统中的所有进程以虚拟方式共享内存。从一个进程的视角来看，它独占系统中所有的物理内存，并且一个进程的地址空间可以远远大于物理内存的大小。进程的地址空间由可寻址的虚拟内存组成，进程通过地址空间中的地址访问内存。一个进程可以选择和其他进程共享地址空间，这样的进程就是我们说的线程。尽管进程最多可以寻址4GB的虚拟内存（在32-bit的...
2018-05-10 10:37:25
1635
原创 Linux内核学习笔记（四）进程管理
进程简介进程（Process）是Unix操作系统最基本的抽象概念之一。进程是正在执行的程序，同时也是操作系统进行资源管理的最小单位，进程需要管理打开的文件、挂起的信号、内核内部数据、处理器状态等。线程（Thread）是进程中正在执行的程序片段，是操作系统进行调度的最小单位，一个线程指的是进程中一个单一顺序的控制流。Linux中线程只是一个特殊的进程，并没有对进程和线程进行专门的区分。进...
2018-05-09 17:10:40
2585
原创 Linux内核学习笔记（三）Block I/O层
块设备（Block Device）简介块设备是一种以块（block）为单位可以进行随机存取的硬件设备。常见的块设备有硬盘，软盘，闪存等。块设备的最小寻址单元是扇区（sector），一个扇区是2\^n个字节，512Bytes是最常见的扇区大小。内核的文件系统使用块（block）作为最小寻址单元。block的大小是sector的2\^n次方倍（n可以为0），但是不大于page size. 常见...
2018-04-27 19:55:04
14317
2
原创 Linux内核学习笔记（二）内存管理
综述本文首先介绍和内存管理相关的一些概念如page，zone，然后介绍多种获得内存的方式，最后介绍Linux的slab层（slab分配器）。页（page）页是Linux内核进行内存管理的基本单元。MMU和虚拟内存也都使用页作为基本管理单元。不同的架构有不同的页大小，绝大部分的情况是32-bit使用4KB页大小，64-bit使用8KB页大小。这意味着如果一台机器的物理内存为1GB大小，大...
2018-04-24 15:33:05
1891
原创 Linux内核学习笔记（一） 虚拟文件系统VFS
什么是VFSVritual Filesystem 是给用户空间程序提供统一的文件和文件系统访问接口的内核子系统。借助VFS，即使文件系统的类型不同（比如NTFS和ext3），也可以实现文件系统之间交互（移动、复制文件等），从用户空间程序的角度来看，VFS提供了一个统一的抽象、接口。这使得用户空间程序可以对不同类型的文件系统发起统一的系统调用，而不需要关心底层的文件系统类型。从文件系统的...
2018-04-20 17:32:20
4344
原创 VFS中的数据结构（superblock、dentry、inode、file）
VFS简介VFS的理念是使用统一的数据结构在内核中保存不同类型文件系统的信息（含操作）。VFS是一个介于用户程序和文件系统实现之间的一个抽象层，VFS既给了不同类型的文件系统支持Linux系统的公共接口，也给用户程序提供了一个统一的调用接口。VFS背后的核心idea是引入了通用文件模型（common file model），该模型其实就是Unix原生文件系统的一个镜像（这样可以在Uni...
2018-04-14 16:18:21
3114
2
原创 《C和C++程序员面试秘笈》中存在的错误
最近在复习C++面试的考点，所以购买了《C和C++程序员面试秘笈》这本书（人民邮电出版社2014.3 ISBN：978-7-115-34113-6）。书整体上是非常不错的，知识点覆盖比较全面，很符合我的需求。美中不足的是书中的错误有点多。阅读的过程中自己做了一个总结，现在贴上来供大家参考。总结的形式比较简单，仅供参考。同时限于本人的水平，总结中可能存在一些错误，欢迎指正。因为我只选择性...
2018-04-12 13:07:06
3402
9
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人