引言

图灵机是计算理论的基石，它提供了一种抽象的计算模型，帮助我们理解计算过程和算法。在这篇博客中，我们将一起探讨如何使用Python实现一个简单的图灵机。这个实现将包括图灵机的核心组件：纸带（Tape）、读写头（Head）、状态寄存器（StateRegister）、转移函数（TransitionFunction）以及图灵机本身。

1. 纸带（Tape）

首先，我们定义纸带类。纸带上的每个单元格可以包含一个符号，我们使用Python的字典来模拟这个无限长的纸带。

1
2
3
4
5
6
7
8
9
10

class Tape:
    def __init__(self):
        self.cells = {}
        self.blank_symbol = '0'

    def read(self, position):
        return self.cells.get(position, self.blank_symbol)

    def write(self, position, symbol):
        self.cells[position] = symbol

2. 读写头（Head）

读写头负责在纸带上移动并读写符号。它知道当前位置，并能执行左移、右移、读取和写入操作。

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

class Head:
    def __init__(self, tape):
        self.position = 0
        self.tape = tape

    def move_left(self):
        self.position -= 1

    def move_right(self):
        self.position += 1

    def read(self):
        return self.tape.read(self.position)

    def write(self, symbol):
        self.tape.write(self.position, symbol)

3. 状态寄存器（StateRegister）

状态寄存器用于存储图灵机的当前状态。

1
2
3
4
5
6
7
8
9

class StateRegister:
    def __init__(self):
        self.current_state = None

    def set_state(self, state):
        self.current_state = state

    def get_state(self):
        return self.current_state

4. 转移函数（TransitionFunction）

转移函数定义了图灵机在不同状态和读写头读到的符号时的行为。

1
2
3
4
5
6
7
8
9

class TransitionFunction:
    def __init__(self):
        self.transitions = {}

    def add_transition(self, current_state, current_symbol, new_state, new_symbol, direction):
        self.transitions[(current_state, current_symbol)] = (new_state, new_symbol, direction)

    def get_transition(self, current_state, current_symbol):
        return self.transitions.get((current_state, current_symbol), None)

5. 图灵机（TuringMachine）

最后，我们将所有组件组合到图灵机类中，并实现运行方法。

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

class TuringMachine:
    def __init__(self):
        self.tape = Tape()
        self.head = Head(self.tape)
        self.state_register = StateRegister()
        self.transition_function = TransitionFunction()

    def run(self):
        while True:
            current_symbol = self.head.read()
            current_state = self.state_register.get_state()
            transition = self.transition_function.get_transition(current_state, current_symbol)
            if transition is None:
                break
            new_state, new_symbol, direction = transition
            self.head.write(new_symbol)
            if direction == 'L':
                self.head.move_left()
            elif direction == 'R':
                self.head.move_right()
            self.state_register.set_state(new_state)

示例运行

1
2
3
4
5

tm = TuringMachine()
tm.state_register.set_state('start')
tm.transition_function.add_transition('start', '0', 'halt', '1', 'R')
tm.run()
print(tm.tape.cells)

在这个例子中，图灵机从起始状态开始，在读到符号’0’时写入’1’并向右移动，然后进入停止状态。运行结果应该是 {0: '1'}。

结论

通过这个简单的实现，我们深入了解了图灵机的基本组件以及它们之间的交互。使用Python编写图灵机的实现，使我们能够直观地理解计算理论的基本概念，同时也展示了面向对象编程在建模复杂系统中的优越性。这只是计算理论和图灵机的冰山一角，希望这篇博客能激发你对计算机科学基础的更深层次探索。

从约束视角看待后端架构

以下代码是一个使用FastAPI和Langchain的异步流处理的例子。它创建了一个FastAPI应用，该应用有一个POST路由/stream，该路由接收一个消息，然后使用Langchain的ChatOpenAI模型生成一个响应流。
完整实例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69

import asyncio
import os
from typing import AsyncIterable, Awaitable

import uvicorn
from dotenv import load_dotenv
from fastapi import FastAPI
from fastapi.responses import StreamingResponse
from langchain.callbacks import AsyncIteratorCallbackHandler
from langchain.chat_models import ChatOpenAI
from langchain.schema import HumanMessage
from pydantic import BaseModel

# Two ways to load env variables
# 1.load env variables from .env file
load_dotenv()

# 2.manually set env variables
if "OPENAI_API_KEY" not in os.environ:
    os.environ["OPENAI_API_KEY"] = ""

app = FastAPI()


async def send_message(message: str) -> AsyncIterable[str]:
    callback = AsyncIteratorCallbackHandler()
    model = ChatOpenAI(
        streaming=True,
        verbose=True,
        callbacks=[callback],
    )

    async def wrap_done(fn: Awaitable, event: asyncio.Event):
        """Wrap an awaitable with a event to signal when it's done or an exception is raised."""
        try:
            await fn
        except Exception as e:
            # TODO: handle exception
            print(f"Caught exception: {e}")
        finally:
            # Signal the aiter to stop.
            event.set()

    # Begin a task that runs in the background.
    task = asyncio.create_task(wrap_done(
        model.agenerate(messages=[[HumanMessage(content=message)]]),
        callback.done),
    )

    async for token in callback.aiter():
        # Use server-sent-events to stream the response
        yield f"data: {token}\n\n"

    await task


class StreamRequest(BaseModel):
    """Request body for streaming."""
    message: str


@app.post("/stream")
def stream(body: StreamRequest):
    return StreamingResponse(send_message(body.message), media_type="text/event-stream")


if __name__ == "__main__":
    uvicorn.run(host="0.0.0.0", port=8000, app=app)

以下是代码的主要部分的解释：

send_message函数：这是一个异步生成器函数，它接收一个消息，然后使用Langchain的ChatOpenAI模型生成一个响应流。这个函数使用了一个AsyncIteratorCallbackHandler来处理模型的回调，并使用一个后台任务来运行模型的生成器函数。每当生成器产生一个新的令牌时，这个函数就会产生一个新的服务器发送的事件。

StreamRequest类：这是一个Pydantic模型，用于验证流请求的请求体。它只有一个字段message，表示要发送的消息。

/stream路由：这是一个POST路由，它接收一个StreamRequest对象，然后调用send_message函数来生成一个响应流。它使用StreamingResponse来返回这个流，媒体类型设置为text/event-stream，这是服务器发送的事件的标准媒体类型。

主函数：如果这个脚本作为主程序运行，它将使用uvicorn来启动FastAPI应用。

concepts

• connection pool

• multiplexing

• borrowing

• pinning

• target group

• targets

• transaction level reuse
  若不使用autocommit,只有在rollback或者commit时才会复用连接

青年：为什么需要索引?

大师：这是为了加速数据查找.

青年：嗯。。

大师：没懂？打个比方，你查字典是怎么查的？你会从头到尾一页一页翻吗？不，你会按拼音，偏旁，或者笔画，找到字所对应的页码，然后再直接翻到对应的页码上.

青年：有点懂了

大师：你经常用MySQL，你知道MySQL使用什么数据结构吗？

青年：好像是叫B+树，但为啥叫B+树啊？

大师：B+树是一种改进的B树。B树的B是Balanced的缩写意思，Balanced Tree，就是平衡树。平衡意思是它会保持树的左右两边节点数量差距尽量小。

青年：B+树相对B树改进在哪里呢？

大师：问得好。
一是在于所有叶子节点位于同一层，并且并且通过指针连接成一个有序链表
二是非叶子节点不存储数据，只存储索引信息。
三是B+树每个节点可以存储多个关键字，这些关键字按生序排列

青年：为什么要做这些改进，有啥作用？

大师：是这样的。
第一，叶子结点连成链表，是为了让范围查询更高效。
第二，非叶子结点不存数据，这样索引就更适合放到内存里，
第三，节点可以存储多个关键字，那么树的高度就会相对低一点，查询的耗时跟树的高度是相关的，树的高度越低，查询性能就越好

青年：原来如此。但是我知道这些有什么用呢？

大师：别急呀。作为程序员你经常需要优化SQL的性能。要优化性能，理解B+树的特点是关键所在。
你听我慢慢道来。MySQL数据表是一颗使用主键搭建起来的B+树。叶子结点上存放着表的所有行。
其他索引也是B+树，只不过叶子结点上存放的是主键。

大师：当一个query使用了索引时，往往先是从索引找到主键，再根据主键去主表查具体数据行
根据主键去主表查具体数据行的这个操作叫做回表，它往往很慢，因为主表上的具体数据行存储再磁盘上而不是内存里。
磁盘的一次随机寻址大约1千万纳秒，而一次内存寻址只需要100纳秒，相差十万倍。
所以回表是要尽量避免的。如何避免呢，当query所需要查的列就在索引中时，就不需要回表了。这样的请求就会很高效

所以SQL优化的关键点就是

1. SQL只查所需要的列
2. 针对对高频的查询，设计索引，使得所需要的列全部都在索引中

青年：现在我明白了，为啥经常说禁止使用select *。原来是为了方便发现高频请求，以便设计索引。

做需求收集有很多方法论，我个人认可的有以下这些

• 用例 （Use Case)
• 用户故事 (User Story)
• 用户故事地图 (User Story Mapping)
• 影响地图 (Impact Mapping)

用例

用例是一种识别、澄清和组织系统需求的方法论。它一般配合UML图一起使用，是一种有效的需求沟通工具。它是最早出现的需求收集分析的方法论。
以下是一个用例图的示例

graph LR
A[Actor] --> B((Use Case 1))
A --> C((Use Case 2))
B --> D{System}
C --> D
D --> E[Actor]
D --> F[Actor]

用例技术非常有用，但是也存在局限性
使用use case收集分析需求的局限性包括以下几点：

1. 复杂性：使用use case方法需要详细描述系统的各种功能和交互，特别是在大型系统中，可能会导致大量的use case，难以管理和维护。

2. 语言障碍：use case通常使用专业的技术术语和领域特定的语言，可能会导致与非技术人员的沟通困难。

3. 详细度：use case需要详细描述系统的各种功能和交互，可能会导致过度关注细节而忽视整体需求。

4. 可变性：use case通常是一次性的文档，一旦编写完成，很难进行修改和更新，随着需求的变化，可能会导致use case的失效。

为了解决use case方法的局限性，用户故事（user story）方法产生了。

用户故事

用户故事是一种简洁的描述用户需求的方法，强调与用户的对话和协作，而不是详细的文档。用户故事通常以如下形式描述：作为一个[角色]，我想要[目标]，以便[原因]。用户故事易于理解和记录，并且可以随时修改和更新，以适应需求的变化。此外，用户故事注重用户价值和用户体验，更侧重于用户需求的核心，而不是过度关注技术细节。因此，用户故事方法更加适用于敏捷开发等快速迭代的开发方法。

用户故事是敏捷开发中的一种需求描述技术，它用简洁的语言描述用户的需求和期望，以便开发团队能够更好地理解用户的需求并提供相应的解决方案。

用户故事通常包含以下要素：

1. 角色：用户故事描述了一个特定的用户或角色，例如“作为一名购物者”或“作为一名管理员”。

2. 目标：用户故事描述了用户想要实现的目标或期望的结果，例如“我希望能够浏览商品并添加到购物车”或“我希望能够管理用户账户”。

3. 动作：用户故事描述了用户采取的行动或操作，例如“我点击商品列表并浏览商品详情页面”或“我登录系统并更新用户信息”。

4. 价值：用户故事描述了用户从实现目标中获得的价值或好处，例如“通过浏览商品并添加到购物车，我能够方便地购买所需的商品”或“通过管理用户账户，我可以更好地控制和保护我的个人信息”。

用户故事通常以以下格式进行描述：作为一个[角色]，我想要[目标]，以便[价值]。开发团队可以根据用户故事来制定开发计划、优先级和测试方案，以确保最终产品符合用户的需求。

用户故事很棒，但是当你有成百上千个用户故事卡片，如何得到一个全局视图而不迷失在细节碎片中呢？如何为这些需求规划优先级呢？

为了解决这些问题，用户故事地图方法诞生了

用户故事地图

用户故事地图是一种工具，用于可视化和组织用户故事。它是一个二维图表，横轴表示用户故事的优先级，纵轴表示用户故事的主题或功能。用户故事地图按照用户的需求和优先级进行排列，使团队可以清晰地了解整个产品的功能和用户需求。

用户故事地图有以下几个用途：

1. 产品规划：用户故事地图可以帮助团队理解产品的整体功能和用户需求，以便更好地进行产品规划和决策。

2. 优先级排序：通过用户故事地图，团队可以根据用户故事的优先级进行排序，确定哪些功能是最重要的，以便在开发过程中优先实现。

3. 交流和沟通：用户故事地图可以作为一个视觉化的工具，帮助团队成员之间更好地交流和沟通，共享对产品功能和用户需求的理解。

4. 追踪进展：通过用户故事地图，团队可以清晰地了解每个用户故事的状态和进展情况，以便及时调整和管理开发进度。

用户故事地图很好，但它是一种相对重量级的规划，同时它并没有产品带来的商业价值给予足够的考虑。在增长黑客方法论的引领下，
一种更适应快迭代，更强调组织业务目标的方法论产生了

影响力地图

影响力地图是一种轻量级的、协作的规划技术，适用于希望通过软件产品产生巨大影响的团队。它基于用户交互设计、结果驱动的规划和思维导图。影响力地图帮助交付团队和利益相关者可视化路线图，解释交付成果如何与用户需求相连接，并传达用户结果与更高级别组织目标之间的关系。

影响力地图包括以下要素：

1. 组织目标：描述了组织希望实现的最终目标或结果。

2. 用户结果：描述了用户希望通过软件产品实现的具体结果或价值。

3. 交付成果：描述了软件产品或功能的具体交付成果。

4. 任务：描述了为实现交付成果而需要执行的具体任务或行动。

graph LR
A[Organizational Goal] --> B(User Outcome)
B --> C(Deliverables)
C --> D(Tasks)

总结
Use Case解决了清晰结构化描述需求的问题
User Story鼓励更多直接沟通，而不是通过文档沟通
User Story Mapping用于组织和规划大量的User Story
Impact Mapping强调业务目标的达成，只做对组织目标有益的事

高并发问题解决基本思路

高并发问题的本质是有限的资源应对大量的请求

一般存在以下解决方向

• 提高单位资源处理能力

• 增加资源

• 减少请求

• 提升处理速度

以下分别讨论

提高单位资源处理能力

一般是采用更高性能的硬件或者更有针对性的硬件驱动。例如，使用固态硬盘替换机械硬盘以提升MySQL的处理能力

增加资源数量

单位资源的处理能力总是受制于物理极限的天花板，并且高性能硬件往往更加昂贵。因此通过增加资源数量来提升处理能力才是主流。这种方式也称为水平扩展。水平扩展要能实现并非无代价，代价就是无状态性。要满足无状态性通常有三种方案

• 相同session路由到同一服务器

• 集中session存储

• 只用token存储session状态

减少请求

减少请求一般有三种思路

• 错峰

• 排队

• 限流

处理速度

请求到一般处理流程是

前端访问->前置条件校验->业务处理->数据存储->结果响应返回。

根据经验，前置条件校验，业务处理，数据库IO是耗时关键

前置条件校验优化思路：

• 缓存：前置条件校验一般是查询多，解决思路是使用更近的存储，代价是需要维护缓存一致性。

业务处理优化思路：

• 异步：有些处理并不是实时需要，如通知等，可以异步处理

• 并行：业务处理往往包含许多步骤，假如有些步骤没有依赖关系，可以并行处理，根据情况采用合适的并发模型。假如有依赖关系也可以尝试重新设计数据模型消除依赖。并行的代价是提升编码复杂性，需要小心设计避免资源竞争问题

数据库IO优化思路：

• 缓存：尽量使用缓存分担数据库查询压力

• 分散：例如MySQL主从模式分散请求流量

• 异步持久化：需要极致性能的场景不要直接磁盘访问。通过kafka之类的消息中间件异步持久化

计算机科学领域随处可见的标度对称性

什么是标度对称性

标度对称性是指一个系统的形态、规律等特征在尺度缩放变化时会保持不变。

例如，人体整体形态是“一分五”结构，即人体躯干分出双手双脚和头，而人的手和脚也是“一分五”结构

在计算机科学领域也随处可见这种特征。

例如

• 多级存储结构：客户端->CDN->数据中心，API->缓存->数据库，CPU->Cache->内存。

• 事件总线：系统层的事件总线，应用编程中的事件驱动模式，CPU中的I/O总线

• 派生数据模式：现代后端系统中，常常使用写入主数据库之后触发其他派生数据库的同步更新，例如Elasticsearch，MonogoDB。而MySQL数据库中，写入主表会触发索引、视图的更新。

为什么会有这种特征？我认为有两种角度的解释。

第一种解释是，虽然计算机系统的规模一直在扩大，但本质都是在解决计算、存储、数据、通信的问题，所以问题系统规模扩大后，微观构件的组成规律在宏观层面仍然适用。

第二种解释是，计算机在历史上是自底向上发展起来的，早期硬件工程师的想法影响了做软件的工程师，软件工程师的想法又影响了设计企业级系统的架构师。现在我们常用的一些技术概念我猜都是来源于早期硬件设计，例如“写逻辑”的说法来源与逻辑电路。TCP中的多路复用概念可能来源于硬件中的multiplexer，前端和后端的概念可能是来源于编译系统，编译系统中前端指的是词法分析，语法分析，语义分析，后端指的是生成中间代码、优化、生成目标代码。

我最喜欢的三个技术面试问题

• 一台关闭的个人电脑，从按下电源键到显示桌面之间发生了什么，请尽可能详细地描述

• 在个人电脑桌面，从双击chrome浏览器图标到显示浏览器默认页之间发生了什么，请尽可能详细地描述

• 在浏览器地址栏敲下baidu.com，从按下回车到看到百度首页之间发生了什么，请尽可能详细地描述

第一个问题可以考察候选人对计算机体系结构理解，从硬件到操作系统，所有类型的工程师都适用。

第二个问题可以考察候选人对操作系统工作原理以及应用软件的理解，客户端开发工程师必问，对于移动端开发者还可以进一步替换成具体的Android或者iOS手机

第三个问题可以考察候选人对网络协议，后端服务，以及浏览器工作原理的理解，对于后端工程师可以进一步深挖对服务端的理解，对前端工程师可以进一步深挖对浏览器的理解

具体考察过程中，我会记下他回答中使用的技术概念，然后就他提出的技术概念继续深挖他对这个技术概念的理解，在他的回答中再记下他提到的新的技术概念，然后再深挖。用一种类似深度优先遍历的顺序让他遍历他的知识面。最终他能够正确解释的概念数量基本上就可以代表他的计算机基础知识水平

这几个问题的好处是能够比较量化地度量工程师的水平，大部分工程师基本都能说出一些大的过程步骤，但是真正基础扎实的工程师，能够更加深入解释各种技术细节。

我也会隔一段时间，问自己这些问题，看看我能解释的深入程度是否比上次更加深入了，以此检验我的知识是否有增长。这些问题就像七龙珠里外星人使用的战斗力侦测AR眼镜，让战斗力这种模糊概念可以做量化度量了。

坦白说，我觉得自己对计算机仍然知之甚少，要学的东西太多了。

代码要写三遍

• 第一遍，捕获需求

• 第二遍，优化设计

• 第三遍，调优性能

“捕获”需求而不是“实现”需求

因为“实现”需求，假设的是需求都是确定的，但现实是，需求往往是在落地过程中得到反馈逐步确定的。而“捕获”需求，从一开始就接受需求是不确定的，往往在实现落地过程中会有细节变化。“捕获”需求要求工程师要从技术可行性，逻辑完备性，变更风险控制角度来审视需求，发现和确认遗漏捕获的细节。写技术方案应该被看作一种捕获需求的工具。同时要求工程师采用一种最小化反馈周期的做事方式。一个采用这种做事哲学的工程师，他懂得用最小可交付粒度来切割它的工作，如果是一个后端工程师，那么他应该按前端接口的粒度去交付，尽快获得来自前端和测试的反馈。而不是所有工作堆积到临近deadline才一起交付，然后面对一大波返工。

捕获需求阶段不过度考虑优化设计

这里讲的优化设计是指不改变功能前提下，提升代码可读性，降低程序员认知负担，使得后续维护和扩展更方便。捕获需求阶段不过度考虑优化设计。因为第一，不确定的需求，不提前做优化设计。第二，即使是比较确定的需求，如果后续修改可能性比较小也没必要过度优化设计。我的经验是，如果代码不是很难理解，可以容忍他上生产环境，接受一波来自用户的检验后，再思考如何优化设计。

设计糟糕的代码会让你的同事难受

一个团队一起工作，一些基本的设计原则要遵守的，一个团队最好要使用同一种框架来做事，因为每个人都不可能维持一年365天24小时可用，分分钟都有可能要求别的同事去改你的代码，如果你的代码让人很难读懂，那么他只能在你休假的时候打电话去打扰你了，这样大家都不好过。所以代码上线后，也不要忘了持续优化设计。

可读性 > 性能

长期来看，几乎所有的代码都是要改的。容易被读懂的代码更容易被修改而得到性能优化。性能优化要如果没有数量级的变化就不知道为它牺牲可读性。因为硬件性能一直以摩尔定律的速度提升，所有的软件不做任何改变都能从硬件升级中获得红利。

测试防护网是一切的基本

既然代码注定要被多次修改，那么如何保证不破坏原有功能呢？答案只有一个：自动化测试。我们常说为了短期快速完成而走的临时方案是技术负债，长期来看，几乎所有的代码在刚刚诞生的那一刻都是负债。那么有没有什么代码在他诞生的一刻就是资产呢？如果有，我觉得就是自动化测试。只要代码后续还需要改，自动化测试就是保障我们不改出毛病的保障。设计良好的自动化测试，无疑会占据我们的开发时间，但它能保证我们的进步都是可叠加的。结硬寨，打呆仗。这是我喜欢的做事哲学。