现代浏览器已经不再是简单的浏览网页的工具，其潜能正在通过技术不断地被挖掘和扩展。得益于 WebAssembly 等技术的出现，让浏览器能够以接近原生的速度执行非 JavaScript 语言编写的程序，从而打开了浏览器的“潘多拉魔盒”。

开源组织 Leaning Technologies 正是这一方面的先锋，他们开发的 Cheerp、CheerpJ 和 CheerpX 等开源项目，使 C/C++、Java、Flash 和 x86 程序能够在浏览器中流畅地运行，它们正在逐步打破传统桌面应用程序和 Web 应用之间的“壁垒”。

• Cheerp：运行在浏览器里的 C/C++ 编译器
• CheerpJ：运行在浏览器里的 Java 虚拟机和运行时环境
• CheerpX：运行在浏览器里的 x86 虚拟机

比如本周的开源热搜项目，基于 CheerpX 引擎的 WebVM 开源项目，它支持用户在浏览器中运行完整的 Linux 环境，无需下载和安装。开源的 Web 应用防火墙 BunkerWeb，让你的 Web 默认配置变得安全。极小的 fetch 封装库 Wretch，让前端请求数据更加轻松惬意。在浏览器里控制多台 Android 设备的平台 stf，优化 React 组件性能的工具 million 也是让人眼前一亮。

最后是一周涨了近 1w Star 微软开源的新型 RAG 框架 GraphRAG 和 LLM 一站式开发和部署工具 LitGPT。

• 本文目录
  
  • 1. 开源热搜项目
    
    • 1.1 在浏览器中运行 Linux 虚拟机：WebVM
    • 1.2 开源的 Web 应用防火墙：BunkerWeb
    • 1.3 轻量且直观的 fetch 库：Wretch
    • 1.4 一站式的 LLM 开发和部署工具：LitGPT
    • 1.5 微软开源的 RAG 框架：GraphRAG
  • 2. HelloGitHub 热评
    
    • 2.1 浏览器控制多台 Android 设备的平台：stf
    • 2.2 优化 React 组件性能的工具：million
  • 3. 结尾

1. 开源热搜项目

1.1 在浏览器中运行 Linux 虚拟机：WebVM

主语言：JavaScript
，
Star：3.5k
，
周增长：600

该项目可以让用户在浏览器中运行 Linux 虚拟机，无需服务器、完全客户端的虚拟环境。它基于 CheerpX 虚拟化引擎，提供了一个安全、沙盒的 x86 虚拟环境，可运行二进制文件、命令行工具、文本编辑器、编译 C/C++ 程序和 Python 等语言的脚本，登录后还能访问互联网，适用于演示和快速访问 Linux 开发环境等场景。

GitHub 地址→
github.com/leaningtech/webvm

1.2 开源的 Web 应用防火墙：BunkerWeb

主语言：Python
，
Star：4.9k
，
周增长：1.1k

该项目是用 Python 开发的 Web 应用防火墙，可以无缝集成至现有环境（Linux、Docker、K8s 等）。它基于 Nginx 构建、默认配置安全，拥有简单易用的 Web 界面，支持自动配置 HTTPS A+ 评级、安全 Header 和丰富的插件系统，可检测常见的攻击模式、限制访问、防止机器人和爬虫等恶意访问，保护你的网站、API 和 Web 应用。

GitHub 地址→
github.com/bunkerity/bunkerweb

1.3 轻量且直观的 fetch 库：Wretch

主语言：TypeScript
，
Star：4.6k

这是一个极小、类型安全、围绕 fetch API 构建的网络请求封装库。它提供了通俗易懂的网络请求 API，简化了网络请求错误处理和序列化，同时压缩后仅 2KB 大小，支持主流浏览器并兼容 Node.js，适用于各种前端 HTTP 请求的场景。

wretch("anything")
  .get()
  .notFound(error => { /* ... */ })
  .unauthorized(error => { /* ... */ })
  .error(418, error => { /* ... */ })
  .res(response => /* ... */)
  .catch(error => { /* uncaught errors */ })

GitHub 地址→
github.com/elbywan/wretch

1.4 一站式的 LLM 开发和部署工具：LitGPT

主语言：Python
，
Star：8.6k
，
周增长：300

该项目是一款用 Python 编写的提供了 20 多种 LLMs 的预训练、微调和部署的工具。它可以通过 Pyhton 库或者命令行的方式使用，对模型进行微调、预训练、评估和部署服务等操作，支持自动从 HF 下载模型、自定义数据集、性能优化、降低内存要求（precision）等功能，以及 LoRA、QLoRA、Adapter 等多种微调方法。

from litgpt import LLM

llm = LLM.load("microsoft/phi-2")
text = llm.generate("Fix the spelling: Every fall, the familly goes to the mountains.")
print(text)
# Corrected Sentence: Every fall, the family goes to the mountains.       

GitHub 地址→
github.com/Lightning-AI/litgpt

1.5 微软开源的 RAG 框架：GraphRAG

主语言：Python
，
Star：10k
，
周增长：9k

该项目是由微软开源的基于知识图谱的检索增强型生成（RAG）系统，它利用大型语言模型生成知识图谱，将非结构化的文本转换为具有标签的知识图谱数据，从而增强 LLMs 的输出结果。相较于基准 RAG（向量相似性），基于知识图谱的 GraphRAG 在回答更抽象（关系）和总结性问题时表现更好。

GitHub 地址→
github.com/microsoft/graphrag

2. HelloGitHub 热评

在这个章节，将会分享下本周 HelloGitHub 网站上的热门开源项目，欢迎与我们分享你上手这些开源项目后的使用体验。

2.1 浏览器控制多台 Android 设备的平台：stf

主语言：JavaScript

这是一个用 Node.js 开发的安卓智能设备群测工具，它提供了一个可远程调试多台 Android 设备的 Web 平台，支持 Android 手机和手表等设备。

项目详情→
hellogithub.com/repository/af0868c1e3ea4d608e92849b405a8ddb

2.2 优化 React 组件性能的工具：million

主语言：TypeScript

该项目是专为 React 应用设计的优化编译器，它通过优化虚拟 DOM 和直接更新 DOM 节点，来减少页面更新的耗时，从而提升 React 组件性能，最高可达 70%，支持 VSCode 插件和命令行的使用方式。

项目详情→
hellogithub.com/repository/406d03f678a64294b6c7e763a783b972

3. 结尾

我最近正全身心投入 HelloGitHub 官网的国际化工作中，这使得其他一些事情（HelloStar 等）不得不暂停。我之所以如此专注于国际化，是因为我深信这将提升 HelloGitHub 的全球影响力：它不仅能够让国内的开源项目通过一个国际化的平台被世界看到，也能让国外的开源项目作者理解并知道 HelloGitHub 在做的事情。

虽然这项工作充满挑战、进展缓慢，但我希望能够在「第100期」特别版发布之前完成它，让这一里程碑时刻更加有意义。

在此，我要向所有参与这个项目的朋友们（@雪峰、@塔咖...）表达感谢。正是因为有了你们的无私奉献和坚定支持，让这一切才得以可能。
一个人或许可以走得很快，但一群人定会走得更远
。HelloGitHub 渴望成为每位开源爱好者旅程中的伙伴，让我们一起穿越难关，共同迎接乌云背后的阳光！

以上就是本期「GitHub 热点速览」的全部内容，希望你能够在这里找到自己感兴趣的开源项目，如果你有其他好玩、有趣的 GitHub 开源项目想要分享，欢迎来
HelloGitHub
与我们交流和讨论。

往期回顾

• GitHub 创始人资助的开源浏览器
• 超快的 Python 包管理工具

背景介绍

MySQL的数据字典（Data Dictionary，简称DD），用于存储数据库的元数据信息，它在8.0版本中被重新设计和实现，通过将所有DD数据唯一地持久化到InnoDB存储引擎的DD tables，实现了DD的统一管理。为了避免每次访问DD都去存储中读取数据，使DD内存对象能够复用，DD实现了两级缓存的架构，这样在每个线程使用DD client访问DD时可以通过两级缓存来加速对DD的内存访问。

整体架构

图1 数据字典缓存架构图

需要访问DD的数据库工作线程通过建立一个DD client（DD系统提供的一套DD访问框架）来访问DD，具体流程为通过与线程THD绑定的类Dictionary_client，来依次访问一级缓存和二级缓存，如果两级缓存中都没有要访问的DD对象，则会直接去存储在InnoDB的DD tables中去读取。后文会详细介绍这个过程。

DD的两级缓存底层都是基于std::map，即键值对来实现的。

• 第一级缓存是本地缓存，由每个DD client线程独享，核心数据结构为Local_multi_map，用于加速当前线程对于同一对象的重复访问，以及在当前线程执行DDL语句修改DD对象时管理已提交、未提交、删除状态的对象。
• 第二级缓存是共享缓存，为所有线程共享的全局缓存，核心数据结构为Shared_multi_map，保存着所有线程都可以访问到的对象，因此其中包含一些并发控制的处理。

整个DD cache的相关类图结构如下：

图2 数据字典缓存类图

Element_map是对std::map的一个封装，键是id、name等，值是Cache_element，它包含了DD cache object，以及对该对象的引用计数。DD cache object就是我们要获取的DD信息。

Multi_map_base中包含了多个Element_map，可以让用户根据不同类型的key来获取缓存对象。Local_multi_map和Shared_multi_map都是继承于Multi_map_base。

两级缓存

第一级缓存，即本地缓存，位于每个Dictionary_client内部，由不同状态（committed、uncommitted、dropped）的Object_registry组成。

classDictionary_client {private:

  std::vector<Entity_object *> m_uncached_objects;  //Objects to be deleted.
  Object_registry m_registry_committed;    //Registry of committed objects.
  Object_registry m_registry_uncommitted;  //Registry of uncommitted objects.
  Object_registry m_registry_dropped;      //Registry of dropped objects.
  THD *m_thd;                        //Thread context, needed for cache misses.
...

};

代码段1

其中m_registry_committed，存放的是DD client访问DD时已经提交且可见的DD cache object。如果DD client所在的当前线程执行的是一条DDL语句，则会在执行过程中将要drop的旧表对应的DD cache object存放在m_registry_dropped中，将还未提交的新表定义对应的DD cache object存放在m_registry_uncommitted中。在事务commit/rollback后，会把m_registry_uncommitted中的DD cache object更新到m_registry_committed中去，并把m_registry_uncommitted和m_registry_dropped清空。

每个Object_registry由不同元数据类型的Local_multi_map组成，通过模板的方式，实现对不同类型的对象（比如表、schema、tablespace、Event 等）缓存的管理。

第二级缓存，即共享缓存，是全局唯一的，使用单例Shared_dictionary_cache来实现。

Shared_dictionary_cache *Shared_dictionary_cache::instance() {staticShared_dictionary_cache s_cache;return &s_cache;

}

代码段2

与本地缓存中Object_registry相似，Shared_dictionary_cache也包含针对各种类型对象的缓存。与本地缓存的区别在于，本地缓存可以无锁访问，而共享缓存需要在获取/释放DD cache object时进行加锁来完成并发控制，并会通过Shared_multi_map中的条件变量来完成并发访问中的线程同步与缓存未命中情况的处理。

缓存读取过程

逻辑流程

DD对象主要有两种访问方式，即通过元数据的id，或者name来访问。需要访问DD的数据库工作线程通过DD client，传入元数据的id，name等key去缓存中读取元数据对象。读取的整体过程：一级本地缓存 -> 二级共享缓存 -> 存储引擎。流程图如下：

图3 数据字典缓存读取流程图

由上图所示，在DD cache object加入到一级缓存时，已经确保其在二级缓存中也备份了一份，以供其他线程使用。

代码实现如下：

//Get a dictionary object.
template <typename K, typename T>
bool Dictionary_client::acquire(const K &key, const T **object,bool *local_committed,bool *local_uncommitted) {

  ...//Lookup in registry of uncommitted objects
  T *uncommitted_object =nullptr;bool dropped = false;

  acquire_uncommitted(key,&uncommitted_object, &dropped);



  ...//Lookup in the registry of committed objects.
  Cache_element<T> *element =NULL;

  m_registry_committed.get(key, &element);



  ...//Get the object from the shared cache.
  if (Shared_dictionary_cache::instance()->get(m_thd, key, &element)) {

    DBUG_ASSERT(m_thd->is_system_thread() || m_thd->killed ||m_thd->is_error());return true;

  }



  ...

}

代码段3

在一级本地缓存中读取时，会先去m_registry_uncommitted和m_registry_dropped中读取（均在acquire_uncommitted()函数中实现），因为这两个是最新的修改。之后再去m_registry_committed中读取，如果读取到就直接返回，否则去二级共享缓存中尝试读取。共享缓存的读取过程在Shared_multi_map::get()中实现。就是加锁后直接到对应的Element_map中查找，存在则把其加入到一级缓存中并返回；不存在，则会进入到缓存未命中的处理流程。

缓存未命中

当本地缓存和共享缓存中都没有读取到元数据对象时，就会调用DD cache的持久化存储的接口Storage_adapter::get()直接从存储在InnoDB中的DD tables中读取，创建出DD cache object后，依次把其加入到共享缓存和本地缓存中。

DD client对并发访问未命中缓存的情况做了并发控制，这样做有以下几个考量：

1.因为内存对象可以共用，所以只需要维护一个DD cache object在内存即可。

2.访问持久化存储的调用栈较深，可能涉及IO，比较耗时。

3.不需要每个线程都去持久化存储中读取数据，避免资源的浪费。

并发控制的代码如下：

//Get a wrapper element from the map handling the given key type.
template <typename T>template<typename K>
bool Shared_multi_map<T>::get(const K &key, Cache_element<T> **element) {

  Autolockerlock(this);*element =use_if_present(key);if (*element) return false;//Is the element already missed?
  if (m_map<K>()->is_missed(key)) {while (m_map<K>()->is_missed(key))

      mysql_cond_wait(&m_miss_handled, &m_lock);*element =use_if_present(key);//Here, we return only if element is non-null. An absent element//does not mean that the object does not exist, it might have been//evicted after the thread handling the first cache miss added//it to the cache, before this waiting thread was alerted. Thus,//we need to handle this situation as a cache miss if the element//is absent.
    if (*element) return false;

  }//Mark the key as being missed.
  m_map<K>()->set_missed(key);return true;

}

代码段4

第一个访问未命中缓存的DD client会将key加入到Shared_multi_map的m_missed集合中，这个集合包含着现在所有正在读取DD table中元数据的对象key值。之后的client在访问DD table之前会先判断目标key值是否在m_missed集合中，如在，就会进入等待。当第一个DD client构建好DD cache object，并把其加入到共享缓存之后，移除m_missed集合中对应的key，并通过条件变量通知所有等待的线程重新在共享缓存中获取。这样对于同一个DD cache object，就只会对DD table访问一次了。时序图如下：

图4 数据字典缓存未命中时序图

缓存修改过程

在一个数据库工作线程对DD进行修改时，DD cache也会在事务commit阶段通过remove_uncommitted_objects()函数进行更新，更新的过程为先把DD旧数据从缓存中删除，再把修改后的DD cache object更新到缓存中去，先更新二级缓存，再更新一级缓存，流程图如下：

图5 数据字典缓存更新流程图

因为这个更新DD缓存的操作是在事务commit阶段进行，所以在更新一级缓存时，会先把更新后的DD cache object放到一级缓存中的m_registry_committed里去，再把m_registry_uncommitted和m_registry_dropped清空。

缓存失效过程

当Dictionary_client的drop方法被调用对元数据对象进行清理时，在元数据对象从DD tables中删除后，会调用invalidate()函数使两级缓存中的DD cache object失效。流程图如下：

图6 数据字典缓存失效流程图

这里在判断DD cache object在一级缓存中存在，并在一级缓存中删除掉该对象后，可以直接在二级缓存中完成删除操作。缓存失效的过程受到元数据锁（Metadata lock, MDL）的保护，因为元数据锁的并发控制，保证了一个线程在删除共享缓存时，不会有其他线程也来删除它。实际上本地缓存的数据有效，就是依赖于元数据锁的保护，否则共享缓存区域的信息，是可以被其他线程更改的。

缓存容量管理

一级本地缓存为DD client线程独享，由RAII类Auto_releaser来负责管理其生命周期。其具体流程为：每次建立一个DD client时，会定义一个对应的Auto_releaser类，当访问DD时，会把读取到的DD cache object同时加到Auto_releaser里面的m_release_registry中去，当Auto_releaser析构时，会调用Dictionary_client的release()函数把m_release_registry中的DD缓存全部释放掉。

二级共享缓存会在Shared_dictionary_cache初始化时，根据不同类型的对象设定好缓存的容量，代码如下：

voidShared_dictionary_cache::init() {

  instance()->m_map<Collation>()->set_capacity(collation_capacity);

  instance()->m_map<Charset>()->set_capacity(charset_capacity);

  ...

}

代码段5

在二级缓存容量达到上限时，会通过LRU的缓存淘汰策略来淘汰最近最少使用的DD cache对象。在一级缓存中存在的缓存对象不会被淘汰。

//Helper function to evict unused elements from the free list.
template <typename T>
void Shared_multi_map<T>::rectify_free_list(Autolocker *lock) {

  mysql_mutex_assert_owner(&m_lock);while (map_capacity_exceeded() && m_free_list.length() > 0) {

    Cache_element<T> *e =m_free_list.get_lru();

    DBUG_ASSERT(e&& e->object());

    m_free_list.remove(e);//Mark the object as being used to allow it to be removed.
    e->use();

    remove(e,lock);

  }

}

代码段6

总结

MySQL 8.0中的数据字典，通过对两级缓存的逐级访问，以及精妙的对缓存未命中情况的处理方式，有效的加速了在不同场景下数据库对DD的访问速度，显著的提升了数据库访问元数据信息的效率。另外本文还提到了元数据锁对数据字典缓存的保护，关于元数据锁的相关机制，会在后续文章陆续介绍。

点击关注，第一时间了解华为云新鲜技术~

我们为什么需要微服务架构，它一定是为了解决我们某些问题才出现了。这篇文章我们讨论下微服务架构模式所解决的问题，带来的挑战，以及他的核心思想本质。

1 早期的服务架构

上图是一个典型的服务分层架构：
Client：
调用方是browser web或者App
应用层：
实现计算层的业务逻辑，从上游数据层获取数据，对下游Client返回html/json/File等
数据-缓存层：
提高访问数据的性能
数据-数据库层：
持久化数据层

2 它存在的问题

1. 重装单体模式
如果是电商类型的系统，以上的架构明显需要把 用户登录、商品浏览、下单、结算、支付、订单查询都实现在一个系统里面，实在笨重。

2. 流量和并发量限制
当系统的流量或并发量达到一定的阈值，比如日活跃用户数量超过百万，或者每秒请求数（QPS）达到数千甚至更高时，传统的单体架构可能难以支撑如此高的负载。

3. 迭代频率
如果业务需求变更非常频繁，例如每周两次以上甚至每天都有新的功能需要上线，那么整个系统要全量发布，不论你的模块是不是变更了。难顶哟！

4. 系统难以扩展
当系统需要快速扩展以满足业务增长时，微服务架构可以更容易地实现水平扩展。

4. 耦合度和依赖关系
如果旧系统中的模块之间存在高度的耦合和复杂的依赖关系，这可能导致维护和升级变得困难。

5. 缺失故障隔离和容错能力
如果系统中的某个模块出现故障，是否会影响到整个系统的正常运行？答案是肯定的

3 微服务架构的演进

上面的问题，明显是日益膨胀的功能模块和流量规模对单体架构系统的挑战，如果不优化，将衍生出一系列的问题。
我们可以
通过微服务架构演进，对系统逐步的升级
。以下是我们在业务实践过程中总结的一些经验，予以参考。

3.1 基于业务逻辑拆分

基于业务逻辑拆分相对好理解一点，典型的单一职责原则，我们将功能相近的业务整合到一个服务颗粒上。

业务领域模型拆分
举一个典型的电商业务例子。电商的业务体系庞大，涉及各方面的细节。但是我们大概能够根据业务的职能做一个拆分，比如
阿里的电商中台业务，包含 用户账号子系统、商品子系统、订单子系统、客户子系统、物流子系统 等。
因为职能不同，这些领域之间包含清晰的界限，所以我们可以按照这个方向将服务于不同领域（商品域和订单域）的子系统拆成独立的服务颗粒。如下图：

用户群体拆分
根据用户群体做拆分，我们首先要了解自己的系统业务里的用户角色领域是否没有功能耦合，有清晰的领域界限。
比如教育信息化系统，教师的业务场景和学生的业务场景，基本比较独立，而且拆分后流量上有明显的削弱。如下图所示：

3.2 基于可扩展拆分

这个需要区分系统中变与不变的部分，
不变的部分一般是成熟的、通用的服务功能，变的部分一般是改动比较多、需要不断满足业务迭代扩展性需要的功能。
根据二八原则，系统中经常变动的部分大约只占 20%（如 运营、活动），而剩下的 80% （用户信息、基本商品信息、物流信息 等模块的管理能力和视图界面）基本不变或极少变化。如下图所示：

3.3 基于可靠性拆分

核心模块拆分
我们团队在做MySQL数据库和Redis集群拆分的时候，总会
把一些重要的模块独立放在一个集群上，不与其他模块混用，而这个独立的集群，服务机性能要是最好的
。这样做的目的是，当重要度较低的模块发生故障时，不会影响重要度高的模块。同样的道理，我们将账号、支付等核心服务单独拆分在一个服务颗粒上，建立独立服务集群，保证资源独享，来提升可用性。 如下图所示：

主次链路拆分
在各个业务系统中，其实都会有主次业务链路。主业务链条，完成了业务系统中最核心的那部分工作。而次链路是保证其他基础功能的稳定运行。
以电商为例子：商品搜索->商品详情页->购物车模块->订单结算->支付业务，就是一条最简单的主链路。主链路是整个系统的核心主战场，最好的资源跟火力都要放在这里，保证不失守。

这样的拆分模式保障了核心链路的计算资源分配优先、异常容错处理优先、服务隔离保护等等。

3.4 基于性能需求拆分

根据性能需求来进行拆分。简单来说就是访问量特别大，访问频率特别高的业务，又要保证高效的响应能力，这些业务对性能的要求特别高。比如积分竞拍、低价秒杀、限量抢购。
我们要识别出某些超高并发量的业务，尽可能把这部分业务独立拆分出来。

4 代价

分布式系统的固有复杂性
微服务架构是基于分布式的系统，而构建分布式系统必然会带来额外的性能开销和可靠性挑战。
服务的依赖管理和测试
在单体应用中，通常使用集成测试来验证依赖是否正常。而在微服务架构中，单元测试和整条服务链路的可用性都需要关注。
有效的配置版本管理
需要引入配置的版本管理、环境管理。
自动化的部署流程
有效地构建自动化部署体系，配合服务网格、容器技术，是微服务面临的另一个挑战。
对于DevOps有更高的要求
开发者也需承担起整个服务的生命周期的责任，包括部署、链路追踪、监控。构建全功能的团队，也是一个不小的挑战。
运维成本飙升
运维主要包括配置、部署、监控与告警和日志收集四大方面。微服务架构中，每个微服务粒度都需要独立地配置、部署、监控和收集日志，成本呈指数级增长。服务化粒度越细，运维成本越高。

5 微服务架构思想本质

最终的微服务架构可能是这种状态：

所以我们可以看出微服务架构的本质应该有如下几个：

• 风险隔离：
  高度自治和高度隔离
  ，明显不让低等级的服务影响高等级
• 分治原理：
  单个服务的吞吐始终是有限的，通过微服务拆分可以突破扩展上限
  ，分拆流量可支撑全球化的业务，不再受机房规模甚至地域影响
• 单一职责：
  单体系统逐渐演变成具有
  单一职责的细粒度微服务

在前端开发中，处理和搜索大量数据时，效率是一个关键因素。二分查找算法是一种高效的查找算法，适用于在有序数组中快速找到目标值。本文将详细介绍二分查找算法的基本原理、实现方法及其在前端开发中的应用。

什么是二分查找？

二分查找（Binary Search）是一种在有序数组中查找目标值的算法。它通过不断将查找范围缩小一半来快速锁定目标值的位置。该算法的时间复杂度为 O(log n)，显著优于线性查找算法的 O(n)。

二分查找的工作原理

1. 初始化
   ：确定数组的起始索引和结束索引。
2. 计算中间点
   ：取中间索引值
   mid = (left + right) / 2
   。
3. 比较中间值
   ：
   
   • 如果中间值等于目标值，则查找成功，返回中间索引。
   • 如果中间值小于目标值，则将查找范围缩小到中间索引的右侧部分。
   • 如果中间值大于目标值，则将查找范围缩小到中间索引的左侧部分。
4. 重复步骤 2 和 3
   ：直到找到目标值或查找范围为空。

二分查找的实现

以下是 JavaScript 中二分查找算法的实现：

functionbinarySearch(arr, target) {

  let left= 0;

  let right= arr.length - 1;while (left <=right) {

    let mid= Math.floor((left + right) / 2);if (arr[mid] ===target) {return mid; //找到目标值，返回索引
    } else if (arr[mid] <target) {

      left= mid + 1; //缩小到右侧部分
    } else{

      right= mid - 1; //缩小到左侧部分
}

  }return -1; //未找到目标值
}

示例：

const sortedArray = [1, 3, 5, 7, 9, 11, 13, 15];

const targetValue= 7;



const result=binarySearch(sortedArray, targetValue);

console.log(result);//输出 3，因为 7 在数组中的索引是 3

二分查找的应用场景

1. 数组查找
   ：快速在有序数组中查找目标值的位置。
2. DOM 操作
   ：在前端开发中，二分查找可以用于优化 DOM 操作，例如在虚拟 DOM 中高效查找特定节点。
3. 数据处理
   ：处理和分析大数据集时，通过二分查找快速定位特定数据点。

优化和变种

1. 递归实现
   ：除了迭代实现，二分查找也可以使用递归方式实现：

functionrecursiveBinarySearch(arr, target, left, right) {if (left >right) {return -1; //未找到目标值
}



  let mid= Math.floor((left + right) / 2);if (arr[mid] ===target) {return mid; //找到目标值，返回索引
  } else if (arr[mid] <target) {return recursiveBinarySearch(arr, target, mid + 1, right); //右侧部分
  } else{return recursiveBinarySearch(arr, target, left, mid - 1); //左侧部分
}

}//使用递归实现
const resultRecursive = recursiveBinarySearch(sortedArray, targetValue, 0, sortedArray.length - 1);

console.log(resultRecursive);//输出 3

变种算法
：二分查找的变种包括查找第一个或最后一个符合条件的元素、查找插入位置等。

Grafana Loki查询加速：如何在不添加资源的前提下提升查询速度

来自
Grafana Loki query acceleration: How we sped up queries without adding resources
，介绍了Loki如何通过n-grams + 布隆过滤器来加速查询。

在过去的5年中，我们在平衡特性开发和支持大规模用户之时，改善了日志聚合系统。早在Loki 3.0之前，我们就已经将峰值吞吐量从Loki 1.0的 10GB/s 提升到了1TB/s 以上。但为了更进一步，并符合低成本、易使用的准则，我们需要寻求一种更加明智的方式。

例如，最近我们在
过滤查询
时遇到一个有趣的事情：查询时会访问大量根本不需要的数据。例如在一个对7天数据的查询中，我们的Grafana Labs生产集群处理了280PB的日志，但从结果上看，大约有140PB的搜索日志并不匹配任何过滤表达式，换句话说，对50%的数据的查询并没有返回任何结果。更糟糕的是，在65%的数据(182PB)处理中，每1百万日志仅返回了1条日志行。

当然，我们可以通过增加更多的计算资源来解决吞吐量问题，但这与我们的愿景(Loki应该是高效可扩展的)不符。我们将此看做是一个挑战，也是一个机会。那么如何在保持Loki易用性和成本的同时提升过滤查询的效率？

如何加速Loki的查询

在深入这个话题之前，我们需要介绍本文中的两个概念：
n-grams
and
布隆过滤器
：

• 我们使用n-grams提供子字符串排列。如假设给定字符串"abcdef"，那么三元组(n-grams的n=3)为"abc"、"bcd"、"cde"和"def"
• 布隆过滤器是一种用于概率匹配的数据结构。它可以判断假阳性，但无法判断假阴性。它在数据库层面有相当长的应用历史。

正如上面所述，我们观察到，请求时间内的大部分数据都是不相关的数据，对特定的查询来说，这些数据毫无价值。我们需要识别并消除这些不相关数据，确保只搜索相关的数据。为此我们需要关注"不相关的数据在哪里"，并找到一种"足够好的"空间有效的数据结构来评估出一个过滤查询的相关数据的所在位置，然后忽略掉其余数据。

另一个关键要素是n-grams。它可以帮助Loki维护"结构无意识性"(即没有schemas)。该算法会创建很多数据，但鉴于很多日志行都有共同的信息，因此可以大大减少创建的数据量。例如，下面粗体的部分在所有日志中都是重复的，这部分内容就称之为共同信息：

msg=”adding item to cart” userID="
a4hbfer74g"
itemID="
jr8fdnasd65u4"

msg=”adding item to cart” userID="
a4hbfer74g"
itemID="
78kjasdj4hs21"

msg=”adding item to cart” userID="
h74jndvys6"
itemID="
yclk37uzs95j8”

幸运的是，布隆过滤器可以解决重复数据在空间上的问题。下面这张图展示了一条访问日志，其中绿色部分表示日志中经常出现的信息，黄色部分表示有时候出现的信息，而红色部分表示很少出现的信息。

将上述技术组合起来，就得到了如下方式，后续章节将详细介绍它是如何运作的：

这意味着，可以通过布隆过滤器来提升过滤查询的效率， 而在观察中发现，布隆过滤器的大小仅为日志的2%。

除了已经讨论过的所有内容之外，查询加速还附带了一种全新的查询分片策略，在该策略中，我们利用布隆过滤器来生成更少、更公平的查询分片。

传统上，通过分析TSDB的索引统计数据，Loki会将数据划分为大小大致相等的分最接近二次幂的分片。但事实上并非如此，有些序列的数据量要大于其他序列的数据量，导致分片数据处理不均衡。

我们使用布隆过滤器来降低查询前端在准备阶段需要处理的chunks数，并将chunks均衡地分发到每个需要处理的分片查询上。

布隆过滤器组件是如何工作的

下面让我们看下如何创建布隆过滤器，以及如何使用它们来匹配过滤表达式。我们引入了两个组件：Bloom compactor和Bloom gateway。

compactor会从对象存储的chunks之上构建布隆过滤器。我们为每个序列构建一个Bloom，并将其聚合为block文件。Bloom blocks中的序列遵循与Loki的
TSDB
和分片计算相同的排序方案。由于相同分片中的序列有可能存在于相同的block，因此有利于本地数据查询。除blocks之外，compactor还维护了一个包含对Bloom blocks的引用以及构建所需要的TSDB索引文件的元数据文件列表。

Bloom compactor是可以水平扩展的，它们使用一个环来分割租户，并声明对序列的key空间的子集的所有权。对于一个给定的序列，负责该序列的compactor会遍历其所有的chunks中日志行来构建一个Bloom。对于每个日志行，我们会计算其n-gram，并将每个n-gram的哈希值以及每个n-gram加上chunk标识符的哈希值追加到Bloom中，前者用于让gateways跳过整个序列，而后者用于跳过整个chunks。

例如，在chunk "aaf67d"中有一条日志行"abcdef"，首先计算其n-grams: "abc", "bcd", "cde", "def"，然后追加序列的布隆：hash("abc")、hash("abc" + "aaf67d") … hash("def")、hash("def" + "aaf67d")。

另一方面Bloom Gateway会处理来自index gateway的chunks过滤请求，它使用一系列chunks和过滤表达式来匹配布隆过滤器，并移除掉哪些不匹配过滤表达式的chunks。
类似Bloom compactors，Bloom gateways也是可以水平扩展的，并使用环来实现和compactor相同的目的：租户分片和序列key空间。index gateways使用环，并基于chunk的序列指纹来确定应该发送chunk过滤请求的bloom gateway。

将n-grams而非整条日志行添加到compactor的布隆过滤器中，可以实现Bloom gateway的部分匹配。例如上面例子中，过滤表达式
|= "abcd"
可以生成两个n-grams: "abc" 和 "bcd"，两种都匹配布隆。

对于序列中的每个chunk，我们可以通过将chunk ID追加到n-gram的方式来进行布隆测试。

下图展示了如何构建布隆，并利用它来跳过不匹配过滤表达式的n-grams的序列和blocks。

可以看到bloom compactor用于构建bloom，而bloom gateway则会查询compactor构建的bloom。

n-grams的大小是可以配置的，n-grams越长，追加到布隆过滤器的tokens越少。但同时也需要更长的过滤表达式来匹配布隆过滤器。例如，当n-grams长度为3时，则过滤表达式的长度也最少需要3个字符。

创建一个好的用户体验

当然，我们的首先目标是加快查询速度，这种方式更倾向于查询一些比较少见的数据，如UUID。
布隆过滤器非常适用于精确查询，例如，如果你要在所有日志中查找一个特定的消费者ID或一个特定的错误码，对于开发者或支持工程师来说这是一种常见的使用模式。由于布隆过滤器可以让Loki只处理可能包含这些术语的日志，而这些术语可能出现在很少的日志行中，所以对搜索时间的影响是巨大的。

所有迹象都表明布隆过滤器确实有效。早期的内部测试发现，通过引入布隆过滤器，Loki可以在查询时跳过相当大比例的日志数据。在我们的测试环境中发现，
相比之前的查询
，现在可以过滤掉70%到90%的chunks。
下面是一个使用布隆过滤器执行"大海捞针"式的查询的结果，该查询包括几个过滤条件，代表了我们看到客户在由Loki支持的Grafana Cloud Logs上运行的典型使用场景。

使用注意事项

当前实现中，并不是所有的查询都能受益于布隆过滤器。下面看下哪些地方会用到布隆过滤器，哪些地方不会用到布隆过滤器。
下面场景的查询可以使用布隆过滤器：

• 包含至少一个过滤表达式，如
  {env="prod"} |= "order=17863472" | logfmt
  就可以使用布隆过滤器，但
  {env="prod"} | logmt
  则不会

下面查询则会阻止使用布隆过滤器：

• 布隆过滤器并不适用于非等式过滤：常规和正则表达式过滤器。如
  != "debug"
  和
  !~ "(staging|dev) "
  都不会使用布隆过滤器
• line_format
  之后的过滤表达式也不会使用布隆过滤器。如
  |= `level="error"` | logfmt | line_format "ERROR {{.err}}" |= `traceID="3ksn8d4jj3"`
  其中
  |= `level="error"`
  将使用布隆过滤器，但
  |= `traceID="3ksn8d4jj3"`
  则不会使用。
• 查询尚未从Bloom gateways下载的Bloom blocks。

总结

Loki新引入的这个特性包含两个组件compactor和gateway。compactor用于生成序列的布隆过滤器, 布隆过滤器有两种，一种是根据序列表达式生成的n-grams布隆过滤器，另一种是将序列表达式和对象存储的buckets关联起来的布隆过滤器。当gateway接收到一个查询请求时，会根据该请求序列表达式生成n-grams，然后在第一个布隆过滤器中查找是否存在该序列，如果不存在则直接返回，如果存在则继续通过第二个过滤器排除掉不匹配请求表达式的buckets，进而减少需要处理的buckets。