山东大学操作系统课设lab5
 
实验五 具有二级索引的文件系统(lab5)
实验目的
实验环境
实验思路
调试记录
 

 
实验五 具有二级索引的文件系统(lab5)
 
实验目的
 
Nachos系统原有的文件系统只支持单级索引，最大能存取NumDirect * SectorSize的大小的文件。本次试验将在理解原文件系统的组织结构基础上扩展原有的文件系统，设计并实现具有二级索引的文件系统。
 
实验环境
 
虚拟机下Ubuntu Linux 16.04 LTS系统，nachos-3.4内核管理模块和MIPS CPU软件模拟模块，文件系统模块，代码在lab5文件夹下面实现。
 
实验思路
 
有参考这个：https://wenku.baidu.com/view/049223482b160b4e767fcfd6.html
 其实通过lab4就可以看出,思路是沿着fstest.cc里的Append()去扩展文件系统，具体是Append()里的openFile.Write()，更底层就到了Write()调用的WriteAt()。说到底，就是这一小段代码最终确定了如何分配，如何扩展，如何索引整个文件系统的扇区。所以在lab5实验里只用关注AllocateSpace()方法就好。（不对）
 
 因为filesystem里Create()方法有创建文件头对象，且构造方法里也有调用到filehdr里的Allocate()等方法，所以filehdr.cc里的每个方法，只要涉及到数组保存，都要由一个数组写成两个数组，才能完成由一级索引到二级索引的转换。
 

 
 之前lab4里的filehdr.cc里的Allocate()，文件是通过一个数组dataSectors来进行分配的。
 
 Filehdr.h里最初的定义部分有：
 #define NumDirect ((SectorSize - 2 * sizeof(int)) / sizeof(int))
 
 这是在filehdr.h里private定义dataSectors[]的大小
 之前在lab4实验报告里有说，
 
 
 所以一个sector里128个字节，sectorSize = 128,sizeof(int) = 4，则NumDirect = 30，即有存储文件消耗30个sector，30*128 = 3840，即文件可占字节为3840
 想要扩展文件系统，还是从存储文件字节的数组下手。
 建立一个dataSectors2数组，
 定义大小
 ==#define NumDirect2 (SectorSize/sizeof(int)) == 大小为128/4 = 32
 修改
 ==#define MaxFileSize ((NumDirect+NumDirect2)*SectorSize) ==
 
之前单级索引是用数组的最后1位作为索引号，dataSectors[0]-dataSectors[28]作为存取数据的块号；如果dataSectors[29]=-1，则表明没有没有二级索引块，如果dataSectors[29]为任意正值，则与二级索引块相应块号对应，即dataSectors2[]值。文件超过dataSectors[]可存放大小，则放到dataSector2[]中，dataSectors2[]返回的Sector号对应着dataSectors[-1]的值。
 文件读取还是依照之前的方法，openFile里WriteAt()添加的AllocateSpace()，其中AllocateSpace()添加了filehdr的ExpandSpace()。只是需要修改读数组dataSectors[]的方法，在读到最后一位时，需要跳到dataSectors2里去继续读二级索引的数据内容。
 关键源代码注释以及程序说明：
 这是lab4里filehdr.cc里的Allocate():
 
 但是现在需要判断一些先需加入的扇区内容是否有超过文件大小范围。如果没超过，还是一级索引可以承受的；如果超过了，则需要用到二级索引。
 如果没超过文件内容，则和lab4基本一致, 将dataSectors[-1]设置为-1;超过文件内容则使用二级索引，先将dataSectors[-1]设置为，并设置dataSectors2的大小，把其他放不下的数据块放到二级索引数组里。并把相应块号设为一级索引的值。
 
 
Filehdr里的deallocate原来是这样：
 
 相应的deallocate需要修改：如果只有一级索引，则与之前无异；若有二级索引，则将dataSector[]数组内容清除，再清楚dataSectors2[]数组内容。
 
 Lab4的ExpandSpace()是这样的。
 
 相应的加上dataSectors2的修改内容。
 
 
 ByteToSector()和Print()也相应地添加上关于dataSectors2[]的内容。
 
调试记录
 
./nachos -f
 ./nachos -D
 ./nachos -cp test/big big
 ./nachos -ap test/big big *5
 
 但是当我继续 ./nachos -ap test/big big 时就报错了。
 
我也许是没有真正实现二级索引，所以才会这样。
 发现之前一直没有make，而且在makefile和makefile.local里面是filesys而不是lab5,因为filesys和lab5是同级文件，而且内部都有filesys.cc，所以会调用错。需要修改成lab5。
 
 
 发现其实在lab4里面也是调用的filesys，修改之后make再执行，如下。
 
 Lab5修改后make再执行如下：
 
 修改了输出格式，想把一级索引对应的二级索引也写出来。
 

 做到现在，感觉对二级索引终于有了一点了解，对linux系统的debug也有了一点了解。
 虽然现在最多可以扩展到68，但是还有个很诡异的事情，就是中间会报一次错，但是之后又可以继续扩展。很奇怪，待解决。
 

原文链接
 
我的归纳： 
 （1）InnoDB的主键采用聚簇索引存储，使用的是B+Tree作为索引结构，但是叶子节点存储的是索引值和数据本身（注意和MyISAM的不同）。 
 （2）InnoDB的二级索引不使用聚蔟索引，叶子节点存储的是KEY字段加主键值。因此，通过二级索引查询首先查到是主键值，然后InnoDB再根据查到的主键值通过主键索引找到相应的数据块。 
 （3）MyISAM的主键索引和二级索引叶子节点存放的都是列值与行号的组合，叶子节点中保存的是数据的物理地址 
 （4）MyISAM引擎使用B+Tree作为索引结构，叶节点的data域存放的是数据记录的地址 
 （5）为什么用B+Tree 不是BTree： 
 B-Tree：如果一次检索需要访问4个节点，数据库系统设计者利用磁盘预读原理，把节点的大小设计为一个页，那读取一个节点只需要一次I/O操作，完成这次检索操作，最多需要3次I/O(根节点常驻内存)。数据记录越小，每个节点存放的数据就越多，树的高度也就越小，I/O操作就少了，检索效率也就上去了。 
 B+Tree：非叶子节点只存key，大大滴减少了非叶子节点的大小，那么每个节点就可以存放更多的记录，树更矮了，I/O操作更少了。所以B+Tree拥有更好的性能。
 
 
下面是原文中对聚簇索引的介绍，介绍的很简单易懂：
 
1.聚簇索引是对磁盘上实际数据重新组织以按指定的一个或多个列的值排序的算法。特点是存储数据的顺序和索引顺序一致。 
 一般情况下主键会默认创建聚簇索引，且一张表只允许存在一个聚簇索引。
 
在《数据库原理》一书中是这么解释聚簇索引和非聚簇索引的区别的： 
 聚簇索引的叶子节点就是数据节点，而非聚簇索引的叶子节点仍然是索引节点，只不过有指向对应数据块的指针。
 
因此，MySQL中不同的数据存储引擎对聚簇索引的支持不同就很好解释了。
 
2.下面，我们可以看一下mysql中MYISAM和INNODB两种引擎的索引结构。
 
如原始数据为： 
 
 
MyISAM引擎的数据存储方式如图： 
 
 
（1）MYISAM是按列值与行号来组织索引的。它的叶子节点中保存的实际上是指向存放数据的物理块的指针。 
 从MYISAM存储的物理文件我们能看出，MYISAM引擎的索引文件（.MYI）和数据文件(.MYD)是相互独立的。
 
（2）而InnoDB按聚簇索引的形式存储数据，所以它的数据布局有着很大的不同。它存储数据的结构大致如下： 
 
 
注：聚簇索引中的每个叶子节点包含主键值、事务ID、回滚指针(rollback pointer用于事务和MVCC）和余下的列(如col2)。
 
（3）INNODB的二级索引与主键索引有很大的不同。InnoDB的二级索引的叶子包含主键值，而不是行指针(row pointers)，这减小了移动数据或者数据页面分裂时维护二级索引的开销，因为InnoDB不需要更新索引的行指针。其结构大致如下： 
 
 
INNODB和MYISAM的主键索引与二级索引的对比： 
 
 
（4）InnoDB的的二级索引的叶子节点存放的是KEY字段加主键值。因此，通过二级索引查询首先查到是主键值，然后InnoDB再根据查到的主键值通过主键索引找到相应的数据块。而MyISAM的二级索引叶子节点存放的还是列值与行号的组合，叶子节点中保存的是数据的物理地址。所以可以看出MYISAM的主键索引和二级索引没有任何区别，主键索引仅仅只是一个叫做PRIMARY的唯一、非空的索引，且MYISAM引擎中可以不设主键。

一级索引
 
索引存储的结构
 

 不会出题。。。。
 
多级索引
 

 多级索引求占用物理块数
 设有一个包含1000个记录的索引文件，每个记录正好占用一个物理块。一个物理块可以存放10个索引表目。建立索引时，一个物理块应有一个索引表目，试问索引应占几个物理块？
 
首先求出建立了几级的索引
物理块的n次方恰好大于等于总记录，则N为索引级别。如此题10^3为1000，所以应建立三级索引。
则有如下示意图
 
一级一个，二级10个，三级100个，每个索引占1块，所以共计111个。
 
增量索引
 

 A1个1级索引，A2个2级索引，A3个3级索引…,磁盘每块大小为XB，每块地址为YB求管理最大文件
 
每个磁盘块能装多少个索引项X/Y项
求有多少个块${\sum }_1^{n}Ai\times {\left(\frac{X}{Y}\right)}^{i-1}$
再乘以每块的大小$XB\ast {\sum }_1^{n}Ai\times {\left(\frac{X}{Y}\right)}^{i-1}$
 
一个文件系统,磁盘每块大小为2KB,每块地址用4B表示。采用UNIX System V文件系统管理的最大的文件是多少？
 
2KB/4B=512条
$$\begin{gathered} 直接索引有10个，一级索引有1个所以1\ast 512块， \\ 二级索引有一个所以1\ast 512\ast 512块， \\ 3级索引一个所以1\ast 512\ast 512\ast 512。 \end{gathered}$$
所以最大文件为:
 $$\begin{gathered} 2KB\ast (10+512+512\ast 512+512\ast 512\ast 512) \\ =20KB+1MB+0.5GB+0.25TB \end{gathered}$$
 
多级索引和增量索引给出两个例题，但实际做题中，都会相互考到，请理解计算过程和原理。

一.概述
 
Hbase适用于大表的存储，通过单一的RowKey查询虽然能快速查询，但是对于复杂查询，尤其分页、查询总数等，实现方案浪费计算资源，所以可以针对hbase数据创建二级索引(Hbase Secondary Indexing)，供复杂查询使用。
Solr是一个高性能，采用Java5开发，基于Lucene的全文搜索服务器。同时对其进行了扩展，提供了比Lucene更为丰富的查询语言，同时实现了可配置、可扩展并对查询性能进行了优化，并且提供了一个完善的功能管理界面，是一款非常优秀的全文搜索引擎。
Key-Value Store Indexer是Hbase到Solr生成索引的中间工具。在CDH5中的Key-Value Store Indexer使用的是Lily HBase NRT Indexer服务
Lily HBase Indexer是一款灵活的、可扩展的、高容错的、事务性的，并且近实时的处理HBase列索引数据的分布式服务软件。它是NGDATA公司开发的Lily系统的一部分，已开放源代码。Lily HBase Indexer使用SolrCloud来存储HBase的索引数据，当HBase执行写入、更新或删除操作时，Indexer通过HBase的replication功能来把这些操作抽象成一系列的Event事件，并用来保证写入Solr中的HBase索引数据的一致性。并且Indexer支持用户自定义的抽取，转换规则来索引HBase列数据。Solr搜索结果会包含用户自定义的columnfamily:qualifier字段结果，这样应用程序就可以直接访问HBase的列数据。而且Indexer索引和搜索不会影响HBase运行的稳定性和HBase数据写入的吞吐量，因为索引和搜索过程是完全分开并且异步的。Lily HBase Indexer在CDH5中运行必须依赖HBase、SolrCloud和Zookeeper服务。
 
二.近实时(NRT)查询方案
 
分工：hbase负责海量数据存储；solr负责构建索引和提供对外查询；Indexer负责提供hbase到solr的索引构建。
索引创建流程：Hbase->Lily HBase Indexer->Solr
数据使用流程图 
  
 hbase-indexer-structure 
 
 
三.二级索引创建方法
 
1.hbase启用复制（在CM的hbase上搜索复制，勾选启用复制） 
  
 2.hbase表开启REPLICATION功能（1表示开启replication功能，0表示不开启，默认为0 ）
 
已存在的表
 
disable 'table' 
alter 'table',{NAME => 'cf', REPLICATION_SCOPE => 1} 
enable 'table' 
 
新创建的表
 
create 'table',{NAME => 'cf', REPLICATION_SCOPE => 1}
 
3.创建solr实体目录,其中/home/data/collectionSmsDay是在本地自定义目录。命令执行后完成工作：生成solr的配置文件。
 
solrctl instancedir --generate /home/data/collectionSmsDay
 
编辑已生成的schema.xml
 
把hbase表中需要索引的列添加到scheme.xml的filed中,其中的name属性值要与Morphline.conf文件中的outputField属性值对应，以便indexer中间件完成hbase到solr的索引创建工作。其中id保存的是hbase的rowkey；uniqueKey也是id；field的类型最好使用string；root、version、text等field不能少。
 
        <field name="_version_" type="long" indexed="true" stored="true"/>

   <!-- points to the root document of a block of nested documents. Required for nested
      document support, may be removed otherwise
   -->
   <field name="_root_" type="string" indexed="true" stored="false"/>
   <field name="timestamp" type="tdate" indexed="true" stored="true" default="NOW+8HOUR" multiValued="false"/>
   <field name="text" type="text_general" indexed="true" stored="false" multiValued="true"/>

   <field name="id" type="string" indexed="true" stored="true" required="true" multiValued="false" />

   <!-- points to the root document of a block of nested documents. Required for nested
        document support, may be removed otherwise
   -->
   <field name="send_number" type="string" indexed="true" stored="true" multiValued="false"/>
   <field name="send_parent_account" type="string" indexed="true" stored="true" multiValued="false"/>
   <field name="busi_type" type="string" indexed="true" stored="true" multiValued="false"/>
   <field name="cnts" type="string" indexed="true" stored="true" multiValued="false"/>
   <field name="day_id" type="string" indexed="true" stored="true" multiValued="false"/>

    <uniqueKey>id</uniqueKey>
 
4.创建collection并将配置文件上传至zk
 
solrctl instancedir --create collectionSmsDay /home/data/collectionSmsDay
 
登陆zk客户端查看节点:ls /solr/configs/collectionSmsDay,该节点下有solrconfig.xml、scheme.xml等配置文件;ls /solr/collection/下有collectionSmsDay
 
[root@db1 ~]# cd /opt/cloudera/parcels/CDH/lib/zookeeper/bin/
[root@db1 bin]# ./zkCli.sh 
...
[zk: localhost:2181(CONNECTED) 3] ls /solr/configs/collectionSmsDay
[admin-extra.menu-top.html, currency.xml, protwords.txt, mapping-FoldToASCII.txt, solrconfig.xml.secure, _schema_analysis_synonyms_english.json, _rest_managed.json, solrconfig.xml, _schema_analysis_stopwords_english.json, stopwords.txt, lang, spellings.txt, mapping-ISOLatin1Accent.txt, admin-extra.html, schema_bak.xml, xslt, synonyms.txt, scripts.conf, update-script.js, velocity, elevate.xml, admin-extra.menu-bottom.html, schema.xml, clustering]
[zk: localhost:2181(CONNECTED) 4] 
[zk: localhost:2181(CONNECTED) 3] ls /solr/configs
[collectionSmsDay]
 
solrctl工具使用方法
 
[hadoop@db1 lib]$ solrctl --help

usage: /opt/cloudera/parcels/CDH-5.5.1-1.cdh5.5.1.p0.11/bin/../lib/solr/bin/solrctl.sh [options] command [command-arg] [command [command-arg]] 
solrctl [options] command [command-arg] [command [command-arg]] ...  
可选参数有：  
--solr：指定 SolrCloud 的 web API，如果在 SolrCloud 集群之外的节点运行命令，就需要指定该参数。  
--zk：指定 zk 集群solr目录。  
--help：打印帮助信息。  
--quiet：静默模式运行。  

command 命令有：  
init [--force]：初始化配置。  
instancedir：维护实体目录。可选的参数有：  
--generate path  
--create name path  
--update name path  
--get name path  
--delete name  
--list  


collection：维护 collections。可选的参数有：  
[--create name -s <numShards>
                              [-a Create collection with autoAddReplicas=true]
                              [-c <collection.configName>]
                              [-r <replicationFactor>]
                              [-m <maxShardsPerNode>]
                              [-n <createNodeSet>]]
--delete name: Deletes a collection.  
--reload name: Reloads a collection.  
--stat name: Outputs SolrCloud specific run-time information fora collection.  
`--list: Lists all collections registered in SolrCloud.  
--deletedocs name: Purges all indexed documents from a collection.  


core：维护 cores。可选的参数有：  
--create name [-p name=value]]  
--reload name: Reloads a core.  
--unload name: Unloads a core.  
--status name: Prints status of a core.  


cluster：维护集群配置信息。可选的参数有：  
--get-solrxml file  
--put-solrxml file 
 
5.在solr上创建collection:collectionSmsDay
 
solrctl collection --create collectionSmsDay  -s 6 -m 15 -r 2 -c collectionSmsDay -a

其中-s是6个分片(shard)，我们的solrclound是6台机器，-r是2个副本(replication)，-c是指定zk上solr/configs节点下使用的配置文件名称，-a是允许添加副本(必须写，否则创建不了副本)，-m 默认值是1，注意三个数值：numShards、replicationFactor、liveSolrNode，一个正常的solrCloud集群不容许同一个liveSolrNode上部署同一个shard的多个replic，因此当maxShardsPerNode=1时，numShards*replicationFactor>liveSolrNode时，报错。因此正确时因满足以下条件：
numShards*replicationFactor<liveSolrNode*maxShardsPerNode
 
创建solr分片时，要根据实际情况定shard、replication，maxShardsPerNode,否则报错
 
[root@db1 conf]# solrctl collection --create  solrtest  -s  7 –r 2 -m 20
Error: A call to SolrCloud WEB APIs failed: HTTP/1.1 400 Bad Request
Server: Apache-Coyote/1.1
Content-Type: application/xml;charset=UTF-8
Transfer-Encoding: chunked
Date: Tue, 11 Oct 2016 01:11:36 GMT
Connection: close
<?xml version="1.0" encoding="UTF-8"?>
<response>
<lst name="responseHeader">
<int name="status">
400</int>
<int name="QTime">
73</int>
</lst>
<str name="Operation createcollection caused exception:">
org.apache.solr.common.SolrException:org.apache.solr.common.SolrException: Cannot create collection solrtest. Value of maxShardsPerNode is 1, and the number of live nodes is 6. This allows a maximum of 6 to be created. Value of numShards is 7 and value of replicationFactor is 1. This requires 7 shards to be created (higher than the allowed number)</str>
<lst name="exception">
<str name="msg">
Cannot create collection solrtest. Value of maxShardsPerNode is 1, and the number of live nodes is 6. This allows a maximum of 6 to be created. Value of numShards is 7 and value of replicationFactor is 1. This requires 7 shards to be created (higher than the allowed number)</str>
<int name="rspCode">
400</int>
</lst>
<lst name="error">
<str name="msg">
Cannot create collection solrtest. Value of maxShardsPerNode is 1, and the number of live nodes is 6. This allows a maximum of 6 to be created. Value of numShards is 7 and value of replicationFactor is 1. This requires 7 shards to be created (higher than the allowed number)</str>
<int name="code">
400</int>
</lst>

</response>
[root@db1 conf]# 
 
如果修改/home/data/collectionSmsDay/confs下的配置文件schema.xml，需要重新上传加载，执行以下语句:
 
solrctl instancedir --update collectionSmsDay /home/data/collectionSmsDay
solrctl collection --reload collectionSmsDay
 
web端查看新创建的collection 
 
 
6.在hbase-solr目录下创建morphline-hbase-mapper-smslogday.xml
 
其中morphlineId 的value是对应Key-Value Store Indexer 中配置文件Morphlines.conf 中morphlines 属性id值。morphlineId不要和hbase的table名称相同。
 
[hadoop@db1 hbase-solr]$ pwd
/opt/cloudera/parcels/CDH/lib/hbase-solr
[hadoop@db1 hbase-solr]$ vi morphline-hbase-mapper-smslogday.xml
<?xml version="1.0" encoding="UTF-8"?>
<indexer table="tb_sms_log_day" mapper="com.ngdata.hbaseindexer.morphline.MorphlineResultToSolrMapper">
 <param name="morphlineFile" value="morphlines.conf"></param>
 <param name="morphlineId" value="smslogdayMap"></param>
</indexer>
~
 
7.修改Morphlines配置文件, 在CM中进入Key-Value Store Indexer面板->配置->类别->Morphlines-Morphlines文件；如果添加多个morphline，用逗号分隔。
 
{
id : smsdayMap
importCommands : ["org.kitesdk.**", "com.ngdata.**"]

commands : [                    
  {
    extractHBaseCells {
      mappings : [
        {
          inputColumn : "cf:send_number"
          outputField : "send_number" 
          type : string 
          source : value
        }
        {
          inputColumn : "cf:send_parent_account"
          outputField : "send_parent_account" 
          type : string 
          source : value
        }
        {
          inputColumn : "cf:busi_type"
          outputField : "busi_type" 
          type : string 
          source : value
        }
        {
          inputColumn : "cf:cnts"
          outputField : "cnts" 
          type : string 
          source : value
        }
        {
          inputColumn : "cf:day_id"
          outputField : "day_id" 
          type : string 
          source : value
        }     
      ]
    }
  }


  { logDebug { format : "output record: {}", args : ["@{}"] } }
]
}
 
 
8.将morphline-hbase-mapper-smsday.xml注册到Lily Hbase Service服务中
 
-n表示indexer的名称，-c表示加载的indexer的配置文件名称，–connection-param表示连接的solr的zk地址和对应的collection名称，–zookeeper表示indexer要上传到的zk地址。
 
hbase-indexer add-indexer 
-n smsdayIndexer 
-c /opt/cloudera/parcels/CDH/lib/hbase-solr/morphline-hbase-mapper-smsday.xml 
--connection-param solr.zk=nn1.hadoop:2181,nn2.hadoop:2181,dn7.hadoop:2181,dn5.hadoop:2181,dn3.hadoop:2181/solr  
--connection-param solr.collection=collectionSmsDay 
--zookeeper nn1.hadoop:2181,nn2.hadoop:2181,dn7.hadoop:2181,dn5.hadoop:2181,dn3.hadoop:2181
 
查看索引器是否创建成功，关键Processes是否都是running processes
 
[hadoop@db1 hbase-solr]$ hbase-indexer list-indexers --zookeeper nn1.hadoop:2181
Number of indexes: 1

smsdayIndexer
  + Lifecycle state: ACTIVE
  + Incremental indexing state: SUBSCRIBE_AND_CONSUME
  + Batch indexing state: INACTIVE
  + SEP subscription ID: Indexer_smsdayIndexer
  + SEP subscription timestamp: 2016-10-22T11:13:48.888+08:00
  + Connection type: solr
  + Connection params:
    + solr.collection = collectionSmsDay
    + solr.zk = nn1.hadoop:2181,nn2.hadoop:2181,dn7.hadoop:2181,dn5.hadoop:2181,dn3.hadoop:2181/solr
  + Indexer config:
      268 bytes, use -dump to see content
  + Indexer component factory: com.ngdata.hbaseindexer.conf.DefaultIndexerComponentFactory
  + Additional batch index CLI arguments:
      (none)
  + Default additional batch index CLI arguments:
      (none)
  + Processes
    + 2 running processes
    + 0 failed processes
 
如果索引器需要重建，删除使用下列方法。如果删除不了，始终在删除中的死循环中，就需要到zk上手动删除节点信息：ls /ngdata/hbaseindexer下。
 
hbase-indexer delete-indexer -n smsdayIndexer --zookeeper nn1.hadoop:2181
 
9.hbase插入测试,solr中查询成功
 
put 'tb_sms_day', '20161012000000001', 'cf:send_number', '15173751522'
put 'tb_sms_day', '20161012000000001', 'cf:day_id', '2016-10-21'
put 'tb_sms_day', '20161012000000001', 'cf:cnts', '1'
put 'tb_sms_day', '20161012000000001', 'cf:busi_type', 'SMS'
 
 
以上，有问题请留言！