1<!doctype html><html lang=zh-cn><head><meta name=generator content="Hugo 0.79.0"><meta charset=utf-8><meta name=viewport content="width=device-width,initial-scale=1"><meta name=robots content="noodp"><meta http-equiv=x-ua-compatible content="IE=edge, chrome=1"><title>Studying & Blogging</title><meta name=Description content="Keep Moving, Keep Learning"><meta property="og:title" content="Studying & Blogging"><meta property="og:description" content="Keep Moving, Keep Learning"><meta property="og:type" content="website"><meta property="og:url" content="https://zhewuzhou.github.io/"><meta property="og:image" content="https://zhewuzhou.github.io/logo.png"><meta property="og:updated_time" content="2020-12-20T16:51:45+08:00"><meta name=twitter:card content="summary_large_image"><meta name=twitter:image content="https://zhewuzhou.github.io/logo.png"><meta name=twitter:title content="Studying & Blogging"><meta name=twitter:description content="Keep Moving, Keep Learning"><meta name=application-name content="Studying & Blogging"><meta name=apple-mobile-web-app-title content="Studying & Blogging"><meta name=theme-color content="#ffffff"><meta name=msapplication-TileColor content="#da532c"><link rel="shortcut icon" type=image/x-icon href=/favicon.ico><link rel=icon type=image/png sizes=32x32 href=/favicon-32x32.png><link rel=icon type=image/png sizes=16x16 href=/favicon-16x16.png><link rel=apple-touch-icon sizes=180x180 href=/apple-touch-icon.png><link rel=mask-icon href=/safari-pinned-tab.svg color=#5bbad5><link rel=manifest href=/site.webmanifest><link rel=canonical href=https://zhewuzhou.github.io/><link rel=alternate href=/index.xml type=application/rss+xml title="Studying & Blogging"><link rel=feed href=/index.xml type=application/rss+xml title="Studying & Blogging"><link rel=stylesheet href=/lib/normalize/normalize.min.css><link rel=stylesheet href=/css/style.min.css><link rel=stylesheet href=/lib/fontawesome-free/all.min.css><link rel=stylesheet href=/lib/animate/animate.min.css>
1<script type=application/ld+json>{"@context":"http://schema.org","@type":"WebSite","url":"https:\/\/zhewuzhou.github.io\/","inLanguage":"zh-CN","author":{"@type":"Person","name":"zhewuzhou"},"description":"Keep Moving, Keep Learning","license":"This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.","name":"Studying \u0026 Blogging"}</script>
1</head><body header-desktop=fixed header-mobile=auto>
1<script type=text/javascript>(window.localStorage&&localStorage.getItem('theme')?localStorage.getItem('theme')==='dark':('auto'==='auto'?window.matchMedia('(prefers-color-scheme: dark)').matches:'auto'==='dark'))&&document.body.setAttribute('theme','dark');</script>
1<div id=mask></div><div class=wrapper><header class=desktop id=header-desktop><div class=header-wrapper><div class=header-title><a href=/ title="Studying & Blogging"><span class=header-title-pre><i class="far fa-kiss-wink-heart fa-fw"></i></span>zhewu's blog</a></div><div class=menu><div class=menu-inner><a class=menu-item href=/posts/>æç« </a><a class=menu-item href=/tags/>æ ç¾ </a><a class=menu-item href=/categories/>åç±» </a><a class="menu-item active" href=/ title=GitHub><i class="fab fa-github fa-fw"></i></a><span class="menu-item delimiter"></span><span class="menu-item search" id=search-desktop><input type=text placeholder=æç´¢æç« æ 颿å 容... id=search-input-desktop> 2<a href=javascript:void(0); class="search-button search-toggle" id=search-toggle-desktop title=æç´¢><i class="fas fa-search fa-fw"></i></a><a href=javascript:void(0); class="search-button search-clear" id=search-clear-desktop title=æ¸ ç©º><i class="fas fa-times-circle fa-fw"></i></a><span class="search-button search-loading" id=search-loading-desktop><i class="fas fa-spinner fa-fw fa-spin"></i></span></span><a href=javascript:void(0); class="menu-item theme-switch" title=忢䏻é¢><i class="fas fa-adjust fa-fw"></i></a></div></div></div></header><header class=mobile id=header-mobile><div class=header-container><div class=header-wrapper><div class=header-title><a href=/ title="Studying & Blogging"><span class=header-title-pre><i class="far fa-kiss-wink-heart fa-fw"></i></span>zhewu's blog</a></div><div class=menu-toggle id=menu-toggle-mobile><span></span><span></span><span></span></div></div><div class=menu id=menu-mobile><div class=search-wrapper><div class="search mobile" id=search-mobile><input type=text placeholder=æç´¢æç« æ 颿å 容... id=search-input-mobile> 3<a href=javascript:void(0); class="search-button search-toggle" id=search-toggle-mobile title=æç´¢><i class="fas fa-search fa-fw"></i></a><a href=javascript:void(0); class="search-button search-clear" id=search-clear-mobile title=æ¸ ç©º><i class="fas fa-times-circle fa-fw"></i></a><span class="search-button search-loading" id=search-loading-mobile><i class="fas fa-spinner fa-fw fa-spin"></i></span></div><a href=javascript:void(0); class=search-cancel id=search-cancel-mobile>åæ¶</a></div><a class=menu-item href=/posts/>æç« </a><a class=menu-item href=/tags/>æ ç¾</a><a class=menu-item href=/categories/>åç±»</a><a class=menu-item href=/ title=GitHub><i class="fab fa-github fa-fw"></i></a><a href=javascript:void(0); class="menu-item theme-switch" title=忢䏻é¢> 4<i class="fas fa-adjust fa-fw"></i></a></div></div></header><div class="search-dropdown desktop"><div id=search-dropdown-desktop></div></div><div class="search-dropdown mobile"><div id=search-dropdown-mobile></div></div><main class=main><div class=container><div class="page home" posts><div class=home-profile><div class=home-avatar><a href=/posts/ title=æç« ><img class=lazyload src=/svg/loading.min.svg data-src=https://blog-image-1258275666.cos.ap-chengdu.myqcloud.com/My-Avatar.png data-srcset="https://blog-image-1258275666.cos.ap-chengdu.myqcloud.com/My-Avatar.png, https://blog-image-1258275666.cos.ap-chengdu.myqcloud.com/My-Avatar.png 1.5x, https://blog-image-1258275666.cos.ap-chengdu.myqcloud.com/My-Avatar.png 2x" data-sizes=auto alt=https://blog-image-1258275666.cos.ap-chengdu.myqcloud.com/My-Avatar.png title=https://blog-image-1258275666.cos.ap-chengdu.myqcloud.com/My-Avatar.png></a></div><h2 class=home-subtitle><div id=id-1 class=typeit></div></h2><div class=links><a href=https://github.com/zhewuzhou title=GitHub target=_blank rel="noopener noreffer me"><i class="fab fa-github-alt fa-fw"></i></a><a href=https://linkedin.com/in/zhewuzhou title=LinkedIn target=_blank rel="noopener noreffer me"><i class="fab fa-linkedin fa-fw"></i></a><a href=https://www.douban.com/people/54706537 title=è±ç£ target=_blank rel="noopener noreffer me"><i data-svg-src=/lib/simple-icons/icons/douban.min.svg></i></a><a href=https://space.bilibili.com/221640611 title=bilibili target=_blank rel="noopener noreffer me"><i data-svg-src=/svg/icons/bilibili.min.svg></i></a><a href=mailto:[email protected] title=Email rel=me><i class="far fa-envelope fa-fw"></i></a><a href=/index.xml title=RSS target=_blank rel="noopener noreffer me"><i class="fas fa-rss fa-fw"></i></a></div></div><article class="single summary" itemscope itemtype=http://schema.org/Article><h1 class=single-title itemprop="name headline"><a href=/posts/weekly-paper-bridging-the-archipelago-between-row-stores-column-stores-hybrid-workloads/>æ¯å¨ä¸è®ºæï¼Bridging the Archipelago betweenRow-Stores and Column-Stores for Hybrid Workloads</a></h1><div class=post-meta><span class=post-author><a href=/ title=Author rel=author class=author><i class="fas fa-user-circle fa-fw"></i>zhewuzhou</a></span> <span class=post-publish>åå¸äº <time datetime=2018-10-20>2018-10-20</time></span> <span class=post-category>æ¶å½äº <a href=/categories/%E6%95%B0%E6%8D%AE%E5%BA%93/><i class="far fa-folder fa-fw"></i>æ°æ®åº</a></span></div><div class=content>论ææè¦ ä¼ ç»çæ°æ®åºåæä¸¤ç§ä¸åç±»åï¼ 5åéäºå¡å¤çï¼online transactional processin, OLTPï¼ï¼æ¤ç±»æ°æ®åºå°ä¸å屿§è¿ç»åå¨ï¼ä¹å³æè¡åå¨ãæè¡åå¨å¯ä»¥ä½¿å¾æå ¥/æ´æ°/å 餿´å¿«ï¼æ¯ç«ä¸æ¡æ°æ®çææå±æ§æ¯è¿ç»åå¨çãè¿ç§å卿¨¡åä¹å«å N-Ary Storage Model (NSM)ã åéæ°æ®åæï¼online analytical processing, OLAPï¼ï¼æ¤ç±»æ°æ®åºå°ä¸åæ°æ®çåä¸å±æ§è¿ç»åå¨ï¼ä¹å³ååå¨ãè¿ç§åå¨å¯ä»¥ä½¿å¾æ¥è¯¢æä½åªè¯»å ³å¿çæ°æ®å±æ§ï¼è䏿¯ä¸æ´æ¡æ°æ®ï¼åå°æµªè´¹ï¼æåå¨åå¯ä»¥æ´å¥½å°æ¯æå¤ææ¥è¯¢ãè¿ç§å卿¨¡åä¹å«å Decomposition Storage Model (DSM)ã å¾å¤ä¼ä¸æ¶æä¸ï¼è¿ä¸¤ç§ä¸åç±»åçä»»å¡å嫿ä¸åçææ¯æ ä¸åçå¢é宿ï¼ä¸ OLAPï¼å¾å¤æ åµä¸ä¹å«å䏿ºè½ï¼Business Intelligenceï¼ ç±»çä»»å¡ä¸è¬é½ç¦»çº¿è¿è¡ï¼ç¶èéçæ¶é´çæ¨ç§»ï¼æ°æ®åæçä»·å¼è¶æ¥è¶å°ã䏿æ¯ä¸é¢ä¸´å¦ä¸é®é¢ï¼ 6OLAP å OLTP ç³»ç»é´é叏伿å åéçè³å å°æ¶çæ¶å»¶ï¼OLAP æ°æ®åºå OLTP æ°æ®åºä¹é´çä¸è´æ§æ æ³ä¿è¯ï¼å¾
6龿»¡è¶³å¯¹åæç宿¶æ§è¦æ±å¾é«çä¸å¡åºæ¯ã ä¼ä¸éè¦ç»´æ¤ä¸åçæ°æ®åºä»¥ä¾¿æ¯æä¸¤ç±»ä¸åçä»»å¡ï¼ç®¡çåç»´æ¤ææ¬é«ã ä¼ä¸è½¯ä»¶å¼åå¢ééè¦ä¸ºä¸åçæ°æ®åºç¼åæ¥è¯¢è¯å¥ï¼ä¸æå¯è½éè¦å°ä¸åç³»ç»çæ°æ®è¿è¡èåï¼å¼åææ¬é«ã æ¬ç¯è®ºææè¿°äºå䏿°æ®åºå¦ä½æ¯æåæ(Hybrid transactional/analytical processing, HTAP) ã 7HTAP æ°æ®åºå表 为äºåºå¯¹ä¸è¿°ææï¼HTAP æ°æ®åºå³å䏿°æ®åºåæ¶æ¯æ OLAP/OLTPä¸å¡åºæ¯åºè¿èçï¼æ¯å¦ï¼ 8è ¾è®¯äº TiDB é¿éäº HybridDB for MySQL ç¾åº¦ BaikalDB æ°æ®åº MemSQL HTAP 为ä»ä¹åçï¼ æ°æ®åè¿å ¥æ°æ®åºçæ¶ï¼å¯ç§°ä¹ä¸ºâçæ°æ®âï¼çæ°æ®å¨ OLTP åºæ¯ä¸ä¼è¢«é¢ç¹ä¿®æ¹ãæ¤æ¶æ°æ®å®è¡åå¨ã éçæ°æ®æ ¢æ ¢åä¹ ï¼æ°æ®è¶æ¥è¶âå·âï¼è¿ä¸ªæ¶åæ°æ®ä¸å¤ªå¯è½è¢«é¢ç¹çä¿®æ¹ï¼å¯¹æ°æ®çæ¥è¯¢ååæè¶æ¥è¶å¤ãæ¤æ¶æ°æ®å®ååå¨ã å¦ä½å®ç° HTAPï¼ æ¬ç¯è®ºææä¾äºä¸ç§ç»ä¸çæ¶æï¼åæ¶æ¯æ OLTP/OLAPï¼ 9æ°æ®ä¸å纯粹çè¡åå¨ãæè ååå¨ï¼èæ¯æç §å(Tile)è¿ç»åå¨ï¼å³è¥å¹²å±æ§ç»æä¸ä¸ªåã æ°æ®åºæ§è¡å¼æä¼å®æ¶æ¶éæ§è¡çææ ï¼è¿äºææ éè¿èç±»ç®æ³(K Means) 宿¶è°æ´é£äºä¸ä¸ªåç±é£äºå±æ§ç»æãâçæ°æ®â åæ¶µçå ¶ææå±æ§ï¼éçæ°æ®åâå·âï¼æ°æ®åä» æ¶µçç¸å ³æ§å¼ºç屿§ï¼å³å¨è¡åå¨ååå卿¯ååå¨ç两ç§ä¸åçå½¢å¼ï¼å¨ååå¨ä¸ï¼æ°æ®éçæ¶é´çæ¨ç§»ï¼æ ¢æ ¢ç±è¡åå¨åæååå¨ã ç©ççæ°æ®åä¹ä¸ï¼æä¾äºä¸æ¬¡è½å¤é»è¾æ°æ®åçæ½è±¡ï¼å ¶ä¸»è¦çç®çå¨äºä½¿å¾æ°æ®åºçæ§è¡å¼ææ éå ³ç³»æ°æ®çåå¨ï¼æä½å¼å§æ§è¡çæ¶åå建é»è¾åï¼å¨æç»è¿åç»æçæ¶åï¼å°é»è¾å¿«è½¬æ¢æç©çåï¼æ´ä¸ªæ§è¡è¿ç¨ä¸ï¼æ§è¡å¼ææ éç¥éååå¨çç»èã HTAP ç±äºè¦æ¯æ OLAP åºæ¯ï¼å æ¤å¹¶åæ§å¶è¦æ±è¯»ä¸é»å¡åï¼å æ¤éæ© MVCC ä½ä¸ºå¹¶åæ§å¶ã æ»ç» å¨å¤§æ°æ®æ¨å¨è¡ä¸åå±ç年代ï¼ä¼ä¸å¾å¾éæ©å¤ç§æ°æ®åºäº§åï¼å嫿¯æå¨çº¿äº¤æãæ¥è¡¨çæãæ¥å¿åå¨ã离线åæçï¼ç¨ä»¥é©±å¨ä¸å¡çé«éåå±ï¼ä½è¿ç§ç»åå¼è§£å³æ¹æ¡ï¼éè¦ç²¾ç»çæ§å¶ä¸å产åé´çæ°æ®æµè½¬åä¸è´æ§é®é¢ï¼ä½¿ç¨é¾åº¦é¢é«ï¼æ¯ä¸ªæ°æ®åºäº§åé´çæ°æ®åæ¥ååä½ï¼ä¹å¸¦æ¥äºå¾é«çææ¬å¼éï¼è¿ä¸æ¥éå¶äºä¼ä¸çº§åºç¨çåå±ãHTAP æ°æ®åºå¨é«åº¦å¯æ©å±çæ åµä¸ï¼åæ¶æ¯æ OLTP/OLAPï¼æ¯è§£å³è¿äºé®é¢çææææ®µã</div><div class=post-footer><a href=/posts/weekly-paper-bridging-the-archipelago-between-row-stores-column-stores-hybrid-workloads/>é è¯»å ¨æ</a><div class=post-tags><i class="fas fa-tags fa-fw"></i> <a href=/tags/%E6%AF%8F%E5%91%A8%E4%B8%80%E8%AE%BA%E6%96%87/>æ¯å¨ä¸è®ºæ</a>, <a href=/tags/htap/>HTAP</a>, <a href=/tags/olap/>OLAP</a>, <a href=/tags/oltp/>OLTP</a></div></div></article><article class="single summary" itemscope itemtype=http://schema.org/Article><h1 class=single-title itemprop="name headline"><a href=/posts/database-indexes/>æ°æ®åºç´¢å¼æ°æ®ç»ææ»ç»</a></h1><div class=post-meta><span class=post-author><a href=/ title=Author rel=author class=author><i class="fas fa-user-circle fa-fw"></i>zhewuzhou</a></span> <span class=post-publish>åå¸äº <time datetime=2018-10-18>2018-10-18</time></span> <span class=post-category>æ¶å½äº <a href=/categories/%E6%95%B0%E6%8D%AE%E5%BA%93/><i class="far fa-folder fa-fw"></i>æ°æ®åº</a></span></div><div class=content>æè¦ æ°æ®åºç´¢å¼æ¯æ°æ®åºä¸æéè¦çç»æé¨åï¼èç´¢å¼çæ°æ®ç»æè®¾è®¡å¯¹æ°æ®åºçæ§è½æéè¦çå½±åãæ¬æå°è¯éåå ç§å ¸åçç´¢å¼æ°æ®ç»æï¼æ»ç»åæï¼ä»¥çª¥æ°æ®åºç´¢å¼ä¹å ¨è²ã 10B+Tree B+Tree æ¯ä¸ç§æ æ°æ®ç»æï¼æ¯ä¸ä¸ªnåæåºæ ï¼æ¯ä¸ªèç¹é常æå¤ä¸ªå©åï¼ä¸æ£µB+Treeå 嫿 ¹èç¹ãå é¨èç¹åå¶åèç¹ãæ ¹èç¹å¯è½æ¯ä¸ä¸ªå¶åèç¹ï¼ä¹å¯è½æ¯ä¸ä¸ªå å«ä¸¤ä¸ªæä¸¤ä¸ªä»¥ä¸å©åèç¹çèç¹ã 11B+Tree å 乿¯æ°æ®åºé»è®¤çç´¢å¼å®ç°ï¼å ¶ç»èå¦ä¸ï¼ 12ç»´åºç¾ç§å¨ B+ æ ä¸çèç¹é常被表示为ä¸ç»æåºçå ç´ ååæéã妿æ¤B+æ çåºæ°ï¼orderï¼æ¯m ï¼åé¤äºæ ¹ä¹å¤çæ¯ä¸ªèç¹é½å 嫿å°$ {\displaystyle \lfloor m/2\rfloor }
12 \lfloor m/2\rfloor$ 个å ç´ æå¤ m-1 个å ç´ ï¼å¯¹äºä»»æçèç¹ææå¤ m 个åæéãå¯¹äºææå é¨èç¹ï¼åæéçæ°ç®æ»æ¯æ¯å ç´ çæ°ç®å¤ä¸ä¸ªãå 为ææå¶åé½å¨ç¸åçé«åº¦ä¸ï¼èç¹é常ä¸å å«ç¡®å®å®ä»¬æ¯å¶åè¿æ¯å é¨èç¹çæ¹å¼ã æ¯ä¸ªå é¨èç¹çå ç´ å å½åå¼å®çåæ çå离å¼ãä¾å¦ï¼å¦æå é¨èç¹æä¸ä¸ªåèç¹ï¼æåæ ï¼åå®å¿ é¡»æä¸¤ä¸ªåç¦»å¼æå ç´ a1 å a2ãå¨æå·¦åæ ä¸ææçå¼é½å°äºçäº a1ï¼å¨ä¸é´åæ 䏿æçå¼é½å¨ a1 å a2 ä¹é´((a1ï¼a2]ï¼ï¼è卿å³åæ 䏿æçå¼é½å¤§äº a2ã 13B+Tree æå¦ä¸æ§è´¨ï¼ 14æ¥è¯¢æ¶é´å¤æåº¦ä¸º $O(\log _{m}n)$ æå ¥æ¶é´å¤æåº¦ $O(\log _{m}n)$ å 餿¶é´å¤æåº¦ $O(\log _{m}n)$ æç´¢ä¸ä¸ªèå´çé®ï¼k 个é®ï¼æ¶é´å¤æåº¦ä¸º ${\displaystyle O(\log _{m}n+k)}$ B+ Tree çå¤çº¿ç¨åæ¥ **æç´¢ï¼**仿 ¹èç¹å¼å§ï¼è·ååèç¹ç读é©ï¼ç¶åéæ¾ç¶èç¹ç读é©ï¼éå¤è¿ä¸ªè¿ç¨ï¼ç´å°æ¾å°ç®æ èç¹ä½ç½®ã **æå ¥/å é¤ï¼**仿 ¹èç¹å¼å§ï¼è·ååèç¹çåé©ï¼éå¤è¿ä¸ªè¿ç¨ï¼ç´å°æ¾å°ç®æ èç¹ä½ç½®ï¼å¦æåèç¹æ¯å®å ¨çï¼æå ¥/å é¤ä¸ä¼å¼èµ·æ ç»æçååå³ç¶èç¹ä¸éè¦è°æ´ï¼å¯éæ¾ææç¥å åé©ï¼ä¹è§çæå ¥/å 餿¯å èµ°æç´¢è·å¾ç®æ èç¹ç读é©ï¼å¦æç®æ èç¹å¹¶ä¸å®å ¨ï¼ååå½ä¸è¿°ä»æ ¹èç¹è·å¾åé©çè¿ç¨ã Skip Listï¼è·³è¡¨ï¼ Skip Listæ¯ä¸ç§éæºåçæ°æ®ç»æï¼åºäºå¹¶èçé¾è¡¨ï¼å ¶æç坿¯æäºäºåæ¥æ¾æ ï¼å¯¹äºå¤§å¤æ°æä½éè¦O(log n)平忶é´ï¼ãåºæ¬ä¸ï¼è·³è·å表æ¯å¯¹æåºçé¾è¡¨å¢å ä¸éå çåè¿é¾æ¥ï¼å¢å æ¯ä»¥éæºåçæ¹å¼è¿è¡çï¼æä»¥å¨å表ä¸çæ¥æ¾å¯ä»¥å¿«éçè·³è¿é¨åå表(å æ¤å¾å)ãæææä½é½ä»¥å¯¹æ°éæºåçæ¶é´è¿è¡ãSkip Listå¯ä»¥å¾å¥½è§£å³æåºé¾è¡¨æ¥æ¾ç¹å®å¼çå°é¾ã 15ä¸ä¸ªè·³è¡¨ï¼åºè¯¥å ·æä»¥ä¸ç¹å¾ï¼ 16ä¸ä¸ªè·³è¡¨åºè¯¥æå 个å±ï¼levelï¼ç»æï¼ 跳表ç第ä¸å±å 嫿æçå ç´ ï¼ æ¯ä¸å±é½æ¯ä¸ä¸ªæåºçé¾è¡¨ï¼ 妿å ç´ xåºç°å¨ç¬¬iå±ï¼åæææ¯iå°çå±é½å å«xï¼ ç¬¬iå±çå ç´ éè¿ä¸ä¸ªdownæéæåä¸ä¸å±æ¥æç¸åå¼çå ç´ ï¼ å¨æ¯ä¸å±ä¸ï¼-1å1两个å ç´ é½åºç°(åå«è¡¨ç¤ºINT_MINåINT_MAX)ï¼ Topæéæåæé«å±ç第ä¸ä¸ªå ç´ ã ç¸å¯¹äº B+Treeï¼Skip List æå¦ä¸ä¼å¿ï¼</div><div class=post-footer><a href=/posts/database-indexes/>é è¯»å ¨æ</a><div class=post-tags><i class="fas fa-tags fa-fw"></i> <a href=/tags/skiplist/>Skiplist</a>, <a href=/tags/bw-tree/>Bw-Tree</a>, <a href=/tags/adaptive-radix-tree/>Adaptive Radix Tree</a>, <a href=/tags/masstree/>Masstree</a>, <a href=/tags/b+tree/>B+Tree</a>, <a href=/tags/%E7%B4%A2%E5%BC%95/>ç´¢å¼</a>, <a href=/tags/%E6%97%A0%E9%94%81/>æ é</a></div></div></article><article class="single summary" itemscope itemtype=http://schema.org/Article><h1 class=single-title itemprop="name headline"><a href=/posts/weekly-paper-an-empirical-evalution-of-in-memory-mvcc/>æ¯å¨ä¸è®ºæï¼An Empirical Evaluation of In-Memory Multi-Version Concurrency Control</a></h1><div class=post-meta><span class=post-author><a href=/ title=Author rel=author class=author><i class="fas fa-user-circle fa-fw"></i>zhewuzhou</a></span> <span class=post-publish>åå¸äº <time datetime=2018-09-29>2018-09-29</time></span> <span class=post-category>æ¶å½äº <a href=/categories/%E6%95%B0%E6%8D%AE%E5%BA%93/><i class="far fa-folder fa-fw"></i>æ°æ®åº</a></span></div><div class=content>è®ºææ¦è¦ å¤çæ¬å¹¶åæ§å¶(Multi-Version Concurrency Controlï¼ä»¥ä¸ç®ç§°MVCC) æ¯å½ä»æ°æ®åºé¢åææµè¡çå¹¶åæ§å¶å®ç°ï¼MVCC 卿大åå¹¶ååº¦çæ åµä¸å°½å¯è½ä¿è¯äºå¡çæ£ç¡®æ§ï¼å ¶å¥½å¤æï¼ 17åä¸ä¼é»å¡è¯» åªè¯»äºå¡æ éæ°æ®åºéå°±è½æ¯æå¯éå¤è¯» å¯ä»¥å¾å¥½å°æ¯æå岿°æ®æ¥è¯¢ MVCC çå ³é®å¨äºé¦å åè®¾æ°æ®åºè¯»åå²çªä¸ä¼å¾å¤§ï¼å ¶æ¬¡éè¿ç»´æ¤åä¸ä»½æ°æ®çå¤ä¸ªçæ¬ï¼æ¯çäºå¡ä¹é´çå²çªå°½å¯è½å°ï¼å½ä¸ä¸ªäºå¡ä¿®æ¹æ°æ®çæ¶åï¼å建ä¸ä¸ªæ°ççæ¬ï¼å½ä¸ä¸ªäºå¡è¯»æ°æ®çæ¶åï¼è¿åææ°çæ¬æ°æ®ï¼ææå¯¹äºæ°æ®çä¿®æ¹é½åçå¨äºå¡çç§æç©ºé´å ï¼å¨æäº¤çæ¶åè¿è¡éªè¯ã 18å½ä»ä¸»æµçæ°æ®åºåºæ¬é½æ¯æMVCCï¼ æ¬ç¯è®ºæç³»ç»çæ»ç»äº MVCC çææ¯è¦ç¹ï¼å æ¬ï¼ 19å¹¶åæ§å¶åè®® å¤çæ¬åå¨ åå¾åæ¶ ç´¢å¼ç®¡ç å¹¶åæ§å¶åè®® MVTO éè¿é¢å 计ç®é¡ºåºçæ¹å¼æ¥æ§å¶å¹¶åï¼äºå¡ç读æä½è¿åææ°çæ²¡æè¢«åéé宿°æ®ççæ¬ï¼äºå¡çåæä½è¿ç¨å¦ä¸ï¼ 20å½åæ²¡ææ´»è·çäºå¡é宿°æ® å½åäºå¡çäºå¡ç¼å·å¤§äºææ°æ°æ®ä¸ç读äºå¡çäºå¡ç¼å· 妿è¿ä¸è¿°æ¡ä»¶æç«ï¼é£ä¹å建ä¸ä¸ªæ°çæ°æ®çæ¬ MVOCC å¨ MVOCC ä¸ï¼äºå¡è¢«åæä¸ä¸ªé¶æ®µï¼å嫿¯ï¼ 21è¯»æ°æ®é¶æ®µï¼çè¿ä¸ªé¶æ®µæ°ççæ¬è¢«åå»ºåºæ¥ã éªè¯é¶æ®µï¼å¨è¿ä¸ªé¶æ®µä¸ä¸ªæäº¤ç¼å·è¢«åé ç»è¯¥äºå¡ï¼ç¶ååºäºè¿ä¸ªç¼å·è¿è¡éªè¯ï¼ æäº¤é¶æ®µï¼å®ææäº¤ã MV2PL 顾åæä¹ï¼MV2PL æ¯ä¼ ç»ç䏤鶿®µéå¨å¤çæ¬å¹¶åæ§å¶ä¸çåºç¨ï¼äºå¡è¯»åæè åå»ºæ°æ®çæ¬é½éè¦è·å¾å¯¹åºçéã 22SSI å¯ä¸²è¡åå¿«ç §é离(serializable snapshot isolationæSSI)æ¯å¨å¿«ç §é离ç
22º§å«ä¹ä¸ï¼æ¯æä¸²è¡åãPosgtreSQL ä¸å®ç°äºè¿ç§é离级å«ï¼æ°æ®åºéè¿ç»´æ¤ä¸ä¸ªä¸²è¡çå¾ç§»é¤äºå¡å¹¶åé æçå±é©ç»æã 23å¤çæ¬åå¨ æ°æ®åºéè¿æ éæéé¾è¡¨ç»´æ¤å¤ä¸ªçæ¬ï¼ä½¿å¾äºå¡å¯ä»¥æ¹ä¾¿ç读åç¹å®çæ¬çæ°æ®ã ä» é追å åå¨(Append-Only) ææççæ¬åå¨å¨åä¸ä¸ªè¡¨ç©ºé´ æ´æ°çæ¶å追å å¨çæ¬é¾è¡¨ä¸è¿½å æ°èç¹ é¾è¡¨å¯ä»¥ä»¥ææ§å°ææ°çæ¹å¼ç»ç»ï¼ é¾è¡¨ä¹å¯ä»¥ä»¥ææ°å°ææ§çæ¹å¼ç»ç»ï¼è¡¨å¤´ä¸ºææ°çæ¬ æ¶åºåå¨(Time-Travel Storage) æ¯æ¬¡æ´æ°çæ¶åå°ä¹åççæ¬æ¾å°æ§è¡¨ç©ºé´ æ´æ°ä¸»è¡¨ç©ºé´ä¸ççæ¬ ä» å·®å¼åå¨(Delta Storage) æ¯æ¬¡æ´æ°è¿åå¨ä¿®æ¹çé¨åï¼å°å ¶å å ¥é¾è¡¨ï¼ä¸»è¡¨ç©ºé´åå¨å½åçæ¬ éè¿æ§çä¿®æ¹é¨åï¼å¯ä»¥å建æ§çæ¬ åå¾åæ¶ MVCC å¨äºå¡è¿ç¨ä¸ä¸å¯é¿å çä¼äº§çå¾å¤çæ§çæ¬ï¼è¿äºæ§çæ¬ä¼å¨ä¸åæ åµä¸è¢«åæ¶</div><div class=post-footer><a href=/posts/weekly-paper-an-empirical-evalution-of-in-memory-mvcc/>é è¯»å ¨æ</a><div class=post-tags><i class="fas fa-tags fa-fw"></i> <a href=/tags/%E6%AF%8F%E5%91%A8%E4%B8%80%E8%AE%BA%E6%96%87/>æ¯å¨ä¸è®ºæ</a>, <a href=/tags/%E9%94%81/>é</a>, <a href=/tags/mvcc/>MVCC</a></div></div></article><article class="single summary" itemscope itemtype=http://schema.org/Article><h1 class=single-title itemprop="name headline"><a href=/posts/weekly-paper-a-survey-of-b-tree-locking-techniques/>æ¯å¨ä¸è®ºæï¼A Survey of B-Tree Locking Techniques</a></h1><div class=post-meta><span class=post-author><a href=/ title=Author rel=author class=author><i class="fas fa-user-circle fa-fw"></i>zhewuzhou</a></span> <span class=post-publish>åå¸äº <time datetime=2018-09-25>2018-09-25</time></span> <span class=post-category>æ¶å½äº <a href=/categories/%E6%95%B0%E6%8D%AE%E5%BA%93/><i class="far fa-folder fa-fw"></i>æ°æ®åº</a></span></div><div class=content>è®ºææ¦è¦ B-Tree ååç§åç§æ°æ®ç±»åä½ä¸ºæ°æ®åºç´¢å¼å·²ç»æå åå¹´çåå²äºï¼è½ç¶æ¤ç±»æ°æ®ç»æåè½ç®åï¼æ éæ¥è¯¢ãæå ¥åå é¤èç¹ï¼ç¶èå¹¶åæ§å¶å´å¼å¸¸å¤æï¼å°¤å ¶æ¯æ¶åå°æ°æ®åºäºå¡çæ åµä¸ãæ¬ç¯è®ºæç³»ç»çæ»ç»äºåºäº B-Tree çæ°æ®åºç´¢å¼çå¹¶åæ§å¶ï¼æçº²æé¢ã 24é®é¢å®ä¹ æ°æ®åºä¸çå¹¶åé®é¢åä¸ºä¸¤ç±»ï¼ 25å¤çº¿ç¨å¹¶å访é®å åæ°æ®ç忥é®é¢ãæ°æ®åºä¸æå¾å¤çº¿ç¨å ±äº«æ°æ®ï¼æ¯å¦æ°æ®åºçéå®è¡¨(Locking Table)ãæ¤ç±»é®é¢å³ç¼ç¨ä¸å¸¸è§çå¹¶åæ§å¶é®é¢ï¼é常大家éè¿é(Locking)峿¤ç±»åæ¥é®é¢ï¼ä½å¨æ°æ®åºåæ ·çææ¯å´è¢«å½å为é©(Latchs)ï¼ä»¥ä¾¿å´å«äºå¡å¹¶åã å¤ä¸ªäºå¡å¹¶åè®¿é®æ°æ®åºå 容ç忥é®é¢ãæ¯å¦ä¸¤ä¸ªäºå¡å¹¶å读åé®åä¸ä¸ªç´¢å¼èç¹ï¼åæè 两个äºå¡åæ¶è¯»ååä¸ä¸ªå å页ãä¸è¬è§£å³äºå¡å¹¶åä¼ç¨å°é(Locks)ã é©çå®ç° ä¸åé©çåºç¡ CAS(Compare and Swap): å³ CPU ååæä»¤ï¼å¯¹äºç»å®çå åå°åMï¼æ¯è¾å ¶å¼Aåç»å®å¼B 26CAS æä½å å«ä¸ä¸ªæä½æ° ââ å åä½ç½®ï¼Vï¼ã颿åå¼ï¼Aï¼åæ°å¼(B)ã妿å åä½ç½®çå¼ä¸é¢æåå¼ç¸å¹é ï¼é£ä¹å¤çå¨ä¼èªå¨å°è¯¥ä½ç½®å¼æ´æ°ä¸ºæ°å¼ãå¦åï¼å¤çå¨ä¸å任使ä½ãæ 论V弿¯å¦çäºAå¼ï¼é½å°è¿åVçåå¼ãCAS ææå°è¯´æäºï¼æè®¤ä¸ºä½ç½® V åºè¯¥å å«å¼ Aï¼å¦æå å«è¯¥å¼ï¼åå° B æ¾å°è¿ä¸ªä½ç½®ï¼å¦åï¼ä¸è¦æ´æ¹è¯¥ä½ç½®ï¼åªåè¯æè¿ä¸ªä½ç½®ç°å¨çå¼å³å¯ 27æ°æ®åºé©çå®ç° æä½ç³»ç»æä¾çäºæ¥é(Mutex): å ¶ç¹ç¹æ¯ç®åæç¨ï¼å éæè éæ¾éæä½éè¦ç³»ç»è°ç¨ï¼å æ¤éå¸¸æ ¢ï¼å¤§æ¦éè¦å å nsï¼å¤§æ¦ç¸å½äº 100个 CPU æä»¤ï¼50次 CPU L1 ç¼å访é®ã
27 读åé(Reader and Writer Lock) å¯ä»¥åºäºèªæéå®ç°ï¼éè¿ç»´æ¤ä¸ä¸ªè¯»åä¸ä¸ªåçåå计æ°ï¼å 许å¤çº¿ç¨å¹¶å读ï¼è¯»åéç设计éè¦èèå¾å¤é®é¢ï¼è¯»ååçä¼å 级å¦ä½ä¿è¯ï¼éçå ¬å¹³æ§å¦ä½ä¿è¯ï¼ æ£æ¥å¹¶è®¾ç½®èªæé(Test-and-Set Spin Lock): Test-and-Set æ¯ CPU çååæä»¤ï¼ç»å¶å®å å设置ç»å®çå¼ï¼å¹¶è¿åæ§å¼ãTest-and-Set SpinLock æ¯æä½ç³»ç»å¸¸ç¨çéææ¯ï¼æ¯è¾é«æï¼ä½å¹¶ä¸ä¿è¯å ¬å¹³æ§ã æå·èªæé(Queue Based Spin Lock) MCS: åºäºé¾è¡¨çèªæé MCS Spinlock æ¯ä¸ç§åºäºé¾è¡¨ç坿©å±ã髿§è½ãå ¬å¹³çèªæéï¼ç³è¯·çº¿ç¨åªå¨æ¬å°åéä¸èªæï¼ç´æ¥å驱è´è´£éç¥å ¶ç»æèªæï¼ä»èæå¤§å°åå°äºä¸å¿ è¦çå¤çå¨ç¼ååæ¥çæ¬¡æ°ï¼éä½äºæ»çº¿åå åçå¼éãç¬è ä½¿ç¨ Linux å æ ¸å¼åè Nick Piggin çèªæéååæµè¯ç¨åºå¯¹å æ ¸ç°æçæéèªæéå MCS Spinlock è¿è¡æ§è½è¯ä¼°ï¼å¨ 16 æ ¸ AMD ç³»ç»ä¸ï¼MCS Spinlock çæ§è½å¤§çº¦æ¯æéèªæéç 8.</div><div class=post-footer><a href=/posts/weekly-paper-a-survey-of-b-tree-locking-techniques/>é è¯»å ¨æ</a><div class=post-tags><i class="fas fa-tags fa-fw"></i> <a href=/tags/%E6%AF%8F%E5%91%A8%E4%B8%80%E8%AE%BA%E6%96%87/>æ¯å¨ä¸è®ºæ</a>, <a href=/tags/%E4%BA%8B%E5%8A%A1/>äºå¡</a>, <a href=/tags/%E5%B9%B6%E5%8F%91/>å¹¶å</a>, <a href=/tags/%E9%94%81/>é</a>, <a href=/tags/%E9%97%A9/>é©</a>, <a href=/tags/mysql/>MySQL</a>, <a href=/tags/postgresql/>PostgreSQL</a></div></div></article><article class="single summary" itemscope itemtype=http://schema.org/Article><h1 class=single-title itemprop="name headline"><a href=/posts/sql_compilation_technology_for_performance/>æ°æ®åºæ§è½ä¹ç¿¼ï¼SQL è¯å¥è¿è¡æ¶ç¼è¯</a></h1><div class=post-meta><span class=post-author><a href=/ title=Author rel=author class=author><i class="fas fa-user-circle fa-fw"></i>zhewuzhou</a></span> <span class=post-publish>åå¸äº <time datetime=2018-09-13>2018-09-13</time></span> <span class=post-category>æ¶å½äº <a href=/categories/%E6%95%B0%E6%8D%AE%E5%BA%93/><i class="far fa-folder fa-fw"></i>æ°æ®åº</a></span></div><div class=content>æ°æ®åºæ§è½ä¹ç¿¼ï¼SQL è¯å¥è¿è¡æ¶ç¼è¯ æè¦ ç°ä»£æå¡å¨çä¸å¤§ç¹ç¹æ¯å åè¶æ¥è¶å¤§ï¼å¯¹äºè¿è¡å¨è¿äºæå¡å¨ä¸çæ°æ®åºï¼æ§è½çç¶é¢æ¯ CPU èéå åï¼ç¶èä¼ ç» SQL æ§è¡æ¨¡åå³âç«å±±æ¨¡åâ è¯çäºå 忝ç¶é¢ç年代ï¼å ¶ä»¥è¡ä¸ºåä½çè¿ä»£æ§è¡è¿ç¨è½ç¶çµæ´»ï¼ä½å¯¹ CPU é常ä¸å好ã 28å¨è¿ä¸ªå¤§èæ¯ä¸ï¼SQL è¯å¥è¿è¡æ¶ç¼è¯ææ¯åºè¿èçï¼ä¸ºä¼ ç»çå ³ç³»åæ°æ®åºç SQL æ§è¡æ§è½æä¸ç¿ èã 29ä¸äº SQL ç¼è¯çå®ç°å¦ä¸ï¼ 30Apache Spark Tungsten 弿è¿è¡æ¶å° SQL è¯å¥ç Where é¨åè½¬æ¢ææ½è±¡è¯æ³æ ï¼ç¶åå讲æ½è±¡è¯æ³æ è¿è¡æ¶ç¼è¯æ Java åèç ã Oracle æ°æ®åºå° SQL è¯å¥è¿è¡æ¶è½¬æ¢ä¸º C\C++ 代ç ï¼ç¶åå°å ¶ç¼è¯ä¸ºæºå¨ç ã Postgres 11 䏿ä¾äºåºäº LLVM ç峿¶ç¼è¯(JIT) ç SQL è¯å¥æ§è¡å¼æãæå®éªè¯æ Postgres ä¸ SQL è¯å¥ç¼è¯ææ¯è½å¤å° Postgres çäºå¡å¤çè½åæå20%ä¹500%ã éç CPU å夿 ¸ç¶é¢æ¥ç叿¾ï¼SQL è¯å¥ç¼è¯ææ¯ä¼æä¸ºéè¦çæ°æ®åºæ§è½æåææ¯ãå¸æè¯»è éè¿æ¬ç¯å客è½å¤äºå¯¹ SQL ç¼è¯ææ¯æä¸ªå¤§æ¦ç认è¯ã 31为ä»ä¹è¦è¿è¡ SQL ç¼è¯ éç¨ï¼æ½è±¡ï¼ vs å®åä¼å SQL æ¯ä¸ä¸ªé常ä¼ç§çæ½è±¡æ¨¡åï¼å¯¹äºä½¿ç¨è æ¥è®²ï¼SQL ç®åæç¨ï¼ä¸ç¨å ³å¿ SQL èåç诸å¦åå¨ã忥åå 忥å¿çç»èï¼ä»è使å¾ï¼ 32SQL å¯ä»¥è¿è¡å¨ä»»ä½ä¸å°è®¡ç®æºä¸ å¼å人åä¸éè¦å ³å¿ SQL è¯å¥çæ§è¡è¿ç¨ï¼éè¿éè¿°çæ¹å¼æè¿°ä¸å¡é»è¾ å¦å¤ä¸æ¹é¢ï¼ç°ä»£çè®¡ç®æºç¡¬ä»¶å¨ä¸æè¿æ¥ï¼SQL è¯å¥è¿è¡é度çå ³é®æ¯é对è¿äºç¡¬ä»¶è¿è¡å®åä¼åã</div><div class=post-footer><a href=/posts/sql_compilation_technology_for_performance/>é è¯»å ¨æ</a><div class=post-tags><i class="fas fa-tags fa-fw"></i> <a href=/tags/%E5%85%B3%E7%B3%BB%E5%9E%8B%E6%95%B0%E6%8D%AE%E5%BA%93/>å ³ç³»åæ°æ®åº</a>, <a href=/tags/sql/>SQL</a>, <a href=/tags/sql%E8%AF%AD%E5%8F%A5%E7%BC%96%E8%AF%91/>SQLè¯å¥ç¼è¯</a>, <a href=/tags/%E9%AB%98%E6%80%A7%E8%83%BD/>髿§è½</a>, <a href=/tags/jit/>JIT</a></div></div></article><article class="single summary" itemscope itemtype=http://schema.org/Article><h1 class=single-title itemprop="name headline"><a href=/posts/spring_aop_trap/>Spring AOPï¼å é¨è°ç¨é·é±</a></h1><div class=post-meta><span class=post-author><a href=/ title=Author rel=author class=author><i class="fas fa-user-circle fa-fw"></i>zhewuzhou</a></span> <span class=post-publish>åå¸äº <time datetime=2018-09-01>2018-09-01</time></span> <span class=post-category>æ¶å½äº <a href=/categories/framework/><i class="far fa-folder fa-fw"></i>Framework</a></span></div><div class=content>æè¦ æè¿å代ç ï¼éå°ä¸ä¸ª 奿ªçSpring AOP æå ³çé®é¢ï¼æ¬æä»è¿ä¸ªé®é¢åºåï¼éè¿é®é®é¢çæ¹å¼æç¤ºè¿ä¸ªé®é¢èåæ·±å±åå ã 33AOP é®é¢ä»£ç æ¸ å AOP Aspect: HttpHeaderValidator.java 1 2 3 4 5 6 7 @Aspect public class HttpHeaderValidator { @Before public void isUserInfoExist(){ ... } }
33 AOP Joint Point: Logger.java 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 @Aspect public class Logger { public void logTransactionA(){ String user = this.getUserFromHeader(); .</div><div class=post-footer><a href=/posts/spring_aop_trap/>é
读å
¨æ</a><div class=post-tags><i class="fas fa-tags fa-fw"></i> <a href=/tags/spring/>Spring</a>, <a href=/tags/aop/>AOP</a></div></div></article><ul class=pagination><li class="page-item active"><span class=page-link><a href=/>1</a></span></li><li class=page-item><span class=page-link><a href=/page/2/>2</a></span></li></ul></div></div></main><footer class=footer><div class=footer-container><div class=footer-line>ç± <a href=https://gohugo.io/ target=_blank rel="noopener noreffer" title="Hugo 0.79.0">Hugo</a> 强åé©±å¨ | ä¸»é¢ - <a href=https://github.com/dillonzq/LoveIt target=_blank rel="noopener noreffer" title="LoveIt 0.2.10"><i class="far fa-kiss-wink-heart fa-fw"></i>LoveIt</a></div><div class=footer-line><i class="far fa-copyright fa-fw"></i><span itemprop=copyrightYear>2020</span><span class=author itemprop=copyrightHolder> <a href=/ target=_blank>zhewuzhou</a></span> | <span class=license><a rel="license external nofollow noopener noreffer" href=https://creativecommons.org/licenses/by-nc/4.0/ target=_blank>CC BY-NC 4.0</a></span></div></div></footer></div><div id=fixed-buttons><a href=# id=back-to-top class=fixed-button title=åå°é¡¶é¨><i class="fas fa-arrow-up fa-fw"></i></a><a href=# id=view-comments class=fixed-button title=æ¥çè¯è®º><i class="fas fa-comment fa-fw"></i></a></div><link rel=stylesheet href=/lib/lightgallery/lightgallery.min.css>
33<script type=text/javascript src=/lib/smooth-scroll/smooth-scroll.min.js></script>
33<script type=text/javascript src=/lib/autocomplete/autocomplete.min.js></script>
33<script type=text/javascript src=/lib/algoliasearch/algoliasearch-lite.umd.min.js></script>
33<script type=text/javascript src=/lib/lazysizes/lazysizes.min.js></script>
33<script type=text/javascript src=/lib/twemoji/twemoji.min.js></script>
33<script type=text/javascript src=/lib/lightgallery/lightgallery.min.js></script>
33<script type=text/javascript src=/lib/lightgallery/lg-thumbnail.min.js></script>
33<script type=text/javascript src=/lib/lightgallery/lg-zoom.min.js></script>
33<script type=text/javascript src=/lib/clipboard/clipboard.min.js></script>
33<script type=text/javascript src=/lib/sharer/sharer.min.js></script>
33<script type=text/javascript src=/lib/typeit/typeit.min.js></script>
33<script type=text/javascript>window.config={"code":{"copyTitle":"å¤å¶å°åªè´´æ¿","maxShownLines":10},"data":{"id-1":"A place to write my learnings"},"lightGallery":{"actualSize":false,"exThumbImage":"data-thumbnail","hideBarsDelay":2000,"selector":".lightgallery","speed":400,"thumbContHeight":80,"thumbWidth":80,"thumbnail":true},"search":{"algoliaAppID":"XNEGAJ4RGK","algoliaIndex":"zhewuzhou.github.io","algoliaSearchKey":"200e37ab4b326abd73ff15c859620520","highlightTag":"em","maxResultLength":10,"noResultsFound":"æ²¡ææ¾å°ç»æ","snippetLength":50,"type":"algolia"},"twemoji":true,"typeit":{"cursorChar":"|","cursorSpeed":1000,"data":{"id-1":["id-1"]},"duration":-1,"speed":100}};</script>
33<script type=text/javascript src=/js/theme.min.js></script>
33<script type=text/javascript>
vendor: 118 bytes, line 33
33window.dataLayer=window.dataLayer||[];function gtag(){dataLayer.push(arguments);}gtag('js',new Date());gtag('config','
33UA-71202311-1
vendor: 25 bytes, line 33
33',{'anonymize_ip':true});
33</script>
vendor: 78 bytes, line 33
33<script type=text/javascript src="https://www.googletagmanager.com/gtag/js?id=
33UA-71202311-1
vendor: 17 bytes, line 33
33" async></script>
33</body></html>
Line numbers count LF bytes from the start of the resource, as the search results do. Vendor segments are library code the classifier recognised; they are stored but not indexed. Bytes are shown as Latin1 characters, one per byte.