数据结构思维 第十四章 持久化

2022-12-01 18:59:20 浏览数 (1)

第十四章 持久化

原文：Chapter 14 Persistence 译者：飞龙 协议：CC BY-NC-SA 4.0 自豪地采用谷歌翻译

在接下来的几个练习中，我们将返回到网页搜索引擎的构建。为了回顾，搜索引擎的组件是：

  • 抓取：我们需要一个程序，可以下载一个网页，解析它，并提取文本和任何其他页面的链接。
  • 索引：我们需要一个索引，可以查找检索项并找到包含它的页面。
  • 检索：我们需要一种方法，从索引中收集结果，并识别与检索项最相关的页面。

如果你做了练习 8.3，你使用 Java 映射实现了一个索引。在本练习中，我们将重新审视索引器，并创建一个新版本，将结果存储在数据库中。

如果你做了练习 7.4，你创建了一个爬虫，它跟踪它找到的第一个链接。在下一个练习中，我们将制作一个更通用的版本，将其查找到的每个链接存储在队列中，并对其进行排序。

然后，最后，你将处理检索问题。

在这些练习中，我提供较少的起始代码，你将做出更多的设计决策。这些练习也更加开放。我会提出一些最低限度的目标，你应该尝试实现它们，但如果你想挑战自己，有很多方法可以让你更深入。

现在，让我们开始编写一个新版本的索引器。

14.1 Redis

索引器的之前版本，将索引存储在两个数据结构中：TermCounter将检索词映射为网页上显示的次数，以及Index将检索词映射为出现的页面集合。

这些数据结构存储在正在运行的 Java 程序的内存中，这意味着当程序停止运行时，索引会丢失。仅在运行程序的内存中存储的数据称为“易失的”，因为程序结束时会消失。

在创建它的程序结束后，仍然存在的数据称为“持久的”。通常，存储在文件系统中的文件，以及存储在数据库中的数据是持久的。

使数据持久化的一种简单方法是，将其存储在文件中。在程序结束之前，它可以将其数据结构转换为 JSON 格式（http://thinkdast.com/json），然后将它们写入文件。当它再次启动时，它可以读取文件并重建数据结构。

但这个解决方案有几个问题：

  • 读取和写入大型数据结构（如 Web 索引）会很慢。
  • 整个数据结构可能不适合单个运行程序的内存。
  • 如果程序意外结束（例如，由于断电），则自程序上次启动以来所做的任何更改都将丢失。

一个更好的选择是提供持久存储的数据库，并且能够读取和写入数据库的部分，而无需读取和写入整个数据。

有多种数据库管理系统（DBMS）提供不同的功能。你可以在 http://thinkdast.com/database 阅读概述。

我为这个练习推荐的数据库是 Redis，它提供了类似于 Java 数据结构的持久数据结构。具体来说，它提供：

字符串列表，与 Java 的List类似。 哈希，类似于 Java 的Map。 字符串集合，类似于 Java 的Set。

译者注：另外还有类似于 Java 的LinkedHashSet的有序集合。

Redis 是一个“键值数据库”，这意味着它包含的数据结构（值）由唯一的字符串（键）标识。Redis 中的键与 Java 中的引用相同：它标识一个对象。我们稍后会看到一些例子。

14.2 Redis 客户端和服务端

Redis 通常运行为远程服务；其实它的名字代表“REmote DIctionary Server”（远程字典服务，字典其实就是映射）。为了使用 Redis，你必须在某处运行 Redis 服务器，然后使用 Redis 客户端连接到 Redis 服务器。有很多方法可用于设置服务器，也有许多你可以使用的客户端。对于这个练习，我建议：

不要自己安装和运行服务器，请考虑使用像 RedisToGo（http://thinkdast.com/redistogo）这样的服务，它在云主机运行 Redis。他们提供了一个免费的计划（配置），有足够的资源用于练习。 对于客户端，我推荐 Jedis，它是一个 Java 库，提供了使用 Redis 的类和方法。

以下是更详细的说明，以帮助你开始使用：

  • 在 RedisToGo 上创建一个帐号，网址为 http://thinkdast.com/redissign ，并选择所需的计划（可能是免费的起始计划）。
  • 创建一个“实例”，它是运行 Redis 服务器的虚拟机。如果你单击“实例”选项卡，你将看到你的新实例，由主机名和端口号标识。例如，我有一个名为dory-10534的实例。
  • 单击实例名称来访问配置页面。记下页面顶部附近的网址，如下所示： redis://redistogo:1234567feedfacebeefa1e1234567@dory.redistogo.com:10534

这个 URL 包含服务器的主机名称dory.redistogo.com，端口号10534和连接到服务器所需的密码，它是中间较长的字母数字的字符串。你将需要此信息进行下一步。

14.3 制作基于 Redis 的索引

在本书的仓库中，你将找到此练习的源文件：

  • JedisMaker.java包含连接到 Redis 服务器并运行几个 Jedis 方法的示例代码。
  • JedisIndex.java包含此练习的起始代码。
  • JedisIndexTest.java包含JedisIndex的测试代码。
  • WikiFetcher.java包含我们在以前的练习中看到的代码，用于阅读网页并使用jsoup进行解析。

你还将需要这些文件，你在以前的练习中碰到过：

Index.java使用 Java 数据结构实现索引。 TermCounter.java表示从检索项到其频率的映射。 WikiNodeIterable.java迭代jsoup生成的 DOM 树中的节点。

如果你有这些文件的有效版本，你可以使用它们进行此练习。如果你没有进行以前的练习，或者你对你的解决方案毫无信心，则可以从solutions文件夹复制我的解决方案。

第一步是使用 Jedis 连接到你的 Redis 服务器。JedisMaker.java展示了如何实现。它从文件读取你的 Redis 服务器的信息，连接到它并使用你的密码登录，然后返回一个可用于执行 Redis 操作的 Jedis 对象。

如果你打开JedisMaker.java，你应该看到JedisMaker类，它是一个帮助类，它提供静态方法make，它创建一个 Jedis 对象。一旦该对象认证完毕，你可以使用它来与你的 Redis 数据库进行通信。

JedisMaker从名为redis_url.txt的文件读取你的 Redis 服务器信息，你应该放在目录src/resources中：

  • 使用文本编辑器创建并编辑ThinkDataStructures/code/src/resources/redis_url.txt。
  • 粘贴服务器的 URL。如果你使用的是 RedisToGo，则 URL 将如下所示： redis://redistogo:1234567feedfacebeefa1e1234567@dory.redistogo.com:10534

因为此文件包含你的 Redis 服务器的密码，你不应将此文件放在公共仓库中。为了帮助你避免意外避免这种情况，仓库包含.gitignore文件，使文件难以（但不是不可能）放入你的仓库。

现在运行ant build来编译源文件，以及ant JedisMaker来运行main中的示例代码：

代码语言：javascript复制
    public static void main(String[] args) {

        Jedis jedis = make();

        // String
        jedis.set("mykey", "myvalue");
        String value = jedis.get("mykey");
        System.out.println("Got value: "   value);

        // Set
        jedis.sadd("myset", "element1", "element2", "element3");
        System.out.println("element2 is member: "   
                           jedis.sismember("myset", "element2"));

        // List
        jedis.rpush("mylist", "element1", "element2", "element3");
        System.out.println("element at index 1: "   
                           jedis.lindex("mylist", 1));

        // Hash
        jedis.hset("myhash", "word1", Integer.toString(2));
        jedis.hincrBy("myhash", "word2", 1);
        System.out.println("frequency of word1: "   
                           jedis.hget("myhash", "word1"));
        System.out.println("frequency of word1: "   
                            jedis.hget("myhash", "word2"));

        jedis.close();
    }

这个示例展示了数据类型和方法，你在这个练习中最可能使用它们。当你运行它时，输出应该是：

代码语言：javascript复制
Got value: myvalue
element2 is member: true
element at index 1: element2
frequency of word1: 2
frequency of word2: 1

下一节中我会解释代码的工作原理。

14.4 Redis 数据类型

Redis 基本上是一个从键到值的映射，键是字符串，值可以是字符串，也可以是几种数据类型之一。最基本的 Redis 数据类型是字符串。我将用斜体书写 Redis 类型，来区别于 Java 类型。

为了向数据库添加一个字符串，请使用jedis.set，类似于Map.put; 参数是新的键和相应的值。为了查找一个键并获取其值，请使用jedis.get：

代码语言：javascript复制
        jedis.set("mykey", "myvalue");
        String value = jedis.get("mykey");

在这个例子中，键是"mykey"，值是"myvalue"。

Redis 提供了一个集合结构，类似于 Java 的Set<String>。为了向 Redis 集合添加元素，你可以选择一个键来标识集合，然后使用jedis.sadd：

代码语言：javascript复制
        jedis.sadd("myset", "element1", "element2", "element3");
        boolean flag = jedis.sismember("myset", "element2");

你不必用单独的步骤来创建集合。如果不存在，Redis 会创建它。在这种情况下，它会创建一个名为myset的集合，包含三个元素。

jedis.sismember方法检查元素是否在一个集合中。添加元素和检查成员是常数时间的操作。

Redis 还提供了一个列表结构，类似于 Java 的List<String>。jedis.rpush方法在末尾（右端）向列表添加元素：

代码语言：javascript复制
        jedis.rpush("mylist", "element1", "element2", "element3");
        String element = jedis.lindex("mylist", 1);

同样，你不必在开始添加元素之前创建结构。此示例创建了一个名为mylist的列表，其中包含三个元素。

jedis.lindex方法使用整数索引，并返回列表中指定的元素。添加和访问元素是常数时间的操作。

最后，Redis 提供了一个哈希结构，类似于 Java 的Map<String, String>。jedis.hset方法为哈希表添加新条目：

代码语言：javascript复制
        jedis.hset("myhash", "word1", Integer.toString(2));
        String value = jedis.hget("myhash", "word1");

此示例创建一个名为的myhash哈希表，其中包含一个条目，该条目从将键word1映射到值"2"。

键和值都是字符串，所以如果我们要存储Integer，在我们调用hset之前，我们必须将它转换为String。当我们使用hget查找值时，结果是String，所以我们可能必须将其转换回Integer。

使用 Redis 的哈希表可能会令人困惑，因为我们使用一个键来标识我们想要的哈希表，然后用另一个键标识哈希表中的值。在 Redis 的上下文中，第二个键被称为“字段”，这可能有助于保持清晰。所以类似myhash的“键”标志一个特定的哈希表，然后类似word1的“字段”标识一个哈希表中的值。

对于许多应用程序，Redis 哈希表中的值是整数，所以 Redis 提供了一些特殊的方法，比如hincrby将值作为数字来处理：

代码语言：javascript复制
        jedis.hincrBy("myhash", "word2", 1);

这个方法访问myhash，获取word2的当前值（如果不存在则为0），将其递增1，并将结果写回哈希表。

在哈希表中，设置，获取和递增条目是常数时间的操作。

你可以在 http://thinkdast.com/redistypes 上阅读 Redis 数据类型的更多信息。

14.5 练习 11

这个时候，你可以获取一些信息，你需要使用它们来创建搜索引擎的索引，它将结果储存在 Redis 数据库中。

现在运行ant JedisIndexTest。它应该失败，因为你有一些工作要做！

JedisIndexTest测试了这些方法：

  • JedisIndex，这是构造器，它接受Jedis对象作为参数。
  • indexPage，它将一个网页添加到索引中；它需要一个StringURL和一个jsoup Elements对象，该对象包含应该建立索引的页面元素。
  • getCounts，它接收检索词，并返回Map<String, Integer>，包含检索词到它在页面上的出现次数的映射。

以下是如何使用这些方法的示例：

代码语言：javascript复制
        WikiFetcher wf = new WikiFetcher();
        String url1 = 
            "http://en.wikipedia.org/wiki/Java_(programming_language)";
        Elements paragraphs = wf.readWikipedia(url1);

        Jedis jedis = JedisMaker.make();
        JedisIndex index = new JedisIndex(jedis);
        index.indexPage(url1, paragraphs);
        Map<String, Integer> map = index.getCounts("the");

如果我们在结果map中查看url1，我们应该得到339，这是 Java 维基百科页面（即我们保存的版本）中，the出现的次数。

如果我们再次索引相同的页面，新的结果将替换旧的结果。

将数据结构从 Java 翻译成 Redis 的一个建议是：记住 Redis 数据库中的每个对象都以唯一的键标识，它是一个字符串。如果同一数据库中有两种对象，则可能需要向键添加前缀来区分它们。例如，在我们的解决方案中，我们有两种对象：

  • 我们将URLSet定义为 Redis 集合，它包含URL，URL又包含给定检索词。每个URLSet的键的起始是"URLSet:"，所以要获取包含单词the的 URL，我们使用键"URLSet:the"来访问该集合。
  • 我们将TermCounter定义为 Redis 哈希表，将出现在页面上的每个检索词映射到它的出现次数。TermCounter每个键的开头都以"TermCounter:"开头，以我们正在查找的页面的 URL 结尾。

在我的实现中，每个术语都有一个URLSet，每个索引页面都有一个TermCounter。我提供两个辅助方法，urlSetKey和termCounterKey来组装这些键。

14.6 更多建议（如果你需要的话）

到了这里，你拥有了完成练习所需的所有信息，所以如果准备好了就可以开始了。但是我有几个建议，你可能想先阅读它：

  • 对于这个练习，我提供的指导比以前的练习少。你必须做出一些设计决策；特别是，你将必须弄清楚如何将问题分解成，你可以一次性测试的部分，然后将这些部分组合成一个完整的解决方案。如果你尝试一次写出整个项目，而不测试较小的部分，调试可能需要很长时间。
  • 使用持久性数据的挑战之一是它是持久的。存储在数据库中的结构可能会在每次运行程序时发生更改。如果你弄乱了数据库，你将不得不修复它或重新开始，然后才能继续。为了帮助你控制住自己，我提供的方法叫deleteURLSets，deleteTermCounters和deleteAllKeys，你可以用它来清理数据库，并重新开始。你也可以使用printIndex来打印索引的内容。
  • 每次调用 Jedis 的方法时，你的客户端会向服务器发送一条消息，然后服务器执行你请求的操作并发回消息。如果执行许多小操作，可能需要很长时间。你可以通过将一系列操作分组为一个Transaction，来提高性能。

例如，这是一个简单的deleteAllKeys版本：

代码语言：javascript复制
    public void deleteAllKeys() {
        Set<String> keys = jedis.keys("*");
        for (String key: keys) {
            jedis.del(key);
        }
    }

每次调用del时，都需要从客户端到服务器的双向通信。如果索引包含多个页面，则该方法需要很长时间来执行。我们可以使用Transaction对象来加速：

代码语言：javascript复制
    public void deleteAllKeys() {
        Set<String> keys = jedis.keys("*");
        Transaction t = jedis.multi();
        for (String key: keys) {
            t.del(key);
        }
        t.exec();
    }

jedis.multi返回一个Transaction对象，它提供Jedis对象的所有方法。但是当你调用Transaction的方法时，它不会立即执行该操作，并且不与服务器通信。在你调用exec之前，它会保存一批操作。然后它将所有保存的操作同时发送到服务器，这通常要快得多。

14.7 几个设计提示

现在你真的拥有了你需要的所有信息；你应该开始完成练习。但是如果你卡住了，或者如果你真的不知道如何开始，你可以再来一些提示。

在运行测试代码之前，不要阅读以下内容，尝试一些基本的 Redis 命令，并在JedisIndex.java中编写几个方法。

好的，如果你真的卡住了，这里有一些你可能想要处理的方法：

代码语言：javascript复制
    /**
     * 向检索词相关的集合中添加 URL
     */
    public void add(String term, TermCounter tc) {}

    /**
     * 查找检索词并返回 URL 集合
     */
    public Set<String> getURLs(String term) {}

    /**
     * 返回检索词出现在给定 URL 中的次数
     */
    public Integer getCount(String url, String term) {}

    /**
     * 将 TermCounter 的内容存入 Redis
     */
    public List<Object> pushTermCounterToRedis(TermCounter tc) {}

这些是我在解决方案中使用的方法，但它们绝对不是将项目分解的唯一方法。所以如果他们有帮助，请接受这些建议，但是如果没有，请忽略它们。

对于每种方法，请考虑首先编写测试。当你弄清楚如何测试一个方法时，你经常会了解如何编写它。

祝你好运！

云数据库Redis 搜索引擎 数据库 sql java

0 人点赞