1. Agent定义

AI Agent是利用人工智能技术以实现特定目标并为用户完成任务的软件系统。它们展现出推理、规划、记忆以及一定程度的自主性，能够进行决策、学习和适应环境 。这些Agent能够同时处理包括文本、语音、视频、音频和代码在内的多模态信息，并具备对话、推理、学习和决策的能力 。

Agent和Workflow的区别：Workflow是把固定的流程和逻辑固化成工作流，处理流程是固定的；而Agent则在运行时确定执行方案、调用工具、反思，具备较大的自主性。

理解AI Agent的这些高级能力，如自主性和复杂决策制定，对于将其与如简单的聊天机器人或基础AI助手等更简单的自动化系统区分开来至关重要。这种区分也解释了为何AI Agent需要更为复杂和精细的基础设施支持。

Agent的基础设施，应该覆盖Agent从研发到部署、运营等整个生命周期。

2. AI Agent的核心功能组件

AI Agent的强大功能源于其内部多个核心组件的协同工作。这些组件共同构成了Agent的感知、思考、决策和行动能力。

2.1. “大脑”：核心LLM、推理与规划

AI Agent的“大脑”是其智能的核心，主要由大型语言模型（LLM）、推理机制和规划模块构成。

• 核心LLM：作为中央决策者，LLM负责执行推理、规划和语言生成等核心认知任务 。它处理输入信息，进行推断，并生成与上下文相关的输出。可以通过任务特定的提示、角色扮演模板或领域知识来配置LLM，以增强其处理特定任务的能力 。
• 规划模块：该模块使Agent能够洞察复杂的工作流程，并生成结构化的、多步骤的计划 。这对于将复杂任务分解为可管理的小块至关重要 。常用的规划技术包括思维链（Chain of Thought, CoT）、思维树（Tree of Thought, ToT）和ReAct（Reasoning and Act）。这些技术赋予Agent处理模糊性、迭代解决方案和动态调整策略的能力 。规划能力对于Agent识别必要步骤、评估潜在行动，并根据可用信息和期望结果选择最佳行动方案至关重要 。

2.2. 感知与行动模块：与环境交互

为了使Agent不仅仅停留在对话层面，它需要感知其所处的数字或物理环境，并据此采取行动。感知和行动模块即是Agent的“感官”和“效应器”。

• 环境感知模块：感知模块负载把需要的上下文、环境信息召回，传递给大模型。在感知模块中，语义搜索、NL2SQL等能力是基础，这些模块的能力把LLM感知环境的需求转换为具体的获取数据的操作。
• 行动模块 ：负责执行Agent的决策，这可能包括调用API、与外部工具交互、生成文本或代码，甚至在机器人技术中执行物理动作。

环境感知是至关重要的。LLM只负责推理，而针对的场景要有环境感知模块决定。如果获取的数据不对，那么LLM也很难给出完美的答案。

2.3. Memory：学习与维护上下文

Memory将LLM从一个无状态的处理器转变为一个能够学习和适应的Agent。强大的记忆能力对于Agent的连续性、连贯性、从过去的交互中学习以及通过回忆历史交互和适应新情况来提高性能至关重要 。LLM缺乏个性化，而记忆系统充分提取个性化特征，是的LLM可以根据个性化特征给与个性化回复。

在Memory中又分为长期记忆和短期记忆：

• 短期记忆 (Short-Term Memory)：
  • 通常在LLM的上下文窗口内处理，用于支持轮次间的对话和即时回忆 。它能够维持会话内的上下文 。
  • 对于需要在多次交流中保持上下文的对话式AI非常有用 。
  • 由于上下文受限，在短期记忆中，如果把全部的会话记录都保存下来，会导致LLM失去重点，产生幻觉。因而更好的方式是对短期记忆进行不断地总结、归纳，提取出需要的信息。因而在短期记忆中，总结能力是必须的。而召回能力则不是。
• 长期记忆 (Long-Term Memory)：
  • 涉及对交互历史、事实或学习到的行为进行持久化存储，通常使用向量数据库（如FAISS、Pinecone）或知识图谱来实现 。
  • 使Agent能够从过去学习，提取洞察以改进未来的会话 。以及提供个性化的能力。
  • LTM的类型包括 ：
    • 情景记忆 (Episodic Memory)：回忆特定的过去经历或事件。通过记录关键事件、行动及其结果来实现。
    • 语义记忆 (Semantic Memory)：存储结构化的事实知识（如事实、定义、规则）。通过知识库、符号AI或向量嵌入来实现。
    • 程序记忆 (Procedural Memory)：存储和回忆技能、规则和学习到的行为，以便自动执行任务。通常通过强化学习获得。
  • 检索增强生成（Retrieval-Augmented Generation, RAG）技术能够从LTM中动态获取和整合相关知识 。
• 分层记忆系统：如工作记忆、短期记忆和长期记忆的组合，可以提高检索速度和上下文保真度 。

短期记忆和长期记忆之间的区别，以及各种长期记忆类型，凸显了强大记忆基础设施所需的复杂性。向量数据库是实现有效长期记忆的关键赋能技术。

2.4. 工具集成与使用：扩展Agent能力

LLM本身受限于其训练数据。工具为Agent提供了访问实时信息、外部系统和专业功能的途径，从而极大地扩展了Agent的实际应用能力。

工具的使用将一个被动的LLM转变为一个能够执行现实世界任务的主动Agent 。这些工具使LLM Agent能够与外部环境（如维基百科搜索API、代码解释器、数学引擎）、数据库、知识库和外部模型进行交互 。集成点包括Web搜索和摘要API、数据库查询（SQL生成器）、代码执行引擎以及各种第三方服务 。

在工具中，涉及到的内容包括：

• 交互协议层：

  • MCP协议：LLM 和工具之间的标准化交互协议。

  • A2A协议：Agent2Agent的交互协议。

• 浏览器工具：browser-use是一个很重要的tool，用于Agent浏览和操作网页中的内容，浏览器工具允许Agent不仅仅通过API访问环境和操作环境。Browserbase, Lightpanda, and Browserless 这些公司在构建浏览器工具的基础设施。

• 工具发现和整合：全网那么多的MCP工具，怎么找到合适的工具是一个难题，这催生了工具发现类的服务。

• 沙箱：沙箱是保障工具安全运行的前提。除了调用外部工具存在安全性的担忧，对LLM on-demand生成的工具也存在类似担忧。在未来，大部分的工具应该是由LLM按需生成的。在沙箱内运行这些工具，可以避免一些安全性问题。有一些公司提供沙箱内的服务，比如E2B。

• Agent as a Service：一些公司，提供tool类的服务。例如：

  • 搜索类：搜索应该是一些场景的基础，例如问答类机器人。搜索相关的上下文可以提升信息的时效性，提供更加准确的信息。例如tavily，提供了搜索的API。
  • 数据爬取：爬虫或者数据类产品，例如Firecrawl 是一款 可以将网站转换为 Markdown 格式的爬虫工具 ，主要 提供 API 服务 ，无需站点地图，只需要接收一个 URL 地址就可以爬取网站及网站下可访问的所有子页面内容。
  • UI-Automation：操作浏览器类工具。
  • 支付类工具：提供支付服务。

2.5. 路由器/控制器：管理复杂工作流

随着Agent处理日益复杂、涉及多个工具或子Agent的多步骤任务，一个有效的控制器对于协调这些组件变得至关重要。

在复杂的Agent中，路由机制根据任务需求决定调用哪个工具或子流程 。这个控制器管理动态工作流，并在推理、记忆检索和工具执行之间进行协调，确保Agent能够根据实时情况做出适当响应 。

AI Agent的核心功能模块——大脑（LLM、推理与规划）、感知与行动、记忆、工具和控制器——并非简单相加，而是高度相互依赖。任何一个环节的薄弱都会显著削弱整体的“智能代理”能力。例如，一个拥有强大LLM但记忆系统欠佳的Agent无法有效学习或维持上下文。一个规划能力出色但缺乏工具的Agent则无法与外部世界互动。因此，Agent基础设施的设计需要采取整体方法，确保每个组件不仅自身强大，而且能与其他组件无缝高效集成。工具的多样性、可靠性和可访问性是决定Agent解决广泛现实世界问题能力的主要因素。基础设施不仅要允许工具使用，更要促进广泛且可扩展工具集的轻松集成、管理和安全调用。同样，记忆系统的复杂程度（如短期记忆、长期记忆类型、检索机制）对Agent学习、长期适应和提供个性化体验的能力至关重要。基础设施必须支持多种信息类型的有效编码、强大的检索机制（如基于向量数据库的RAG）以及潜在的分层结构，以有效管理不同范围的记忆。

3. Agent系统运维基础设施

为了确保AI Agent系统在实际应用中的高效、稳定和安全运行，一套关键的运维基础设施必不可少。这包括LLM API网关、缓存策略以及安全的工具执行环境。

3.1. LLM API网关：统一访问、安全与可观测性

随着企业越来越多地使用多个LLM或微调模型，以及提供企业内的服务，LLM API网关成为管理访问、确保安全、优化性能和控制成本的关键组件。它将底层模型的复杂性从应用开发者那里抽象出来。

LLM网关充当访问多个LLM提供商或自托管模型的集中接口，提供统一的API 。它简化了处理特定模型API、速率限制、重试机制和基础设施差异的复杂性 。其核心功能包括 ：

• 统一访问：为各种LLM提供单一入口点。
• 安全与合规：管理身份验证（如集中密钥管理、基于角色的访问控制RBAC）和数据治理。
• 审计：记录访问LLM的内容。在无法获得LLM侧的访问日志的前提下，在网关侧记录日志有利于审计。
• 性能优化：跨模型/提供商进行负载均衡，并实现响应缓存。
• 路由与回退：当主模型出现问题时自动切换到备用模型，并对瞬时错误进行自动重试。
• 速率限制：管理请求量以防止过载并控制成本。
• 可观测性：提供性能监控（如延迟、错误率）、使用情况分析（如Token使用量）和成本管理功能。
• 内部分账：不同部分访问同一个LLM账号，而网关则用于区分不同的内部账号。

3.2. LLM响应的缓存策略：性能与成本优化

LLM的推理过程可能既缓慢又昂贵。有效的缓存对于构建响应迅速且经济高效的Agent应用至关重要，尤其适用于处理常见问题或重复任务的场景。

LLM缓存通过存储和重用先前计算的LLM响应来减少延迟和计算成本 。主要的缓存策略包括：

• 精确键缓存 (Exact Key Caching)：为特定、完全相同的输入查询存储响应。这种方法检索速度快，实现简单，但对输入的微小变化（如多余空格或拼写错误）非常敏感 。
• 语义缓存 (Semantic Caching)：根据输入内容的语义相似性来存储和检索响应。这种方法能够处理措辞不同但含义相同的查询，从而提高缓存命中率，但存在因语义相似而导致错误匹配（即“假阳性”）的潜在风险 。

缓存设计模式包括单层LLM缓存、多层缓存（例如，第一层精确匹配，第二层语义匹配）以及基于RAG的缓存（预检索文档缓存和后检索响应缓存）。有效的缓存管理还涉及可配置的缓存过期策略、缓存失效机制、优化缓存命中率以及平衡缓存大小与内存使用（例如，使用最近最少使用LRU淘汰策略）。缓存的典型用例包括客户支持机器人（处理高频查询）、搜索引擎（缓存常用搜索词）、推荐系统和内容生成应用 。

对于交互式Agent，尤其是在对话或执行实时任务时，低延迟对于用户满意度和感知智能至关重要。语义缓存能够处理措辞变化的查询，显著提高了缓存命中率，这意味着更多用户请求可以从缓存中快速得到服务，从而减轻了对LLM的负载。因此，复杂的、可能是多层次的、并利用语义理解的缓存策略，是构建高性能、可扩展的Agent系统的重要基础设施组成部分。

3.3. 安全的工具执行环境：沙箱与凭证管理

如果Agent能够执行代码或通过API与外部工具交互，确保这一过程的安全性至关重要。Agent自主性的增加，特别是在使用工具（如执行代码）时，会引入重大的安全风险，例如任意代码执行 。

沙箱 (Sandboxing) 对于管理资源和创建安全的执行环境至关重要，它可以封装潜在的有害代码，防止其影响更广泛的系统 。

4. Agent编排与协作

Agent的智能不仅仅体现在其个体能力上，更在于它们如何组织自己的“思维”过程以及如何与其他Agent或系统进行协作。编排模式和系统架构的选择对Agent的整体效能有深远影响。

4.1. 关键编排模式：构建Agent思维与行动

编排模式为Agent（或其LLM大脑）如何处理问题、制定决策以及与工具互动提供了框架。选择合适的模式会影响Agent的能力、复杂性和可解释性。

• 思维链 (Chain-of-Thought, CoT)：将任务分解为更小的步骤，以逐步求解。非常适合需要逻辑或多步骤推理的任务 。它帮助模型分解任务，使其思考过程更易于理解 。
• ReAct (Reasoning and Acting, 推理与行动)：将CoT推理与外部工具使用相结合 。它涉及一个“思考 (Thought) -> 行动 (Action) -> 观察 (Observation)”的循环 。这使得Agent能够根据新信息或前一步骤的结果动态调整其方法 ，从而增强LLM在Agent工作流中处理复杂任务和决策的能力 。
• Reflexion (反思)：利用反馈循环，使LLM能够反思过去的输出并迭代地改进其性能 。这种模式非常适用于需要多次尝试进行优化和复杂推理的任务 。

4.2. 单Agent与多Agent系统架构

问题的复杂性往往决定了是单个高能力的Agent足够，还是一个由专业化、协作的Agent组成的团队更为有效。这一选择对通信和协调基础设施有重大影响。

• 单Agent系统：最适合需要快速执行且无需协调或协作的任务 。
• 多Agent系统 (MAS)：适用于动态的、多层面的环境，其中专业化和协调至关重要 。在MAS中，可以为Agent分配专门的角色并让它们协同工作 。多Agent工作流为僵化的基于规则的自动化提供了一种灵活的、自然语言驱动的替代方案 。Agent之间可以协作、辩论想法、相互学习，从而做出更好的决策 。
• MAS的挑战：协调复杂性、性能可变性、可扩展性、资源管理是MAS面临的主要挑战 。有效的通信渠道设计本身就很复杂 。

从单Agent系统转向多Agent系统不仅仅是数量上的扩展，更是一种质的转变，引入了Agent间通信、协调和信任等挑战，这些都需要专门的基础设施组件来支持。单个Agent主要进行内部推理，而多个Agent则必须有效沟通，可能还需要协商、解决冲突，并维持共享的态势感知或目标。这意味着MAS基础设施需要的不仅仅是单个Agent的执行环境，还需要强大的Agent间通信协议（例如，支持双向通信 ）、共享内存或“黑板”系统 、角色管理，以及可能更高级别的编排器或“管理Agent”（如CrewAI的层级化流程 ）。MAS的“社会”动态意味着基础设施不仅要支持计算，还要支持协作。

5. 开发、部署与管理

构建、部署和有效管理AI Agent系统，需要依赖于合适的开发框架、遵循LLMOps的最佳实践，并对基础设施的构建与购买做出战略性决策。

5.1. 开源Agent框架概述

开源Agent框架旨在通过提供预构建的组件和抽象来简化Agent的开发过程。了解它们的理念、优势和劣势是选择合适工具或决定采用自定义方法的关键。

• LangChain：采用模块化架构，适用于具有直接工作流的简单Agent。它支持向量数据库和记忆功能，其LangSmith平台可用于调试和监控 。然而，一些开发者认为它过度抽象，难以使用，甚至有些过度工程化 。
• LangGraph：作为LangChain生态系统的一部分，LangGraph采用图架构（节点代表任务/动作，边代表转换），并包含一个状态组件来维护任务列表。它非常适合周期性、条件性或非线性工作流 。LangGraph提供了比其他框架更高的可控性，并有意保持其底层和集成无关性 。
• AutoGen：由微软推出的多Agent AI框架，采用分层架构（核心层、AgentChat层、扩展层）。它支持异步消息传递和对话式AI助手的构建，并提供AutoGen Bench和AutoGen Studio用于开发和基准测试 。
• CrewAI：一个用于多Agent解决方案的编排框架，采用基于角色的架构（Agent、任务、流程——顺序或分层）。它底层使用了LangChain ，但本身是一个独立的框架 。其局限性在于目前主要支持顺序编排，并且可能产生不完整的输出 。
• LlamaIndex：一个全面的LLM应用开发框架，在RAG（检索增强生成）方面表现出色。它提供统一API、文本处理工具，并针对性能进行了优化 。其主要模块包括 llama-index-core、llama-index-integrations和llama-index-packs 。适用场景包括聊天机器人、内容生成、数据提取/分析和代码辅助 ，尤其适用于涉及大型图谱、多样化检索和资源效率的RAG应用 。但也有用户认为它不必要、复杂，且底层代码难以阅读 。

在开源Agent框架中，其主要作用是负责Agent逻辑的编排，而过度封装则导致使用复杂。Langgraph是这比较符合Agent工程的框架。

5.2. Agent系统的LLMOps：生命周期管理

随着Agent从原型走向生产环境，系统化的LLMOps方法对于确保其可靠性、可扩展性和持续改进至关重要。Agent系统因其推理、规划和工具使用能力，为传统的MLOps带来了新的复杂性。

LLMOps的定义与重要性：LLMOps是指在LLM的整个生命周期中对其进行管理，包括开发、测试、部署、监控和优化 。它是MLOps的一个专门子集，专注于生成式AI模型 。LLMOps之所以重要，是因为它有助于避免诸如错误答案、安全漏洞和模型性能下降等风险，确保模型输出的一致性和高性能 。

针对Agent的关键LLMOps实践 ：

• 组件版本控制与组合性：跟踪Agent模块（大脑、记忆、工具等）的变更，并允许轻松替换。
• 可观测性与可调试性：能够检查决策树、推理链和行动日志。像Weave这样的工具可用于追踪。
• CI/CD集成：验证变更不会导致功能退化。
• 提示版本控制与测试流水线：跟踪提示的变更及其产生的效果。
• 工具注册表：管理外部API、数据库和插件。
• 安全过滤器与约束：确保Agent在定义的边界内行动，例如使用Guardrails监控安全性和偏见。

Agent的评估与监控 ：

• Agent的行为是动态且不确定的。评估需要覆盖多步骤工作流和决策树，而不仅仅是单个提示的完成情况。
• 使用自动化评估工作流，结合定量指标（如困惑度、BLEU分数）和定性指标（如人工反馈、幻觉率）。
• 监控模型的漂移、幻觉、延迟和偏见 。
• 采用A/B测试和影子部署等方法评估变更效果 。

Agent评估是比较重要的基建，甚至比其他内容还要重要，因为其他内容是可以由LLM自动生成出来的。而评估，则是要有用户制定粗来评估内容，以符合用户的目标。在一些产品中，例如Databricks的AgentBrick，采用评估驱动的方式自动生成Agent。用户定义好目标和评估指标，服务自动生成满足要求的Agent

6. 企业应用与架构考量

将AI Agent应用于企业实际业务场景，不仅能带来显著效益，也对现有IT架构提出了新的挑战。理解这些应用和挑战，对于成功部署和扩展Agent系统至关重要。

6.1. 真实世界的企业用例

通过具体的用例可以更好地理解Agent基础设施在实际应用中的价值和需求。

• 文档智能与合规
• 客户支持与会员服务
• 财务与采购
• 降本体校

6.2. 企业规模化采用的架构挑战

将AI Agent从试点项目推广到企业范围的部署，会暴露出一些重大的架构和运营挑战，这些挑战必须通过相应的基础设施来解决。

• 指令过载/提示工程：过度依赖自然语言提示会导致指令臃肿、不一致、难以扩展且难以调试。企业需要模块化的Agent配置框架，包括声明式目标、防护栏、工具模式和可复用的指令块。
• 规划能力不足：将用户模糊的请求转化为精确、可分解的任务计划是一个主要障碍。当前的Agent在被明确告知任务后执行良好，但在初始解读和规划方面能力较弱。这需要强大的规划Agent或规划模块，能够理解意图，访问知识图谱或工作流本体，分解任务并进行路由。
• Agent间的通信原始：目前主要通过传递自然语言输出作为彼此输入的方式进行通信，这种方式较为原始，易导致结构丢失、错误级联和审计困难。企业需要类型化的、结构化的、基于契约的通信机制（如JSON、事件模式、共享内存/黑板）。多向通信也可能存在问题 。
• 治理、可审计性与安全性：
  • 缺乏信任框架：安全部门在没有审计追踪、回退机制和工具使用防护栏的情况下，对批准自主Agent持谨慎态度 。
  • 需要为Agent实施基于角色的访问控制、可追踪的推理链、综合监控和异常检测机制 。这些不仅仅是Agent本身的特性，更是由周边基础设施（如日志系统、Agent的身份和访问管理系统、能够解读Agent决策路径的监控工具）启用和强制执行的系统属性。
• 可扩展性与性能瓶颈 ：编排大量Agent会带来性能挑战。传统的云扩展模型可能会发生转变，因为Agent AI对某些任务的集中处理需求可能较低 。
• 互操作性：与多样化的数据源、API和遗留系统交互需要周密的规划。

7. Agent基础设施的挑战与未来方向

AI Agent基础设施领域正经历快速发展，同时也面临着诸多技术挑战。洞察这些挑战并把握新兴趋势，对于规划和构建面向未来的Agent系统至关重要。

7.1. 当前技术挑战

尽管AI Agent展现出巨大潜力，但其基础设施仍面临一些亟待解决的技术难题：

• 长期规划难题：在处理较长步骤的问题时，大模型可能会出现幻觉，错误的理解任务，或者陷入某种死循环操作。
• 有限上下文长度 ：大模型的上下文长度有限，需要把关键的数据作为上下文。
• 理解人类意图：使Agent完全理解人类的意图存在困难，在细节处理上自作主张，导致出现偏差。
• 提示的鲁棒性与可靠性：LLM Agent通常依赖多个提示，即使对提示进行微小改动也可能引发问题。它们容易产生幻觉，尤其是在从外部组件获取到冲突信息时。 因而对prompt的任何改动都需要回测。
• 知识边界：控制LLM的知识范围非常困难；其内部知识可能在特定环境中引入偏见或影响Agent的行为。
• 效率与成本：大量的LLM请求会影响Agent的行动效率（这在很大程度上取决于LLM的推理速度）。部署多个Agent时的成本也是一个需要关注的问题。
• 多Agent系统的协调复杂性 ：随着系统规模的扩大，协调难度呈指数级增长。时序问题可能导致任务失败。
• MAS的性能稳定性：环境变化、Agent能力差异、网络延迟以及复杂交互产生的突现行为，都可能导致系统结果的不可预测性。
• MAS的可扩展性与资源管理：增加Agent数量有时可能导致收益递减甚至系统崩溃。资源分配尤为棘手。

7.2. 新兴趋势

展望未来，Agent基础设施正朝着更智能、更协同、更可信的方向发展：

• 增强的推理能力与LLM集成：更先进的LLM正在提升Agent的理解力、上下文感知能力，使其能够处理复杂的多轮对话并支持高风险决策。
• 用于自我改进的强化学习：Agent能够通过强化学习在动态环境中自我学习并优化决策（例如，在自主交易系统中）。
• 多环境操作：未来的自主Agent将能够无缝地在虚拟平台和物理操作之间转换（例如，在物流领域同时管理仓库自动化和在线库存系统）。
• 群体智能/高级多Agent协作：多个Agent协同工作，共享数据和决策，以集体解决复杂问题。AI技术将更深入地集成以改善协调。
• 个性化与定制化：通过行为分析和上下文学习，提供更量身定制的体验。
• 结构化的Agent开发环境：类似于“Agent的VSCode”，提供集成工具、模拟、测试和版本控制功能。

大数据计算引擎编程语言的迭代

伴随着Hadoop和Mapreduce的出现，引发了大数据时代。在大数据时代，计算引擎及其附加组价通常以java来实现，一方面java语言的开发难度比较低，另一方面原因是基础的组件是java开发，那么附加的生态以及拓展不得不以java开发，以实现协同效应。

Hadoop系统解决了分布式计算的问题，这是原来的数据库系统所解决不了的，因而在web风行的年代，Hadoop成为了大数据系统的不二选择。

反应过来的数据库圈子，借助于Mapreduce的理念，在原有数据库系统架构基础上，完成了数据库的分布式执行的改造。

而MapReduce系统，随着市场的推广，也遇到了他的难题：

1. 编写分析程序的代价比较高。这也导致受众有限。而数据库凭借着半个世纪的积累，以及SQL这种门槛非常低的语言，成功的挽回了半壁江山。
2. 执行的延时比较高，分析一个程序可能需要几个小时。对于快速迭代的互联网来说是不可接受的。

因此又出现了一些替代品，使用内存计算来加速，例如Presto。再后来，为了更加深挖性能，出现了Clickhouse这种性能怪物。那么像Clickhouse的这种速度极致的计算引擎，原因有很多种，本文关注在语言层面的原因。

Clickhouse，Velox等基础现代化的计算引擎，普遍采用c++17+的编程语法。以往大数据引擎通常java实现，生态丰富，开发代价比较小，而Clickhouse的成功布道了基于c++的计算引擎也是可以的，不仅可以完成，而且速度更快。

C++11+：一种全新设计理念的语言

每一种编程语言都有自己特定的编程风格：

c : 过程式

c++ ：面向对象

java: 异步回调

c++11+ : 什么风格？

c++11版本的发布距离上一个版本过去了c++03过去了8年的时间。更新了大量重量级的feature，以及全新的编程理念。

虽然都是以c++命名，但是c++的语言在c++11之后发生非常大的变化。这种变化，即使让我们称呼c++11以后的语言是一种全新的语言，也不为过。这种关系就像c和c++的关系：虽然c中也有结构体，但是c是一种过程式的语言，而c++则是一种面向对象的语言。而c++和c++11+也一样，虽然c++中也有模板，但是这种模板跟宏替换没太大区别；而在c++11+中，模板被提升到了新的高度，灵活的语法让我们具备了在编译期编程的能力，在c++11以后，是对于c++11的修补。基于c++11+ ，我们有能力告诉编译器，编译期应该怎么做。这种编译期的编程行为，称为是“元编程”。例如类型计算、编译器常量计算、生成代码控制。在本章节中，我们将介绍c++11+中模板元编程的核心方法。

c++11+ 的新的技术诞生了新的编程理念。关于template知识点比较零碎，但是我们可以聚焦于借助于template的新的技能，我们如何完成更高效的程序。在本文的最后，我们给出模板元编程的通用范式。

模板元编程的定义

模板元编程是什么？按照Wikipedia的定义：

1

metaprogramming is a computer programming technique in which computer programs have the ability to treat other programs as their data. It means that a program can be designed to read, generate, analyse, or transform other programs, and even modify itself, while running.

因此我们可以这样说，模板元编程就是在编译阶段，通过指令操纵编译器生成目标程序的过程，也就是操作程序的程序。

哪些系统在使用

模板元编程在现代化的计算引擎中得到了广泛应用。

• Clickhouse
• Velox
• Processila
  • Makes extensive use of C++ template metaprogram- ming for compile time code generation. This allows utilizing many optimization techniques, such as partial application, to be applied to a single function imple- mentation automatically, while avoiding large virtual call overheads.

模板元编程解决什么问题：

通过编译器行为，控制编译生成的代码，在编译器生成所有的可能的代码，避免运行时的多态、分支跳转。

虚函数是比较众所周知的降低性能的点。虚函数降低性能的的原因：

• 动态寻址，打破流水线
  • 如果预测准确，可以实现预加载
• 阻碍编译优化，如函数内联
  • 这一点才是最主要因素，我们看一个样例

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

#include <cmath>
#include "timer.h"
struct Base 
{
public: 
    virtual int f(double i1, int i2) 
    {   
        return static_cast<int>(i1 * log(i1)) * i2; 
    }   
};
int main() 
{
    TimerLog t("timer");
    Base *a = new Base(); 
    int ai = 0;  
    for (int i = 0; i < 1000000000; i++) 
    {          
        ai += a->f(10, i); // 这里有改动   
    }   
    cout << ai << endl;
}

虚函数版本屏蔽了函数内联，导致每次都要重复计算。而非虚函数可以在静态阶段就计算出各个值，甚至可以复用重复的计算结果。

虚函数版本:29761.8 ms

非虚函数版本：0.00038ms

模板元编程核心技术

接下里介绍几个模板元编程的核心技术：类型萃取、模板特化、SFINAE、不定长参数。这些核心技术构成了模板元编程的主要概念。

类型萃取

类型萃取是 C++ 中的一项模板编程技术，它允许在编译时查询和操作类型的属性。类型萃取广泛用于模板元编程和泛型编程，特别是在实现编译时决策、条件编译、类型检查和类型转换时非常有用。说人话就是，类型萃取以类型作为变量，在编译时进行一些判断逻辑

类型萃取通常通过使用特殊的模板结构来实现，这些模板结构称为类型特征（type traits）。C++ 标准库 <type_traits> 头文件中提供了一组丰富的类型特征，用于对类型进行各种检查和转换。

类型特征可以返回关于类型的信息，如是否是整数类型、是否是指针类型、是否具有某个成员函数等。这些信息通常以编译时常量（如 true 或 false）或者类型（如 T::value_type）的形式提供。

以下是一些常见类型特征的类别和示例：

基本类型特征

• std::is_integral<T>：检查 T 是否是整数类型。
• std::is_floating_point<T>：检查 T 是否是浮点类型。
• std::is_array<T>：检查 T 是否是数组类型。
• std::is_pointer<T>：检查 T 是否是指针类型。
• std::is_reference<T>：检查 T 是否是引用类型。
• std::is_const<T>：检查 T 是否有 const 限定符。
• std::is_function<T>：检查 T 是否是函数类型。

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

#include <type_traits>
#include <iostream>

template <typename T>
typename std::enable_if<std::is_integral<T>::value, T>::type 
foo(T value) {
    std::cout << "foo called with an integral type: " << value << std::endl;
    return value;
}
int main() {
    foo(10); // 有效，因为 int 是整数类型
    foo<int>(10);
    // foo(3.14); // 无效，因为 double 不是整数类型
}

上边中，std::is_integral::value返回bool， enable_if返回type

模板特化和SFINAE

模板特化是 C++ 模板编程中的一个强大特性，允许程序员为特定的模板参数提供特殊的实现。模板是代码的通用实现，而模板特化是特殊性实现。模板特化分为全特化和偏特化，它们可以应用于函数模板和类模板。

全特化（Full Specialization）

全特化是针对所有模板参数提供一个特定实现的过程。当模板实例化时，如果实际参数与特化参数完全匹配，编译器会使用特化版本的模板。

类模板全特化示例：

1
2
3
4
5
6
7
8
9
10

template <typename T>
class MyArray {
    // 通用模板实现
};

// 全特化版本，针对 int 类型
template <>
class MyArray<int> {
    // 特殊化实现
};

在这个例子中，当实例化 MyArray<int> 时，编译器会使用全特化版本，而其他类型比如 MyArray<double> 会使用通用模板。

函数模板全特化示例：

1
2
3
4
5
6
7
8
9
10

template <typename T>
void print(T value) {
    std::cout << "General template: " << value << std::endl;
}

// 全特化版本，针对 int 类型
template <>
void print<int>(int value) {
    std::cout << "Specialized for int: " << value << std::endl;
}

当调用 print(10)（T 为 int 类型）时，会使用全特化版本。调用 print(3.14) 时，则会使用通用模板。

偏特化（Partial Specialization）

偏特化是针对一部分模板参数提供特定实现的过程，它只适用于类模板。在偏特化中，一部分模板参数被固定，其他保持通用。

类模板偏特化示例：

1
2
3
4
5
6
7
8
9
10

template <typename T1, typename T2>
class MyPair {
    // 通用模板实现
};

// 偏特化版本，第二个模板参数固定为 int 类型
template <typename T1>
class MyPair<T1, int> {
    // 特殊化实现
};

在这个例子中，无论 T1 是什么类型，只要 T2 是 int 类型，就会使用偏特化版本。

特化的规则和用途

• 当特化的实例与通用模板实例冲突时，编译器会选择最特殊化（最具体）的版本。
• 模板特化可以用于优化特定类型的性能，提供特殊行为，或处理特定类型的限制。
• 特化不改变原始模板的接口，但提供了不同的实现细节。
• 特化必须在原始模板已定义的情况下进行。
• 模板特化必须在全局或命名空间作用域进行，不能在类或函数作用域内。
• 模板特化应该谨慎使用，因为过多的特化可能导致代码维护困难，而且可能会破坏模板的泛型性。
• 函数模板不支持偏特化，但可以通过重载或者模板参数的默认值来模拟偏特化行为。

模板特化是 C++ 模板编程中用来根据特定情况定制或优化代码的一个强大工具。通过模板特化，开发者可以针对特定类型或条件提供高效的算法实现，同时保持代码的通用性和可重用性。

分支特化constexpr

模板特化是类级别或者函数级别的。而代码块级别需要使用constexpr。

在模板函数中，经常会在一个函数体内生成针对多种类型的计算逻辑。当模板实例化后，部分逻辑就不需要了，只需要走实例化类型对应的逻辑就行。为了减少这种多余的代码，可以采用constexpr关键字来声明。constexpr 是 C++11 引入的关键字，其目的是指示编译器在编译时计算表达式的值，前提是所有表达式中的参数值在编译时均可知。使用 constexpr 可以创建编译时常量表达式，这对嵌入式系统和性能敏感的代码尤其有用，因为它可以消除运行时的计算成本并节省内存。

const关键字代表对象在运行期间值不变；而constexpr关键字代表从编译时就确认了对应的值，可以在编译时做更多优化。constexpr可以用于：

1. constexpr 变量

   当你声明一个 constexpr 变量时，编译器会尝试在编译时计算其值。这要求变量的初始化表达式必须是一个常量表达式。

   1 2 3 4 5 6

   constexpr int factorial(int n) { return n <= 1 ? 1 : (n * factorial(n - 1)); } constexpr int val = factorial(5); // val 在编译时计算为 120

2. constexpr 函数

   constexpr 函数是指能在编译时产生常量表达式的函数。对于 constexpr 函数，编译器会在编译时进行函数调用，前提是提供给函数的所有参数也都是常量表达式。

   在 C++11 中，constexpr 函数的限制比较严格，要求函数体只能包含一条返回语句。但是在 C++14 和 C++17 中，对 constexpr 函数的限制放宽了，允许它们包含更丰富的语句，如循环和多个返回语句。

   1 2 3 4 5 6 7 8 9 10

   // C++14 开始，允许使用循环和多条语句 constexpr int factorial(int n) { //如果函数没有声明成constexpr，则后边定义const变量会报错。 int result = 1; for (int i = 2; i <= n; i++) { result *= i; } return result; } constexpr int val = factorial(5); // val 仍然在编译时计算为 120

3. constexpr 构造函数

   类的构造函数也可以是 constexpr 的。constexpr 构造函数允许在编译时创建和初始化类或结构体的对象。

   1 2 3 4 5 6

   struct Point { constexpr Point(double xVal, double yVal) : x(xVal), y(yVal) {} double x, y; }; constexpr Point p(1.0, 2.0); // 在编译时创建和初始化 Point 对象

4. constexpr用于限制代码区块：

   C++17 引入了所谓的 constexpr if 语句，它允许在编译时根据常量表达式的值选择执行不同的代码路径。这是一个在编译时进行条件分支的强大特性，它可以用来移除非活动分支的代码，从而减少编译后程序的大小，并且可以减少模板元编程中的模板实例化。

   使用 constexpr if 时，如果条件为 true，编译器只会编译 if 分支内的代码；如果条件为 false，则只会编译 else 分支内的代码（如果存在）。非活动的代码分支甚至不需要是合法的代码，因为它会在编译时被丢弃。

   这对于模板编程尤其有用，因为它允许根据模板参数的特性条件性地启用或禁用代码。

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

   #include <iostream> #include <type_traits> template <typename T> void process(const T& value) { if constexpr (std::is_integral<T>::value) { // 对整数类型的处理 std::cout << "Integer: " << value << std::endl; } else if constexpr (std::is_floating_point<T>::value) { // 对浮点类型的处理 std::cout << "Floating point: " << value << std::endl; } else { // 对其他类型的处理 std::cout << "Other type" << std::endl; } } int main() { process(10); // 输出 "Integer: 10" process(3.14); // 输出 "Floating point: 3.14" process("hello"); // 输出 "Other type" }

SFINAE

SFINAE 是 C++ 模板编程中的一个基本原则，全称是 “Substitution Failure Is Not An Error”，意为“替换失败不是错误”。这个原则是指在模板参数替换的过程中，如果某个候选函数由于替换导致编译错误，这个错误将不会导致编译失败，而只是导致该候选函数被编译器丢弃，不参与后续的重载决议过程。

SFINAE 主要用于三个方面：

1. 函数模板的重载决议：在函数模板重载决议中，如果一个候选函数模板在替换过程中失败（例如，由于类型不匹配或表达式不合法），编译器会简单地忽略该函数模板，继续尝试其他重载或模板。值得注意的是，只有函数模板才会有SFINAE的特性。也就是说函数必须声明成模板。一个模板类的成员函数，即便使用了类的模板变量，也不是一个模板函数，不具备SFINAE特性。
2. 模板特化的选择：在类模板或函数模板的特化选择中，如果特化在替换过程中失败，那么它不会被选择。
3. 类型萃取：利用 SFINAE 检测类型是否具有某些属性，如成员函数、嵌套类型等。

SFINAE 常通过以下方式实现：

• 类型萃取和 std::enable_if：利用 std::enable_if 在编译时基于类型特征条件启用或禁用某些模板。enable_if的机制是在满足特定条件时，才会特化出特定类型。当替换失败时，类型萃取无法获得完整的类型或者数据，例如没有type。

1
2
3
4
5
6
7
8
9
10
11
12

#include <type_traits>

// 使用 std::enable_if 限制 T 必须是整数类型
template <typename T, typename = std::enable_if_t<std::is_integral<T>::value>>
void foo(T val) {
    // ...
}
//作为函数返回类型，替换失败时，没有返回值，触发错误
template <typename T>
typename = std::enable_if_t<std::is_integral<T>::value>> foo(T val) {
    // ...
}

• 表达式 SFINAE：通过尝试解析特定的表达式来触发 SFINAE。

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

#include <iostream>

template <typename T>
auto print(T t) -> decltype(std::cout << t, void()) {
    // 如果 T 类型可以通过 std::cout 打印，则使用此重载
    std::cout << t;
}

template <typename T>
void print(T t) {
    // 如果 T 类型不能通过 std::cout 打印，回退到此重载
    std::cout << "Cannot print";
}

• 尾置返回类型：使用尾置返回类型的 SFINAE 来检测表达式的合法性。

1
2
3
4

template <typename T>
auto multiply(T x, T y) -> decltype(x * y) {
    return x * y;
}

• 无效指针：将类型检查的结果映射到指针类型（例如 nullptr），只有在检查为真时才产生合法的类型。

1
2
3
4

template <typename T>
void foo(T* ptr) {
    // 只有 T 是指针类型时，此重载才有效
}

SFINAE 和编译错误

• 在使用 SFINAE 时，只有在模板参数替换阶段出现的错误才会被忽略，如果错误发生在替换之后（例如，函数体中的语义错误），那么它仍然会导致编译失败。
• 在众多的可选项中，至少要有一个替换成功。或者会报错。

不定长模板参数（Variadic Templates）

在 C++11 中引入的不定长模板参数列表（或称为可变参数模板）是一种高级的模板特性，它允许你定义接受任意数量模板参数的模板函数或模板类。这些参数可以是类型参数，也可以是非类型参数，或两者的混合。不定长模板参数列表提供了极大的灵活性，可以用来编写泛化的算法和数据结构。

不定长模板参数列表通常使用省略号 ... 来表示。

函数模板的不定长参数

当定义一个函数模板，你可以允许它接受任意数目的参数，这些参数可以是不同的类型。

例如：

1
2
3
4

template <typename... Args>
void print(Args... args) {
    // ...
}

在这个例子中，Args... 表示一个可变数量的类型参数。

类模板的不定长参数

同样地，类模板也可以定义为接受任意数目的模板参数：

1
2
3
4

template <typename... Elements>
class Tuple {
    // ...
};

在这个例子中，Tuple 可以持有任意数目和类型的元素。

展开不定长模板参数列表

展开不定长模板参数列表意味着在编译时对参数列表中的每个参数执行操作。有几种不同的方法可以展开参数列表：

1. 递归模板函数

可以通过递归模板函数的方式来展开参数列表。每个递归调用处理参数列表中的一个参数，然后将剩下的参数传递给下一个递归调用，直到参数列表为空。递归的终止条件：只有一个参数的场景，也就是可变参数列表为空的场景。

例如：

1
2
3
4
5
6
7
8
9
10

template <typename T>
void print(T arg) {
    std::cout << arg << std::endl;
}

template <typename First, typename... Rest>
void print(First first, Rest... rest) {
    std::cout << first << ", ";
    print(rest...); // 递归调用
}

2. 初始化列表展开

这种技术涉及到创建一个初始化列表，它会在编译时展开参数列表，并且可以应用于任意表达式。

1
2
3
4

template <typename... Args>
void print(Args... args) {
    (void(std::initializer_list<int>{(std::cout << args << std::endl, 0)...}));
}

这里，每个参数 args 都被插入到初始化列表中，并且通过逗号运算符，每个参数对应的表达式都会被执行。在这里等同于是展开为逗号表达式。

3. 折叠表达式（C++17）

C++17 引入了折叠表达式，这是展开参数包的一个更简单和直接的方法。

1
2
3
4

template <typename... Args>
void print(Args... args) {
    (std::cout << ... << args) << std::endl;
}

在这个例子中，<< 运算符被折叠应用于参数包 args 的每个元素，从左到右。

不定长模板参数列表和参数包的展开技术，大大增强了 C++ 模板的能力，使得编写能够处理任意数量和类型参数的泛型代码成为可能。这些技术在实现复杂的库功能如类型安全的变参函数、元组和函数对象绑定等时非常有用。

折叠表达式有两种形式：

1. 二元右折叠（Binary Right Fold）： (pack op ... op init)，其中 op 是二元运算符，pack 是参数包，init 是初始值。右折叠的含义是从右向左对参数包的元素进行折叠。

   例如(args + ...);(1, 2, 3, 4)展开成(1 + (2 + (3 + 4)))。

2. 二元左折叠（Binary Left Fold）： (init op ... op pack)，其中运算符和参数与右折叠相同。左折叠是从左向右对参数包的元素进行折叠。

   例如(... + args);(1, 2, 3, 4)展开成((1 + 2) + 3) + 4。

Clickhouse 变参展开

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

    static bool castType(const IDataType * type, F && f)
    {   
        return castTypeToEither<
            DataTypeUInt8,
            DataTypeUInt16,
            DataTypeUInt32,
            DataTypeUInt64,
            DataTypeUInt256,
            DataTypeInt8,
            DataTypeInt16,
            DataTypeInt32,
            DataTypeInt64,
            DataTypeInt128,
            DataTypeInt256,
            DataTypeFloat32,
            DataTypeFloat64,
            DataTypeDecimal<Decimal32>,
            DataTypeDecimal<Decimal64>,
            DataTypeDecimal<Decimal128>,
            DataTypeDecimal<Decimal256>,
            DataTypeFixedString
        >(type, std::forward<F>(f));   
     }
 template <typename... Ts, typename T, typename F>                
static bool castTypeToEither(const T * type, F && f)             
{                                                                
    /// XXX can't use && here because gcc-7 complains about parentheses around && within ||
    return ((typeid_cast<const Ts *>(type) ? f(*typeid_cast<const Ts *>(type)) : false) || ...);
}    

如何去虚

变参展开去虚

在动态运行时，由于不知道参数的实际类型，必须会产生一次动态类型解析。在普通的虚函数调用时，每次调用子类的函数都需要调用虚函数，而调用虚函数的过程就涉及到一次动态类型解析，引发访问虚表的开销。

基于模板的实现是怎么做的呢？由于运行时不知道实际类型，必然产生至少一次类型解析。那么我们可以使用一次类型解析，把变量转换为实际的类型。然后之后的运行调用类型中的函数，无论调用多少次，都不会产生虚函数调用的开销。而模板要做的，就是为每一个子类的每一个函数调用生成执行代码。

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

//定义类型
class ColumnWriter
{
public:
    virtual void func(){};
    virtual ~ColumnWriter(){}
};
class LongColumnWriter : public ColumnWriter
{
public:
    void Write(int v, int row)
    {   
        std::cout<<"LongColumnWriter, write int"<<std::endl;
    }   
    void Write(double  v, int row)
    {   
        std::cout<<"LongColumnWriter, write double"<<std::endl;
    }   
};
class DoubleColumnWriter : public ColumnWriter
{
public:
    void Write(int v, int row)
    {   
        std::cout<<"DoubleColumnWriter, write int"<<std::endl;
    }   
    void Write(double  v, int row)
    {   
        std::cout<<"DoubleColumnWriter, write double"<<std::endl;
    }   
};  

//type resovler 模板
template <typename... Ts, typename T, typename F>                
static bool castTypeToEither(T * type, F && f)             
{                                                                
    /// XXX can't use && here because gcc-7 complains about parentheses around && within ||
    return ((typeid_cast<const Ts *>(type) ? f(*typeid_cast<const Ts *>(type)) : false) || ...);
}  

template<typename T>
int processColumnImpl(T * writer,SrcWriter * src,int row)
{
    using NonConstType = typename std::remove_const<T>::type;
    NonConstType * w = const_cast<NonConstType*>(writer);
  	for(int i = 0;i < row;++i) {
    	 src -> process(w,i);
    }
  return 0;
}

template <typename F>
static bool castType(ColumnWriter* type, F && f)
{   
    return castTypeToEither<
        DoubleColumnWriter,
        LongColumnWriter
        >(type, std::forward<F>(f));
}
int processColumn(ColumnWriter * writer , SrcWriter * src, int row)
{
     castType(writer, [&](auto & w)
             {   
             processColumnImpl(&w,src,row);
             return true;
             });
     return 0;
}

在processColumn中，调用castType。而castType在编译时为多种类型生成执行代码。并且在运行时通过typeid_cast动态识别类型，把类型转换为实际的类型后，在lambda函数中调用真正的处理函数processColumnImpl。而processColumnImpl是一个模板函数，为每一种类型都生成了代码。在运行时批量处理大量的数据。也就是说实现了一次类型转换，在实际类型中批量处理大量数据。避免了每处理一次数据就调用一次虚函数的开销。

CRTP去虚

CRTP可以用于消除虚函数调用，我们以Clickhouse中的使用样例为例：

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

class IAggregateFunction
{
    ...

    virtual ~IAggregateFunction() = default;

    virtual void add(
        AggregateDataPtr place,
        const IColumn ** columns,
        size_t row_num,
        Arena * arena) const = 0;

    virtual void addBatch(
        size_t row_begin,
        size_t row_end,
        AggregateDataPtr * places,
        size_t place_offset,
        const IColumn ** columns,
        Arena * arena,
        ssize_t if_argument_pos = -1) const = 0;
    ...
}
template <typename Derived>
class IAggregateFunctionHelper : public IAggregateFunction
{
    void addBatch(size_t row_begin, size_t row_end, AggregateDataPtr * places,
        size_t place_offset, const IColumn ** columns, Arena * arena,
        ssize_t if_argument_pos = -1) const override
    {
        if (if_argument_pos >= 0)
        {
            auto * column = columns[if_argument_pos];
            const auto & flags = assert_cast<const ColumnUInt8 &>(*column).getData();
            for (size_t i = row_begin; i < row_end; ++i)
            {
                if (flags[i] && places[i])
                    static_cast<const Derived *>(this)->add(places[i] + place_offset,
                        columns, i, arena);
            }
        }
        {
            for (size_t i = row_begin; i < row_end; ++i)
                if (places[i])
                    static_cast<const Derived *>(this)->add(places[i] + place_offset,
                        columns, i, arena);
        }
    }

}
template <typename T, typename Derived>
class IAggregateFunctionDataHelper : public IAggregateFunctionHelper<Derived>
{
    ...
}

class AggregateFunctionCount final : public IAggregateFunctionDataHelper<AggregateFunctionCountData,
    AggregateFunctionCount>
{
    void add(AggregateDataPtr __restrict place, const IColumn **, size_t, Arena *) const override
    {
        ++data(place).count;
    }
}

add是一个虚函数，如果每一行调用一次add函数，必然产生比较大的虚函数开销。但是在子类中，我们可以把子类作为函数模板传入中间的基类中，然后在中间的基类中强制转换成模板类的类型来实现虚函数的调用。

Variant

std::variant

std::variant 是一个模板类，它可以容纳给定类型列表中的任何一个类型的值。在任何时刻，std::variant 只包含这些类型中的一个。如果你熟悉 C 的联合体（union），std::variant 可以被看作是联合体的类型安全版本。std::variant 可以保证存储的值始终是有效的，而且可以在运行时检查当前保存了哪种类型的值。

1
2
3
4
5
6
7
8

#include <variant>
#include <string>

std::variant<int, float, std::string> v;//定义三种类型的联合体

v = 20; // 现在 v 存储 int 类型的值
v = 3.14f; // v 存储 float 类型的值
v = "Hello, World!"; // v 存储 std::string 类型的值

std::variant 提供成员函数 index() 来查询当前存储的类型的索引值，std::get 可以根据类型或索引来访问存储的值。如果使用错误的类型或索引，std::get 将抛出异常。

std::variant提供了除虚函数以外的另外一种方法去实现动态多态。为了访问variant中的内容，需要使用std::visit。

std::visit

std::visit 是一个函数模板，用于访问存储在一个或多个 std::variant 对象中的值。它接收一个可调用对象和一个或多个 std::variant 对象作为参数。可调用对象的形参类型必须能够接受 std::variant 所有可能值的类型。

使用 std::visit 的主要好处是它允许你编写一个泛型的访问者，它可以处理 std::variant 包含的任意类型的值，你不需要手动检查 std::variant 当前包含的是哪种类型。

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

#include <variant>
#include <iostream>

int main() {
    std::variant<int, float, std::string> v = "Hello, World!";

    std::visit([](auto&& arg) {
        use T = decla(arg)
        if constexprt T == int
			{

			}
        std::cout << arg << std::endl;
    }, v);
    
    return 0;
}

在这个例子中，我们定义了一个 std::variant，它可以存储 int、float 或 std::string 类型的值。使用 std::visit 和一个泛型 lambda 表达式，我们可以访问并打印存储在 std::variant 中的值，而不需要关心它当前包含的具体类型。

std::visit 和 std::variant 配合使用，提供了一个强大的模式匹配机制，非常适合用于那些需要根据运行时确定的类型来执行不同行为的场景。这种类型安全和灵活性在 C++ 中是非常有价值的，尤其是在处理复杂的数据结构和算法时。

基于variant和visit的方法，相比基于虚函数的方法，性能可以提升20%左右。

Velox variant

velox中使用variant容纳不同的类型。

1
2
3
4
5
6
7
8

template <TypeKind KIND>
const auto& value() const {
  checkIsKind(KIND);
  checkPtr();

  return *static_cast<
      const typename detail::VariantTypeTraits<KIND>::stored_type*>(ptr_);
}

一些坑

模板元编程是编译期行为，要区分清楚运行时行为。一个简单的例子：

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

class ColumnWriter 
{
public:
    virtual void WriteBatch(double ) {}; 
    virtual void WriteBatch(long ) {}; 
};
template <class T>
class FixedWidthColumnWriter  : public ColumnWriter
{
public:
    virtual void WriteBatch(T ) override
    {}  

};
using LongColumnWriter = FixedWidthColumnWriter<long>;
using DoubleColumnWriter = FixedWidthColumnWriter<double>;
//以下为调用
    template<typename T>
    int process(T * t,int row)
    {   
        if(type == 0){ 
            t -> Write(1,row);
            int x = 1;
            t -> WriteBatch(&x ,1,row);
        }   
        else{
            t -> Write(1.0,row);
            double x = 1.0;
            t -> WriteBatch(&x ,1,row);
        }   
        return 0;
    }   

在编译阶段，是找不到基类的函数的，只能看到本类内的函数签名。

模板元编程的一个终极案例：

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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95

#include <iostream>
#include <vector>
using namespace std;
enum class Strategy
{
    FILL_0,
    FILL_NULL
};
// v1 直接版本
// callV1 -> fillContentV1
void fillContentV1(Strategy strategy, int v)
{
  switch(strategy)
  {
    case Strategy::FILL_0:
			cout<<"fillContent0V1:"<<endl;
      break;
    case Strategy::FILL_NULL:
			cout<<"fillContentNullV1:"<<endl;
      break;
  }
}
void callV1(Strategy strategy,const std::vector<int> & v)
{
    for(size_t i = 0;i < v.size();++i){
        fillContentV1(strategy,v[i]);
    }   
}

//v2 函数指针版本,不同的策略放在不同的函数中实现
//callV2 -> fillNullV2/fill0V2
void fill0V2(int v)
{
    cout<<"fillContent0V2:"<<endl;
}
void fillNullV2(int v)
{
    cout<<"fillContentNullV2:"<<endl;
}

void callV2(Strategy strategy, const std::vector<int> & v)
{
    void (*funcPtr)( int);
    if(strategy == Strategy::FILL_0)
        funcPtr = & fill0V2;
    else if (strategy == Strategy::FILL_NULL)
        funcPtr = & fillNullV2;

     for(size_t i = 0;i < v.size();++i){
         funcPtr(v[i]);
     }   
}
//V3版本，在最高层就把动态参数变成模板参数，之后所有底层函数模板化。fill函数把strategy作为模板参数，call也实现了一个基于strategy模板参数的函数callV3WithStrategy。 在调用callV3中，首先解读动态参数strategy，通过if判断，分别进入不同的函数执行。在之后的执行中，strategy就完全模板化了。
template<Strategy T>  
void fillContentV3(int v)
{
    cout<<"invalid fill:"<<endl;
}
template<> 
void fillContentV3<Strategy::FILL_0>(int v)
{
    cout<<"fillContent0V3:"<<endl;
}
template<> 
void fillContentV3<Strategy::FILL_NULL>(int v)
{
    cout<<"fillContentNullV3:"<<endl;
}
template<Strategy T>
void callV3WithStrategy(const std::vector<int> & v)
{
    for(size_t i = 0;i < v.size();++i){
        fillContentV3<T>(v[i]);
    }   
}
void callV3(Strategy strategy, const std::vector<int> & v)
{
    if(strategy == Strategy::FILL_0)
    {
        callV3WithStrategy<Strategy::FILL_0>(v);
    }
    else if(strategy == Strategy::FILL_NULL)
    {
        callV3WithStrategy<Strategy::FILL_NULL>(v);
    }
}

int main(int argc,char ** argv)
{
    std::vector<int> a  = {0,1,2,3};
    callV1(Strategy::FILL_0,a);
    callV2(Strategy::FILL_0,a);
    callV3(Strategy::FILL_0,a);
}

模板元编程加速计算的范式

模板元编程解决分支和虚函数问题的原理大概如此，就是想办法把提前解析动态类型，把动态类型转换为实际的类型。然后执行实际类型的函数。然后通过模板为每一种可能的模板参数组合写出所有的实现。下图是模板元编程和虚函数风格的不同。当我们理解了这种风格之后，再去看代码，就会有一种豁然开朗的感觉，也就不存在代码可读性的问题了。

目录

• 1. 数据分析的重要性及OLAP引擎的角色

  • 数据分析的重要性及OLAP引擎的角色
  • 数据分析的链路
  • 大数据的历史
  • 软件系统的发展
  • SQL on Hadoop时代
  • MPP时代
  • 向量化时代
  • 未来的发展方向

• 2. SQL语法

  • 数据分析的语言接口
  • 数据模型
  • SQL
  • SQL语法
  • 本章小结

• 3. 语法分析

  • 语法分析
  • 从SQL到抽象语法树的转换过程
  • 本章小结

• 4. 逻辑执行计划

  • 抽象语法树和逻辑执行计划的区别
  • 逻辑操作算子
  • 本章小结

• 5. 基于规则的优化器RBO

  • 理论基础：代数变换定律
  • 基于规则的查询优化器
  • 优化器案例
  • 本章小结

• 6. CBO基于代价的优化器

  • CBO简介
  • CBO通用流程
  • CBO的主要使用场景
  • CBO 在join重排和join类型选择中的应用
  • CBO 的技术挑战
  • 估算错误和应对策略
  • 本章小结

• 7. 运行时优化

  • 7.1 启发式优化器
  • 7.2 可变执行计划
  • 7.3 改变并行度
  • 7.4 任务负载迁移
  • 7.5 算法动态切换
  • 7.6 其他运行时优化
  • 7.7 小结

• 8.任务调度和并行执行:

  • 8.1执行框架
  • 8.2任务调度
  • 8.3分布式算法
  • 8.4 Shared-Nothing vs Shared-Disk vs Shared-Memory
  • 8.5 指令集并行SIMD

  •  [8.6任务调度和并行计算章节小结](http://mp.weixin.qq.com/s?__biz=MzI0MDI2Mzk5Mw==&mid=2247483965&idx=1&sn=0c38c9b19b5e05a7879826dc6bdd6eca&chksm=e91c346bde6bbd7de42979033deffc8da9f722a2da6e36f351f7762694394b614bc13206f19f&scene=21#wechat_redirect)
    

• 9.LLVM与代码生:

  • 9.1物理执行计划的转化与优化
  • 9.2 LLVM的历史与普及原因
  • 9.3 LLVM与协同开发的协同性
  • 9.4 LLVM项目组成
  • 9.5 LLVM工具介绍
  • 9.6 LLVM IR 介绍
  • 9.7 IR代码数据结构
  • 9.8 LLVM-JIT
  • 9.9 向量化执行
  • 9.10 Reduction指令
  • 9.11 IR优化器
  • 9.12 LLVM在Clickhouse中的应用
  • 9.13 JIT代码缓存
  • 9.14 章节小结

• 10 SIMD指令

  • 10.1 计算加速的技术
  • 10.2 SIMD扩展指令集
  • 10.3 SIMD指令
  • 10.4 非并行指令，却能做到加速效果
  • 10.5 显式使用SIMD指令的缺点
  • 10.6 基于编译器的自动向量化
  • 10.7 小结

• 11 计算机体系结构

  • 11.1 计算机层次结构
  • 11.2 优化数据局部性
  • 11.3 避免CPU缓存失效
  • 11.4 减少内存访问
  • 11.5 减少磁盘I/O
  • 11.6 减少网络通信：
  • 11.7 加速系统性能：使用固态硬盘
  • 11.8 批量处理
  • 11.9 使用非阻塞算法
  • 11.10 避免流水线中断
  • 11.11并行计算和向量化：
  • 11.12 NUMA架构
  • 11.13 CPU绑定
  • 11.14 小结

• 12 基于存储的性能优化

  • 12.1 存储硬件
  • 12.2 存储格式
  • 12.3 编码格式
  • 1.2.4 压缩算法
  • 12.5 列存、编码和压缩算法
  • 12.6 索引技术
  • 12.7 缓存技术
  • 12.8 章节小结

• 13 模板元编程

  • 13.1 运行时代价和编译时代价
  • 模板元编程基础概念
    • 13.2模板参数
    • 13.3不定长模板参数
    • 13.4 类型推导
    • 13.5类型萃取
    • 13.6类型工具
    • 13.7基于模板的多态
  • 基于模板元编程加速计算
    • 13.8逻辑开关
    • 13.9批量生成代码
    • 13.10基于模板的计算
    • 13.11 基于模板去除虚函数调用
    • 13.12基于模板去除虚函数总结
    • 13.13 Clickhouse中模板的应用
  • 13.4 小结和参考文献

• 14 并行架构

  • 14.1 分布式OLAP架构的驱动因素
  • 14.2 并行、并发、分布式的区别
  • 14.3 并行系统的评估指标
  • 14.4 影响并行性能的核心因素
  • 14.5 网络结构
  • 14.5 网络通信设备
  • 14.7 并行架构
  • 14.8 分布式存储，分区和并行化
  • 14.9 数据本地性 vs 计算存储分离
  • 14.10 读写分离的架构
  • 14.11 多租户架构
  • 14.12 分布式调度和运行时监控
  • 14.13 调度执行
  • Presto-分布式计算架构
    • 14.14 Presto架构
    • 14.15 Presto并行化执行计划
  • 14.14 ClickHouse存储架构
  • 14.14 章节小结

• 15 OLAP现状和未来展望

计算加速的技术

计算加速可以从多个方面入手。软件加速/硬件加速。从软件上来讲，尽可能的榨干硬件的性能；从硬件上讲，尽可能的提高主频。从方向上讲，可以横向扩展，使用更高的并发处理能力；或者在纵向上提高单点的性能。并发处理能力，从粒度上区分，从到小有机器级别的并发，堆机器做同样的事情；或者线程级别的并发，利用多线程多核并发计算；或者指令级别的并发，在一个指令上操作多个数据。

其他并发处理方式比较常见，那么指令级并发怎么理解呢？冯诺依曼式架构是CPU从存储系统中加载指令和数据，完成指令并把结果保存到存储系统。通常一个指令操作一个数据，生成一份结果。而SIMD(Single Instruction Multiple Data)指令是一类特殊的CPU指令类型，这种指令可以在一条指令中，同时操作多个数据。

SIMD指令的作用是向量化执行(Vectorized Execution)，中文通常翻译成向量化，但是这个词并不是很好，更好的翻译是数组化执行，表示一次指令操作数组中的多个数据，而不是一次处理一个数据；向量则代表有数值和方向，显然在这里的意义用数组更能准确的表达。在操作SIMD指令时，一次性把多条数据从内存加载到宽寄存器中，通过一条并行指令同时完成多条数据的计算。例如一个操作32字节(256位)的指令，可以同时操作8个int类型，获得8倍的加速。同时利用SIMD减少循环次数，大大减少了循环跳转指令，也能获得加速。SIMD指令可以有0个参数、1个数组参数、2个数组参数。如果有一个数组参数，指令计算完数组中的每个元素后，分别把结果写入对应位置；如果是有两个参数，则两个参数对应的位置分别完成指定操作，写入到对应位置。

编译器通过SIMD加速的原理是：通过把循环语句展开，减少循环次数，循环展开的作用是减少循环时的跳转语句，跳转会破坏流水线；而流水线可以预先加载指令，减少CPU停顿时间，因此减少跳转指令可以提升流水线的效率。

图：SIMD指令同时操作A和B中4对数字，产生4个结果存放到C中

以如下代码为例，对4个float计算平方：

1
2
3
4
5
6
7
8
9

void squre( float* ptr )
{
		for( int i = 0; i < 4; i++ )
   	{
			const float f = ptr[ i ];
    	ptr[ i ] = f * f;
		}
}

上述代码转写成SIMD指令，则可以删除循环，用三条指令即可完成计算，分别是加载到寄存器，计算平方，结果写回内存:

1
2
3
4
5
6

void squre(float * ptr)
{
	  __m128 f = _mm_loadu_ps( ptr ); 
	  f = _mm_mul_ps( f, f ); 
     _mm_storeu_ps( ptr, f );
}

理论上，各种数据类型和指令宽度下的加速比如下表，在最好的情况，对char类型可实现64倍提速。

SIMD扩展指令集

SIMD指令的运行方式时，把一组数据加载到宽寄存器(128位、256位、512位）中，然后生成结果放到另一个宽寄存器中。

SIMD指令需要硬件支持MMX系列，SSE(Streaming SIMD Extensions)系列、AVX(Advanced Vector Extensions)系列扩展指令集。SSE1、SSE2、SSE3、SSE4.1、SSE4.2操作的是16字节寄存器，AVX、AVX2引入了32字节寄存器，AVX512引入了64字节寄存器。目前大部分CPU都支持AVX2，只有最新的CPU才支持AVX512。

指令集需要CPU硬件支持，下标列出了支持各个指令集的CPU。

ARM也引入了SIMD扩展指令。典型的SIMD操作包括算术运算(+-*/)以及abs、sqrt等，完整的指令集合请参考英特尔提供的使用文档https://software.intel.com/sites/landingpage/IntrinsicsGuide/#

那么如何生成SIMD指令呢？有几种方式：

1. 编译器自动向量化：
   1. 静态编译。
   2. 即时编译（JIT）。
2. 可以手写SIMD指令。

编译器静态自动向量化：

对于编译器自动向量化，需要有几个条件：

1. 代码满足一定的范式。后续会详细展开介绍各种case。
2. 对于常用的编译器入gcc和clang，在编译选项上加上-O3的选项，开启向量化。

编译器选择和选项

在编译时，编译选项中加上-O3或者 -mavx2 -march=native -ftree-vectorize，可以开启向量化。

只有高版本的编译器才能实现向量化，gcc 4.9.2及以下测试不支持向量化。gcc 9.2.1支持。gcc对向量化的支持更加友好，而clang对某些代码无法转化成向量化。而有些情况下，clang生成的向量化代码性能比gcc更好（采用更宽的寄存器指令导致的）。不一而足。因此，建议编写符合规范的代码，然后分别测试两种编译器的性能。

1
2

res[i] = tmpBitPtr[i] & opBitPtr[i];   //使用下标访问地址，clang和gcc都支持
*(res + i) = *(tmpBitPtr + i) & *(opBitPtr + i);  //使用地址运算访问内存，clang不支持，gcc支持

如何写出可向量化的代码：

为了更好的引导编译器给你的代码生成向量化代码，编程上有一些最佳实践。

1 循环的次数要是可计数的

循环的变量初始值和结束值要固定，例如

1
2

for (int i = 0;i < n ;++i ) //总的次数是可以计数的,这种写法可以向量化
for (int i = 0;i != n;++i) //总的次数不可计数，这种写法无法向量

2 简单直接的计算，不包含函数调用

计算只包含简单的加减乘除等数学运算、与或非等逻辑运算。不要包含switch，if，return等语句。

此处有一些例外是，部分三角函数(sin,cos等)或者算术函数(pow,log等)因为lib提供了内置的向量化实现，是可以自动向量化的。

3 在循环的最内层

只有最内层的循环可以向量化

4 访问连续的内存空间

也就是函数的计算参数和结果必须存放在连续空间中，通过一条simd指令从内存加载到寄存器。

1
2

for (int i=0; i<SIZE; i+=2) b[i] += a[i] * x[i];   //访问连续空间，可以向量化
for (int i=0; i<SIZE; i+=2) b[i] += a[i] * x[index[i]] //访问非连续空间，不能向量化

5 数据无依赖

这是最重要的一条，因为是并行计算，属于同一条并行指令的多个独立指令所操作的数字，之间不能有关联，否则就不能并行化处理，只能串行计算。

数据依赖有几种场景：

1
2
3
4
5
6
7
8
9

for (j=1; j<MAX; j++) A[j]=A[j-1]+1;// case 1 先写后读，不能向量化
for (j=1; j<MAX; j++) A[j-1]=A[j]+1;// case 2 先读后写，不能向量化
for (j=1; j<MAX; j++) A[j-4]=A[j]+1;// case 3 虽然是先读后写，但假如4组数据组成一个向量，那么同一组数据内无依赖的，因而可以向量化
                                     // case 4 先写后写，无法向量化（此处无案例）
for (j=1; j<MAX; j++) B[j]=A[j]+A[j-1]+1;//case 5 先读后读，因为没有写操作，不影响向量化
for (j=1; j<MAX; j++) sum = sum + A[j]*B[j] //case 6 这种可以向量化，虽然每次都会读同一个变量，再写一个变量，因为可以先用一个宽寄存器表示sum，分别累加每一路数据，循环结束后再累加宽寄存器中的值。
 for (i = 0; i < size; i++) {
 		c[i] = a[i] * b[i];
 }// case 7这种要确认c的内存空间和a/b的内存空间十分有交集。如果c是a或者b的别名，比如c=a+1，那么c[i] = a[i+1]，那a和c就有内存交集了。

上述几个例子中，case 3、5、6是可以向量化的，这些case属于比较特殊的case，正常而言建议还是写出明确无任何依赖问题的代码。如果确定有依赖，仍想使用向量化，可以手动编写SIMD代码。

6 使用数组而不是指针

尽管使用指针可以达到数组类似的效果，但是使用数组，可以减少出现意外依赖的可能。而使用指针的时候，有些场景下连编译器也无法确认是否可以向量化。使用数组则没有这种担忧，编译器可以很容易的向量化。

7 使用循环的计数器作为数组的下标

直接使用循环的计数器作为数组的下标访问，可以简化编译器的理解。如果额外的使用其他值作为下标，则很难确认能否向量化。例如

1
2

for(int i = 0;i < 10;i++)  a[i] = b[i] //这种较好
for(int i =0,index=0;i < 10;i++)  a[index++]=b[index] //这种无法向量化

8 使用更高效的内存布局

数据最好以16字节或者32字节对齐。数组的元素最好是基础类型，而不是结构体或类。如果是一个复杂结构，那么同一个数组中每个对象的相同元素并不是相邻存储的。

9 循环次数并不需要是指令宽度的整数倍。

在一些老的编译器中，循环的次数需要是指令宽度的整数倍，例如128位指令，操作4字节的int类型，可以同时操作4个int类型，那么就要求循环次数是4的整数倍。因此写代码时，需要写成两个循环，第一部分是4的整数倍循环；第二部分是末尾多出来的少量数据。

而最新的编译器以及能够自动化的处理这种情况，编写代码按照正常逻辑写就行，无需拆分成两部分。编译器生成的代码会自动生成两部分逻辑。

手写SIMD 代码

编译器能把直接了当的逻辑转换为SIMD指令，并且需要我们认真的考虑代码风格，避免阻碍向量化。但是有些比较复杂的逻辑，编译器是无法自动向量化的，而我们人类知道这里边的逻辑是每个操作数分别计算，互不干扰，可以使用向量化。这种情况，我们可以手写SIMD代码。举一个典型的例子，把一个字符串转成全小写。

SIMD代码例子和不同编译器性能对比

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

const static char not_case_lower_bound = 'A';
const static char not_case_upper_bound= 'Z';
static void lowerStrWithSIMD(const char * src, const char * src_end, char * dst)
{   
    const auto flip_case_mask = 'A' ^ 'a';

#ifdef __SSE2__
    const auto bytes_sse = sizeof(__m128i);
    const auto * src_end_sse = src_end - (src_end - src) % bytes_sse;
    
    const auto v_not_case_lower_bound = _mm_set1_epi8(not_case_lower_bound - 1);
    const auto v_not_case_upper_bound = _mm_set1_epi8(not_case_upper_bound + 1);
    const auto v_flip_case_mask = _mm_set1_epi8(flip_case_mask);
    
    for (; src < src_end_sse; src += bytes_sse, dst += bytes_sse)
    {   
        /// load 16 sequential 8-bit characters
        const auto chars = _mm_loadu_si128(reinterpret_cast<const __m128i *>(src));
        
        /// find which 8-bit sequences belong to range [case_lower_bound, case_upper_bound]
        const auto is_not_case
            = _mm_and_si128(_mm_cmpgt_epi8(chars, v_not_case_lower_bound), _mm_cmplt_epi8(chars, v_not_case_upper_bound));
        
        /// keep lip_case_mask _mm_and_si128(v_flip_case_mask, is_not_case);
        
        /// flip case by applying calculated mask
         const auto xor_mask = _mm_and_si128(v_flip_case_mask, is_not_case);
        const auto cased_chars = _mm_xor_si128(chars, xor_mask);
        
        /// store result back to destination
        _mm_storeu_si128(reinterpret_cast<__m128i *>(dst), cased_chars);
    }
#endif
    
    for (; src < src_end; ++src, ++dst)
        if (*src >= not_case_lower_bound && *src <= not_case_upper_bound)
            *dst = *src ^ flip_case_mask;
        else
            *dst = *src;
}
static void lowerStr(const char * src, const char * src_end, char * dst)
{   
    const auto flip_case_mask = 'A' ^ 'a';

    for (; src < src_end; ++src, ++dst)
        if (*src >= not_case_lower_bound && *src <= not_case_upper_bound)
            *dst = *src ^ flip_case_mask;
        else
            *dst = *src;
}

上述两个函数用于把字符串中的大写字母转换成小写字母，第一个函数采用了SIMD实现（采用128位指令），第二个函数采用了普通的做法。由于第一个是128位指令（16字节），理论上相比非向量化指令，加速比是16倍。但是由于第二个代码在结构上是很清晰的，也可以自动向量化，在这里我们测试下不同编译器的编译性能,g++版本9.3.0,clang++12.0.0

结论：在相同的优化级别下，clang生成更宽的指令，性能更好。

解读SIMD指令

最简单的SIMD指令，实现两个数字的加法:

1

const __m128i dst = _mm_add_epi32(left,right);

这条指令把4组int类型数字相加，填写到结果中。__m128i代表是128位宽寄存器，存放的是int类型（4字节32位），可以存放4个int类型。_mm_and_epi32是一个simd指令，_mm开头表示128寄存器，add表示相加,epi32表示32位整数。SIMD指令的命名规范：在SIMD指令中，需要表达三个含义，分别是寄存器宽度、操作类型、和参数宽度。

各种类型对应到各种宽度的寄存器上的写法：

寄存器宽度，例如128位寄存器以_mm开头,参考如下表格映射关系：

操作类型，例如xor、and、intersect等操作。

参数宽度：参数中单条数据的位数，在指令的后缀中包含该信息，例如浮点数是32位，双精度浮点数是64位，那么在128位寄存器上，可以输入4个浮点数或者2个双精度浮点数。有些指令没有输入参数，则没有参数宽度信息。例如epi16代表16位int，详细的信息参考如下表格:

例如函数__m128 _mm_div_ps (__m128 a, __m128 b)，根据指令名称__mm开头，代表寄存器是128位，div表示除法，ps结尾代表操作的参数是32位浮点数。即同时加载两个数组，每个数组包含了4个32位单精度浮点数，完成两个数组对应位置数字的除法运算，返回4个除法结果.

通常，指令的结果宽度是和参数的宽度是保持一致的，但也有例外。

通常，两个向量执行SIMD指令，是两个向量的对应位置的数据分别执行操作。但也有些例外，比如同一个向量的相邻数据执行操作，称为水平操作，例如指令__m128i _mm_hadd_epi16 (__m128i a, __m128i b)，指令中的h代表horizontal，依次把a和b相邻的数据想加，如果a值为[1,2,3,4]，b值为[5,6,7,8]，那么结果为[1+2,3+4,5+6,7+8]。

通常，两个向量的所有数据都参与计算，但也有例外，通过掩码控制部分数据参与计算，掩码的第几位为1，则代表第几个数字参与计算。例如函数__m128i _mm_mask_add_epi16 (__m128i src, __mmask8 k, __m128i a, __m128i b)，用k作为掩码，第几位为1，则返回a和b对应位数的和；如果为0，则返回src对应位置的数。

SIMD 指令集合中包含的功能有：算术、比较、加密、位运算、逻辑运算、统计和概率、位移、内存加载和存储、shuffle。

1)SIMD内存操作

SIMD内存操作把数据加载到寄存器，并且返回对应SIMD类型。加载16位数据指令_mm_load_si128，加载64位数据指令：_mm256_load_ps，这两个指令要求数据是对齐的。如果是非对齐的数据，则采用_mm_loadu_si128和_mm256_loadu_ps。

2)SIMD初始化寄存器指令

初始化为0的指令。_mm_setzero_ps和_mm256_setzero_si256把寄存器初始化为0，初始化操作没有任何依赖。

初始化为特定值。_mm[256]_set_XXX把每一个点初始化不同的值，_mm[256]_set1_XXX 把每一个点初始化相同的值。[256]代表是否出现256，如果出现256。_mm_set_epi32(1,2,3,4)表示按照顺序初始化为整型数[1,2,3,4]。如果时倒序初始化，则使用_mm_setr_epi32(1,2,3,4)。

3)位运算指令

Float和int有很多位运算指令，包括AND、OR、XOR。如果要执行NOT指令，则最快的方式就是和全1做XOR，而获得全1的最快方式就是把两个0做相等比较。如下代码样例：

1
2
3
4
5
6

__m128i bitwiseNot(__m128i x)
{
	const __m128i zero = _mm_setzero_si128();
	const __128i one = _mm_cmpeq_epi32(zero, zero);
	return _mm_xor_si128(x, one);
}

4)浮点数指令

浮点数指令支持基础的运算+-*/，和扩展的运算sqrt。一些比较有用的函数有_mm_min_ss(a,b)， 对于32位浮点数，如果要完成，对应的SIMD指令是_mm_rcp_ps，而对应的SIMD指令是_mm_rsqrt_ps，采用SIMD指令可以在一条指令内完成，速度更快。

如果想加两个数组，例如[a,b,c,d]+[e,f,g,h]=[a+e,b+f,c+g,d+h]，对应的SIMD指令是_mm_hadd_ps，_mm_hadd_pd，_mm256_hadd_pd，_mm256_hadd_ps

5)非并行指令，却能做到加速效果

有些指令，在一条数据中只能操作一条数据，但是也能达到加速的效果。例如_mm_min_ss指令，表示取两个浮点数的最小值，该指令可以用一条指令完成计算，避免跳转，避免通过分支指令跳转。同理，取最大值的指令是_mm_max_sd。

手写SIMD指令的缺点

虽然手写SIMD指令看起来很酷，但是存在一个很大的问题是可移植性不强，如果你手写一个512位宽的指令，却在一个不支持avx指令集的机器上运行，那就会出问题。所以最好的方案还是编写符合编译器向量化规范的代码，把向量化这件事情交给编译器好了！最新的编译器会帮助我们解决这些事情。

结论

最新的编译器已经足够智能，能够自动化的实现向量化。而飞天长期使用4.1.2的编译器，最近一年才改到4.9.2，和最新的9.x编译器对比起性能，仍有比较大的差距。这种差距过于明显，是明显的代差，能够相差几倍。试想一下，代码不变的情况下，仅仅提升下编译器版本就能实现几倍的性能提升，这种结果过于震撼。因此提升编译器版本势在必行。

除了提升编译器版本，也需要提高开发者编写代码的能力，能够尽可能的编写出符合上文定义的几种规范，然后让编译器帮助我们生成高效的执行代码。

遗留问题：

c++ vector类型能否向量化。

foreach能否向量化

寄存器类型和数量

寄存器、内存体系结构。

上海突然封城，造成了物资紧张。大人还好办，好赖能充饥就行。但是小孩的物资是很挑剔的，奶粉和尿不湿是必需品。因此我就考虑了怎么才能远距离把紧急物资投送到家里。正好在B站看了一些航模的介绍，于是就做了下航模的调研，看能否用来载货。

无人机的分类

大众常见的无人机类型包括：

固定翼

固定翼是最传统的航空模型，主要由飞手使用遥控器目视飞行。固定翼是最传统的航空模型，主要由飞手使用遥控器目视飞行。固定翼也是最接近真实飞机的，各种组件以及飞行原理，和真实飞机类似。多旋翼依靠发动机实现向前的推力，有了速度后，通过机翼实现向上的升力。固定翼的好处在于，能够达到一个很低的推重比，在空中的姿态有更多的可玩性，同时因为推力在水平方向上，可以达到很高的速度。固定翼的劣势在于，起降需要借助跑道，需要严格关注空中的姿态，操作不当就会炸机，非常考验操作者的观察能力和操作能力，因此更具备挑战性，更烧钱。鉴于固定翼飞机能够达到一个很低的推重比，相同的发动机下，固定翼可以载货更多，因此本文主要介绍固定翼飞机的原理。

多旋翼

多旋翼的典型参考大疆的无人机。多旋翼和单旋翼一样，通过发动机的推力维持。多旋翼可以实现空中悬停，不需要跑道就能起降，因此门槛较低。但是多旋翼完全依靠电机的推力实现载重，推重比需要达到1以上才能起飞，所谓大力飞砖就是说只要推力足够大，火箭也能升上天。而发动机是制造成本里边占比最高的组件了，因此成本也很高。不过多旋翼的优势在于可以垂直起降，并且可以稳定在空中，因此操作成本较低，不会轻易炸机，玩家受众多。

固定翼和多旋翼是我们常见的两种无人机，还有其它一些衍生的无人机，这里不再一一介绍，本文的目标是介绍固定翼飞机的原理和入门，介绍这两种无人机只是方便对无人机有一个简单的认知。航模界的玩家一般是把一些商用大飞机或者战斗机，等比例缩小，制作成模型飞机，再配上一些关键的组件，完成空中的飞行。

固定翼结构和核心组件

主体结构

1. 从主体结构上，飞机由前后的机身和左右的机翼构成主体结构。
2. 在机身的头部可以安装发动机和螺旋桨，当然发动机和螺旋桨也可以安装到机翼上。
3. 在机身的尾部是尾翼，分为水平尾翼和垂直尾翼，水平尾翼上有可以调整水平方向的升降舵，可控制机头的抬起和下降。垂直尾翼上有方向舵，可控制飞机左右调整方向。
4. 在机翼上附着的组件有襟翼和副翼。襟翼靠近内侧，距离重心较近，因此他不会用来调整方向，而是提供升力。襟翼只能向下运动，向下运动后，襟翼的受力会转化成升力。
5. 副翼是机翼上离中心较远的组件，由于离重心较远，受力可通过杠杆作用放大，用于实现飞机的滚转。在同一时刻，左右副翼的运动是相反的。也就是同一时刻，左右副翼的受力正好相反，但达到的效果是相同的，要么顺时针受力，要么逆时针受力，以此实现滚转。
6. 起落架，起飞和降落时需要起落架。

在原理上可以区分襟翼和副翼，但是在机身上，襟翼和副翼可以实现混控，也就是机身组件是同一套，但是通过舵机实现不同的效果，当同向运动时，是襟翼；当向相反方向运动时，是副翼。

控制组件

上边这些结构是飞机上能看到的核心组件，还有一些控制组件，用于控制飞机的飞行。

1. 发动机需要能源，能源可以是燃油也可以是电池，一般藏在机身内部，重心附近。
2. 襟翼、尾翼、方向舵、升降舵的动作也需要动力来源，动力来自舵机。由舵机控制四个组件运动。舵机通过钢丝线拉动舵面运动。
3. 遥控器和接收机，遥控器是地面人员用于控制飞机速度和姿态的，接收机安装在机身内，用于接受遥控器的无线电信号。
4. 发动机的速度变化，需要通过调节电流来达到控制速度变化的目的。电调就是控制电流变化的组件。在遥控器上调节油门时，电调就可以调整电流的大小，进而达到控制发动机速度的。在选择电调时，要注意最大工作电流，需要大于电机的最大工作电流。

电池介绍

航模一般使用锂电池，电池涉及到一些基本参数，比如4S 2200maH，2200mAh代表电池的容量，表示可以以2200mA持续放电1小时，4S指的是串联电芯数，也就是4块电芯，每块电芯的标准电压是3.7V，充满电是4.2V。4S的标准电压也就是14.8V，充满电是16.8V。也有并联的电池，3S4P代表3串4并，并联可以提升电流，一般不需要并联电池。此外还有最大放电倍率和最大充电倍率，最大放电倍率35C，代表最大可以是标准电流的35倍放电，最大充电倍率5C代表以标准充电电流的5倍充电，其中标准电流就是上边是2200mA，也就是2.2A。锂电池要注意保养，不能长时间低于3.7V工作，可以通过安装BB响，针对低电压告警。

电机介绍

根据动力系统的不同，航模可分为电动、油动、涡轮喷气、火箭助推和无动力滑翔这几类。电机靠带动螺旋桨旋转，窝喷靠喷推动。电机的动力比不上窝喷。但是电机比较便宜，涡喷发动机比较贵。对于新入门而言，电机是更主流的选择，安装调试和保养都比较简单。电动机也可以模仿喷气式飞机，电机外围包裹涵道，在内部安装多片直径较小的螺旋桨。包裹在涵道内的螺旋桨可以产生更大的推力，但相比窝喷仍然是比较低的。
电机的核心参数是KV值。KV值指的是电机的压每升高1V，转速就提高一个KV值的数目，转速越高，电机输出扭力越小，反之亦然。遥控器通过控制电调调整电流大小，进而改变电机的转速。
一般来说，高KV值电机搭配小直径的螺旋桨，低KV值电机则搭配较大的螺旋桨。
在航模领域，常用的电机是新西达电机，性价比高。

螺旋桨

螺旋桨主要关注桨的尺寸，和电机的功率要匹配，注意电机到地面的距离。

遥控器

遥控器发射信号，机身上的接收机接受信号，并传递给对应组件。遥控器分为左手油门和右手油门，顾名思义，油门分别在左侧或者右侧。真实的飞机，油门在左侧，因此推荐左手油门。 以左手油门为例，左侧摇杆上下控制油门，左右控制方向舵；右手摇杆上下控制升降，左右控制副翼。
除了油门，还有多个通道，每个通道控制一个舵机的运动。通道当然越多越好，但是越多肯定越贵，一般旋转6通道就足够了。
此外，还要关注，遥控器的距离，至少需要500米到1000米。如果太短，飞机飞出遥控距离容易失控；而太长了，人也看不清飞机的姿态，也容易失控。
入门级遥控器，有富斯i6价位在200多,MC6C价位在100多。遥控器不同于其他组件，其他组件飞上天可能会摔坏，但是遥控器是可以长期使用的，不建议买太差的。

接收机

接收机每个通道分别有正极、负极、信号孔，执行设备通过排线连接接收机。接收机可通过电调供电，插入任意一个通道即可。
操作各个通道，飞机各个部分的动作如下：

固定翼飞行原理

升力原理

固定翼飞机是如何升上天空的呢？特殊构造的机翼表面，下方接近扁平，而上方则有凸起。发动机提供了向前的速度，当气流流过机翼表面时，上方的气流压强较小，下方气流压强较大。上下的压强差提供了向上的升力。当升力大于重力时，飞机上升高度。升力翼形和翼展相关。

舵机

舵机有金属齿和塑料齿。前者更重一些，但是不容易扫齿，更耐用。舵机上也会注明扭矩，也就是力量。一般来说，尺寸大的，扭矩更大。

控制方式

通过电机的转速可以改变飞行速度。
而飞机的姿态、方向的变化，则通过方向舵、升降舵、副翼来完成。这三个结构的特点是离重心比较远，受力后通过杠杆作用放大；围绕重心两侧，一侧受力，一侧不受力，受力不均衡就会产生偏斜，以此达到改变姿态的效果。
襟翼，位于重心附近，而且重心两侧的受力是一样的，因此不会改变飞行姿态，但是会增加阻力，把一部分阻力转化为升力。

反扭力

如果发动机安装到机头，螺旋桨向一个方向转动时，形成的空气漩涡会撞击到机尾的垂直尾翼上，导致尾翼受到一个同方向的力。由于尾翼远离重心，收到的力叠加杠杆作用，会导致尾部向受力方向偏转。由于机尾和机头位于重心的两端，所以相当于机头受到了一个反方向的力，也就是和旋转方向相反的力，这就是反扭力。因此单发飞机会出现偏航。
要克服反扭力，在安装发动机时，可以适当偏斜一点，以抵消反扭力。
另一种办法是安装双发动机，分别位于机翼的两侧，两个发动机按照相反方向运动，互相抵消反扭力。

模拟器

好了，硬件装备介绍完了，那么怎么才能让飞机升天呢？人在地面遥控飞机，和坐在飞机里驾驶飞机，感觉是完全不一样的。坐在驾驶舱，有各种仪表设备显示飞机的各项指标，能清楚的感知飞机的姿态和状态。而在地面遥控飞机，首先看不清飞机姿态，其次，地面视角还要转化成飞行员视角，这是很难的。而稍微操作不当。而稍微操作不当，导致飞机掉下来，把硬件摔坏，损失就太大了。机身或者零件摔坏，就得重新花钱买，因此玩航模的成本极高。为了避免炸机，最好的办法是在模拟器上训练好在上天，能做到从地面视角理解飞行员视角。最重要的是，即便是在模拟器中摔掉100架飞机，你也不会损失一分钱。

模拟器是安装在电脑上的软件，遥控器通过加密狗接入电脑，可以控制模拟器飞机的运动。

新手入门，最简单的是练习无边航线，通过无边航线训练起飞，转弯，降落等重要的操作。

飞机常见动作

起飞

飞机在跑道上达到足够的速度后，通过让升降舵向上抬起，升降舵受到向下的力，相当于机头受到一个向上的力，进而飞机抬头上升。机头抬起时，容易失速，应该注意速度。

上升

上升过程类似起飞，也是让机头抬起。

下降

下降时，通过让升降舵下压。让机尾收到向上的力，相当于机头受到向下的力。进而飞机向下俯冲。飞机向下俯冲时，叠加重力因素，飞机会加速。

降落

降落，则是初学飞行时最难掌握的本领。降落分为欧式降落或俄式降落。
在降落时，飞机飞行的高度、俯冲的角度和接地时的速度都需要精确操控，而且不同的飞机在降落阶段的特性也各不相同，必须逐个细心掌握。概括起来说，降落包括3个环节：首先降低飞行高度，低空通过场地并保持航线；然后调整油门，进一步降低高度；当飞机距离地面一米左右时，持续拉一点升降舵，使飞机轻微仰头，让起落架平稳地接触地面。
欧式降落，保持机头向上，通过降低速度，不断降低高度，后起落架先着地，由于重心在前后起落架中间，速度向前，因此后起落架先着地的冲击力比较小。由于速度和升力相关，如果速度过低，会导致升力不足而失速。因此在下降时，需要时刻关注飞行姿态。如果降落发生问题，无法落地，复飞也会因为速度不足而受影响。
俄式降落，是向下俯冲，下降过程速度不降低，直到快落地时才调整机头向上。这种做法比较有挑战。

滚转

滚转通过控制副翼的上下运动来实现，两侧副翼相向运动，使一侧受到向上的力，机翼上升；另一侧收到向下的力，机翼下降，在回正前，会持续圆周运动，也就是发生滚转。

偏航

飞机的偏航由垂直方向舵控制，需要向哪边转就向对应方向打方向舵。偏航只用于微调运动方向。不适用于转弯。

转弯

转弯需要副翼和升降舵配合使用。首先，利用副翼将机翼向要转的方向滚转，然后将副翼操纵杆“回中”(回归零位，以便下次操作），以使机翼不再进一步倾斜。此时立即拉升降舵，直到飞机转向到合适位置，再将升降舵操纵杆回中，以停止转弯。然后向相反方向打副翼，使机翼恢复水平状态。最后，在机翼恢复水平状态的那一刹，将副翼回中。

实操

一般玩航模，上边说的那些控制组件，可以分别购买。机身可以购买空的机身或者用3D打印自己打印机身。机身因为负载比较轻，一般是泡沫材料。

入门机型

新手入门采用的机型有：赛斯纳，冲浪者。赛斯纳是一款真私人飞机的微缩版，冲浪者没有原型。两者的区别在于，赛斯纳有起落架，螺旋桨在最前方，因而速度更高；冲浪者螺旋桨没有起落架，螺旋桨在翼后方。因此在炸机时，赛斯纳的螺旋桨更容易损坏，而冲浪者的螺旋桨可以受到保护。但是赛斯纳可以训练起飞和降落，而冲浪者因没有起落架而无法训练起飞和降落。

炸机常见问题

航模炸机的主要原因：看不清飞机姿态；飞机失速。其实这些问题都可以用自动驾驶来解决。在飞机上安装陀螺仪和GPS。通过陀螺仪判断飞机的姿态，上下左右是否平衡。通过GPS判断位置和计算速度。采集的信息传递到机载芯片上，对姿态做一下判断，然后做一下对应的操作应对。如果是失速，则应该立即下压机头，俯冲提速。如果向左或者向右倾斜，则打副翼让姿态回正。一些玩具厂家就是通过内在陀螺仪，自动纠正错误姿态，避免炸机。通过这种程序化的处理，是可以减少炸机的概率的。同时通过无人驾驶，设定好GPS航路坐标后，可以脱离遥控器飞得更远。如果加上物联网卡，则可以实现远程的控制。

搭载货物

搭载货物意味着提升了重力，需要更大的升力。对于多旋翼飞机，推重比至少得是1。而固定翼飞机，推重比能够低到0.2。 也就是相同的发动机，固定翼的载货量可以达到多旋翼的5倍以上。固定翼飞机的速度，升力，转弯的灵活度等，都是相互关联的性能因素，可以通过调整参数结构，尽可能的牺牲其他性能，尽可能的提升载重量。通过设计机翼，采用高升阻比的低速翼型，机翼平面形状做大。不过载重提升后，对机翼的结构强度要求比较高。从一些航模比赛中获得的数据，大概可以承受自重的5到6倍以上。

成本估算

最便宜的入门遥控器MC6C 200+
最便宜的一套控制配件 100
赛斯纳空机 100+
充电器100+
总体而言需要500+的入门费用。
此外模拟机需要用windows电脑。
如果炸机，则需要更换损坏的机身或者配件。航模真是个烧钱并且劝退的兴趣。

资料库

Flite Test 提供航模的资料和图纸。

参考资料

固定翼飞机的结构及飞行原理.ppt
固定翼无人机的结构及飞行原理
【机型知识】固定翼飞机的飞行原理简介（一）
航模飞空(上)
航模飞空(下）
【航模制作入门】5分钟了解航模电子设备
如何用最低的价格，买一套入门航模设备
【固定翼飞手1】航模入门教程•必要设备介绍
固定翼飞手2】航模入门教程•怎样购买空机与航模装备 最便宜？高性价比？
无人机基础知识-组成-航模电机

数据用途和玩转数据的手段

数据分析通常用于商业决策，一般在大公司中，会养一个专门的商业分析部门，专门采集各种数据用于辅助董事会/CEO等决策层做核心的商业决策。但是，数据分析的需求无处不在，在各个业务线中也有对于数据分析的诉求，例如运营部分，一个运营活动的好坏、应该向哪个渠道投放资源，不能靠拍脑袋决定，要分析具体数据。同样对于开发运维也一样，线上系统是否稳定，各个模块指标怎么样，都需要数据得到反馈。对于董事会，可以养一个专门的机构搞数据分析；而对于普通的业务线，那只能自助分析了。今天我们就来总结一下数据分析的方法，如何洞察数据中的有效信息。
数据分析首先得有数据，从各个地方采集数据。所谓巧妇难为无米之炊，没有数据更谈不上数据洞察。有些公司，成立商业分析部门，干的活却是窃取其他公司的商业核心数据，愣是把一个高上大的技术名词搞成了间谍。20世纪上半叶，数学上的统计学在各行各业流行开来，数学家们，利用很少的数据，再加上统计学理论，推断一个结论。如经典的”女士品茶”这个故事，通过数据判定女士到底有没有某个超能力。至于把商业分析干成商业间谍的人，大概是不懂得需要如何合法的采集数据，以及分析数据的手段吧。
数据存储无需多讨论，要分析数据，首先要把数据存储下来，无论是存储在云端也好，还是excel也好，只有存储下来，才能方便后续的计算和分析。
数据有哪些使用方式呢？这里列举了四种用法，例如report，monitoring，analysis，exploration/mining。我们可以按照两个维度来划分，需求是否明确，分析方式是否成熟。

有些需求场景是明确的，例如老板需要每天看几个关键的业务指标，那么就需要每天跑个固定的脚本，生成报告。在这个过程中分析方法也是固定的，即运行固定的计算逻辑。有些需求需要经过一番分析，例如某天业务量降低了，要分析下原因是什么，就需要从多种指标里边去探索。
还有些需求场景是不明确的，给你一份数据，我们知道数据里边有金矿，关键是怎么把数据中的核心信息捞出来，也需要探索才能找到，但是探索的目标不确定。这就是个开放式的话题了，也就是探索式数据分析：有数据，尝试找信息。应该沿着怎么样的一条路是探索呢？我认为有两种方式：

• 尝试不同的分析方法，例如统计方法/机器学习方，挨个尝试，看能得到什么结果。有哪些分析方法，会在下文列一下常用的手段。
• 尝试不同的目标，比如，首先用一句话描述数据的总体分布，然后找出其中的一些异常点，最后通过拟合数据做未来预测等等，有哪些分析目标，也会在下文列出一下常用的。

洞察数据的目标

寻找common pattern

common pattern是数据中出现频率最高的特征，可用于概括行描述一个数据集的总体信息。
​

寻找outlier

outlier是离群点，即数据集合中某个偏离common pattern的数据。在一些异常监控中经常用到。
​

分类

把一个数据集合分成不同的子集合，分成不同的类别。
​

验证假设

首先给出一个假设，通过数据给出证明。

预测

拟合已有的数据，根据模型预测未来数据。
​

无论哪种目标，最终都是需要能过帮助完成决策，只有完成决策，才算完沉了闭环，否则就是无意义的数据分析。

洞察数据的方法

一个优秀的软件，必定是有灵魂的，他的灵魂就是背后的方法论。Saas的本质，就是输出管理的理念和方法论，并且提供解决方案的工具。具体到数据分析工具而言，一个优秀的数据分析工具一定以数据分析方法论的为基础的，融合集合常见的数据分析方法。而不是东一榔头、西一棒槌追加分析函数，永远跟着甲方的需求跑，面向客户开发，面向demo开发，这样的话永远不成体系。
我们先来看个数据分析的笑话：

手里有个锤子，看什么都是钉子，数据分析专业的同学，看到什么都要现象都要分析一把。疫情也要分析一把，强行刷存在感。不过笑归笑，外行看热闹，内行看门道。在这个简短的笑话中，我们看到一些常见的数据分析方法：相关性分析、假设检验、ab测试、z test、数据分布、标准差、显著性水平等。

那么常见的数据分析方法有哪些呢？这些我们在大学的各个数学课程中都学习过了。首先我们做个分类，按照实现方式，数据分析包括：

• 基于统计算法的数据分析。
• 基于机器学习的数据分析。

按照是否需要人工标注，数据分析分为：

• 无监督学习，无需人工标注数据，根据已有数据直接分析。
• 监督学习，需要标注数据，根据数据标签训练模型，再用于推断未知数据的结论。
• 半监督学习，是无监督学习和监督学习的结合。

接下来将逐个介绍各种方法：

统计量分析

统计量用于评估数据的整体状况，统计量使用单一数字来描述数据的分布。例如估计位置信息：

• 均值
• 中位值

描述变异性：

• 方差
• 标准差

描述性统计量：

• 方差/标准差
• 离散系数
• 峰度
• 偏度
• 绝对中位差
• 中位数
• 单调性

分位统计量：

• 最大值
• 最小值
• 中位值
• 25分位
• 75分位
• 范围
• 四分位距

数据分布

数据分布的目标主要是查看数据的分布频率(分布密度)，针对不同的数据采取不同的分析方式，对于连续数据，采取散点图/箱线图(分位统计)描述。在散点图中，把所有的点都打印到图中，密度比较高的地方则说明分布比较多。对于离散数据，采取堆叠图/直方图描述。按照每个不同的类别，分桶后统计计数，然后用直方图绘出。同样的，对于连续数据也可以采取直方图的方式，把连续数据按照固定的桶大小分桶后再计数。

相关性

上文的统计量分析/数据分布分析，是用于分析单变量。 而对于多变量分析，则需要用到相关性分析。探索两个变量之间的相关性。在计算相关性时，主要计算两个数据集合的相关性系数。常见的相关性系数有皮尔逊系数、斯皮尔曼系数等。在计算好相关性系数后，可以绘制出一个相关性表如下：

抽样分布

抽样分布是用少量数据估算整体数据的分布情况，用途有三种：第一,可以概括性描述整体分布;第二可以根据整体分布预测未来的新数据；第三，可以利用分布系数来排查异常值。
常见的分布有：

• 正态分布： 如果确定数据服从正态分布，估算出正态分布的sigma后，我们可以使用3sigma来排除异常值。
• 长尾分布：大部分现实数据不是严格匹配正态分布的，数据的中心位置也许符合正态分布，但是在尾部常常有长尾效应。
• T分布
• 二项分布
• 泊松分布
• 指数分布

柏松分布和指数分布通常用于估算事件发生率，也可用于估算IT系统的故障发生率。或者用于估算系统的上限水位，例如一个IT系统，每分钟的流量是x qps，那么根据泊松分布，可以估算出最大值是多少qps，系统需要准备多少资源。
​

在现实的数据中，可能具备多种形状和类型，在特定场景下，应该首先确定数据集合服从哪种分布，求的分布系数后，再进行下一步的分析。
​

统计实验和假设性检验

假设检验有个很好的用途，例如我们的营销团队做了个活动，那么如何评估活动是否带来了客流量呢？我们都知道现实的数据可能是有波动的，可能有N天变高，M天变低。所以要评估是否活动的影响，可以使用假设检验来验证。
最常见的业务场景，例如A/B测试。两种算法，哪个效果更好，可以通过假设检验来完成。
常见的方法有T检验、卡方检验
例如

不同的标题下，有不同的点击率，那么这个点击率是随机造成的，还是标题起到了关键作用呢？可以通过卡方检验，计算皮尔逊残差，结果证明完全是随机作用。
​

回归和预测

在现实中，我们经常要回答的一个问题是，这两个指标之间是否有关联？如果有关联，是否可以通过其中一个指标预测另外一个指标。预测常见的一个使用场景是：根据预测的结果和实际的结果进行比对，然后判断是否有异常。

分类

在数据分析中，经常要回答一个问题，一个电子邮件是否是钓鱼邮件？一个客户是否会流失？这种情况就需要分类。分类是有监督的学习。
常用的分类算法有：

• 朴素贝叶斯
• 线性判别分析
• KNN
• 决策树
• Bagging
• 随机森林
• boosting
• SVM

聚类

聚类是无监督学习的分类方法，根据算法把数据集合分成几个类。常用的算法有：

• 主成因分析
• K-means
• 层次聚类

神经网络

神经网络是有监督学习，通过标注数据训练出模型，然后推断新的数据结果，篇幅有限，这里不再展开详细介绍。常用的算法有：

• 卷积神经网络CNN
• 循环神经网络RNN
• 深度神经网络DNN

数据分析工具和数据洞察解决方案

上文介紹了很多数据分析的方法算法。这些方法，归根结底是一个个工具，或者说是积木，用户可以使用这些积木组合成解决方案，解决自己特定的问题。市场上有很多系统提供类似的数据分析工具，例如Pandas，R，SQL，Tensorflow等等。 但是这依赖于使用者既要明确自己的分析目标，又要十分精通使用工具。 对于开放式的话题，在分析时需要不断尝试各种各样的手段进行分析，有些分析手段可能是无效的，因此需要不断尝试，在这个过程中浪费了太多的时间。如何能够快速洞察数据呢？
有些工具尝试集合数据分析的工具和数据洞察的解决方案，例如tableau，Knime等，而Pandas profiling则是一个纯粹的数据洞察方案。它自动的尝试上文描述的各种手段，把结论呈现给客户，减少了数据探索的时间，能过快速的完成数据洞察。
​

数据洞察工具的价值

针对开放式的课题，需要投入大量的人工时间在各个方向上探索，这存在几个问题：

• 可能以后某些关键路径，例如在分钟级别的数据看不出信息，而秒级别数据才能看出信息。若没有想到该方式，那么将极大延长发现问题的时间。
• 需要人工采用各种工具，在多个方向上探索。这无异需要大量的时间。

因此对于数据洞察工具的诉求就是：能过完全自动化的在各个方向上、尝试多种工具挖掘数据信息，达到最终对数据的insight。
​

2021年3月25日凌晨0：00，我参加了PrestoCon2021全球技术峰会，在会上直播分享了阿里云SLS使用Presto构建交互式分析产品的挑战和优化。本文是演讲稿全文。PrestoCon2021日程：https://prestoconday2021.sched.com/?iframe=no，直播视频已经上传到B站https://www.bilibili.com/video/BV1hK4y1m7qe/，B站还包括其他演讲视频。

hello everyone my name is yunlei. I work at Alibaba Cloud log service team. Today I will share petabytes scale log data analysis at Alibaba group, I will share our experience with presto, the challenges we faced and the optimizations we did for presto.
​
So today, I will first give an introduction about our team and talk about the motivation why we provide analysis service for logging data. And then I will talk about the challenges we face. And after that I will share our architecture to achieve scalability. And also share some ways to achieve low latency and high qps or high concurrency. And after that I will talk about some additional work based on the scalable framework of presto. And finally, I will talk about the future roadmap.
​
​

First let me introduce my team, this may help you have a better understanding of the background, and the motivation of my we provide analysis service for logging data. And we are log service team, we are providing the infrastructure of all kinds of logging data inside Alibaba group., for example linux server, web page, mobile phone, or kubernetes.. and all these data from different kinds of platforms are collected to our clusters in real time. And then, consumers can consume streaming data in real time, without worrying about different platforms.
And after that, we wanted to provide service just like what engineers can do on their linux servers. For example, we found that engineers often use the command grep to search some key word from their log file. So, in order to provide the real time interactive search, we build inverted index for logging data. By using inverted index, people can search large amount data with very low latency.
And after that we notices that in this era of data explosion, even the searching result may contain thousands to millions, even to billions of rows. That is a very large number, even thousands of data is large amount of data for human being’s eye, it is not easy to fully understand what is really appending inside the large amount data. But If, we can summarize the data, do aggregation on data, take web access log as an example, if we can calculate the average response time or max response time, we can better understand the whole data. That is the motivation my we provide analysis service for logging data. And we also have a visualization service, to visualize the interactive query result, which is helpful for understanding the data trend.
So, in summary, our team provide multi-tenant, interactive analysis for petabytes scale real time logging data.

What are the challenges we faced? The first challenge is the high QPS and high concurrency. Every day, we process about 400 millions queries, at the peak hour there are about 10000 queries running concurrently. Second, every day presto process over 1 quadrillion rows. Which is huge amount of data. But we can deliver the interactive query with very low latency. The average latency is only about 500 ms. So, how do we deal with those challenges, and how to achieve that low latency? In the latter slides, I will talk about some techniques we used.

​

In order to provide the interactive log analysis. The first thing we did is introducing presto into our system. Many people ask me the question that, why did we choose presto in the first day. Well, I think the first and most import reason is that, presto is really really fast, very flexible for interactive query. It suits our use case. Second reason, presto has a scalable framework. We can develop our own connector/function/optimization rule which makes it very easy to integrate presto with our own storage. Last, the architecture and coding style Is very elegant. The architecture is simple, it doesn’t rely on any external components for deployment. The coding style is also very simple, it is easy for us to learn its internal implementation, also easy for us to do some modification for optimization. That is the reason why we choose presto in the first day.
​

In order to deal with the large amount of data ingested every day. We design our architecture like this. This is simplified architecture, only analysis related components are included. Data from different kinds of platforms are collected to our cluster, in the backend, the index worker keeps building inverted index and column format data for logging data. And then all the data are stored in the distributed file system, which is called pangu. This is the flow of data ingestion. When submitting query, users can send their query by sdk or jdbc client through our front api server, to one coordinator. We support distributed coordinators, and I will talk more detail about the design. In the backend, presto server read inverted index for filtering and column data for computing. This is the flow of querying. And presto play a key role in this architecture.
​
How to support querying large amount of data? Every day we process about 1quadrillinon rows. Fortunately, presto is a pure computing engine, so it is easy to decouple computing and storage separately. So that we can scale presto horizontally. Also, log data has a feature that it is immutable after ingested. And in the backend, we keep compacting small file into larger file, when the file is large enough, the file will become immutable. One immutable file contains tens of millions rows.so, each time we schedule a file, we schedule each immutable file to one presto server. And by this way, we can use a lot of presto server for one query. And thus, we can query large amount of data in one query. And the performance is also significant. If we run a simple group by query on 200 billions rows, it only takes about 20 seconds. That is a large amount of data and the latency is acceptable.
​
So, how to achieve low latency? There are a few techniques we used. The first technique we used is column format storage. In the backend, we keep building column format data. We all know that column storage is helpful for reducing data size to read from disk, and also helpful for vectorized execution, thus it will makes query faster.
​

Another technique we used is data locality. We all know that, network speed inside cluster is much faster than network between clusters. So, we deploy storage and computing engine in same shared cluster. When scheduling task, we choose a free node by the order of machine, rack, cluster.
​

There are some other techniques we used, for example cache, inverted index. I will talk more detail about that.
​
We all know that cache can make query faster, it can also help us removing some duplicated computation. And in order to take advantage of cache, the scheduling algorithm has to remember scheduling history in memory. Every time we schedule a file, we schedule each immutable file to the same node it has been scheduled before, unless the workload of specified node is much too high. In that case, we will choose another free node.
So there are three layers of cache, from the bottom up, there are raw data cache, intermediate result cache, and final result cache. The raw data cache and final result cache are common solutions. But the intermediate cache is a very rare solution. So, I’d like to talk more detail about the intermediate cache. As I mentioned earlier, file is immutable. So, every time we schedule a file, we schedule each mapper with exactly one immutable file. Then after finishing the partial aggregation operator, we store the result of partial aggregation operator in memory. And next time when we run exactly the same partial aggregation operator on exactly the same immutable file, we can just read the result from the memory, and send the intermediate result to final aggregation operator directly, without reading data from disk and recomputing the partial aggregation operator. We all know that partial aggregation operator deals with large amount of data, and only generate small amount of data. So, most of the computation happens in the partial aggregation operator. By using intermediate cache, we can achieve a faster query and also save a lot of cpu and IO resource.
​

What about the performance of cache? Every day, there are more than about 100 millions query hitting final result cache. The average latency when hitting final result cache is only about 6 milliseconds. So, it is really fast. What’s more, final result cache can help us prevent a lot of duplicated computations and save us a lot of resource. What about the performance of intermediate cache? For 1 billion rows. It only takes about 1.3 second when hitting intermediate cache, but it will take 6 seconds when not hitting intermediate cache. So, the comparation of two latency is impressive.
​

Another technique we used is inverted index. In the first day, we use inverted index for searching data. After introducing presto into our system. I push down predicate from presto to storage system, and then use the inverted index to first calculate the matched row id, and use the matched row id to read matched rows, and then send only matched data to presto. This strategy is very effective if we can use inverted index to skip some file or only read small part of file. If you run a query select count(*), that will be extremely fast by using only index!.
​
Every day we are processing more than 400 million queries. And the main challenge is on coordinator. This picture was taken about 2 years ago. And at that time there was only one single coordinator. This picture shows the top 4 nodes with highest CPU usage of presto, the fist picture is coordinator. You may notice that the CPU usage of coordinator is much higher than normal workers. In our cluster, one single coordinator can process 1000 queries concurrently at most. So, the single coordinator is the bottleneck of the cluster. It has the problem of both scalability and availability. In order to improve the performance of coordinator, I did a few optimizations. The first optimization is supporting distributed scalable coordinators. The second optimization is transferring data from output stage to client directly, without worrying coordinator.
​
Let us look at the detailed design of distributed coordinators. I design the distributed coordinators for scalability. And there are two kinds of roles in this design: the global coordinator, and the distributed coordinators. The global coordinator has only one instance. It is responsible for cluster management. For example, detect node state, replicate all the node state to other coordinators, track memory usage, assign largest query to reserved pool. The distributed coordinators are responsible for query management. For example, parse query, create logical plan, optimize logical plan, schedule task, track task state. It is also responsible for a user queue. Every time submitting a query, user send his query to one coordinator based on the hashing of user name, in this way, all the queries belonging to one user can always be found in one coordinator. This design is not 100 percent perfect, because the global queue is not supported. But it is enough for our scenario. It helps us to scale coordinators horizontally for much higher concurrency.
​
Another thing we did is optimizing the data transfer flow. In the original design, the coordinator transfers query result from output stage to client. So, the coordinator has to serialize query result into json format. We all know that json serialization is very slow. What if coordinator transfers large amount of data? For example, 1 gigabytes data. That will take a lot of CPU usage of coordinator. In order to optimize the performance of coordinator, here is my solution. The coordinator will tell the client all the addresses of the output stage. Because there may more than one node in the output stage. And then client will use the addresses to talk to output stage to directly fetch data with protobuf format. By this way we can make query faster and save a lot of cpu usage of coordinator.
​

Here is the final performance. We can process 400 million queries every day by supporting distributed coordinator and optimizing data transfer. And by decoupling computing and storage, we can support processing over 1 quadrillion rows every day. By taking advantage of column storage, data locality, cache, inverted index, we can provide interactive query with very low latency, the average latency is only about 500 milliseconds.
​
Besides those optimizations, we also did a few additional works based on the scalable framework of presto. The first thing we did is machine learning library for time series data. We also noticed that only logging data is not enough for analysis. Sometimes, we need to join logging data with some external data. So, I developed a connector to read object file on OSS storage. We also use presto as a federated SQL engine.
​
In the future, there are still a lot of things to do. The biggest challenge is still on coordinator. We will keep optimizing coordinator. Another thing we want to do is increase the availability of discovery, by now, discovery has only one instance. We also want to improve the performance of data exchange by using rpc protocol, which will make it faster to shuffling large amount of data.

If you are interested in data analysis engine or OLAP engine, don’t hesitate connect me, our team are hiring OLAP engineers, let us work together to make data easy to understand!
​

数据分析类产品的发展历史

单机数据库时代

关系型数据库是发展了很多年的技术，在单机时代，微软的sql server ,甲骨文的oracle RDBMS，IBM的DB2是商业数据库的霸主。但是商业数据库实在太贵了，后来出现了开源的MySQL。阿里则干脆喊出了去IOE的口号。O就是oracle数据库。

在数据库上，用户不仅有OLTP的使用需求，也有分析的需求，就是OLAP。但是单机数据库，无论硬件性能还是软件扩展能力，都是有限的。为了应对分析需求，一般采用一些技巧来实现，一般有这几种方式

• 构建CUBE，按照要分析的问题，预计算出结果。这种思想在后来的Apache kylin上也有体现。
  • 这种方式的缺点在于，
    1. 维度多的时候数据膨胀会比较厉害；
    2. 需要预先把要分析的维度加入CUBE，不够灵活。
• 分库分表。单表的查询在百万以内还能应付，超过千万级别，性能急剧下降。因此一般会根据某些列拆成多张表，查询时只命中需要的表即可。这种思想类似于数仓中的分区概念。

MapReduce时代

2004年，Google发表了MapReduce论文，开启了大数据时代。Google产生的大数据需要分析，传统的数据库依赖单机的性能来提升查询能力，但单机的能力毕竟是有限的，无法支持PB级别的规模，Google则另辟蹊径，通过MapReduce算法，把成千上万的小型机调动起来运行同一个分析程序。

雅虎支持的开源社区则根据Google论文的思想，开发了Hadoop，成为现代大数据套件的鼻祖。Hadoop包含了MapReduce运行框架和HDFS分布式文件系统。之后的十多年间，围绕Hadoop衍生出了一整套的大数据生态系统，有做资源管理的，有做调度的，有做任务管理的，有做分布式锁的。要在生产环境把hadoop完整的跑起来，需要玩转多个组件，还真不容易。

MapReduce，解决了对大数据的分析需求。

SQL on hadoop时代

hadoop需要自己编写MapReduce的逻辑，使用门槛非常的高。一个公司内，需要有专门的大数据团队，来给各个业务方写分析程序。严重制约了使用范围。为了降低使用门槛，数据库常用的SQL语言被搬了出来。SQL可以说是数据分析领域受众最广的语言了。hive 就是典型的代表。数据存在在HDFS上，用户输入SQL，程序自动的拆解成MapReduce逻辑。用户不再需要关心底层的数据是怎么分布的，分析程序该如何根据哪个partition拆解MapReduce。大大降低了使用门槛。

SQL on hadoop的本质，是提供了SQL的interface，但底层还是MapReduce的DAG执行方式。每个任务的执行结果，需要写入磁盘。每个阶段执行完后，下一个阶段才能开始执行。这种方式延时会非常高，跑一个复杂的job，需要几个小时；一个简单的job也需要几分钟。因此通常称为离线任务，放到晚上业务空闲期跑。

SQL on hadoop 解决了对分析大数据的体验的需求。

MPP时代

离线任务能够帮助人们分析大数据，但是由于运行时间长，只能做一些固定模式的报表，每天晚上跑一跑前一天的数据，给领导一个报表。

需求是无止境的，互联网业务产生了海量的数据，往往要深入挖掘数据的价值，挖掘这个动作本身，就意味着分析存在不确定性，需要反复的探索数据，尝试不同的方式分析数据。用离线任务去分析，一个job几分钟乃至几个小时，黄花菜都凉了。因此大数据挖掘，对快的要求越来越高。

MapReduce框架代表了在算法层面提升了规模。而另一方面，最近十几年，硬件也在飞速发展。200x年的时候，单机内存有限。今天的服务器，动不动就几百个G，国产化的SSD的单价做到了0.5元/GB。单机几百G的内存，再加几个T的SSD，网卡普遍用上了万兆网卡。单机的硬件性能大大加强。

于是出现了一批新的运行框架，例如Spark， Presto， 充分利用单机的内存做计算，计算结果通过网络传输给下游节点，而不是写到磁盘，再传给其他机器。这些新的软件，不再采用Hadoop的MapReduce运行框架，而是借鉴MapReduce的思想，自己实现了计算逻辑。

这些新的计算系统，抛弃了除了HDFS以外的hadoop生态圈。原来跑起来hadoop需要一堆软件协同，现在只需要一个开箱即用的软件即可。当然像Presto,Spark，本身还是需要读写HDFS，也算是SQL on hadoop 的延续。

DAG vs MPP

本章节命名MPP不是很恰当，MPP只是其中的一种调度和运行模型。MPP源于并行数据库，每个进程都是一个独立的可运行数据库，有完整的解析，优化，codegen，和资源管理，每个进程只负责一部分数据。除了MPP模型，还有DAG模型，DAG的运行前提是shared storage，比如HDFS，由全局节点解析，优化，分配和协调每个节点的任务。

基于内存的OLAP引擎，能够在秒级别完成大规模数据的分析，并拿到结果。做到了之前数据库、数仓做不到的性能和延时。在此之前，要在短时间分析大量数据是不可能的，因而不得不采取一些技巧来完成，例如预计算，流计算，把计算结果保存到NoSQL中，用户查询的时候，直接查询NoSQL的结果即可。但这些技巧本身对用户来说非常不灵活，规则的任何变化，都需要把历史数据重跑一遍。基于内存的计算引擎，让真正的OLAP成为可能。用户不再需要做各种预定义的规则。只需要保存原始的数据，在需要的时候，可以立即通过SQL获得结果。

MPP解决了人们对于快速分析大数据的需求。

ClickHouse

Presto是2012年FB研发出来的，目的是为了加速Hive的查询。Presto是基于Java开发的，大部分的大数据套件都是基于Java开发的，Java的开发生态比较丰富，开发门槛比较低。ClickHouse是2016年俄罗斯开源的OLAP系统，由于ClickHouse的年代更近，因而采用了最新的一些技术，用论文里边一句时髦的话叫state of the art，使得ClickHouse的运行速度领先同类OLAP引擎。本文就从代码层面探究ClickHouse的一些优势。

采用c++ 17语言

ClickHouse的第一个优势是采用c++语言，而且是c++17的标准。能用c++写大型程序的都是好汉。现代软件重要的是协同开发，而不是单打独斗。大数据生态，大多采用java开发，是有道理的。java一次编译，处处运行优势，可以让每一个开发者只负责其中一部分功能，然后以jar包的形式分发，打包成jar包就说明解决了编译问题，而运行时问题则交给jvm，其他开发者只需要引用jar包，就可以完成协同开发，这促进了java丰富的开发生态，基本上需要什么基础轮子，就有对应的jar包，不需要自己重复造轮子。这一点是c++不能比的。c++不同的编译器编译出来的二进制lib，不同的硬件平台上编译出来的lib，都有兼容性问题，这阻碍了基础套件的分发和共享。导致c++代码协同研发必须共享代码，而共享代码在不同编译器上有会遇到各种各样的编译问题。所以很少有基于c++实现的大数据软件。如何提升c++程序的协同开发效率，我会专门开一篇文章介绍LLVM。

鉴于上述描述的c++协同开发的困难，ClickHouse能够用c++代码来实现，说明老大哥还是非常彪悍的，往年用c++搞出了nginx，现在又用c++码出了ClickHouse，c++代码比JAVA代码，在执行效率上高一些，再加上c++能够利用一些指令级别的优化，因而整体而言，c++程序的运行速度要快于JAVA。

更难能可贵的是，ClickHouse采用了c++ 17的标准，用clang10编译器，采用了很多新的语言特性，新的语言特性的优势在于：

1. 编程代码更加简洁，编程效率会更高。例如auto关键字，让c++有了类似脚本语言的快感。
2. 一些新的特性让性能上更上一层楼。比如std::move通过移动构造函数，避免生成临时对象。 std::unique_ptr智能指针，既能够管理对象内存，又能够像对象一样在函数间传递(相对auto_ptr)，却不用承担shared_ptr锁的开销。
3. 更加复杂的编译时表达能力。像enable_if,is_same_v等语法，决定编译时的动作，让模板编程能力更加复杂。在以前，编译时动作只有宏编程，c++11之后，这些新的特性，让开发者有更多的选项告诉编译器该怎么做。
4. 可变长度模板参数列表。模板参数可以像函数的可变长度参数列表一样，支持不定长模板参数列表，快速实例化模板。这个特性会在下文的木版化执行阶段介绍。

这里无意介绍c++11到c++17所有的特性，只是摘出来ClickHouse用到的一些特性做介绍，对c++11/17感兴趣的同学，网上有很多介绍文章。

用最新的编译器+最新的语言特性，带来了编程效率和执行效率的提升，让ClickHouse领先同类产品一个段位。这大概就是后发优势吧

模板化执行代码

在SQL执行引擎中，逻辑执行计划生成物理执行计划，要根据相应的数据类型，函数名称、参数列表，寻找合适的执行代码。例如 1 + 2.2这个计算，要寻找到一个plus函数，参数类型分别是int和float，即签名是plus(int, float)的函数。实现方式上，会提供不同类型的重载函数。

一般而言，有几种方式，第一是采用虚函数的方式，在执行时，根据实际类型选择合适的函数入口。但是我们都知道虚函数是通过虚表实现的。运行时查找函数需要经过一跳。如果每一行记录都在运行时做一次虚表跳转，代价是很大的。

解决方法就是第二种形式，在编译时绑定执行函数。但是还要解决一个泛化的问题，要提供一系列函数，而不止是一个函数。ClickHouse采用的是模板化编程，同一个名字的函数，用模板实现，乃至模板套模板。参数的类型用模板类型表示。并通过可变模板类型参数列表物化出真正的代码，这一过程是在ClickHouse编译时确定的。等到物化执行计划阶段，调用可变模板类型参数列表的函数，逐个匹配各个类型，寻找到合适的类型，就执行对应的函数。可变模板类型列表是一个很重要的概念，ClickHouse依赖它完成泛化代码的编写、代码实例化、运行时多态、

上边提到的1+2.2可能有点复杂，我们首先以单参数函数为例介绍，比如函数abs(-1)，计算-1的绝对值。首先clickhouse提供了一个模板实现FunctionUnaryArithmetic，囊括了所有的单参数数学函数，参数可以是不同的类型，从uint8到decimal256,也可以是string。abs.cpp，则提供了abs算子的具体实现AbsImpl::apply，当然这个算子也用数据类型作为模板，可以支持不同位数的数字，该算子作为FunctionUnaryArithmetic的模板参数。FunctionUnaryArithmetic要做的，就是在运行时根据传入的参数实际类型，选择不同的执行路径，主要是区分是string还是数字。怎么实现运行时动态参数选择呢？主要是通过上文提到的可变长度的模板参数列表来实现:

ClickHouse调用castTypeToEither 函数，并且传入实际的数据类型，和回调函数，当匹配到某一个类型时，就执行f这个lambda函数。

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

static bool castType(const IDataType * type, F && f)
{   
    return castTypeToEither<
        DataTypeUInt8,
        DataTypeUInt16,
        DataTypeUInt32,
        DataTypeUInt64,
        DataTypeUInt256,
        DataTypeInt8,
        DataTypeInt16,
        DataTypeInt32,
        DataTypeInt64,
        DataTypeInt128,
        DataTypeInt256,
        DataTypeFloat32,
        DataTypeFloat64,
        DataTypeDecimal<Decimal32>,
        DataTypeDecimal<Decimal64>,
        DataTypeDecimal<Decimal128>,
        DataTypeDecimal<Decimal256>,
        DataTypeFixedString
    >(type, std::forward<F>(f));

1
2
3
4
5
6

template <typename... Ts, typename T, typename F>                
static bool castTypeToEither(const T * type, F && f)             
{                                                                
    /// XXX can't use && here because gcc-7 complains about parentheses around && within ||
    return ((typeid_cast<const Ts *>(type) ? f(*typeid_cast<const Ts *>(type)) : false) || ...);
}  

castTypeToEither是怎么实现的呢，如上代码样例，模板参数中的Ts是一个可变长度的列表。实现中，为了表达『命中类型就执行f』这个语义，用了短路求值法，但是因为编译器不支持&&这种写法，而用了?:双目运算符。如果检查类型匹配，就以匹配的类型执行，不匹配就检查下一个类型，语法上使用了||… 来表达对每一个模板参数执行相同操作。由于回调函数也是模板，传入实际类型就相当于实例化了对应代码。由于模板函数在编译时有调用才会实例化，不按照这种做法，我们恐怕要在一个地方为每一种类型编写一下调用函数才能实例化。castTypeToEither是非常重要的一个函数，由它实例化出了每一种计算函数的实现。

看到了单参数的实现，接下来看多参数的实现，以上边提到了1+2.2为例，介绍ClickHouse的实现方式,由于双参数的类型组合比单数更多，相当于N*N个组合，比如int8 + float, int16+float,int32+float, float+float。 一般有个做法是，在具体实现时，只实现同类型的，比如Int8+int8， float+float。语法检查器在检查时，会优先寻找函数名匹配，参数类型也完全匹配的函数实现。 如果其中一个参数不匹配，比如Int32+float，找不到这个组合的实现，语法检查器会挨个检查每个函数实现，是否能够做类型转换，把实际类型转化成函数声明类型而不影响精度，比如针对int32+int32的函数实现，float不能转化成int32，所以不能采用该实现，针对float+float，发现int32能够转化成float，那么就会把语法树变成cast(int32 as float) + float来解决这个问题，虽然两者语义上有一定差别，毕竟int 转float在大数情况下会损失精度，但是好歹在目前情况下实现了该运算。

按照这种做法，先强制转化类型，把数据拷贝出来一份，生成一份新的数据，再去计算。

ClickHouse没有这样做，它没有在语法检查阶段添加这种强制类型转换的逻辑。而是用模板实现两个不同类型的计算，然后通过castTypeToEither函数，实例化出不同的组合。

1
2
3
4
5

template <typename F>
static bool castBothTypes(const IDataType * left, const IDataType * right, F && f)
{    
    return castType(left, [&](const auto & left_) { return castType(right, [&](const auto & right_) { return f(left_, right_); }); });
}    

在castBothTypes函数中，通过castType嵌套castType，获得左右两个函数的实际类型后，用实际类型回调lambda函数f。比如你传入的是int+float,就会实例化出该类型。在ClickHouse的编译阶段(注意，不是SQL的编译阶段)，就会通过上文提到的几个函数，实例化出不同的组合，既有int+float,也有int64+float，更有decimal128+float，还有float+decimal128等等各种组合。

ClickHouse的这种做法的好处是什么呢？减少了一次类型转换的开销，节省一个算子。

值得注意的是，模板函数提升的是泛化的能力，总不能给每一种类型都实现一个重载函数吧，在执行效率上，由于是运行时多态，挨个检查每个类型，找到合适的再回调，需要有多次跳转指令，和虚函数也没多大差别，不能充分利用CPU流水线。但是由于ClickHouse采用的是列式方式计算，每一大块数据(几万行数据)只需要执行一次查找即可，不需要每一行数据都做这个检查。但假如你用的是按行处理，那恐怕性能就急剧下降了。

列式计算

上文提到了ClickHouse是按列式计算的，按照列式计算有两个好处，

####1. 更高的存储压缩比
存储时按照列式存储，同一种类型的数据在压缩时会获得一个更好的压缩比，节省存储空间，读取时速度也会更快。
####2. 利用向量化加速计算
按照列式处理，一次加载一批数据，利用单条指令同时操作多条数据，获得提速效果。一次操作一列数据，可以完全放到CPU缓存中。像Presto这种计算引擎，虽然提供了列式的接口，仅仅利用了存储上列的优势，没有用到计算上的优势。向量化如何提速，会在下文介绍。

向量化

向量化主要是利用单条指令操作多条数据，指令称为SIMD指令。在运行时，把满足寄存器大小的数据放到寄存器，CPU一条指令操作寄存器上的多条数据。

向量化一般有两种方式：

1. 利用编译器自动向量化

在编写程序时，如果是符合一定规范的循环语句，循环语句内部是简单的操作，比如+-*/等，编译器优化器，可以把循环语句折叠成向量化执行。

1
2
3
4
5

static void NO_INLINE vectorVector(const A * __restrict a, const B * __restrict b, ResultType * __restrict c, size_t size)
{   
    for (size_t i = 0; i < size; ++i)
        c[i] = Op::template apply<ResultType>(a[i], b[i]);
}

2. 显式使用SIMD指令

c++ 提供了SIMD指令，可以一次把128bit的数据加载到寄存器，以下边的大小写转换的函数为例，一个字符是8bit，一次把128bit，也就是16个字节的字符串加载到寄存器，通过CPU一条指令操作16个字符，相当于获得了16倍的提速。

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

    static void array(const UInt8 * src, const UInt8 * src_end, UInt8 * dst)
    {   
        const auto flip_case_mask = 'A' ^ 'a';

#ifdef __SSE2__
        const auto bytes_sse = sizeof(__m128i);
        const auto src_end_sse = src_end - (src_end - src) % bytes_sse;

        const auto v_not_case_lower_bound = _mm_set1_epi8(not_case_lower_bound - 1); 
        const auto v_not_case_upper_bound = _mm_set1_epi8(not_case_upper_bound + 1); 
        const auto v_flip_case_mask = _mm_set1_epi8(flip_case_mask);

        for (; src < src_end_sse; src += bytes_sse, dst += bytes_sse)
        {   
            /// load 16 sequential 8-bit characters
            const auto chars = _mm_loadu_si128(reinterpret_cast<const __m128i *>(src));

            /// find which 8-bit sequences belong to range [case_lower_bound, case_upper_bound]
            const auto is_not_case
                = _mm_and_si128(_mm_cmpgt_epi8(chars, v_not_case_lower_bound), _mm_cmplt_epi8(chars, v_not_case_upper_bound));

            /// keep `flip_case_mask` only where necessary, zero out elsewhere
            const auto xor_mask = _mm_and_si128(v_flip_case_mask, is_not_case);

            /// flip case by applying calculated mask
            const auto cased_chars = _mm_xor_si128(chars, xor_mask);

            /// store result back to destination
            _mm_storeu_si128(reinterpret_cast<__m128i *>(dst), cased_chars);
        }   
#endif

        for (; src < src_end; ++src, ++dst)
            if (*src >= not_case_lower_bound && *src <= not_case_upper_bound)
                *dst = *src ^ flip_case_mask;
            else
                *dst = *src;
    }

LLVM动态编译执行代码

上文在介绍模板化编程时指出，CickHouse实现多态的方式是通过在运行时检查不同参数类型，直到找到一个合适的类型，再运行这个类型的实例化计算代码。相当于多条跳转指令才能找到真正的执行代码。虽然采用列式计算，但是如果数据块比较多，这个计算开销也是不小的。 再加上计算时函数套函数，一个很小的操作都需要调用函数完成，实际上完成一行的计算需要多条指令才能做到。为了在这上边提升计算速度，ClickHouse还提供了动态编译和JIT的方法。

说到c++的动态编译，就离不开LLVM。LLVM是一种现代化的编译器，我会再开一篇文章详细介绍LLVM和JIT技术。 动态编译代码，就是在程序运行时，把SQL的执行计划，编译成可执行的机器指令，并且在当前程序中执行这些指令。动态编译是相对于静态编译而言的。通常静态编译是说，写完代码用g++、clang++等工具编译成二进制文件，然后运行这个二进制文件。动态代码则是程序运行时动态编译的。动态编译和执行称为JIT技术。

LLVM 为c++提供了很了不起的JIT技术支持。往常只有java代码才有动态编译一说。c++有了动态编译，才给数据库技术加速计算提供了新的方法。

以plus函数为例，plus的运算符提供了编译方法，通过llvm实现一个指令，b.CreateAdd完成左右两个参数的加法的指令。

1
2
3
4

static inline llvm::Value * compile(llvm::IRBuilder<> & b, llvm::Value * left, llvm::Value * right, bool)
{   
    return left->getType()->isIntegerTy() ? b.CreateAdd(left, right) : b.CreateFAdd(left, right);
}   

使用静态代码执行，需要多层函数嵌套，乃至每一行都需要调用一个函数，开销很大，而在JIT 技术下，一个区块的数据只需要调用一个函数就可以了。

当然，动态编译代码代价很大。我们经常说，开发者大部人时间就是等待编译器做编译。JIT也一样，动态编译需要时间，编译一次代价很大。因此在编译后要把结果缓存下来复用。

总结

大数据系统发展了这么多年，数据规模越来越大，速度越来越快。而人们对数据分析的强烈需求是永无止境的。新的编程技术不断涌现，硬件水平也不断发展，每隔几年出现新的、更强大的、更快速的大数据系统。
ClickHouse作为比较新的OLAP引擎，在很多场景的benchmark上处于领先地位。本文从代码层面介绍了为什么ClickHouse计算速度快。ClickHouse利用c++17标准，clang11编译器，相当于最新的编程语言；同时利用模板泛化编程，泛化实现大量算子；也利用指令集别的并行计算，加速计算；利用LLVM动态编译代码，优化执行逻辑。

本文主要探讨为什么计算快，对clickhouse架构方面涉及不多。OLAP引擎一直在发展，新的技术也会不断出现。我们会持续关注，并把最新的技术应用到我们的云计算中。

现在的物联网现状

小米生态链为小米提供了丰富的外围产品。各种物联网设备，小米手环，床头灯，智能门锁，智能插座，打印机等等，可以通过手机进行操作。现在，不仅小米的各种物联网设备，其他的厂商也提供了联网功能，洗衣机能联网了，电冰箱也能联网了。各种各样的设备，都能通过手机上进行操作。总结起来，目前的物联网设备提供的功能主要有3点：

1. 查看设备状态，例如查看开关的开启状态，床头灯的状态。
2. 设置设备状态，例如开启开关，开启、关闭床头灯。
3. 通知设备完成一个操作，例如显示信息，振动。

小米手机通过米家APP提供了管理平台，统一管理小米生态链企业各个物联网设备。而其他的物联网设备，则每个供应商提供了自己的APP，每个供应商都不希望自己的设备给其他的互联网公司添砖加瓦。导致手机上的APP数量越来越多，各家的APP显然是孤立的，互不相同的。即便是米家自己的物联网设备，在APP内部也是按照设备划分功能的，设备之间也不能互联互通。

苹果手机的崛起之路

苹果手机开启了智能手机之路，涌现了无数的APP，开启了长达十多年的移动互联网时代，产生了多家独角兽。

苹果手机之所以称为智能手机，就是可编程这一个能力，允许开发者基于苹果手机提供的API构建各种各样的场景。更重要的是，苹果手机上集成了各种传感器，传感器提供出API，供编程。例如GPS，产生了高德导航；饿了么，美团也可以根据定位，提供外卖服务。在智能手机出现之前，车载导航还需要专门的设备，但是车载导航的GPS没有衍生出更加丰富的使用场景，原因就是没有可编程能力。

物联网更多想象力

物联网设备提供了一下内置功能，例如手环，可以检查睡眠，可以有振动闹铃。小米手环提供了闹铃功能，闹铃固定时间的闹铃。手机闹铃也是提供固定时间的闹铃。但是我们平时的生活，有时候可能耽误一会儿晚睡了一会儿，有时候早睡了一会儿。都要在固定时间被闹铃吵醒。因为手机没有能力检测到你的睡眠时间。

现在好了，手环里边能够检测你的睡眠，就能够根据实际的睡眠时间，设置动态的闹钟，保证每天睡够8小时。

显然，现在的手环产品经理是没有想到这种场景的，如果手环能够开放API供编程，会有无数的开发者开发出各种各样的使用场景。

从单一设备可编程，到多设备互联互通+可编程

我们再延续上边手环的例子，一个手机APP通过手环的API获得了用户的睡眠状态，发现用户醒了，然后再调用自动窗帘的API，自动打开窗帘。然后调用微波炉，面包机的API，自动开始做早餐。这才是智能家居啊。多个设备，通过手机APP，全部串联了起来！

什么是智能

很多人经常讲物联网智能，智能家居。说的好像就是家具连上网就突然长了大脑，自动给人类做任何事情。

其实不是的，设备的任何操作，都是程序固定化下来的操作。所谓的智能，是因为场景非常丰富而显得无所不能。而构建丰富的使用场景，是离不开大量的开发者，大量的产品经理的脑袋想出无数的创意的！

而要达到这一目标，就需要物联网设备开放API，提供可编程的能力！

从单打独斗到报团取暖

现在，任何一个卖物联网设备的公司，基本是单打独斗，自己根据自己的设备创建使用场景，写一个手机APP。

当你提供了API的可编程能力之后，就能够实现和其他厂商设备的互联互通。就像一个小飞机，搭上了一首航空母舰，瞬间获得强大的销售能力。

物联网的航空母舰是什么？就是智能手机。

虽然目前小米生态链企业众多，拥有非常强大的品牌。但不可否认，小米手机仍然没有能力做这样一首航空母舰。因为小米手机没有做到把物联网设备API化。

windows的崛起之路

很多人疑问，你吹了这么多，小米手机按照你这样说的做了，能达到什么样的效果？

平台的垄断能力是无敌的，如果做得好，成为手机界的windows也不为过。

windows能够横扫PC操作系统，甚至打败Mac，成为多家厂商的操作系统事实标准，原因是什么？有些人说是提供了窗口操作系统。事实上，Windows抄袭Mac口水官司至今牵扯不清。之所以能成为设备厂商的首选，是因为windows提供了大量的驱动，兼容各种各样的外设，甚至非常偏门的供应商的设备驱动，都能过在windows中找到。任何一个电脑厂商，选择windows就就能省心的对接各种外设，如果自研linux，碰到一种外设没有驱动支持，消费者就不买单。这就是生态的力量。

有了各种驱动支持，相当于无缝对接了各种硬件设备，windows又提供API，供开发者开发出各种各样的软件。造就了丰富window生态。生态是一个很神奇的东西，虽然这个词被梦想窒息搞烂了，但不得不承认，如果你能做好生态，有非常大的可能性获得产品的巨大成功。

总结

目前来看，小米仍然是很简单的对接各种物联网设备，没有挖掘出物联网世界的潜能，如何做到呢？从给各种物联网设备实现API，提供可编程的能力开始吧！

上图是关于一个数据分析的笑话，就像手里有把锤子，看什么都像钉子。知道些数据分析的技巧，逮着话题就分析。有句话说，只要你拷问数据上百遍，数据总能招供。不过我们可以从里边窥见数据分析的一般性技巧：假设检验，采样，方差分析，相关性分析等等。

数据分析，或者说数据挖掘，目的是从大数据中寻找到有趣模式和知识。

数据挖掘，使用到了多种技术，包括统计学，模式识别，可视化，机器学习等等。今天我们来探究一下在数据挖掘领域，有哪些算法可以使用。

女士品茶和数据分析

女式品茶是数据分析领域非常有名且有趣的一个故事。一位女士声称能够品尝出来奶茶是先加奶还是先加茶。然后大家设计了多轮实验来验证。然后一位数据科学家通过分析女士猜中的次数来判定她是否有这种能力。这是一个典型的通过假设检验来验证实时的案例。

《女式品茶》这本书，介绍了统计理论发展历史的一本书，介绍了数学家们关于统计学的非常有趣的历史，相比一本正经的教科书，比较生动形象。在书中介绍到一个有趣的事情，在二战后，美国人派遣了大量专家前往日本，教日本人学会美国社会是怎么运作的，其中有一位统计学家也在其中。统计学家向日本的汽车行业介绍了如何用抽样检验来保证汽车生产的质量。日本的汽车产业借助于统计理论，实现了生产质量的提升。在云计算领域，稳定性和SLA代表服务质量，如何利用好数据分析，保障稳定性，实现异常的发现，根因的诊断，是一个值得研究的课题。

统计和假设检验

数据特征描述

统计量是用来描数据特征，例如常用的均值，概括了数据的大致水位，还有哪些统计量来描述数据？

• 位置度量

  • 均值、加权均值、切尾均值(可以排除尾部极大极小值的干扰)。
  • 中位数，加权中位数。中位数可以很好的避免极值的干扰。除了中位数，还有百分位数，四分位距，比如99百分位。
  • 最大，最小，和。
  • 利群点

• 变异性，变异性代表是数据偏离中心的程度

• 偏差，平均绝对偏差，方差，中位数结对偏差，极差

探索数据分布

探索数据分布，可以快速了解数据的大致分布，对整体的情况做一个掌控。

• 百分位数/箱线图，百分位是常用的分析数据分布的度量指标，可以了解所有数据在分布情况。
  • 
• 频数和直方图
• 峰度和偏度，峰度代表的是数据集中的程度，偏度代表的是数据偏离中心的程度。

分类数据描述

分类数据指的是离散数据，连续数据也可以根据区间分成离散数据。

• 众数：出现次数最多的类别和值。
• 期望值：根据概率算出期望
• 条形图：代表每个类别的频数
• 饼图：代表各个分类的占比

相关性

相关性考察的是双因子之间的相关性，可以用相关矩阵来表达，如上图。计算相关系数一般用皮尔逊系数。

相关性视图

图形是最直观的表达形式，可以让读者快速看出数据的特征，上图从左到右依次是散点图、六边形图、等势线图，小提琴图。

• 散点图，可以用来观察两个指标之间的相关性
• 六边形图是对散点图的一种概括，当点比较多时，用六边形来表示，颜色越深，代表数据越多。
• 等势线图
• 小提琴图：作用类似于百分位图，但可以快速看出数据的分布，越宽的地方，代表数据越多。

抽样分布和假设检验

抽样理论是发展了数百年的数学理论，以应对大数据情况下，对大数据的分析。比如如果数据量过大，无法展开人工绘图和检测。

正态分布

钟形正态分布是一种常见的分布形态，不过这里介绍一种更加直观的形式，QQ图。QQ图把数据绘制到对角线上，如果和对角线严格匹配，那么代表是标准的正态分布。像右图那样，尾部偏离对角线，则代表有长尾分布。

正态分布可以用来做异常检测，比如如果确定数据是遵从正态分布的。那么可以通过3σ来判定异常，如果数据偏离到均值的3σ之外，则认为数据是利群点。但前提是要保证数据是遵从正态分布的。

T检验

T检验可以用来对A/B 测试对比，例如下图的案例，改版前后的订单数，如何确定改版确实提升了订单数呢，而不是随机的波动？可以通过T检验来判定。

泊松分布和故障率估计

这里无意深入数学原理中来介绍二项分布、泊松分布、指数分布。三种是可以相互推倒出来。

泊松分布，假定事件发生的概率相同，推测最大期望值，例如包子店，每天要准备多少个馒头才能保证既不浪费，又能够充分的供应。根据每天供应的数量，计算出样本均值，近似代表泊松分布的期望值λ，就可以估算出泊松的概率密度函数。寻找出概率密度最大的部分对应的数值。

统计实验和显著性检验

统计实验可以用于A/B test中，例如两种价格的购买量，是随机结果吗？是否有显著性差异，可以通过卡方检验来完成。

卡方检验，可以验证两个因素之间的相关性。在网站分析中可以用于转化率、Bounce Rate等所有比率度量的比较分析。

机器学习

机器学习从大的方向上分为：

• 基于统计算法的机器学习
• 基于神经网络机器学习

从使用目标上来划分，包括：

• 分类
• 聚类
• 挖掘频繁集、相关性
• 用于预测的回归
• 离群点分析

分类算法

分类算法是一种有监督学习方法，给定一批数据和对应类别（标签），求解未知数据的类别（标签）。

K近邻算法

K近邻算法是最简单的有监督学习分类算法，不需要做提前训练模型，在计算未知数据时，查找距离未知数据最近的K个点，然后查看这K个点的类别，出现最多的类别就是未知数据的类别。

K近邻算法的优势和劣势都是很明显的。

优势：

• 逻辑简单
• 实现简单
• 不需要事先训练模型

劣势：

• 针对每个未知点，都需要计算和每个已知数据的距离，存在大量的重复计算。

K近邻一个案例，如下图，识别手写数字，可以把图片的每个像素，转写成一维向量。有标签的数据会标记图片的实际数字。当要识别一个新的图片的时候，计算新图片和带标签图片的向量距离，判定图片的数字。

决策树

决策树也是一种分类算法，是一种有监督学习。决策树的好处在于，能够训练出模型，再利用模型推断新数据。

决策树的构建过程：每轮迭代，选出一个最佳特征，使得按照这个特征分类后，数据的熵最小。熵代表的是数据的混乱程度。

决策树的优点：

• 计算复杂度不高
• 分类方法容易理解
• 相比其他算法有较高的准确率

缺点：

• 容易过拟合

朴素贝叶斯

朴素贝叶斯是基于条件概率的算法，通过计算条件和标签的条件概率，计算当出现特定条件时，是特定目标的概率。举个例子，一段邮件，要判断是否是垃圾邮件，判断每个词出现的情况下，邮件是垃圾邮件的概率。那么再出现新邮件时，可以根据每个词的频率，判断是否是垃圾邮件。

Logistic回归

logistic回归是用回归方法来实现分类目的。

logistic回归采用的是非线性函数，或者说激活函数，如图，类似一个开关作用，开关可以起到分类的作用。

支持向量机SVM

支持向量机是在多个类别中间，寻找一个平面，使得所有的点距离这个平面的距离最远，那么离这个平面最近的点，就是支持向量。如上图所示，右侧的平面距离所有点距离最远。

上图中，现在对于线性空间才存在这样的一个平面，对于非线性空间怎么处理呢?如下图，一个环形的图形，可以通过核函数把非线性空间转化成线性空间，再寻找支持向量。

Adaboost

在上文中，介绍了多种分类算法，那么每一种算法的准确率如何呢？参考下表，可以说大部分算法的错误率较高，很难应用到实际生产中。究其原因，是单算法表达能力不强，无法应对复杂场景，容易在训练时被训练数据带偏，不能处理新的数据。

Adaboost是自适应的分类器，原理借鉴统计学中ada boosting。通过多个弱分类器，组成一个强分类器，每个分类器分配一个权重，在inference的时候，共同决定结果。

聚类算法

聚类和分类的区别：分类是有监督学习，聚类是无监督学习。

k means算法

把一批数据分成k类，给出每一类的均值。

1. k mean初始时随机分配k个质心，
2. 计算所有点距离每个质心的距离。
3. 把每个点分配给距离最近的质心，形成k个族群。
4. 计算每个族群新的质心。
5. 重复上述步骤，直到质心的位置不再变化为止。

频繁集

频繁集是找出频繁出现的模式，子序列，子结构。著名的啤酒和尿布的故事，就是从一堆物品中，寻找高频出现的集合，并做关联销售。在频繁集算法中，常用的有Ariori和FP-growth算法。

离群点分析

离群点分析，算是一个数据挖掘目标，实现方法是多种多样的。

• 监督学习方法
  • 分类方法建模
• 无监督学习
  • 统计方法

    • 例如3σ方法
      

  • 接近度方法：基于密度或者距离来判断
  • 聚类：属于稀疏类的数据。

深度神经网络

上边提到的adaboost，是利用多种弱分类器来实现一个强大的分类器。算法本身包含了一层网络结构。深度神经网络是一种更加复杂的网络结构。神经网络，从输入节点到输出节点之间有多层隐藏层，每一层有多个节点，相邻的层次之间1*1全连接。多层节点形成前向反馈网络。在最后一层增加一层损失函数层，损失函数连接最终结果。中间层的每个节点，都会连接一些激活函数，参考前文logistic回归中提到的开关函数，通过这类非线性的开关函数，实现非线性的拟合。『深度神经网络』中的深度，含义就是多层网络。

卷积神经网络CNN

上文提到的深度神经网络，各层之间是全链接，对于一些复杂的模型，会导致训练的参数非常多，训练十分困难。 卷积神经网络，节点之间不是全链接。相邻层，通过一个公共的卷积来连接。卷积内是全链接，因此大大减少了训练参数。

一个常见的卷积神经网络如下图所示，通过多层的卷积，池化层、激活函数组成，最后添加一个全连接层，连接到输出。

CNN大多应用于图像识别领域。

循环神经网络

CNN内部没有状态，单纯从输入到输出。因此无法训练上下相关联的场景，例如时间序列数据。循环神经网络RNN，通过内部保存状态，可以让历史上的信息影响未来的输出。已有的状态+输入 ，映射到新的状态和输出。但是RNN无法保存远期记忆，总是由最近的输入决定输出。 LSTM解决了长程依赖问题，通过一些门开关，选择性的把信息输出到下游。适用于时间序列，文本等上下文相互关联的场景。

强化学习

深度神经网络、卷积神经网络、循环神经网络，这些都是有监督学习，在大部分应用场景下，要获得大量的有标签的标注数据，这是不现实的。例如无人驾驶，围棋等场景。这种场景可以通过强化学习来完成。强化学习有三要素，分别是：

• 环境：例如当前棋盘的状态
• 动作：对当前环境的动作，例如下一步的落子
• 评分：最终的评分

通过评分大大小，来判断结果的好坏。并最终训练出最好的模型。

总结

上文列出了一些统计和假设检验、以及统计机器学习、神经网络机器学习的方法。统计机器学习属于比较传统的算法范畴，而神经网络属于最近几年比较火的内容，在特定场景下，还需要根据实际场景选择特定的算法。

参考资料

深度学习

《机器学习》周志华

机器学习实战

TensorFlow实战

Tensorflow：实战Google深度学习框架

面向数据科学家的实用统计学

数据挖掘概念与技术