コネヒト開発者ブログ

コネヒト開発者ブログ

「ベクトル検索 vs 全文検索」〜Amazon Bedrockの埋め込みモデルを用いたプロトタイピング〜

※ この記事は、AWS (Amazon Web Services) の技術支援を受けて執筆しています。

はじめに

この記事はコネヒトアドベントカレンダー 8日目の記事です。

コネヒト Advent Calendar 2023って?
コネヒトのエンジニアやデザイナーやPdMがお送りするアドベント カレンダーです。
コネヒトは「家族像」というテーマを取りまく様々な課題の解決を 目指す会社で、
ママの一歩を支えるアプリ「ママリ」などを 運営しています。

adventar.org


こんにちは!コネヒトの機械学習エンジニア y.ikenoueです。
突然ですがみなさん、Amazon Bedrockをご存知でしょうか。

aws.amazon.com

Amazon Bedrock(以下、Bedrock)は、テキスト生成AIをはじめとする基盤モデル (Foundation Model)*1を提供するAWSのサービスです。単に基盤モデルを呼び出して出力結果を得るだけにとどまらず、ファインチューニングやナレッジベースの構築によるRAG(検索拡張生成, Retrieval Augmented Generation)*2の実現など、基盤モデルに関する様々な操作を統一的なAPIから利用することができます。Bedrockで使用できる基盤モデルには、Amazon自身が開発提供するTitanの他、Anthropicのテキスト生成AIであるClaude、Stability AIの画像生成AIであるStable Diffusionなど、多様な用途をカバーしたモデルが含まれます。


さらに、Bedrockが提供する基盤モデルの中には埋め込みモデル*3がラインナップされています。埋め込みモデルは、画像や自然言語といったデータを特定の次元のベクトルに変換するためのモデルです。埋め込みモデルによって生み出されたベクトルは元のデータの特徴を反映したものとなり、「機械学習モデルに入力する特徴量として用いる」「ベクトル同士の類似性を計算することで検索やレコメンデーション用途に使う」といった活用が考えられます。

そこで本日は、Bedrockの埋め込みモデルを用いたテキストのベクトル化を実践します。さらに、埋め込みモデルによって生成されたベクトルの活用例として「ベクトル検索」*4システムのプロトタイピングを行います。具体的には、Bedrock埋め込みモデルによって生成されたベクトルデータによるベクトル検索の実行結果と従来の全文検索*5の実行結果を比較することで、埋め込みモデルの性能やベクトル検索の特徴に関する理解を深めることを目的とします。

※ 「手っ取り早くベクトル検索と全文検索の比較結果を見たい!」という方は、こちらからお読みください!

※ 当ブログでは、過去にも埋め込みモデルや検索システムに関する記事を公開しています。興味のある方は、下記のリンクからご覧ください。

tech.connehito.com

tech.connehito.com

tech.connehito.com

プロトタイピングの動機

まずは、今回のプロトタイピングを行うに至った動機についてご説明します。

弊社コネヒトでは、母親向けのQ&Aを主なコンテンツとするママリというコミュニティサービスを運営しています。
ママリには毎月十万件以上の質問が新たに投稿されており、これらの大量の質問データの中からユーザーが求めるものを見つけ出すための検索システムは、AWSのOpenSearch Serviceを用いて自社で構築しています。*6現在の検索システムでは、単語の出現頻度に基づく検索アルゴリズムである全文検索をベースとした手法を採用しているのですが、ここにクエリと文書の意味的な類似性に基づく検索を可能とするベクトル検索技術を取り入れることで、ユーザーの検索体験の改善につなげたいという狙いがあります。

またママリでは、質問のレコメンデーション*7や検閲を行う機械学習モデル*8を運用しています。埋め込みモデルによって獲得したベクトルをこれらのモデルの特徴量として活用することで、モデルの精度向上が期待できるのではないかという仮説をもっています。

このように、ママリにおいて埋め込みモデルの活用範囲は非常に広いと考えています。
さらに、弊社ではインフラにAWSを採用しているため、AWS上の他のサービスとの連携を考慮するとBedrockは有力な選択肢となります。

以上のような背景から、まずはBedrockの埋め込みモデルの性能や使い勝手を確認するための検証第一弾として、今回のプロトタイピングを実施することになりました。

プロトタイピングの概要


続いて、今回のプロトタイピングの概要についてご説明します。
繰り返しになりますが、この記事ではベクトル検索と全文検索を行った際に、両者の検索結果にどのような違いが生じるのかを比較することで、両者の検索手法の強み・弱みを可能な限り明らかにしていきます。
この際、ベクトル検索を実行するために必要なベクトルデータは、Bedrockの埋め込みモデルによって生成します。ベクトル検索の実行結果の妥当性を通して、埋め込みモデルの性能に対する理解も同時に深めていきます。

埋め込み及び検索の対象となるデータにはママリの実データを使用します。具体的には、2023年10月に投稿された十万件以上の質問文を対象とします。

以降は、プロトタイピングの手順を以下3ステップに分け、順番にご説明します。

  • ステップ① Bedrockの埋め込みモデルによるベクトルの生成
    • Bedrockの埋め込みモデルを用いて、ママリの質問データ(2023年10月文)をベクトル化します。
  • ステップ② OpenSearch Serviceによる検索システムの構築
    • ママリの質問文及びステップ①で生成したベクトルデータをAWSのOpenSearch Serviceのマネージド型ドメインに格納することで検索システムを構築します。
  • ステップ③ 「全文検索」と「ベクトル検索」の実行と検索結果の比較
    • ステップ②で構築した検索システムを用いて、ママリの質問文に対する「全文検索」と「ベクトル検索」を実行します。そして、両者の検索結果にどのような違いが生じるのかを定性的に比較します。

ステップ① Bedrockの埋め込みモデルによるベクトルの生成


最初のステップとして、Bedrockの埋め込みモデルを用いたテキストのベクトル化を行います。
まずは、埋め込みモデルの選定基準についてご説明します。 2023年12月8日現在、Bedrockにはテキストデータを対象とした埋め込みモデルとして下記3種類が提供されています。

モデル名 開発元 対応言語 コンテキスト長 埋め込み次元 東京リージョンにおける利用可否
(2023/12/8時点)
Titan Embeddings G1 - Text Amazon 多言語
(日本語含む)
8000 1536
Embed English Cohere 英語 512 1024
Embed Multilingual Cohere 多言語
(日本語含む)
512 1024

※ マルチモーダルモデルであるTitan Multimodal Embeddings G1は比較の対象外としています。

3つのモデルのうち、「Embed English」(Cohere)は対応言語が英語のみとなっていることから、日本語データを対象とする今回のプロトタイピングでは選択肢から外れました。

残った2つのモデルに関しては、主にコンテキスト長の差を重視し「Titan Embeddings G1 - Text」(Amazon)を選択しました。コンテキスト長は、埋め込みモデルが入力として考慮することのできる最大のトークン数を指します。「Embed Multilingual」(Cohere)のコンテキスト長は512までとなっていますが、ママリの質問データにはこれを超えるものが存在することから、コンテキスト長が最大8000トークンまでと余裕のある「Titan Embeddings G1 - Text」 (Amazon)が適しているという判断になります。

次に、BedrockのAPIを呼び出し、テキストをベクトル表現に変換するためのコードをご紹介します。
プログラミング言語には、Pythonを使用しています。

import json
import boto3

# Bedrock runtimeに接続するためのclientを生成
bedrock_runtime_client = boto3.client('bedrock-runtime', region_name="ap-northeast-1")

def bedrock_embedding(input_str):
    bedrock_body = {
        "inputText": input_str
    }
    body_bytes = json.dumps(bedrock_body).encode('utf-8')
    # 埋め込みモデルの呼び出し
    response = bedrock_runtime_client.invoke_model(
        accept="*/*",
        body=body_bytes,
        contentType="application/json",
        modelId="amazon.titan-embed-text-v1",
    )

    return json.loads(response.get("body").read()).get("embedding")

コードの要点を取り上げて解説します。

はじめに、Bedrockのモデルを呼び出す際は、bedrock-runtimeに接続したclientが持つinvoke_model()というメソッドを使用します。このメソッドには、モデルの入力とするテキストをキー"inputText"に対応する値として設定したJSON形式のデータを渡す必要があります。
使用するモデルの種類は、引数modelIdに与えます。先述の通り、今回のプロトタイプでは「Titan Embeddings G1 - Text」(Amazon)を使用するため、このモデルのIDに該当する"amazon.titan-embed-text-v1"を指定しています。
なお、モデル名とIDの正式な対応関係は下記のコードで出力されるモデル一覧から知ることができます。

bedrock = boto3.client(service_name='bedrock')
print(bedrock.list_foundation_models())

invoke_model()メソッドのレスポンスには"embedding"という要素が含まれており、これがテキストの埋め込み結果に該当するベクトルデータです。ちなみに、このレスポンスには"embedding"の他に、元のテキストのトークン長が格納された"inputTextTokenCount"が含まれているため、この値を参照することで埋め込みモデルの利用にかかったコストを個別のデータ単位で正確に把握することができます。

ステップ② OpenSearch Serviceによる検索システムの構築

続いて、AWSのOpenSearch Serviceを用いた検索システムの構築についてご説明します。 このステップでは、特にベクトル検索を実行するためのインデックスの構築方法に焦点を当てています。

なお、このステップのプログラムを実行するには、事前にOpenSearch Serviceのドメインを構築しておく必要がありますが、分量が非常に長くなるためこの記事では説明の対象外とします。ドメインの構築方法については、代わりに下記の公式ドキュメントを御覧ください。

以下は、全文検索とベクトル検索の両者に対応したインデックスを作成するためのPythonコードです。実装にはopensearch-pyというライブラリを用いています。

# 必要なライブラリのインポート
from opensearchpy import OpenSearch, RequestsHttpConnection
from opensearchpy.helpers import bulk
from requests_aws4auth import AWS4Auth

region = 'ap-northeast-1'
service = 'es'

credentials = boto3.Session().get_credentials()
awsauth = AWS4Auth(credentials.access_key, credentials.secret_key, region, service, session_token=credentials.token)

host = 'XXX.ap-northeast-1.es.amazonaws.com' # XXXには、事前に構築したドメインのエンドポイントを記入します
port = 443

# OpenSearch Serviceに接続するためのクライアントを生成
client = OpenSearch(
    hosts = [{'host': host, 'port': port}],
    http_auth = awsauth,
    use_ssl = True,
    verify_certs = True,
    connection_class = RequestsHttpConnection,
    timeout=1000
)

# ドキュメントとベクトルが格納された辞書データを受け取り、インデックスに登録する関数
def add_documents_to_index(client, index_name, document_dict):
    
    actions = []
    for i, document_id in enumerate(document_dict):
        
        actions.append({
            "_op_type": "index",
            "_index": index_name,
            "_id": document_id,
            "_source": {
                "document": document_dict[document_id]["document"], # 元のテキストデータを追加
                "embedding": document_dict[document_id]["embedding"] # ベクトルデータを追加
            }
        })
        
        if i % 100 == 0:
            # データをひとまとめにして一括で登録
            bulk(client, actions)
            actions = []
    else:
        bulk(client, actions)

上記のコードでは、”document”フィールドにオリジナルのテキストデータ、”embedding”フィールドにテキストの埋め込み表現を追加しており、それぞれのフィールドを全文検索、ベクトル検索の実行時に使用します。

また、データの登録時には関数bulkを用いて複数件のデータを一度にまとめて登録することで、処理にかかる時間を削減しています。一方で、あまりに多くのデータを一度に転送しようとするとbulkの実行時にエラーが発生することがあるため、ここではデータを100件ごとに区切って処理を実行しています。(一度に登録できるデータ件数の上限は一つのデータあたりの容量などに依存します。)

ステップ③ 「全文検索」と「ベクトル検索」の実行と検索結果の比較

最後に、構築したシステムを用いて検索を実行します。
以下は、全文検索、ベクトル検索を実行するためのPythonコードです。

# OpenSearch Serverlessに構築したVector Storeに対してクエリを実行する関数
def search(query_str, search_type, size=5):
    
    if search_type == "vector":
        # 検索クエリを埋め込み表現に変換
        vec, _ = bedrock_embedding(query_str, bedrock_runtime_client)
        # ベクトル検索用のDSLを定義
        query = {
          "size": size,
          "query": {
            "knn": {
              "embedding": {
                "vector": vec,
                "k": 10
              }
            }
          }
        }
    else:
        # 全文検索用のDSLを定義
        query = {
          "size": size,
          "query": {
            "match": {
                "document": query_str
            }
          }
        } 
    # 検索を実行
    results = client.search(index=index_name, body=query)
    return results

関数searchでは、引数search_typeに”vector”を指定した場合はベクトル検索、それ以外の場合は全文検索用のDSL (ドメイン固有言語: Domain Specific Language) を用いるように条件分岐を行っています。

またベクトル検索を行うには、事前に検索クエリの埋め込み表現を獲得する必要があります。そこで、ステップ①で掲載した関数bedrock_embeddingを使ってテキストデータをベクトルに変換する処理を実行しています。

それでは、いよいよ準備が整ったので、全文検索とベクトル検索の検索結果を比較していきましょう。
今回の比較検証では、以下5つのケースを取り上げてそれぞれの検索結果に対する考察を行います。

  • ケース1. クエリが一つの単語で構成される場合
  • ケース2. クエリが複数の単語で構成される場合
  • ケース3. クエリに固有名詞を含む場合
  • ケース4. クエリに誤字を含む場合
  • ケース5. クエリに文章を使用した場合

ケース1. クエリが一つの単語で構成される場合

検索クエリ: 保育園

まずは、検索クエリが一つの単語で構成される場合の例を見ていきます。以下は、保育園を検索クエリとして用いた場合の検索結果です。

検索ランキング 全文検索 ベクトル検索
1 【愛知県瀬戸市の保育園について】瀬戸市の保育園について教えてください (...以下略...) 保育園ってどのくらい前から探すものですか??
2 親の都合で保育園を8月いっぱいで退園させてしまいました (...以下略...) 八幡西区でベビーカー置き場のある保育園はありますか?
3 千葉県香取市の保育園についてまんまる保育園、香西保育園、たまつくり保育園どんな感じか (...以下略...) 滋賀県愛荘町にお住まいの方!保育園の応募なんですが、この辺り出身ではないので (...以下略...)
4 【通勤途中の保育園と家の近くの保育園、どちらに預けるべきかについて】モヤモヤしてます (...以下略...) 山形市内から天童市内周辺まででおすすめの保育園はありますか?0歳児クラスがあるところ (...以下略...)
5 保育園についてです。今生後7ヶ月の娘が保育園に通っているのですが、3回食にならないと保育 (...以下略...) 通園て何が必要ですか?保育園です。

※ 質問文の全体を掲載すると文章が長くなりすぎてしまう場合があるため、質問文の意味や検索クエリとの関連性が正しく伝わる程度に一部の情報を省略して掲載しています。

両者ともに上位五件の検索結果には保育園という単語が含まれており、正常に検索が行われていると言えそうです。保育園という単語だけではユーザーがどういう情報を求めているのかを判断することが難しいため、検索結果の良し悪しについては、今回のケースではこれ以上の評価することができません。

そのうえで両者の検索結果の違いに着目すると、以下のような傾向が見受けられます。

  • 全文検索では、質問内に保育園というワードが複数個含まれている質問が上位に並んでいる
  • ベクトル検索では、保育園というワードを含みつつも、質問の全体の文章量が少ない質問が上位に並んでいる

全文検索では、クエリと文書の一致度を計算する際に、クエリと文書の単語の出現頻度を考慮しているため、クエリと文書の単語の出現頻度が高いほど検索結果の上位に位置づけられる傾向があるためこういった結果が生まれたと推察できます。

一方、ベクトル検索では、単語の出現頻度ではなくクエリと文書の意味的な類似性に基づき検索スコアが計算されます。今回のケースでは、クエリが保育園という一単語のみで構成されているため、文章が長くなるほど(保育園以外の情報が加わるほど)、保育園からは意味が離れていく作用が働いていると考えられます。

ケース2. クエリが複数の単語で構成される場合

検索クエリ: 保育園 お弁当

続いて、クエリ内に複数の単語が含まれる場合を比較しましょう。以下は、ケース1の保育園に一単語を追加した保育園 お弁当を検索クエリとして用いた場合の検索結果です。

検索ランキング 全文検索 ベクトル検索
1 年少さんのお弁当の量ってどんなかんじですか?保育園で初めてお弁当あり (...以下略...) 保育園の園外保育で給食の方、お弁当はどうされていますか?
2 19日に保育園お弁当の日があります。お弁当のおかずについてです。 (...以下略...) 幼稚園 お弁当オススメおかずありますか?
3 保育園の行事でお弁当を持たせる時 普段給食なのでお弁当は作らないので (...以下略...) 保育園の遠足のお弁当。ほんっと下手くそで泣きそうです (...以下略...)
4 年長 遠足のお弁当 今度、保育園の遠足でお弁当持っていきます (...以下略...) 幼稚園お弁当は何入れてますか?
5 保育園に入ってから初めての遠足が明後日あります!初めてのお弁当です (...以下略...) 保育園幼稚園から帰宅後、家でもおやつやジュースを食べますか?

基本的な検索結果の傾向はケース1と似通っているものの、ベクトル検索の結果に興味深い点があります。それは、検索ランキングの二位と四位に保育園ではなく幼稚園を含む文書が出現したことです。これは、保育園幼稚園が意味的に類似しているため、ベクトル検索では保育園幼稚園を同じような意味を持つ単語として扱っているものと考えられます。

また、検索ランキングの五位にお弁当がなくおやつジュースが含まれる質問があることも同様の理由であると言えそうです。

ケース3. クエリに固有名詞を含む場合

検索クエリ: 多摩総合医療センター

ここからは、検索クエリが特殊な特徴をもつ場合の比較検証を行います。まずは、検索クエリに固有名詞を含む場合です。固有名詞は一般名詞と比べて文書内の出現頻度が低い傾向にあり、その言葉の意味を埋め込みモデルが学習することは困難です。そうなると、ベクトル検索では固有名詞を含む文書を正しく検索することが難しいのではないかと考えられますが、どういう結果が生まれるか見ていきましょう。

以下は、検索クエリに多摩総合医療センターという特定の病院名を与えた場合の例です。

検索ランキング 全文検索 ベクトル検索
1 榊原記念病院、多摩総合医療センター、どちらで分娩するか悩んでいます。(...以下略...) 広島県西条の八本松にある高橋ホームクリニックご存知の方に質問です。(...以下略...)
2 - 吹田徳洲会病院でご出産された方いらっしゃいませんか? (...以下略...)
3 - 神奈川県海老名市付近の婦人科検診と不妊治療が行える病院を探しています (...以下略...)
4 - 仙台市太白区付近でセミオープンおすすめの病院を教えてください。(...以下略...)
5 - 熊本県合志市でおすすめの婦人科教えてください (...以下略...)

全文検索では、多摩総合医療センターについて記述されたデータがヒットしています。(多摩総合医療センターを含む質問は一件しか存在しなかったため、検索結果はこれのみ)

一方で、ベクトル検索を用いた場合の検索結果には多摩総合医療センターを含む文書は上位五件以内には現れませんでした。検索結果として並んだ質問を詳細に見ていくと、地域名と病院を含むという共通点が見受けられるため、多摩総合医療センターと意味的に類似する質問がヒットしているとは言えそうですが、直接的に多摩総合医療センターという病院名を含むデータを上位に位置づけることはできませんでした。

一つの例を確認しただけでは結論づけるのは尚早ですが、特定の施設や商品等、固有名詞による検索を必要とするケースでは、ベクトル検索より全文検索のほうが求める検索結果を得られやすい傾向にあるのかもしれません。

ケース4. クエリに誤字を含む場合

検索クエリ: 子供 正確

続いて、クエリに誤字を含む場合の検索結果を比較します。 ここでは、『子供 性格と打つつもりが、子供 正確と打ち間違えてしまった』ケースを想定して検索結果を比較します。

検索ランキング 全文検索 ベクトル検索
1 すぐに測れる体温計でおすすめありませんか?
(...中略...)
非接触型体温計もあるのですが、全く正確に測れません?
小学一年生になる息子がいます。小規模の小学校でクラスに7人しか男の子がいません。息子はおとなしい (...以下略...)
2 小学校一年生の子供にGPSを持たせようと思いますが、正確に場所とか分かるGPS (...以下略...) 子供って、なんて純粋で優しいんだろう…私は子供を (...以下略...)
3 【犬猫のGPSトラッカーについて】犬猫用のGPS 常に正確な位置を携帯アプリで表示 (...以下略...) 幼稚園の先生から見て満3歳児クラスの子でこの子はまだお母さんといた方が良いのではと思う子って (...以下略...)
4 おでことかにあててピッと一瞬で体温が測れる体温計って正確に測れているんでしょうか? (...以下略...) 息子は口が悪くなったり怒りっぽい一方で、優しく穏やかな時もあります。 (...以下略...)
5 【おすすめの体温計について】医療関係者の方 なるべく早くて正確なおすすめの体温計 (...以下略...) 男の子は優しいよって言われたけど (...以下略...)

はじめに全文検索の結果を見てみると、正確を含む質問が並んでいることからクエリとした投げた子供 正確にそのまま素直に一致するデータを返していることがわかります。

一方、興味深いことに、ベクトル検索の結果には子どもの性格に関する質問が上位に並んでいます。
更に、これらの質問は性格という直接的に一致するキーワードを含んでいるわけではなくおとなしい怒りっぽい等、性格と共起性が高いワードを含む文書たちとなっています。ここからは仮説ですが、埋め込みモデルの学習データにも子供 性格子供 正確と間違えて使用していた文書が多く含まれていたことが、こういった結果を引き起こしたと可能性があります。その場合、子供 正確という言葉と「子供がおとなしい」「子供が怒りっぽい」といった子供の性格を表す表現が意味的に類似性が高いものとして学習されていると考えても不思議ではありません。

このように、ベクトル検索を用いることでたとえクエリに誤字が含まれていたとしても、クエリ内の他のキーワードとの文脈が考慮されることによって、ユーザーが本来求めている情報を検索結果として返すことができる可能性が示唆されました。

ケース5. クエリに文章を使用した場合

検索クエリ: 先日、4歳の子供に「サンタさんはお父さんなの?」と聞かれました。本当のことを言うべきでしょうか?

最後に、キーワードではなく文章をクエリとして使用した場合の検索結果を比較します。ベクトル検索は、文章の文脈を含む意味的な類似性を計算することができるという性質から、文章をクエリとして使用した場合にこそ全文検索にはない強みを発揮するのではないかと考えています。
また、テキスト生成AIの応用技術として注目を浴びているRAG (検索拡張生成, Retrieval Augmented Generation)では、ユーザーが入力した文章をそのまま検索クエリとして使用することが多いため、このケースはRAGの実践を見据えた検証としても重要であると言えるでしょう。

以下は、先日、4歳の子供に「サンタさんはお父さんなの?」と聞かれました。本当のことを言うべきでしょうか?という短い文章を検索クエリとして用いた場合の検索結果です。

検索ランキング 全文検索 ベクトル検索
1 小1男子なんですが、まだサンタさん信じてるんですけどその方が珍しいんですかね?友達にサンタはお父さんとお母さんやでって言われたみたいで ほんまなん?って聞かれました...真実を教える年頃ですか? (...以下略...) 5歳年長の娘が「サンタってほんとはお父さんとお母さんじゃない?」と言い出しました、、
(...中略...)
あんまり嘘つくのもよくないかな下の子もいるしあと3〜4年は信じてもらってたいです
2 あと2ヶ月でサンタさん来ますね!?うちはもう欲しいものが決まってて、サンタさんにこれ貰おうねーとよく話すのですが、(...以下略...) 小1男子なんですが、まだサンタさん信じてるんですけどその方が珍しいんですかね?友達にサンタはお父さんとお母さんやでって言われたみたいで ほんまなん?って聞かれました...真実を教える年頃ですか?|5歳年長の娘が「サンタってほんとはお父さんとお母さんじゃない?」と言い出しました、、?
(...中略...)
あんまり嘘つくのもよくないかな 下の子もいるしあと3〜4年は信じてもらってたいです
3 孫に対して(3歳)言うこと聞かないと機嫌悪くなり
(...中略...)
旦那のお父さんは。子供って中々ご飯食べてくれない時どうしてますか?
【クリスマスプレゼントについて】ちょっと時期早めの話題ですが…6歳前後のお子さんをお持ちの方に質問です。
(...中略...)
子どもの夢は壊したくないからサンタさんいないんだよっていいたくはないし ...
4 〈サンタさんについて〉少し早いですが..サンタさんからのプレゼント?を何歳くらいからやりましたか?直接サンタさんから渡される感じではなく子供達が寝た後、枕元に置くプレゼント?です 【旦那がサンタについて嘘をついたことについて】旦那と息子と3人でたわいもない会話をしながら食卓を囲んでいた時に今年のクリスマスプレゼント何が欲しいーの?サンタさんにお願いしようね!っと私が言うと、旦那が笑いながら息子に対してサンタなんか居ないからと言いました。 (...以下略...)
5 5歳年長の娘が「サンタってほんとはお父さんとお母さんじゃない?」と言い出しました、、
(...中略...)
あんまり嘘?つくのもよくないかな 下の子もいるしあと3〜4年は信じてもらってたいです (...以下略...)
子供がもう、サンタさんの話してる笑 サンタさんくる?!って何回も聞いてくる (...以下略...)

検索クエリと同じく「サンタさんは実在しないことを子供に正直に伝えるべきか」をテーマとした質問に該当するものとしては、全文検索は1位と5位の2件、ベクトル検索は1位〜4位の4件がランクインしています。この後、6位以降の結果も見渡したところ「サンタさんは実在しないことを子供に正直に伝えるべきか」をテーマとした質問は、ベクトル検索の実行結果により多いという印象を受けました。

やはり、クエリが長くなるほど (クエリに込められる意味の情報量が増すほど) ベクトル検索はその強みを発揮する傾向があると言えそうです。

「ベクトル検索」と「全文検索」 比較結果のまとめ

ここまでの検証で得られた結果を改めて整理します。

  • キーワードベースのクエリを用いて検索を実行した場合、全文検索ではそのクエリを文書内に多く含むものが上位に並ぶ傾向があり、ベクトル検索では文書の長さが短いものが上位に並ぶ傾向が見受けられた。
  • 誤字を含むクエリを用いて検索を実行した場合、ベクトル検索は誤字ではなく本来検索者が入力しようとしていた情報に関連性の高い文書を検索結果として返すことができる可能性が示唆された。
  • 固有名詞を含むクエリを用いて検索を実行した場合、ベクトル検索ではその固有名詞を含む文書を上位に位置づけることが困難な場合があることが示唆された。
  • 文章をクエリとして用いて検索を実行した場合、ベクトル検索では文章の文脈を考慮することで全文検索以上にユーザーが求める検索結果を返すことができるという可能性が示唆された。

今回の比較検証ではケースごとに1つのクエリの結果しかご紹介していないため、ベクトル検索と全文検索の検索結果の傾向を一概に判断することはできません。そのうえで、クエリに誤字を含む場合やクエリが文章である場合など、ベクトル検索が全文検索より優れた結果を返す場面が存在することが示唆されたと言えるでしょう。

おわりに

以上、この記事ではAmazon Bedrockの埋め込みモデルを用いたベクトル検索システムのプロトタイピング、及びベクトル検索と全文検索の検索結果の比較検証を行ってきました。

近年は「ハイブリッド検索」という検索手法に注目が集まっており、全文検索とベクトル検索の検索スコアをRRF*9などのアルゴリズムによって統合することで、両者のメリットを活かした検索結果を得ることのできる可能性があります。そこで、今後は「ハイブリッド検索」システムのプロトタイピングにも取り組んでいく所存です。

また、今回のプロトタイピング結果から、Bedrockの埋め込みモデルによって獲得されたテキストのベクトル表現の有用性が確認できたため、今後は検索以外の用途にも活用を広げていきたいと考えています。コネヒト開発者ブログでは、今後も積極的に技術検証の結果を発信していきますので、ぜひ引き続きご注目ください!

それでは、今回の記事が皆さんのお役に立てれば幸いです。お読みいただきありがとうございました!

コネヒトCTO永井からのコメント

生成AI分野の進歩は、目覚ましいものがあると日々感じています。コネヒトでは、これまでAWSのサービスを基盤として、事業を着実に成長させてきました。AWSの堅牢で柔軟なインフラは、私たちのプロダクト開発において不可欠なものになっています。

そして、今回のBedrockを用いた検証結果には、この技術を用いることがユーザーの検索体験の改善につながるという手応えがありました。さらに将来的には、今回検証したベクトル検索技術とテキスト生成AIを組み合わせて使うことで、これまでにない新たなユーザー体験を提供することができる可能性も感じています。今後もコネヒトではスピード感をもってプロダクトに実装し実験を繰り返しながら、より良いユーザー体験を創造していきたいと考えています。

*1:「基盤モデル」... 広範な用途に使用することのできる大規模なAIモデルを指します。

*2:「RAG(検索拡張生成, Retrieval Augmented Generation)」... 検索技術を用いて生成AIの出力結果を改善する技術です。

*3:「埋め込みモデル」... データをベクトルに変換するためのモデルを指します。

*4:「ベクトル検索」... ベクトル同士の距離(類似性)を計算することで検索を実現する手法です

*5:「全文検索」... テキストデータの中から特定のキーワードを含む文書を検索する手法です。

*6:https://tech.connehito.com/entry/2022/09/16/165655

*7:https://speakerdeck.com/takapy/komiyuniteisabisuniokerurekomendesiyonfalsebian-qian-tomlpaipurainnituite

*8:https://tech.connehito.com/entry/2022/03/24/173719

*9:「RRF (Reciprocal Rank Fusion)」 ... 複数の検索スコアを統合するアルゴリズムの一つです。

ドメイン駆動設計入門の輪読会をやってました!

「コネヒト Advent Calendar 2023」の7日目のブログです!

コネヒト Advent Calendar 2023って?
コネヒトのエンジニアやデザイナーやPdMがお送りするアドベント カレンダーです。
コネヒトは「家族像」というテーマを取りまく様々な課題の解決を 目指す会社で、
ママの一歩を支えるアプリ「ママリ」などを 運営しています。

adventar.org


こんにちは。サーバーサイドエンジニアをしている高橋です。

以前からDDDに興味がありましたが、なんとなくしか理解しておらずそんな時に 「ドメイン駆動設計入門」の本をお勧めされました。 DDDの考え方は正解がないものなので、メンバーとワイワイしながら読んでみたいと思いこの輪読会を開催しました。

社内でメンバー募集をした時、サーバーサイドエンジニアに限らずインフラ、Androidエンジニア、機械学習エンジニアなど様々な領域の方が手を挙げてくれました。

既に知見がある方もいれば、DDDに興味があるけどわからないという方もいました。


輪読会の流れ

全15章あり、輪読会を開催したのは11月上旬からで、できれば年内に終わらせたいと思い、2章ずつの合計7回で終わるように設計しました。

2章ずつ読んできてもらい、以下の内容を事前にmiroの付箋に記入してもらいます。

輪読会では以下のように進めました。

  1. 順番に付箋を読み上げていく
  2. 深掘りしたい付箋に一人2票投票する
  3. 票が多かった付箋について深掘りして理解を高める

1時間の輪読会なので、なるべく議論できる時間を作りたいと思い、付箋は事前に書いてきてもらうようにしました。 深掘りタイムでは「自分も同じようにどういうことなんだろうと思った」という意見が多くあったので、DDDに知見のあるメンバーに質問して、疑問点を解消していきました。

具体的にどのような深掘りをしていたか一部紹介します。

本の例にあったものは、名前の登録時のバリデーションについて以下のように記載されていました。

名前にはn文字以上の入力が必須 ⇒ エンティティで実装する

同じ名前は登録できない ⇒ ドメインサービスで実装する

ほみ「名前が何文字以上かはエンティティに記載するのに、重複しているかどうかはエンティティに持たせると不自然になるのはなぜか説明できない」

高谷さん 「本だと「コードで書くと不自然になるから」という説明だったが、あんまりしっくりこなかった」

柳村さん 「インスタンス単体で解決可能かどうかじゃないですかね。たとえば高谷さんに高谷さんって他に存在していますかって聞いても分からないですよね。国の台帳かなんか調べないと分からない。」

aboさん 「値オブジェクトの値はチェックできるが、エンティティの存在チェックは自分でできないという理解をした。」

この会話だと柳村さんの説明でメンバーがなるほどなるほどと納得している様子でした。

DDDは誰かが答えを持っている訳ではないので、メンバー同士の対話を通してより理解を深められたと思いました。

メンバーの声

現状半分まで輪読会を終えて、メンバーに以下のようなアンケートを取ってみました。

この輪読会にどのようなことを期待して参加しましたか。

  • ドメイン駆動設計完全に理解した状態になる。
  • 開発をする上でそこまで意識することは正直ないが、概念として押さえておきたいと思ったから。
  • ドメイン駆動設計の大まかな理解と、可能であれば実務に取り入れていきたい。
  • DDDについての理解を深める。
  • モデリングとの実装のつながりを理解する。
  • 他の方と設計に関する知見交流ができると思ったため。

前半戦を終え、現時点で感じていること(難易度等)教えてください。

  • 実装パターンの話は理解が進んでいる一方で、肝心のドメイン周りは大丈夫?という感じ。でもこの本のテーマ的に、実装パターンから理解してドメイン駆動設計の本丸に進むのを怖くなくするみたいな感じっぽいので、それでいうといい感じ。
  • 業務上直接ドメインを意識することは少ないので、十分に理解した状態には至っていないが、参加メンバーに具体例を出してもらうことで納得できる部分はあり、ほんの少しずつだが理解が進んできている気がする。
  • 設計面はDDDの1側面ではあるので、モデリングとセットで学びたい。
  • 現行のコードに落とし込んでいくには慎重になったほうがよさそう。
  • ドメイン駆動設計を実現するための実装パターンが紹介されてはいるもののOOPのデザインパターンのお話しなど他の知識を知らないとよくわからないみたいな部分も少しあるので知見ない方は理解しずらしかもなと思ってました。

後半の輪読会でもっとこうした方がいいとかあれば教えてください。

  • 議事録をいい感じにみんなで取りたいわね。
  • メンバーで時間いっぱい議論に使えているので、良い会が進められている気がする。
  • 本から学びつつ、ママリの事業で実践するにはという会話を増やせるとよさそう。
  • そのためには一定の図解が必要で、miroで図解しながら話してもおもろいかもですね。
  • 輪読会自体の時間でも良いですし輪読会が終わった後でも良いですが改めて全体で深掘りして聞いてみたいことなどあればお話しできる時間や話せる場所があれば良いのかなと思った。同期的でなくともnotionに非同期で質問書くとでも全然あり。

感想

DDDはバックエンド領域の考え方と思っておりましたが、あくまでそれは実装方法の話であり、ドメインを意識して作っていくという意味ではどの領域のエンジニアにも必要なことだと改めて感じました。

比較的初心者でも読みやすいとは思いつつも、DDDの考え方に慣れていないと結構つまずく部分はありました。このような輪読会を通して、他の方の意見でより理解が深まったと思います。後半戦は年内に終わる予定ですので、引き続きやっていきたいと思っております。

FlutterについてDroidKaigi2023に登壇してました

この記事はコネヒトアドベントカレンダー 2日目の記事です。

コネヒト Advent Calendar 2023って?
コネヒトのエンジニアやデザイナーやPdMがお送りするアドベント カレンダーです。
コネヒトは「家族像」というテーマを取りまく様々な課題の解決を 目指す会社で、
ママの一歩を支えるアプリ「ママリ」などを 運営しています。

adventar.org


初めまして、コネヒトでAndroidエンジニアとして開発しております中島(id:nacatl)です。 開発経歴で言うと、Android→Flutter→Androidという出戻りエンジニアです。 7月にジョインしてから右往左往してたら、もう世間では師走になっており困惑しております。

今回のブログでは、去る9月14日〜16日にかけて開催されました DroidKaigi2023において「Flutterにおけるアプリ内課金実装 -Android/iOS 完全なる統一-」と題しまして登壇したことについて、遅ればせながら少し補足などお話させていただきます。

2023.droidkaigi.jp

当日の様子などはこちらのブログをご覧ください。

tech.connehito.com tech.connehito.com tech.connehito.com

Flutterにおけるアプリ内課金実装 -Android/iOS 完全なる統一-

nacatl名義にて、Day 2のArcticFoxにて 12:00~12:40 の40分間で登壇いたしました。

動画の方もDroidKaigiのYoutubeチャンネルにて、先日無事公開していただきました。 開催の準備から動画の公開まで色々実行していただきましたこと、運営の方々にはこの場を借りて感謝申し上げます。

speakerdeck.com

www.youtube.com

AndroidネイティブではなくFlutterの話、かつまさかの荒木佑一さんのセッションと同じ時間帯ということで伽藍とするだろうとも予想していたのですが、多くの方々に聞いていただきとても嬉しく思いました。

なぜFlutterの登壇だったのか

今回の登壇内容は、表題の通りFlutterというマルチプラットフォームのフレームワークについての発表でした。 ただ先に言っておきますが、コネヒトでは現状Flutterは利用しておりません。

このことは発表内でも述べていますが、冒頭にも書いた通り中島がコネヒトにジョインしたのは7月であって、実はDroidKaigiへセッションを投稿した時点ではまだ以前の職場であるスタディプラス株式会社に所属していました。 そのため、セッション内容もStudyplusの開発における内容で投稿したことが理由です。 発表内容に関しても退職後にも快く協力していただき、改めましてこの場にて感謝申し上げます。

tech.studyplus.co.jp Studyplusからもセッションについて紹介していただいております

セッションの補足について

セッションの本筋に関しましては、Flutterの課金実装に関して自分の知見を余さず発表できたと自負しています。 ただ、最後にまとめとして話したことについて、一言この場で補足いたします。

アプリ内課金も含めてFlutterによる完全なる統一は目指せる

資料にも小さく書いてありますが、「目指すべきか」どうかは各プロダクトの事情によると認識しています。 これは「目指すことが可能である」ことが重要だと思っており、Flutterによってモバイルアプリプロダクトにおける技術選択の幅が確実に広がっていることが肝要です。 Studyplusもこの恩恵に授かったプロダクトのひとつです。

FlutterはモバイルアプリだけでなくWebアプリの開発にも利用できるフレームワークの一つとして、今後も発展していくだろうと期待しています。

FlutterからJetpackComposeへ

ここまで読んでいただいた方にはおそらく、「コネヒトで使ってないんじゃ、転職して知見リセットして仕事してるの?」と思われた方もいらっしゃるかと思います。

これに関しては半分その通りで半分違うという答えになります。

宣言的UI

確かに現状のコネヒトではFlutterそのものは採用していませんが、宣言的UIを用いて開発した経験は活きていると認識しています。 昨今、モバイルアプリの開発では宣言的UIの採用が進んでおり、Android開発では Google I/O 2019 にてJetpack Compose、iOSでも WWDC 2019 でSwiftUIが発表されて、それぞれ既に数年が経っています。

コネヒトの開発するモバイルアプリ「ママリ」においても、それぞれの導入が進んでおります。

developer.android.com

www.youtube.com

developer.apple.com

developer.apple.com

MaterialDesign

また、FlutterはGoogleの後発UIツールキットという立場からか、MaterialDesign、特にMaterialDesign3(以下M3)の導入もAndroidネイティブと同じかそれ以上に進んでいる印象を持っています。 2023/11/16にリリースされたFlutter 3.16では、M3がデフォルト設定になっています。

Throughout the year we’ve worked on completing support for Material 3, the latest version of the Material Design design system. Flutter’s Material widgets now fully support Material 3 and, in Flutter 3.16, Material 3 is now the default style.

medium.com

M3の知見はAndroidでもそのまま適用できるので、コネヒトでもデザイナーの方々と色々知見を共有し合いながら開発を進められていると感じております。

m3.material.io

おわりに

今回は、DroidKaigi2023にてFlutterについて登壇したこと、そこから派生して、転職を経てFlutterの知見をどうAndroidネイティブに活かしているかについて軽く紹介させていただきました。

これからも、Flutterで培った宣言的UIやMaterialDesignの知見を基に、コネヒトのAndroidエンジニアとしてママリをより良いアプリにしていきたい所存です。

明示的メモリ管理が引き起こす問題とガベージコレクションの解法

こんにちは!バックエンドエンジニアのjunyaUです。

社会人になって2回目の冬が来ましたが、どんなに寒くても暖房だけはつけない派です⛄️

今回は明示的メモリ管理が引き起こす問題と、ガベージコレクションがどうやってこの問題に対処するのかについて書いていこうと思います〜!

はじめに

動機

元々、明示的メモリ管理を強いられるC言語を触っていた経験が少しありました。

メモリリークなどの、明示的メモリ管理による問題にちょくちょく遭遇していたので、 なぜ起こるのかはなんとなく把握しているつもりでしたが、明確に言語化することはできませんでした。

しかし、最近読んだ「ガベージコレクション: 自動的メモリ管理を構成する理論と実装」という本の中で明示的メモリ管理に対する言及がされている部分がありました。 この本を読んだ上でこの問題について考えてみると言語化できそうだなと思ったので、得た知識と自分の見解をまとめてみようと思いこの記事を書くことにしました。

結論

明示的メモリ管理が引き起こす、メモリリーク、二重解放、ダングリングポインタなどの問題は、メモリのライフサイクルに関する視点の違いから生じます。 オブジェクトが生きているかどうかの判断は、グローバルな視点で判断される必要があるのに対して、メモリの解放はローカルスコープで判断することを強いられます。 この視点のギャップが問題を引き起こします。

一方で、ガベージコレクションは明示的メモリ管理とは異なり、グローバルな視点からオブジェクトの生存状態を判断して自動的に解放を行うため、これらの問題を解決します。

次節から、両者の特徴や問題点に触れながら、ガベージコレクションがどのように問題を解決するのかを考えていこうと思います。

そもそもメモリ管理って?

プロセスのメモリ領域

プロセスのメモリ領域の簡略図
メモリ管理を理解するには、まずプロセスのメモリ領域についての基本を知っておく必要があります。

プロセスのメモリ領域は、大きく3つのセグメントに分かれます。

テキストセグメント

テキストセグメントは、プログラムの機械語命令が格納される領域です。

この領域は読み取り専用で、プログラムの実行コードが含まれています。

データセグメント

データセグメントは、プログラムのデータを格納するための領域で、主に三つの領域に分けられます。

  • データ領域 : 初期化されたグローバル変数や静的変数が格納されます。
  • BSS領域 : 初期化されていないグローバル変数や静的変数が格納されます。
  • ヒープ領域 : プログラムの実行時に、動的に確保されるメモリが配置されます。サイズは実行時に動的に変化します。

スタックセグメント

スタックセグメントは、関数のローカル変数や引数などが格納される領域です。

この領域は、LIFOの原則に基づいてデータの格納と開放が行われます。

メモリ管理とは

メモリ管理は、プログラムにおけるヒープ領域のメモリ割り当てと解放を適切に行うプロセスを指します。このプロセスは、メモリリソースを効率的に使用し、プログラムのパフォーマンスと安定性を維持するために不可欠です。

ヒープ領域の役割

ヒープ領域は、プログラム実行時に動的にメモリを確保するために使用されるメモリ領域です。

例えば、事前に要素数のわからない配列やクラスのインスタンスは静的にサイズを決定することができないため、ヒープ領域にメモリが割り当てられます。

一方、静的にサイズが決まる場合は、ヒープ以外の領域に割り当てられます。

メモリの枯渇問題

ヒープ領域のメモリは、スタック領域とは異なり、自動的に解放されません。

メモリは有限なので、不要になったヒープ領域のメモリを解放せずに割り当てを行なっていると、メモリの枯渇が発生して、新たなメモリ割り当てが不可能になる可能性があります。

これはパフォーマンスの低下や、クラッシュを引き起こす原因になります。

これを防ぐためには、不要になったメモリを適切に解放する必要があります。メモリ管理は、このようなメモリのライフサイクルを適切に管理し、システムリソースを効率的に利用するために重要な役割を果たします。

明示的メモリ管理とは

概要

明示的メモリ管理とは、プログラマが手動でメモリの割り当てと解放を管理するプロセスのことです。この方法では、プログラマはメモリを必要とする際に明示的に割り当てを行い、不要になったメモリを手動で解放します。

C言語では、malloc()を使用してヒープ領域から指定されたサイズのメモリを割り当てます。使い終わったメモリはfree()を使って解放します。

以下にその一例を示します。

int main() {
    int *array = malloc(sizeof(int) * 10);
        if (array == NULL) {
        printf("malloc failed\n");
        return 1;
    }

    // array を操作

    free(array);

    return 0;
}

このように、プログラマが明示的にfree()を使ってメモリを解放する必要があるのが、明示的メモリ管理の特徴です。freeを呼ぶのを忘れたり、不適切な場所で呼んでしまうと様々な問題が発生してしまいます。

このプロセスにおいて、free()を適切に呼び出す責任はプログラマにあります。もし free() の呼び出しを忘れるか、不適切なタイミングで呼び出すと、様々な問題が発生してしまいます。

明示的解放が引き起こす問題

メモリリーク

メモリリークは、割り当てられたメモリが適切に解放されない場合に発生します。

これにより、使用されなくなったメモリがプログラムの実行中に解放されずに残り、徐々にメモリ使用量が増加していきます。長時間実行されるようなプログラムでは特にこれが問題となり、最終的に新たなメモリ割り当てが不可能になることもあります。

ダングリングポインタ

ダングリングポインタは、すでに解放されたメモリ領域を指し続けるポインタのことを指します。

以下の例では、メモリが解放後にそのメモリ領域へのアクセスを試みる状況を示しています。

int main() {
    int *ptr = malloc(sizeof(int)); // メモリ割り当て
    *ptr = 10;
    free(ptr); // メモリ解放

    // 解放後のメモリへのアクセス(不正な操作)
    *ptr = 42;

    return 0;
}

解放されたメモリへのアクセスは、予期しない動作やデータの破壊を引き起こす可能性があります。

二重解放

二重解放は、同じメモリ領域が複数回解放されることを指します。

これは、プログラムの異なる部分で既に解放されたメモリを再度解放しようとするときに発生します。二重解放はメモリの破壊やプログラムの予期しない動作を引き起こす可能性があり、安定性やセキュリティの問題を生じさせることがあります。

明示的メモリ管理では、プログラマがメモリのライフサイクルを正確に追跡し、適切なタイミングでのみ解放を行う責任を負います。不要なメモリを即座に解放できるという利点がありますが、この手法は誤った使用によりメモリリーク、ダングリングポインタ、二重解放などの様々な問題を引き起こすリスクを伴います。

自動的メモリ管理

概要

自動的メモリ管理とは、プログラマが明示的にメモリ解放を行わなくても、専用のプロセスが自動的に不要と判断したメモリを解放するシステムを指します。

この方法は、JavaやPython、Goなどの高級言語で採用されています。

例えば、弊社が推進しているGoでヒープメモリを割り当てる場合は次のようにします。

package main

import "fmt"

type MyStruct struct {
    Field int
}

func createStruct() *MyStruct {
    // new を使って MyStruct の新しいインスタンスを作成
    ms := new(MyStruct)
    ms.Field = 10
    return ms // 関数の外部に返すことでヒープ割り当てが発生する
}

func main() {
    ms := createStruct()
    fmt.Println(ms)
}

この例では、createStruct() 内で MyStruct のインスタンスをヒープに割り当てていますが、プログラマはそのメモリを手動で解放する必要はありません。

代わりに、専用のプロセスが自動的に使われないと判断したメモリを解放してくれます。この専用のプロセスのことをガベージコレクションと呼びます。

ガベージコレクション

ガベージコレクション(GC)は、プログラムにおいて不要になったメモリを自動的に特定し、解放するシステムです。これにより、プログラマはメモリの手動解放をする必要がなくなり、メモリ管理の負担が大幅に軽減されます。

GCのプロセスでは、アプリケーションコードを実行する部分を「ミューテータ」と呼びます。ミューテータは、プログラムの実行中にメモリを割り当て、使用します。

一方で、GC自体のコードを実行する部分、つまり不要になったメモリを特定し解放する部分は「コレクタ」と呼ばれます。

メモリの割り当てられたオブジェクトは、プログラムにおいて使用される間は「生きている」と見なされます。コレクタは、プログラムの実行中に「生きていない」と判断されたオブジェクト、すなわち「ゴミ」と見なされるオブジェクトを特定し、メモリから解放します。

では、コレクタはどのようにしてゴミを判断するのでしょうか?

ゴミの判別メカニズム

GCは、ポインタの到達可能性に基づいてメモリがゴミかどうかを判断します。

到達可能性とは、グローバル変数や、アクティブなスタックフレームなどの、有限ルート集合からポインタを辿って、直接または間接的にオブジェクトにアクセスできるかという性質のことです。

ポインタ到達可能性の簡略図
上図において、ルート集合からアクセス可能なオブジェクト(例えばObjectA)は生きているとみなせます。

ObjectBObjectCはルート集合から直接アクセスできないものの、ObjectAを介して間接的にアクセス可能なため、これらは生きているとみなされます。一方で、ObjectDはどの生きているオブジェクトからも参照されていないため、ゴミと判断され回収の対象となります。

ガベージコレクションの種類

GCには、主に以下の4つの基本的なタイプがあります。

  • マークスイープGC
  • コピーGC
  • マークコンパクトGC
  • 参照カウントGC

その他のGCアルゴリズムは、通常これらのGCのどれかを組み合わせたGCとなります。

先程せっかくGoに触れたので、ここではGoで使われているマークスイープGCについて軽く紹介します。マークスイープGCは「マークフェーズ」と「スイープフェーズ」という2つのフェーズに分かれています。

マークフェーズ

マークフェーズの簡略図
マークフェーズでは、ルート集合から到達可能なオブジェクトにマークをつけます。

マークされたオブジェクトは、「生きている」と見なされます。

上図ではオブジェクトの中にマークをつけていますが、外部に管理表(ビットマップ)を持たせてそこでマークを管理する方法もあります。

スイープフェーズ

スイープフェーズでは、マークのついていないオブジェクト。つまり「ゴミ」とみなされるオブジェクトのメモリを解放します。全ての解放が終了すると、生きているオブジェクトのマークはクリアされ、新しいサイクルが始まります。

このようにマークスイープGCでは、生きているオブジェクトを特定し、それ以外を解放するため、これを「間接的GC」と呼びます。今回の主題ではないのでかなり省いた説明をしていますが、機会があれば別の記事として書こうかなと思います。

ガベージコレクションの解法

明示的解放の問題が発生する要因

前置きが長くなりましたが、ここからが本題になります。

まずは、明示的メモリ解放が直面する主要な問題であった、メモリリーク、ダングリングポインタ、そして二重解放がなぜ起こるのかをみていきます。

これらの原因を理解するためには、オブジェクトの活性とメモリ解放の判断における視点の違いを考慮する必要があります。

オブジェクトの活性を判断する視点

オブジェクトの活性(生きているかどうか、もう不要かどうか)を判断する際には、プログラム全体のグローバルのコンテキストを考慮する必要があります。

ヒープに割り当てられたオブジェクトは、スタック領域に格納されるローカル変数とは異なり、宣言されたスコープ外でも生存し続け、明示的に解放されるまでメモリを占有します。

このため、特定のスコープでそのオブジェクトが使用されていなくても、どこか一つのスコープでも使われていれば、そのオブジェクトは生きていると判断されます。

オブジェクトの解放を判断する視点

明示的な解放の際には、プログラマはその時点でのローカルスコープに基づいてメモリ解放を判断しなければなりません。

free()などの関数は特定のスコープ内で呼び出されるため、そのスコープの情報のみが判断基準となります。このローカルな視点に基づいた解放判断は、プログラム全体のコンテキストを考慮せずに行われるため、オブジェクトの活性判断のグローバルな視点との間にギャップが生じます。

この視点のギャップが、メモリリークやダングリングポインタ、二重解放といった問題の原因となります。

この問題を示したコードの簡単な例を以下に示します。

void local_scope(int *ptr) {
    // 他のスコープでまだ使われることを知らずに ptr を解放する。
    free(ptr);
}

int main() {
    // ヒープ上に整数のためのメモリを割り当てる。
    int *ptr = (int *)malloc(sizeof(int));
    *ptr = 10;

    local_scope(ptr);

    // ローカルスコープ内で解放されたことを知らずに ptr を使用する。
    printf("pointer value: %d\n", *ptr); // 未定義の振る舞いになる。

    return 0;
}

この例では、local_scope()が関数内でメモリを解放してしまうため、プログラムの他の部分でそのポインタが参照されると問題が発生します。

このコードは小さいので判断できますが、プログラムの規模が大きくなると、ファイルやモジュールが分割されることによって、このギャップの問題はもっと顕著になることが予測できます。

なぜGCではこれらの問題が起きないのか

GCが明示的メモリ管理の問題に効果的である理由は、単に自動的にメモリを解放することだけでではありません。プログラム全体を俯瞰するグローバルな視点に基づいてオブジェクトの解放を判断することにあります。

GCはプログラムの実行状態を全体的に分析し、到達可能性のアルゴリズムに基づいて、活性のあるオブジェクトを維持しつつ、不要になったオブジェクトを特定して解放します。

これによって、すべてのオブジェクトに対して、プログラムのどの部分からもアクセスできないというグローバルな条件を満たした時点でのみ、解放が行われます。

このように、GCはプログラマがローカルスコープの情報に基づいて行う判断を、プログラム全体の状態を基に行います。これにより、メモリリーク、ダングリングポインタ、二重解放といった問題を根本的に解消することが可能になります。また、プログラムが大規模化し、複数のモジュールやファイルに分割されても、GCの効果は維持されます。

ソフトウェア工学的観点の影響

他にもメモリ管理の違いは、ソフトウェア工学的観点の影響を与えます。

ソフトウェア工学において、モジュール間のコミュニケーションは最小限に抑えるということは重要な原則の一つです。この原則は、モジュール間の結合度を低く保ち、他のモジュールに依存を減らし、ソフトウェアの変更や拡張を容易にします。

しかし、明示的メモリ管理はこの原則に反し、「暗黙的なインターフェースの複雑化」という問題を引き起こします。

以下の例を元に考えてみます。

// メモリの所有権について暗黙的に知っておく必要がある関数
void process_and_free(int *data) {
    printf("データ処理中: %d\n", *data);

    free(data);
}

// メモリを割り当てて、呼び出し元が解放することを期待する関数
int* create_data() {
    int *data = (int*)malloc(sizeof(int));
    *data = 42; // 何かの値を設定する。

    return data;
}

int main() {
    // インターフェースは、所有権が呼び出し側に渡ることが暗黙的です。
    int *new_data = create_data();

    // インターフェースは、誰がメモリを解放するべきかについて暗黙的であり、
    // ドキュメントや規約の必要性を生み出します。
    process_and_free(new_data);

    return 0;
}

この例では、create_data()がメモリを割り当ててポインタを返しますが、 この関数を使用する際、呼出し側はこのポインタのメモリを解放する必要があります。

すなわち、メモリの所有権が関数の呼出し元に暗黙的に移譲されるわけですが、このルールは関数のシグネチャから明確に読み取ることができず、メモリリークのリスクを増加させます。

また、process_and_free()では、内部でメモリ解放しますが、その事実もシグネチャからは読み取れません。そのため呼び出し側はその関数の内部を知らなければ、解放済みのメモリのポインタを再度使用してしまう可能性があります。

これらの問題に対処するためには、ドキュメントやコメントなどで補足する必要がありますが、これはインターフェースを不必要に複雑化させ、エラーのリスクや認知負荷が増加させます。加えて、暗黙のルールを理解しなければコードが理解できないとなると、モジュールの再利用性は制限されてしまいます。

一方、自動メモリ管理(GC)はこのような問題を回避できます。

これは、GCがメモリ管理の責任をプログラマから引き受けることによって、インターフェースからメモリ管理の複雑さを取り除くからです。

明示的メモリ管理の場合、メモリを管理するためのコードがあちこちに散りばめられますが、GCの場合は、メモリ管理をするためのコードを書く必要がなくなり、再利用性も改善され保守性が高くなるメリットがあります。

GCの制約

ここまでGCを使うことによる利点を述べてきましたが、万能薬というわけではなく、いくつかの制約を考慮する必要があります。

パフォーマンスオーバーヘッド

GCのプロセスがパフォーマンスに影響を与えることがあります。

特にFull GCと呼ばれるタイプのGCでは、GC実行中に全てのアプリケーションスレッドが停止してしまうことがあり、これは「Stop The World」と呼ばれる現象になります。

他の種類のGCでは「Stop The World」は発生しなくても、パフォーマンス低下を引き起こすことがあります。

メモリ使用量の増加

GCは不要なオブジェクトを即座に解放しないので、メモリ使用量が増えることがあります。特にメモリリソースが限られた環境だとこれが問題になります。

実行タイミングが予想できない

GCがいつ実行されるかは予測できないため、特定のタイミングでのメモリ解放を保証することができません。これは、リソースが限られた環境や、厳格なリソース管理が必要なアプリケーションでは問題になる可能性があります。

生きているオブジェクトが使われるとは限らない

GCは、オブジェクトの生存状態を判断する際に「到達可能性」を基準にしますが、これはオブジェクトが実際に使われているかどうかを必ずしも意味しません。つまり、プログラム内で参照されているが、実際にはもう使用されていない「生きているが使われていない」オブジェクトが存在する可能性があります。

このようなオブジェクトは、GCによって回収されないため、メモリを不必要に占有し続けることになります。

他にもまだ考慮すべき制約はたくさんありますが、これらの制約はGCの利点とのトレードオフになります。GCを使用する際はこれらの制約を理解しておくことが重要になります。

まとめ

明示的メモリ管理における問題の多くは、オブジェクトの活性はグローバルなスコープで判断されるのにもかかわらず、メモリ解放はローカルスコープで判断しなければならないという判断の視点のギャップにありました。

GCは、メモリ解放の決定をグローバルスコープで行い、自動で解放することで明示的メモリの問題の解決を図ります。 それに加えて、モジュールの再利用性も向上し、メンテナンスのしやすいプログラムも書きやすくなるのでした。

しかし、GCは完璧な解決策ではなく、さまざまな制約が存在します。 これらの制約の理解し、コードがどのメモリ領域に格納されるのかを考慮しながらコードを書くことが大事なんだな〜と思いました。

メモリ管理って面白い!( ^∀^)

参考資料

書籍

  • Richard Jones, ガベージコレクション 自動的メモリ管理を構成する理論と実装, 翔泳社, 2016
  • Noam Nisan, コンピューターシステムの理論と実装 —モダンなコンピュータの作り方, オライリージャパン, 2015

サイト

ChatGPTに社内文書に基づいた回答を生成させる仕組みを構築しました

はじめに

はじめまして、8月にコネヒトに入社したy.ikenoueです。

突然ですがみなさん、生成AIは使っておりますでしょうか? ChatGPTやStable Diffusionといった代表的な生成AIの発表から約1年が経過し、そろそろブームも落ち着くかと思っていたのですが、つい先日もOpenAI DevDayにてChatGPTに関する様々なアップデートが発表されるなど、相変わらず目まぐるしい日々が続いていますね。

弊社における生成AIの活用状況はというと、以前に下記の記事にて、Slack上でChatGPTと会話できる環境を社内提供しているという取り組みをご紹介しました。

tech.connehito.com

本日は、上記の社内ツールに新たに追加した「社内文書の参照機能」についてご紹介します。

「社内文書の参照機能」の概要と開発動機

まずは「社内文書の参照機能」の概要と開発にいたった動機についてご説明します。

「社内文書の参照機能」は、その名の通り、ChatGPTが社内に存在する文書を参照したうえで、回答を生成する機能となっております。 というのも、ChatGPTを始めとする大規模言語モデルは、学習時に用いたデータ以外の知識を持っていません。そのため例えば、「経費を精算するにはどういった手順を踏む必要がありますか?」という質問を投げかけたとしても、ChatGPTは一般的な経費精算手順について述べるのみで、特定の企業における正しい経費精算の手順を詳細に回答することは不可能となっています。「社内で発生するQAをChatGPTに回答してもらおう」といった発想はChatGPTを業務で活用するうえで真っ先に思い浮かぶ案の一つかと思いますが、上記の例に代表されるように、質問者が求める情報を正確に提供することができないという場面は非常に多いです。

このような課題に対する解決策として「検索拡張生成 (RAG: Retrieval Augmented Generation)」という技術が知られています。(以降「RAG」と略します。) RAGは、生成AI技術に対して検索技術を掛け合わせることで、本来の生成AIが知り得ない情報に関する回答を可能にする技術です。 ここで、簡素な図を使ってRAGについて説明します。

RAG概要

上記のように、RAGでは、ユーザーが発信したメッセージを生成AIに渡す前に、文書の検索を実行するステップが発生します。(上図②) 検索ステップでは、予め準備された文書の中からユーザーが発信したメッセージと関連性が高い(≒ユーザーが求める回答を生成するために役立つ可能性が高いと考えられる)文書の抽出を試みます。 そして、見つけ出した文書をユーザーが発信したメッセージと一緒に生成AIに与えることで、生成AIが生成する回答の信頼性を高めることができるという仕組みになっています。

この度実装した「社内文書の参照機能」では、以上に述べたRAGの技術を用いて、社内制度やナレッジが書かれた文書の検索とそれらの文書に基づく回答生成を実現しています。 特に今回は、可能な限り低コストで本機能を実現することを重視しており、Azure Cognitive SearchやOpenAIの文章埋め込みモデルといったRAGを実践する際に用いられることの多い有料サービスを使用しない方法を採用しています。低コストで本機能を実現したいと考えている皆さんのお役に立つ内容になっているかと思いますので、参考になれば幸いです。

「社内文書の参照機能」の実現方法

ここからは「社内文書の参照機能」を実現するために用いた具体的な手法について説明していきます。以下は、今回構築したシステムの簡易的な構成図です。

■ 簡易構成図

このシステムによって実行される処理は、「A. 定期バッチ」として行うもの(構成図上部)、「アプリケーション」の実行時に行うもの(構成図下部)の2つに大別されます。以降は、これらを分けてご説明します。

「A. 定期バッチ」では、検索を実行するために必要となる社内文書の取得及び検索用インデックスの構築を行います。今回は、検索手法としてベクトル検索を採用しているため、事前準備として文書のベクトル化を行いベクトルインデックスを構築する必要があります。

「B. アプリケーション」には、ユーザーから受け取ったメッセージに基づく関連文書の検索やOpenAIのAPIを通したChatGPTとのやり取り、ユーザーへの回答送信などを実行します。また、アプリケーションの起動時には、「A. 定期バッチ」で作成された検索用のオブジェクトを読み込みます。

当記事では、「社内文書の参照機能」に特有な下記の3つの手順に焦点を当て、それぞれで実行する処理の中身についてご説明します。

「A. 定期バッチ」

  • 手順① 社内文書のベクトル化 (構成図A-2に該当)

「B. アプリケーション」

  • 手順② ユーザーのメッセージに関連する文書の抽出 (構成図B-1〜B-3に該当)
  • 手順③ ChatGPTに与えるプロンプトの構築 (構成図B-4に該当)

手順① 社内文書のベクトル化 (構成図A-2に該当)

手順①では、社内のマニュアルやナレッジが記載された文書をベクトル化する際の処理についてご説明します。これは、手順②の「ユーザーのメッセージによる関連する文書の抽出」においてベクトル検索を行うための事前準備にあたります。

はじめに、文書をベクトル化するためのアルゴリズムとしては、HuggingFaceにて公開されているモデルmultilingual-e5-small を採用しました。2023年11月時点では、文書をベクトル化するためのモデルの主要な候補としてOpenAI製のtext-embedding-ada-002 がありますが、今回は下記の点を考慮してmultilingual-e5-small の採用を決定しました。

  • 最初はなるべくコストを掛けずに機能の実現可能性・実用性を検証したい
  • ベンチマークにおいて、multilingual-e5 の性能がtext-embedding-ada-002 と大差ないことが報告されている。(※)

multilingual-e5には、モデルサイズ別にsmall / base / largeの3つのバリエーションがありますが、largeサイズの性能はベンチマークによってtext-embedding-ada-002を上回っています。

以下に、multilingual-e5-smallによるベクトル化を実行するためのコードを記載します。実装には、PythonライブラリのLlamaIndexを用いています。

# 手順①-1. モジュールのインポート
import torch
from langchain.embeddings import HuggingFaceEmbeddings
from llama_index import Document, ServiceContext, StorageContext, VectorStoreIndex, set_global_service_context
from llama_index.node_parser import SimpleNodeParser
from llama_index.text_splitter import TokenTextSplitter
from llama_index.vector_stores import SimpleVectorStore

# 手順①-2. 埋め込みモデルに関する設定
EMBEDDING_DEVICE = "cuda" if torch.cuda.is_available() else "mps" if torch.backends.mps.is_available() else "cpu" # 埋め込みモデルの計算を実行する機器
embed_model = HuggingFaceEmbeddings(model_name="intfloat/multilingual-e5-small", model_kwargs={'device': EMBEDDING_DEVICE}) 
node_parser = SimpleNodeParser(text_splitter=TokenTextSplitter(separator=" ", chunk_size=512, chunk_overlap=64))
service_context = ServiceContext.from_defaults(embed_model=embed_model, node_parser=node_parser)
set_global_service_context(service_context)

# 手順①-3. 社内ドキュメントをLlamaIndexのDocument型のデータに変換
llamaindex_documents = []

## ※ 下記の変数original_documentsは、社内ドキュメントを要素とするリスト型の変数であり、
## 各要素は社内ドキュメントの「タイトル」「本文」「URL」が格納された辞書型のデータとします。
for document_dict in original_documents:
    llamaindex_documents.append(Document(
        text=document_dict["本文"],
        metadata={
           "タイトル": document_dict["タイトル"],
           "URL": document_dict["URL"],
    }, 
        excluded_embed_metadata_keys=["url"]
    ))

# 手順①-4. 文書のベクトル化を実行し、文書検索用のオブジェクトを構築
index = VectorStoreIndex.from_documents(llamaindex_documents)

# 手順①-5. 構築した検索用のオブジェクトを保存
persist_dir = "./my_storage"
index.storage_context.persist(persist_dir=persist_dir)

コードの内容について一部解説します。

手順①-2のブロックでは、ベクトル化を実行する際の設定として「ベクトル化を実行するモデルの種類」「計算デバイス」「テキスト分割方法」を決めています。特に「テキスト分割方法」では、今回使用するモデルmultilingual-e5-small の対応シーケンス長が最大512トークンであることから、各文書をあらかじめ512トークン以下の粒度で分割するよう設定しています。

手順①-3のブロックでは、オリジナルの社内文書をLlamaIndexが求めるデータ型 (Document型)に変換する処理を行っています。特にexcluded_embed_metadata_keys=["url"]の部分では、metadataに指定したデータの内、ベクトル化の対象外とするものを指定することができます。このように、「何らかの用途で後から参照する可能性はあるが、検索の用途では意味をなさないためベクトル化の対象からは外したい」といったデータは、ベクトル化の対象から除外することをおすすめします。

手順①-4のブロックでは、ベクトルインデックスを中心とする検索用のオブジェクトを生成します。 文書のベクトル化処理もこのセクションで実行しているので、元の文書量が膨大な場合は処理にそこそこの時間を必要とします。(参考までに、弊社の全文書に対してm2チップを搭載したノートPCで処理を実行した場合、約3時間ほどの時間を要しました。)

手順② ユーザーのメッセージに関連する文書の抽出 (構成図B-1〜B-3に該当)

ここからは、ChatGPTとやり取りを行うアプリケーションの動作時に実行する処理となります。手順②では、ユーザーから受け取ったメッセージと関連性が高い社内文書を見つけ出す処理についてご説明します。

## 〜 コードが重複するため省略 〜
## 手順①-1及び2の「埋め込みの設定」処理をここで実行
## 〜 コードが重複するため省略 〜

# 手順②-1. モジュールのインストール
from llama_index import load_index_from_storage
from llama_index.retrievers import VectorIndexRetriever

# 手順②-2. 手順①で構築した検索用オブジェクトのロード
persist_dir = "./my_storage"
storage_context = StorageContext.from_defaults(persist_dir=persist_dir)
loaded_index = load_index_from_storage(storage_context)

# 手順②-3. ベクトル検索を行い、関連性の高い上位5つの文書を抽出
retriever = VectorIndexRetriever(index=loaded_index, similarity_top_k=5)
## ※ 下記の変数user_messageには、ユーザが入力した文字列が格納されているものとします
retrieved_text_list = retriever.retrieve(user_message)

手順②-2では、手順①で保存したデータを読み込むことで、検索用のオブジェクトをメモリ上に展開しています。

手順②-3では、ベクトル検索を行うことで、ユーザーから受け取ったメッセージと関連性が高い社内文書を見つけ出す処理を行います。注意点として、retriever.retrieve(user_message)の部分では、ユーザから受け取ったテキストに対するベクトル化処理を行っています。ここで使用するモデルは、手順①で社内文書をベクトル化した際と同じモデルである必要があります。

手順③ ChatGPTに与えるプロンプトの構築 (構成図B-4に該当)

最後に、手順②で抽出した文章をユーザーから受け取ったメッセージに追加することで、ChatGPTに与えるプロンプトを作成します。

まずはコードを記載します。

# 手順③-1. 手順②で抽出したドキュメントをユーザーから受け取ったメッセージの末尾に追加
reference_documents = ""
for retrieved_text in retrieved_text_list:
    # 検索にヒットした社内ドキュメントの内容及びタイトルを取得
    document_content = retrieved_text.node.text
    document_title = retrieved_text.node.metadata["タイトル"]
    
    reference_documents += f"\n## 文書「{document_title}」\n{document_content}\n"

# ユーザーのメッセージに、関連文書を追加
user_message += f"\n\nただし、下記の文書を参考にして回答してください。\n{reference_documents}"

上記の処理を実行することで、ChatGPTに与えるプロンプトは以下のような文字列になります。

{ユーザーから受け取ったオリジナルのメッセージ}

ただし、下記の文書を参考にして回答してください。

## 文書「{文書1のタイトル}」
{文書1の本文}

## 文書「{文書2のタイトル}」
{文書2の本文}

## 文書「{文書3のタイトル}」
{文書3の本文}

## 文書「{文書4のタイトル}」
{文書4の本文}

## 文書「{文書5のタイトル}」
{文書5の本文}

このように、ユーザーのメッセージに加えてそれに関連する社内文書を渡すことで、ChatGPTが社内独自のマニュアル・ナレッジに基づいた回答を生成することが可能となります。

「社内文書の参照機能」の使用例

それでは、今回の機能搭載によりChatGPTの回答に具体的にどのような変化が生じるようになったのか、実際の例をお見せします。

以下では「社員が書籍購入補助制度の有無について尋ねる」という場面を想定し、

  • before: オリジナルのChatGPTをそのまま使用した場合
  • after: 「社内文書の参照機能」を使用した場合

として、それぞれの回答例を比較しています。

before: オリジナルのChatGPTをそのまま使用した場合

まずは、「社内文書の参照機能」を使用しない場合の回答結果です。

回答例 -before-

そもそも「コネヒト(弊社)の制度について知りたい」という意図をChatGPTに伝えていないため、ChatGPTの回答は一般的な書籍購入補助制度について述べるにとどまっています。また、弊社の書籍購入補助制度の詳細は外部に公開されているものでもないため、その点でもオリジナルのChatGPTに正確な回答を期待することはできない質問となっています。

after: 「社内文書の参照機能」を使用した場合

続いて、今回新たに搭載した「社内文書の参照機能」を使用した場合の回答例です。(社外に公開していない情報を含んでいるため、マスクしている箇所があります。)

※ 下記のユーザーメッセージ内に含まれる「コネヒト」という文字列は今回搭載した機能を動かすためのトリガーの役割を果たすのみで、ChatGPTに送信するメッセージからは除外する処理をアプリ側で行っています。

回答例 -after-

回答内で言及されている”スキルアップ支援制度”は弊社の書籍購入補助制度の名称です。弊社固有の名称を用いて制度に関する具体的な説明が行われていることから、実際の文書の内容に基づく回答が生成されていることがわかります。(弊社ではドキュメントの管理にNotionを使用しているため、ChatGPTの回答の末尾にNotionページへのリンクを追記することで、回答のソースとなった文書にアクセスできるような導線を引いています。)

おわりに

以上、当記事ではChatGPTに社内文書を参照させたうえで正確な回答を生成させる機能の実現例をご紹介しました。

この機能は社内でリリースしてから約2ヶ月が経過するのですが、嬉しいことに「新入社員のオンボーディングに使いたい」や「社内制度に関するQA一次対応に使いたい」など、具体的なケースでの活用を希望する声があがっています。

弊社では、今後もベクトル検索や生成AIといった技術を積極的に活用することで社内の業務効率化やプロダクトの提供価値向上に挑戦していきます。その際は、得られた知見を同様に記事化してご紹介しますので、引き続き当ブログに注目いただけると幸いです!

カオナビ/スターフェスティバル/リンケージ/コネヒトで合同LT&交流会を開催しました!

こんにちは。コネヒトでAndroidエンジニアをしている@katsutomuです。

2023/10/18に株式会社カオナビスターフェスティバル株式会社株式会社リンケージの皆様と、オフラインの合同LT&交流会を開催しました!

このイベントは、社内だけでは得られないような、各社の生な事例や課題をワイワイと話して、学び合うことを主題にクローズドな形式で開催をしています。

4月に開催した前回の参加企業に加え、リンケージさんにもお声がけして、4社合同での開催となりました。今回はイベントの様子をおすそ分けできればと思います。

カオナビさんのイベントブログ

www.wantedly.com

前回のイベントブログ

tech.connehito.com

前回からのアップデート

今回はイベントにテーマを設けるTryを実施しました。

「交流会での話題が、探り探りになる」、「LTで何を話せば/話していいかわからない」ということが、過去2回の反省点としてあがったことが理由です。

テーマはいくつか候補が上がりましたが、オープンな場だと話題にあげづらい「開発生産性」を選びました。

イベントの概要

各社からのLTと交流会が主な内容になっています。

  • オープニング
    • 18:30 - 18:40: 諸注意・会場案内
    • 18:40 - 19:30: 交流会
  • LT
    • 19:30 - 19:50: LT1~4
    • 19:50 - 20:00: 休憩
    • 20:00 - 20:20: LT5~8
    • 20:20 - 20:30: 飛び入り
  • クロージング(30min)
    • 20:45 - 21:15: LTの感想話したり、片付けたり
    • 21:15 - 21:30: クロージング

交流会

話題に困らないように、トークテーマシートを用意しており、最初にシートから選んで話し始めるグループも多くありました。ひとつひとつの話題は「開発生産性」で話したいことを、コネヒト社内のメンバーから募集した内容を載せています。

最初こそ探り探りでしたが、次第に打ち解けていきました。

何かの話題について、熱く語り合っています。

LT枠

オンラインでの登壇も含み、各社から2名ずつ合計8名の方に話していただきました。 生産性への取り組みに関する各社の事例や、狭義の生産性に着目しビルドトラップに陥る罠など、見識を広げるお話も多く、非常に参考になりました。

テーマを決めた時には、どんなLTが集まるか不安はありましたが、限定的な場だからこそ話せるクローズドイベントならではな内容もあり、嬉しく思っています。

実施後のアンケート

継続的なアップデートのために、毎回参加した弊社メンバーにアンケートを実施しています。 設問は以下の通りです。

  • 今回のイベントに期待してたことを教えてください
  • LTで期待していたことは、得られましたか
  • 交流会で期待していたことは、得られましたか
  • LTや交流の中で、持ち帰ってTryしたい他社の事例はありましたか
  • また次回あったら参加したいですか

「開発生産性」というキーワードと当日の内容にギャップを感じたメンバーもおり、運営側として学びを感じる結果となりまいた。

アンケート結果

今回のイベントに期待してたこと(抜粋)

  • 開発生産性のアップが期待できそうな取り組み事例
  • 他社の皆さんとの交流、LTでの情報収集
  • 友達を増やす!

定量評価

具体的なお声(抜粋)

  • 生産性が落ちるパターンの解説LTが勉強になりました
  • 振り返りの振り返りはtryしてみたいと思った
  • Tryというか、そもそも開発生産性とは?という内容に着目したLTが多かったので、きちんと考えるきっかけになったのが良かった。
  • テーマに対する自分の抱くイメージとLTの話題にギャップが激しく「どちらとも言えない」にしています

まとめ

テーマ設定とトークシートを用意したことで、交流会が盛り上がったことは安心しています。社内でトークシートの内容を募集した際も、色々な聞きたいことが集まり、社外と情報交換したいことは多くありそうだと感じているので、今後もアップデートしながら継続開催していきたいと思います。

反面、テーマから抱くイメージとギャップを感じさせてしまったなど反省もあるので、次回のイベントに活かしていきたいと考えています。

ご協力いただいた各社様に改めて感謝いたします。また次回よろしくお願いします!

配列と連結リストの線形探索における計算速度とキャッシュメモリの重要性

こんにちは!バックエンドエンジニアのjunyaUと申します。

最近はコンビニに売っている生ラムネにハマっていて、1日2袋のペースで食べ続けていましたが、ここ数日コンビニに置いていなくて悲しい思いをしています。

今回は配列と連結リストおいて、線形探索の計算速度はどちらが速いのか、キャッシュメモリがどう関わっているのかについて考えていこうと思います〜!

はじめに

なぜ記事を書こうと思ったのか

最近、個人開発で物理メモリ管理の実装をする機会がありました。

その中で、配列を線形探索する処理があったのですが、

「連結リストと配列を線形探索する時に、どちらの方が計算速度が速いんだろう」

とふと疑問に思ったのがきっかけです。

この問題を調べて勉強していくうちに、キャッシュメモリの存在が両者の計算速度の違いに関わっていることがわかりました。

そこで、配列と連結リストのデータ構造の違い、キャッシュメモリがどのようなものなのかについて触れながら両者の線形探索における計算速度の違いを見ていこうと思います!

なお、ここでの連結リストは単方向の連結リストとします。

結論

配列と連結リストは共に線形探索の時間計算量がO(n)ですが、計算速度は配列の方が速いです。

これは、キャッシュメモリのヒット率が配列の方が高いからです。

連結リストはメモリ上で非連続的に配置される可能性がありますが、配列はメモリ上に連続で配置されることが保証されています。

連続してメモリ上に配置されているので、キャッシュラインに配列の他の要素が含まれる可能性が高いため、キャッシュヒット率が連結リストよりも高くなるのです。

これを理解するには配列と連結リストの構造の違い、キャッシュメモリの概要や特性を知る必要があるので、次節から詳しく見ていきたいと思います。

配列と連結リスト

配列の特徴

私がプログラミングを勉強し始めた頃、配列は「複数のデータを入れることができる箱」と学びました。

しかしそれだけでは、配列がどのような実態を持っているのかを掴めないので、もう少し具体的に定義すると、

「メモリ上に連続して配置された、同じ種類のデータの集合」と言えます。

メモリと配列の簡略図
上の図は、5つの要素を持つ配列を示しています。各要素のサイズは8バイトと仮定しています。

メモリに連続して配置されているので、要素のサイズ分アドレスがずれて要素が配置されていることがわかるかと思います。

連続して配置することによって、いくつかの特性や利点が生まれます。

ランダムアクセス可能

ランダムアクセスは、インデックスを用いて任意の要素に直接アクセスする操作を指します。

例えば、array[2]のような操作と考えれば馴染み深いと思います。

このような直接アクセスが可能なのは、配列の要素がメモリ上に連続して配置されているためです。

アクセスのメカニズムは単純で、arrayという変数には配列の先頭アドレスが格納されており、このアドレスに「要素のサイズ × インデックス」を加えることで、目的の要素のアドレスを瞬時に計算することができます。

array[3] というアクセスがあった場合:

0x10000 + (8 × 3) = 0x10018

この計算でアドレスを求めることによって、O(1)の時間計算量で該当の要素にアクセスすることができます。

配列のインデックスが0から始まる理由も、このメモリ上の連続した配置と密接に関連しています。「なぜ0から?」と初めは誰もが疑問に感じると思いますが、メモリの観点から考えると、アドレス計算を効率化するためであることが明白になります。

削除と挿入操作時のオーバーヘッドが大きい

配列の末尾に対して、挿入や削除をする場合の時間計算量はO(1)です。

しかし先頭や中間に挿入や削除を行う場合、追加の時間計算量がかかります。

配列からindexが2の要素を削除する簡略図
上図は、indexが2の要素を削除した場合の配列を示しています。

削除すると、その位置に空きが生まれます。この空きを埋めるために、削除した要素以降の要素を全て1つ前にずらす必要が出てきます。この操作は、特に配列が大きい場合、大きなオーバーヘッドが発生します。

今回のケースではindex3とindex4の要素を1つ前にずらすという操作が必要となります。

このようなオーバーヘッドを考慮すると、頻繁に削除や挿入が行われるケースでは、配列を使うのではなく、他のデータ構造を使うべきだと言えます。

固定長

C, C++, Java, および Go などの配列は固定長であり、一度確保したサイズを途中で変更することはできません。主な理由は、配列が連続したメモリ領域に配置されているためです。

拡張をしようとしても、配列の直後のメモリには別のデータが配置されている可能性があります。

また、仮に配列を後に拡張するために余分にメモリを確保するとしても、それが後で使用されるかどうか予測することが難しく、メモリの浪費につながります。

なので、データ長を動的に変えたい場合、配列は適したデータ構造ではありません。

連結リストの特徴

連結リストは、複数のデータを管理するという観点では配列と同じですが、そのデータ構造は全く違います。

配列はデータを連続したメモリ領域に確保しますが、連結リストはそのような連続性を保証しません。

単方向連結リストとメモリの簡略図
上図を見ると、それぞれの要素が非連続に配置されていることがわかります。

連結リストの各要素(ノードとも呼ばれる)はデータと、次の要素への参照(ポインタ)を持っています。このポインタをたどることで、次の要素にアクセスすることができ、非連続でも複数データを管理することができます。

このように非連続で配置することによって、いくつかの特性や利点が生まれます。

ランダムアクセスはできない

連結リストは、特定の要素への直接アクセスが配列と比べると非効率です。

配列ではarray[3]のように特定のインデックスを指定して、O(1)の時間計算量でその要素にアクセスできます。

一方、連結リストではデータが連続したメモリ領域に格納されていないため、ベースアドレスを使用してインデックス計算で要素のアドレスを直接特定(ランダムアクセス)することはできません。

n番目の要素にアクセスするためには、連結リストの先頭から、指定された位置に達するまで各要素のポインタを逐次たどる必要があります。

この操作はO(n)の時間計算量がかかることになります。

そのため、特定の要素への高速なアクセスが必要な場合は、連結リストよりも配列を使用する方が適切です。

削除と挿入時のオーバーヘッドが小さい

配列では先頭や中間への要素の挿入や削除に大きなオーバーヘッドがかかりますが、連結リストではこれらの操作をより小さいオーバーヘッドで行うことができます。

連結リストからNode2を削除する簡略図
上図ではNode2を削除していますが、配列のように削除したindex以降の要素をずらすという操作は必要ありません。

Node1が持っていたNode2へのポインタをNode3へのポインタに付け替えるだけで削除の操作は完了します。

このように、頻繁に削除や挿入が行われるケースは配列よりも連結リストの方が適しています。

可変長

連結リストは可変長のデータ構造です。

配列と違い、データを連続して配置する必要はないので、拡張が必要な場合は都度空いているメモリにNodeを割り当て、連結リストを拡張することができます。

動的なデータ長を扱う場合、配列よりも連結リストの方が適したデータ構造と言えます。

比較表

最後にそれぞれの特徴をまとめた表を置いておきます。

特徴/操作 配列 連結リスト
メモリの配置 連続 非連続
ランダムアクセス O(1)(高速) O(n)(低速)
先頭や中間への要素の挿入・削除 O(n)(低速、要素をずらす必要がある) O(1)(高速、ポインタを更新するだけ)
メモリ使用効率 低い(固定長) 高い(可変長)
サイズ変更 困難/不可能(再確保とコピーが必要) 容易(要素の追加・削除でサイズ変更)

線形探索

線形探索について

今回の主題である、連結リストと配列において線形探索する時に、どちらの方が計算コストが少ないのかという問題を考える前に、線形探索について軽く触れておこうと思います。

線型探索は検索のアルゴリズムの1つで、 連結リストや配列に入ったデータに対する検索を行うにあたって、 先頭から順に比較を行いそれが見つかれば終了するといったアルゴリズムです。

優秀なアルゴリズムですが、先頭から片っ端に探していくので「馬鹿サーチ」とも呼ばれているみたいです。(ひどい…😭)

ちなみに連結リストの節で

n番目の要素にアクセスするためには、連結リストの先頭から、指定された位置に達するまで各要素のポインタを逐次たどる必要があります。

このように、ランダムアクセスではなく先頭から逐次辿る必要があると述べましたが、まさにこれが線形探索となります。

どちらの方が計算コストが低いのか

線形探索自体の時間計算量はO(n)となりますが、実際の実行速度はデータ構造によって異なります。

配列と連結リストでは、どちらの方が速く探索できるのかを、実際にコードを書いて検証してみます。

なお今回はC++を使うことにします。

#include <iostream>
#include <forward_list>
#include <random>
#include <algorithm>
#include <chrono>
#include <vector>
#include <numeric>
#include <cmath>

// Generate random data for testing
template<typename Container>
void generate_data(Container &c, size_t size) {
    std::random_device rd;
    std::mt19937 mt(rd());
    std::uniform_int_distribution<int> dist(1, 1000000);

    c.resize(size);
    std::generate(c.begin(), c.end(), [&mt, &dist]() { return dist(mt); });
}

template<typename Container>
void linear_search_test(const Container &c, const std::string &type) {
    const int repeat_count = 200;
    std::vector<long long> times;
    
    for (int i = 0; i < repeat_count; ++i) {
        auto start = std::chrono::system_clock::now();

        // Perform a dummy operation to prevent loop optimization
        int sum = 0;
        for (const auto &val: c) {
            sum += val;
        }

        auto end = std::chrono::system_clock::now();
        auto elapsed = std::chrono::duration_cast<std::chrono::microseconds>(end - start);
        times.push_back(elapsed.count());
    }

    double mean_time = std::accumulate(times.begin(), times.end(), 0.0) / repeat_count;
    double sq_sum = std::inner_product(times.begin(), times.end(), times.begin(), 0.0);
    double stdev_time = std::sqrt(sq_sum / repeat_count - mean_time * mean_time);
    double cv = stdev_time / mean_time * 100;

    std::cout << "Type: " << type << "\n";
    std::cout << "Average time: " << mean_time << "μs\n";
    std::cout << "Time stddev: " << stdev_time << "μs\n";
    std::cout << "Coefficient of variation: " << cv << "%\n\n";
}

int main() {
    const size_t data_size = 10000000;

    std::vector<int> vec;
    std::forward_list<int> list(data_size);

    generate_data(vec, data_size);
    generate_data(list, data_size);

    linear_search_test(vec, "Vector");
    linear_search_test(list, "Forward List");

    return 0;
}

これは、1000万個の要素を持つ連結リストと配列に対して、線形探索を200回ずつ行いそれぞれにかかった時間を計測するコードです。

結果の前に、計測するにあたって考慮した点を軽く紹介していこうと思います。

配列はarrayではなくvectorを使う

今回は、配列の表現に、std::arrayではなくstd::vectorを使うようにしました。

これは、連結リストと同じメモリ領域を使うためです。

std::arraystd::vectorはどちらも配列を表すデータ構造ですが、使われるメモリ領域が異なります。

std::arrayはコンパイル時にサイズが確定するのでスタック領域に割り当てられますが、

std::vectorはヒープ領域に割り当てられます。

それぞれのメモリ領域に軽く触れておくと :

  • スタック領域は、通常は関数の呼び出しや局所変数の保存に利用されるメモリ領域で、アクセス速度が速い
  • ヒープ領域は、動的にデータを割り当てる際に使用されるメモリ領域で、メモリアクセスの速度はスタックに比べて遅い

となっています。

この検証では、「メモリ領域の違い」ではなく「メモリの連続性」に焦点を当てています。

なので、配列と連結リストで使用するメモリ領域を揃えることで、メモリの連続性による影響を強調できるようにしました。

コンパイラがループを最適化しないようにした

線形探索に該当するループの部分でsumという変数に加算を行っています。

これは、何もループ内に処理を書かなければ、この部分の実行はする必要がないとコンパイラに判断されその部分は省略(最適化)されてしまうため、最適化されないようにダミーの処理を追加しています。

結果

こちらが検証に使用したマシンのスペックです。

  • CPU: Apple M2 Max
  • RAM: 64GB
  • OS: Ventura 13.4

このマシンでそれぞれ200回実行した結果は次のようになりました。

Type: Vector
Average time: 47886.5μs
Time stddev: 1139.39μs
Coefficient of variation: 2.3794%

Type: Forward List
Average time: 60295.2μs
Time stddev: 1518.22μs
Coefficient of variation: 2.5180%

結果から明らかなのは、配列(Vector)と連結リスト(Forward List)の平均実行時間には約12,000マイクロ秒の差があるという点です。また、両方のデータ構造における係数の変動(Coefficient of Variation)が低いことから、このデータは一定の信頼性を持っていると判断できます。

(マシンやリソースの状況によって結果は異なりますが)

では、なぜ時間計算量が両方ともO(n)であるにも関わらず、このような実行時間の差が生まれるのでしょうか?

これは、データのメモリ配置に関わる「キャッシュ効率」が大きな要因の1つとして挙げられます。

連続したメモリ領域に配置された配列は、キャッシュメモリにおいて高いヒット率を示すため、全体として計算コストが削減されるのです。

なぜ配列の方がヒット率が高くなるのでしょうか?

ここで登場したキャッシュメモリが持つこれらの性質と、なぜヒット率が異なるのかを次の章で詳しく見ていきます。

キャッシュメモリ

キャッシュメモリの概要

データAをメインメモリからフェッチするときの簡略図

キャッシュメモリは、CPU(処理装置)とメインメモリ(主記憶装置)の中間に位置する、高速なデータアクセスが可能な小さな記憶装置です。

ノイマン型アーキテクチャのコンピュータでは、CPUとメインメモリの処理性能には性能差があります。

いくらCPUの性能を高めようと、そのCPUの処理性能にメインメモリのアクセス速度が追いつけません。 そのため、メインメモリからデータをフェッチする速度の遅さがボトルネックとなり、システム全体の処理速度も遅くなります。

この現象は「ノイマンボトルネック」と呼ばれています。

キャッシュメモリは、両者の処理性能差を埋め合わせることでこの問題の解決を図ります。

具体的には、処理装置がアクセスしたデータやアドレスなどをキャッシュメモリに一時的に保持しておくことで、次に同じデータやアドレスにアクセスがあった場合、メインメモリではなくキャッシュメモリから迅速にデータをフェッチできます。

これにより、メインメモリへのアクセスが削減され、データフェッチの効率の向上、高速化が見込めます。

キャッシュメモリはL1,L2,L3といった複数のレベルを持っています。

記憶階層において、このレベルの数字が小さいほどCPUに近く高速になります。

補足 : 記憶階層とは?

記憶階層の簡略図

CPUにとって、望ましい記憶装置は大容量で高速にアクセスできるものです。

しかし、実際の記憶装置は大容量であるほどアクセス速度が遅くなり、小容量であるほど高速になるというトレードオフがあるので、望むような記憶装置は現状作ることができません。

そこで図のように記憶装置を階層化し、各階層を下位の階層のキャッシュとして用いることで、CPUから見た場合、あたかも大容量で高速な1つの記憶装置であるかのように振舞います。

このように階層化された記憶システムを、記憶階層と言います。

なぜ配列の方がヒット率が高いのか

配列が連結リストと比べてキャッシュメモリのヒット率が高くなる理由は、その連続したメモリ構造とキャッシュメモリのデータ取得方法に密接な関連があります。

キャッシュメモリは「キャッシュライン」という一定の単位でデータを一時的に保持しています。

キャッシュラインのサイズは、プロセッサのアーキテクチャやモデルによって異なりますが、32、64、または128バイトが一般的です。

メインメモリからデータAをフェッチする際、キャッシュメモリはデータAだけでなく、その近傍のデータも合わせて保持します。したがって、次に近傍のデータにアクセスする際はヒットする確率が高くなります。

array[0]のデータをフェッチする簡略図

例として、上図のarray[0]の要素をフェッチする場合を考えてみます。

array[0]をメモリからフェッチする際、その近傍のデータもキャッシュライン(ここでは例として32バイト)としてキャッシュメモリに一時保存します。

すると、4つ全ての要素がキャッシュメモリに保持され、次にこれらの要素にアクセスする際は、メインメモリよりも高速なキャッシュメモリからデータをフェッチすることができます。

これは、配列のメモリ上での連続した配置と、キャッシュメモリがキャッシュライン単位で近傍のデータも一緒に保存する性質とが組み合わさって実現されます。

一方で、連結リストではメモリ上に非連続に配置されているため、キャッシュミスが配列に比べて頻発します。

これが、配列と連結リストの間でキャッシュヒット率が異なる理由です。

また、このキャッシュラインによる近傍データの同時フェッチの考え方は、「空間的局所性」というコンピューティングの性質に基づいています。

空間的局所性

空間的局所性は、一度アクセスされたデータの近傍が近いうちに再びアクセスされる可能性が高い、というプログラムの実行特性を指します。

キャッシュメモリの設計において、キャッシュラインがこの特性に基づいています。

具体的には、一度データをフェッチすると、その近くにあるデータも一緒にキャッシュに取り込むことで、次のアクセスが高速になる可能性が高くなります。

時間的局所性

時間的局所性は本例では触れられていませんが、こちらも重要な特性ですので補足として紹介しておきます。

時間的局所性とは、一度アクセスされたデータが近いうちに再度アクセスされる可能性が高いという特性を指します。

webブラウザにおいて、「戻る」ボタンを押す行動もこの一例となります。

ブラウザは、この操作を高速に行うため、以前アクセスしたページのデータをキャッシュしており、これは時間的局所性に基づいたものになります。

おわりに

結論

配列が連結リストと比較して、線形探索の際のメモリアクセスのコストが低いことがわかりました。

この違いは、配列のほうがキャッシュメモリに対して高いヒット率を示すためです。

キャッシュメモリが高いヒット率を持つ背後には、キャッシュメモリが「空間的局所性」の原理に基づいて設計されていること、及び配列のデータがメモリ上で連続して配置される特性があります。

具体的には、キャッシュメモリはキャッシュラインと呼ばれる単位で近傍のデータも一緒に保持し、これによって近くのデータにアクセスする際もキャッシュから高速にデータを取得することができるので、結果的に配列の線形探索の方が早くなったのでした。

このようにハードウェアの特性や概念を知ることで、コンピュータリソースをより効率的に扱えるようになることにつながります。

Web開発においては、「業務で使わないから」という理由で低レイヤーやアルゴリズムの勉強が軽視されることがありますが、こういった抽象化されている部分を勉強することは、

普段使っている技術への理解が深まりスキルの向上につながると思うので、引き続きこういった内容のブログを発信していこうと思っています!

また、キャッシュメモリは他にもデータの一貫性を保つための「キャッシュコヒーレンシ」など、面白い仕組みがまだまだあるので、機会があればこちらもまた書いていこうと思います〜!