背景

其实想些这篇博客已经很久了，这篇博客的内容其实来源于之前在微店工作期间，公司内部做的技术分享中讲到的Linux同步机制，其中提到了Linux文件锁的内容，一直想找时间记录下来，但是一直都没有动笔，时隔三年之久之后，还是希望能够记录一下之前学到的内容，顺便复习一下。

文件锁类型

Linux操作系统下，想要对一个文件加锁，一般有两种方式，一种是 flock，另外一种则是 fcntl，这两种锁的区别可以总结为下表：

背景

在近期做股票个性化推荐的时候，我们利用协同过滤来计算用户可能喜欢点击的股票，目前的做法是先离线算好数据，然后写入到user profile服务中，整体过程都比较简单。由于GIL的存在，我用了multiprocessing这个包方便调用多进程模块进而加快写入的速度。为了能够在运行的过程中给自己一些提示信息，每写入1000条数据就希望能够打印一条日志，整体思路很简单，最开始使用的是print，但是发现print在多进程的时候，会丢失一部分日志，怀疑是缓冲区的原因造成的，执行的时候，用python -u来执行可以解决这个问题，就更怀疑是缓冲区的问题了，但是没有细揪，而且我还是希望能够得到能够基于时间滚动的日志，所以还是决定采用自带的logging库。在使用库的过程中就发现，很多日志都是没办法输出的，所以一直在寻找各种解决办法，下面记录一下解决过程。

背景

最近遇到一个算法题，题目如下：

题目描述:
对输入的单词进行字典序排序输出：
字典序定义

1. 单词中字母比较不区分大小写，两个单词先以第一个字母作为排序的基准，如果第一个字母相同，就用第二个字母为基准，如果第二个字母相同就以第三个字母为基准。依此类推，如果到某个字母不相同，字母顺序在前的那个单词顺序在前。
2. 当一个短单词和一个长单词的开头部分都相同（即短单词是长单词从首字母开始的一部分），短单词顺序在前。
3. 字母大小写不同的相同单词，只输出一次。

输入描述:
不超过255个字符中,单词间用空格进行分隔，为简单起见，单词不包含连字符，无其它标点符号
输出描述:
输出排序后的单词，单词之间用空格隔开（最后不带空格），重复的单词只输出一次。
示例
输入: Hello hello world
输出: Hello world

背景

一直以来，多线程编程是一个程序员必须知道的一部分，在通常的编程中，一般不会出现需要多线程的时候，直接新建一个线程去做一件事，因为创建线程是一个相对来说比较费时的操作，所以很多程序都会在刚开始运行的时候创建好一个线程池，这样就可以在下次要使用的时候直接申请使用了，那么怎么实现一个线程池呢？

实现分析

要实现一个线程池，要实现一个线程池，一般要从下面几个方面入手：

• 线程池到底是什么
• 如何从线程池中获取一个线程来运行一个任务
• 当任务完成的时候，空闲的线程在做什么
• 当任务比线程池中的线程多的时候，应该怎么处理

简单的代码实现

下面简单写一下线程池实现的代码，同时会在代码中加入一些注释，方便更好的理解线程池是如何实现的。

这篇文章主要是记录一下，在做头条的红包支付系统的过程中，用kafka做消息队列时，如何设计一个可以重试的消费机制

这个方式已经在线上运行了很长的时间，但是后续总觉得这种实现方式不算很好，所以就在网上找到了一篇文章，也是介绍如何构造一个重试队列，而且正好跟我的想法相同，所以就打算把我自己的想法写下来

背景

今年春节的时候，今日头条旗下的产品进行了分别进行了抢红包、百万英雄等活动，用户在活动中获取到的钱能够体现到各自的银行卡中，其中有一个重要的环节就是如何知道用户在我们部门代付出去的钱是否已经成功或失败。在项目中，我们采用了 回调 的方式进行通知。即收到付款完成的回调通知后，我们会再通过回调的方式通知业务方，由于前期考虑到数据量会很大，特别是大年三十的时候回出现高峰期，所以在整个项目中使用了kafka作为消息队列来使用(其实从我的理解来看，kafka作为消息队列并不是一个完美的解决方案，但是考虑到公司内部kafka比较稳定，而且不想在项目中引入更多的依赖项目，所以选用了kafka)

问题

在使用kafka的时候，由于我们需要通知业务方，所以考虑到业务方可能会出现大问题，所以我们暂定了一个规则，重试三次通知业务方，每次间隔十分钟，如果三次都失败则认为失败，中间任意一次成功都可以认为是成功。这个规则就引入了我们今天要讨论的问题，由于kafka不支持延迟消息，那么怎么保证能够做到间隔十分钟通知一次用户呢？

解决方案

kafka简介

kafka是一个分布式流式平台，它通常被用作构建一个实时的数据流平台，但是得益于topic的持久化，它也被用作消息流存储来处理历史数据，为了改进kafka的扩展能力，kafka持久化一个topic的时候，会用一个或者多个分区(partition)来进行存储。kafka的partition的底层是一个只能增加(append-only)的文件，使用这样一个简单的结构可以极大的增加系统的吞吐能力。

简单的重试机制

最简单的重试机制是我们可以在一个线程中处理，如果没有到需要处理的时候，则进行sleep，伪代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

func consumeMessageWithSimpleRetry() {
    for {
        message, ok := <- kafkaConsumer.Message()
        if !ok {
            return
        }

        processed := false
        for !processed {
            err := process(message)
            if !err {
                time.Sleep(waitPeriod)
                processed = true
            }
        }
    }
}

这边博客主要记录一下搭建vps的过程，用于后续搭建vps时能够快速上手

System Required

系统要求：本教程在Centos 7下面经过测试和验证，保证能够使用

Shadowsocks-server

下载 shadowsocks-libev

1
2
3
4

VERSION="3.1.3"
wget "https://github.com/shadowsocks/shadowsocks-libev/releases/download/v${VERSION}/shadowsocks-libev-${VERSION}.tar.gz"
tar -zxvf shadowsocks-libev-${VERSION}.tar.gz
cd shadowsocks-libev-${VERSION}

安装依赖包

1
2
3

yum install epel-release -y
yum update
yum install gcc gettext autoconf libtool automake make pcre-devel asciidoc xmlto c-ares-devel libev-devel libsodium-devel mbedtls-devel rng-tools jitterentropy-rngd -y

编译安装

1

./configure && make && make install

背景

最近在逛微博的时候，看到了一个关于fork这个函数的题，如下：

1
2
3
4
5
6
7
8
9
10
11

#include <stdio.h>
#include <unistd.h>
    
int main()
{
    fork();
    fork();
    fork();
    printf("hello\n");
    return 0;
}

问题是这段程序执行后，最终会打印多少条hello？

这个题对很多人来说都是非常简单的，但是我还是进行了实验，在Ubuntu14.04 + clang++3.5 上进行了测试，结果显示是 8 条，那么为什么是8条呢？

概率检索模型(Probabilistic Retrieval Model)

前面我们提到了向量空间模型(VSM)，这里我们来学习一个不同的模型来设计Ranking函数–概率检索模型，在概率检索模型中，我们基于document与query的相关性来定义Ranking函数，换一句话，我们假设有一个二元随机变量 $R$，document与query的相关度用 $f(q, d)$表示，则概率模型为:
$$f(d,q)=p(R=1|d,q)， R \in {0,1}$$
在VSM中，我们假设document和query都是Vector，但是在这里我们把它们假设成观察到的随机变量，所以这里的检索问题就变成了估计相关性的概率问题了。

在这一类模型中，有很多种不同的模型，其中一个经典的模型最终产出了我们在VSM中学过的BM25，因为BM25实际上更像是一个VSM，这一次我们主要讨论概率空间模型的一个子类–language model，特别是我们将会讨论到 Query Likelihood Retrieval Model，query似然检索模型是高效的概率模型之一，还有另外一种叫做Divergence-from-randomness model的，这个模型最后也变成了一个叫做PL2的函数，这也是一个高效的检索模型。

在前面的几个博客中，我们谈到了许多的信息检索方法以及不同的Ranking方法，那么什么样的方法是最好的呢？为了回答这个问题，我们就需要对这些检索方法和Ranking方法进行比较，这就意味着我们需要来评估这些方法了。

为什么要进行评估

前面我们已经给了一个理由，我们需要使用评估的方式来决定哪种检索方法是最好的，这对我们提升我们自己的知识非常重要，如果不评估的话，我们就不知道一个新的idea是否比老的更好。在前面的博客中我们谈到了文本检索的问题所在，并把文本检索与数据库检索进行了对比，我们认为文本检索是一个基于经验(Empirically defined)的问题，所以哪个检索系统能够有更好的表现就必须由用户来判断，也就是说检索系统的评估依赖于用户，这是一个非常有挑战的问题，因为：

• 如何让用户来对系统进行评估
• 对不同的系统我们怎样做到公平的评估

文本检索实现

前面我们讲到了VSM模型，接下来我们说一说搜索引擎中文本检索方式的简单实现！

搜索引擎在实现的时候主要有两个比较大的挑战

• 存储大容量的数据
• 能够快速对一个query进行相应，同时能够服务多个query的并行查询

下图是一个典型的文本检索系统(Text Retrieval System)的系统架构