Grounding Plugin

Motivation

저는 Obsidian을 통해 개인 지식 관리, personal knowledge management를 하고 있습니다. Obsidian은 노트가 속한 폴더, 그리고 그 폴더가 속한 폴더의 hierarchy에 따라 지식을 관리하는 것에 더해 internal link를 통해 지식을 관리할 수 있도록 돕는 노트 정리 앱입니다. Obsidian에서 internal link를 만드는 방법은 [[]] 를 사용하는 것입니다. Obsidian 앱은 [[ 를 인식하여 연관 있는 노트를 제안(Suggest)합니다.

그리고, 저는 [[ 를 통해 internal link를 만드는 게 익숙해지지 않고, 집중력을 잃는다는 것을 깨달았고, [[ 표시 없이도 자동으로 노트를 제안하는 플러그인을 만들기로 했습니다.

Domain Research

Obsidian Plugin API look around

Obsidian에서 제공하는 Plugin API를 연습해볼 필요가 있었습니다.

아래 두 페이지를 통해 정보를 얻었고, 기본적인 플러그인을 제작했습니다.

1. Obsidian Docs: Obsidian Plugin 관련 API 정보를 제공합니다. Home - Developer DocumentationHome - Developer Documentationdocs.obsidian.md
2. Obsidian Help: Obsidian 사용정보를 제공합니다. Domain Research를 위해 참고했습니다. Home - Obsidian HelpHome - Obsidian Helphelp.obsidian.md

위 문서에서 목록으로 정리해둔 API를 사용해보고 내린 결론은 다음과 같습니다.

Core Obsidian Plugin APIs

Obsidian Plugin API를 통해 생각한 기능을 구현할 수 있는지 확인했습니다. 개발 전 생각한 핵심 기능은 2가지 입니다.

1. 유저의 입력에 따라 적절하게 관련 노트를 제안한다. 제안을 클릭하면 Obsidian Internal Link를 추가한다.
2. vault를 읽어온 다음, 조건(폴더, 태그 등)에 맞는 노트를 따로 선별하여 저장소에 저장(in-memory)해둔다. 유저가 노트 내용을 수정하면 이 저장된 정보도 변경되어야 한다.

유닛 테스트를 통해 아래 API를 사용하여 생각하는 기능을 구현할 수 있는 것을 확인했습니다.

1. EditorSuggest

2. registerEvent - create, modify, delete, rename

   각 이벤트에 대한 테스트 및 결과는 별도의 프로젝트에 정리되어 있습니다.

   https://github.com/Doggy-Footprint/Obsidian-API-Tester/blob/master/main.tsgithub.com

3. Vault, CachedMetadata

Typescript

개발 시작 당시 Javascript는 사용해본 경험이 있었고, Typescript는 사용해본 경험이 없었습니다. 다만 Java와 같이 static type 언어는 충분한 경험이 있었기 때문에 Typescript의 기본 syntax만 익히고 개발을 시작하고, 이후 typescript에 익숙해지면 개선하기로 정했습니다.

Design User Scenarios

Notes to suggest

Obsidian은 vault(Obsidian은 관리하는 모든 노트를 하나의 vault로 다룹니다.)에 포함된 모든 노트의 이름과 그 aliases tag를 가지고 있고, [[ 뒤에 따라오는 입력이 노트의 이름이나 alias와 일치하면 이를 유저에게 제안합니다.

당연히 [[ 없이 모든 노트에 대해 위와 같은 작업을 하면 사용자에게 너무 많은 제안을 할 것이므로 조금 줄여야 할 필요가 있습니다.

제 경험에 의거해서 2가지 조건 중 하나를 만족하는 노트를 제안 대상으로 하기로 했습니다.

1. 특정 폴더에 포함되는 노트이거나,
2. 특정 tag를 포함하는 노트이거나.

위 조건은 유저가 커스텀할 수 있도록 설정할 계획입니다.

Design Application Architecture

Prefix Tree

노트의 이름과 aliases 모두 string으로 관리된다. 따라서 Prefix Tree를 쓰면 빠른 읽기 쓰기가 가능하다고 판단했고, 위에서 말한 in-memory 저장소로 Prefix Tree를 사용했습니다.

Prefix Tree with Content & metadata - search

유저가 cre를 입력했을 때 해당 node를 찾은 다음 적절한 **제안(Suggest)**을 하기 위해서는 두 가지 방법을 생각할 수 있습니다.

1. cre 노드 하위 모든 노드를 검색한다.
2. cre 노드에 하위 노드의 정보를 저장한다.

두 방안을 비교하면 첫 번째 방법은 $O(1)$의 빠른 업데이트가 가능하지만 읽을 때 최대 $O(n)$의 시간 복잡도를 필요로 합니다. 두 번째 방법은 $O(h)$의 느린 업데이트 속도를 제공하지만 $O(1)$의 빠른 읽기 속도가 가능합니다. 다만, 두 번째 방법은 redundant한 정보 저장으로 비교적 많은 메모리를 사용합니다. 이 플러그인은 유저의 쓰기에 반응하는 플러그인이기에 메모리 사용량이 크더라도 빠른 반응 속도를 제공해야 한다 판단했기에 2 번째 방법을 사용했습니다. 또한 metadata 사용의 장점은 유저의 사용에 기반한 정보를 수집하여 자주 사용하거나, 최근 사용한 노트를 추천할 수 있다는 것입니다.

Prefix Tree with Content & metadata - update

Prefix Tree의 특성상 노트 이름 수준의 글자에 대해서는 매우 빠른 속도를 보여줄 수 있습니다. 다만 문제가 되는 부분은 metadata의 수정입니다. 이 과정은 2가지 문제가 있습니다.

1. metadata에 대한 sorting이 필요합니다. (metadata가 추천을 위한 별도 정보를 보유하는 경우)
2. 1의 sorting을 root에 도착할 때까지 반복해야 합니다.

이러면 $O(h \times n \log n)$의 시간 복잡도가 필요합니다.

저는 다음과 같이 최적화했습니다.

1. SortedArray에 metadata 정보를 저장하여 관리했습니다. 따라서 새로운 metadata의 추가/삭제는 $O(h \times \log n)$으로 관리할 수 있습니다.
2. metadata의 변동사항이 없을 때는 전파(propagation)를 중단하도록 최적화했습니다.
3. 2024-07-19 현재 최적화를 위한 metadata 크기의 제한은 없습니다. 이는 profiling 결과에 따라 추가될 수 있습니다.

Separation of Business Logic

이 Plugin에서 Prefix Tree는 TFile 혹은 그 관련 클래스의 객체를 Content로 갖습니다. 다만, Obsidian Plugin API를 사용할 경우 Jest 등을 이용한 테스트가 어려운 문제가 있었습니다. Mocking을 고려했으나, Obsidian Plugin API의 문서화 상태가 부족하여 적절한 Mocking을 만들 수 없을 것으로 판단하여 Prefix Tree 로직을 별도로 분리하였습니다.

이는 srcs , srcs/__test__ 에서 볼 수 있습니다.

Preparing for Sustainable Development

TDD

이 플러그인은 TDD red-green-refactor 방식에 따라 개발했습니다. 테스트 자동화는 개발 시간은 조금 늘어나지만 분명 편했습니다. 하지만 동시에 이런 어려움도 있었습니다.

1. interface 정의에 어려움이 있었습니다.
2. edge case에 대한 테스트 작성에 어려움이 있었습니다.

interface 정의의 어려움

이 플러그인에서 TDD에 해당하는 부분은 옵시디언과 관계 없는 business logic 뿐입니다. 다르게 말하면 plugin과 무관한 library를 작성하고 plugin에서 그 library를 사용하는 형태로 작성되었습니다. 여기서 문제가 된 부분은 Obsidian Plugin에 대해 능숙하지 않은 상태이기 때문에 사용 가능한 정보와 그렇지 않은 정보를 알기 어려웠다는 점입니다.

weird cases & edge cases

개발하면서 가장 황당했던 순간은 제가 작성한 PrefixTree가 항상 root node를 중복으로 사용하고 있다는 것을 알았을 때입니다. 예를 들어, apple을 저장하면 a - a - p - p - l - e와 같이 저장되었습니다. 여기까진 황당한 이야기지만, 더 큰 문제는 해당 로직은 공용이었기에 PrefixTree가 제공하는 search, add, delete, move 모두 정상적으로 동작했다는 점입니다. apple을 저장할 때도 a - a - p - p - l - e을 저장하고, apple을 검색할 때도 a - a - p - p - l - e을 검색하니 이 문제는 우연히 운 좋게 찾지 않았다면 아마 계속 몰랐을지도 모릅니다.

또한 미처 처리하지 못한 edge case가 문제가 되는 경우도 있었습니다. 저는 edge case를 체크하기 위해 gpt의 도움을 받아 예시를 확인했는데, 그럼에도 불구하고 놓치는 경우가 있었습니다. 이렇게 놓친 edge case는 디버깅마다 추가되었지만 아직도 문제가 되는 경우가 있을 거라 생각합니다.

결과적으로 저는 TDD가 효과적인 방법이지만 만능 해결책이 아니란 것을 다시 한 번 실감할 수 있었습니다.

Debugging / Testing with vscode

저는 직관적으로 해결하기 어려운 문제나, 해결한 문제의 근거를 찾기 위해 디버거를 활용하는 것을 좋아합니다. 꾸준한 개발을 위해서 신뢰할 수 있는 문제 해결 방법이 필요했고, vscode에서 typescript를 디버깅할 수 있도록 설정했습니다.

제가 사용한 플랫폼과 IDE는 다음과 같습니다.

• vscode
• node (npm) - typescript
• jest

이 경우 .vscode/launch.json, tsconfig.jest.json, jest.config.js를 설정해주면 vscode를 통해 디버깅할 수 있습니다.

.vscode/launch.json, tsconfig.jest.json 의 주요 내용은 다음과 같습니다.

// .vscode/launch.json
{
	"cofigurations": [
		...
		"program": "${workspaceFolder}/node_modules/jest/bin/jest",
		"args": [
			"--jest-options"
		],
		...
		"skipFiles": [
			"obsidian_srcs/**"
		],
		**"sourceMaps": true**,
		...
	]
}

// **tsconfig.jest.json** : test에서는 별도의 tsconfig를 사용합니다.
{
	"compilerOptions": {
		...
		**"sourceMap": true**,
		**"types": ["jest"]**,
	},
	"include": [
		"srcs/**/*.ts"
	],
	"exclude": [
		"node_modules",
		"obsidian_srcs/**/*.ts"
	]
}

obsidian plugin의 dev와 build에서 tsconfig.json을 사용하기 때문에 테스트용으로 별도의 tsconfig.jest.json을 사용했습니다. 그리고 jest를 사용하기 때문에 jest.config.js 도 설정해야 합니다. 주요 내용은 tsconfig를 tsconfig.jest.json 으로 설정해주는 것입니다.

module.exports = {
    preset: 'ts-jest',
    testEnvironment: 'node',
    moduleFileExtensions: ['ts', 'js'],
    transform: {
        '^.+\\.tsx?$': ['ts-jest', { tsconfig: '**tsconfig.jest.json**' }]
    },
};

결과적으로 다음과 같이 디버깅을 할 수 있었습니다.

Debugging using dev tools

Obsidian은 Chromium engine을 사용하는 앱입니다. 따라서 dev tools를 사용할 수 있습니다. 다만 Obsidian Plugin의 특성상 dev tools를 이용하기 어려운 문제가 있었습니다. 아래 스크린샷을 봐주시기 바랍니다.

눈치 채셨나요? javascript 파일입니다. 게다가 여러 typescript module이 하나의 javascript파일에 컴파일되어 있습니다. 이런 경우는 디버깅하기 상당히 까다롭습니다.

Build with SourceMap

dev tools를 제대로 활용하기 위해 우선 obsidian plugin 빌드 시스템을 수정해 source map을 활성화시켜주겠습니다. Obsidian plugin은 node project이므로 package.json을 먼저 확인합니다.

{
	"name": "suggest-notes",
	...
	"scripts": {
		**"dev": "node esbuild.config.mjs"**
		...
	},
	...
}

esbuild를 사용하는군요. esbuild.config.mjs 를 확인하면 자세한 정보를 볼 수 있습니다.

...
const context = await esbuild.context({
	...
	**sourcemap: prod ? false : "inline"**,
	...
});

이상하지만 이미 inline 설정이 되어 있습니다.

혹시 모르니 tsconfig.json도 확인해보겠습니다. esbuild에서 별도로 설정하지 않으니 기본값인 tsconfig.json을 체크하면 됩니다.

{
	"compilerOptions": {
		...
		**"inlineSourceMap": true,
		"inlineSources": true,**
		...
	}
}

Obsidian Plugin template에서 sourcemap 설정은 문제가 없습니다.

Manually restoring debugging information

Obsidian에서 sourcemap을 파악하지 못하는 문제는 다른 곳에서 해결 방법을 찾을 수 있었습니다.

아래 코드를 봐주시기 바랍니다.

    async reload(plugin) {
        const plugins = app.plugins;

        // Don't reload disabled plugins
        if (!plugins.enabledPlugins.has(plugin)) return;

        await plugins.disablePlugin(plugin);
        console.debug("disabled", plugin);

        **// Ensure sourcemaps are loaded (Obsidian 14+)**
        const oldDebug = localStorage.getItem("debug-plugin");
        localStorage.setItem("debug-plugin", "1");
        try {
            await plugins.enablePlugin(plugin);
        } finally {
            // Restore previous setting
            if (oldDebug === null) localStorage.removeItem("debug-plugin"); else localStorage.setItem("debug-plugin", oldDebug);
        }
        console.debug("enabled", plugin);
        new Notice(`Plugin "${plugin}" has been reloaded`);
    }

이는 개발을 돕는 hot-reload plugin의 코드입니다. 보시면 plugin을 비활성화하고 활성화할 때 “debug-plugin” 정보를 저장했다가 복구하는 과정이 있습니다. 이를 통해 유추할 수 있는 것은 Obsidian 프로그램 자체는 플러그인을 on & off 할 때 debugging 정보를 업데이트 하지 않거나, 지운다는 것입니다.

따라서, hot-reload plugin에 의해 refresh된 플러그인은 정상적으로 typescript sourcemap 정보를 확인할 수 있었습니다.

Architecture

Class Diagram of PrefixTree

Obsidian

주요 클래스는 다음과 같습니다: KeywordSuggestPlugin, LinkSuggest.

KeywordSuggestPlugin

• plugin 초기화
• Obsidian App 로딩 후, 전체 파일을 검색하여 PrefixTree를 구성합니다. - profile 대상
• 파일 변경, 이동, 삭제, 생성 event에 대해 PrefixTree를 업데이트 합니다.
• 유저 설정을 바탕으로 파일을 링크 제안 목록에 포함할 것인지 판단합니다.

LinkSuggest

• 유저 입력에 대해 PrefixTree를 검색해 제안할 수 있는 목록을 생성합니다. - profile 대상
• 유저가 선택한 파일에 대한 internal link를 생성하고 관련 statistics를 업데이트합니다.

Testing & Profiling

Test Set

제가 사용하던 노트를 그대로 복사해서 사용했습니다. 총 565 개 파일, 1310개의 search keyword를 포함하고 있습니다.

시간을 측정해야 하는 기능은 다음과 같이 측정 함수를 통해 측정했습니다.

const isDev = process.env.NODE_ENV === 'development';

export function measurePerformance<T>(lines: () => T, label: string, desc?: string): T {
    if (!isDev) return lines();
    
    performance.mark(`start - ${label}`);

    const result = lines();

    performance.mark(`end - ${label}`);
    performance.measure(label, `start - ${label}`, `end - ${label}`);
    const measure = performance.getEntriesByName(label)[0];
    console.log(`${label} ${desc ?? ''} took ${measure.duration} ms`);

    return result;
}

export function measureFinerLatency<T>(lines: () => T, label: string, desc?: string): T {
    if (!isDev) return lines();

    const start = performance.now();

    const result = lines();

    const end = performance.now();

    console.log(`${label} ${desc ?? ''} took ${(end - start) * 100} micro sec`);

    return result;
}

Profiling Results

Initial Loading

초기 로딩에 걸리는 시간은 12.9 ms 였습니다.

Search

검색에 걸리는 시간은 1 μs 이하 ~ 10 μs로 측정되었습니다.

다만, 동일한 검색어에 대해서도 매번 시간이 다르게 측정되었습니다.

Add & Change

추가 및 수정에 걸리는 시간은 1 μs 이하 ~ 10 μs로 측정되었습니다. 동일한 수행에 대해서도 다른 결과를 보이기도 했습니다.

Deletion

삭제에 걸리는 시간은 1 μs 이하 ~ 40 μs로 측정되었습니다. 걸리는 시간은 10 μs의 배수에 근접한 값으로 측정되었습니다.

삭제의 경우 편차가 큰 것은 하나의 노트가 여러 keyword를 포함하고 있을 수 있기 때문인 것으로 보입니다.

Analysis

Search vs Add, Change, Deletion

구현상 Search는 metadata의 수정을 포함하지 않습니다. 즉, Prefix Tree를 통한 검색이 전부입니다. 따라서 Add, Change, Deletion과 비슷하게 10 μs가 소요될 수 있는 것은 이상합니다.

Multiple of 10 μs

위 결과에도 적혀있듯, 동일한 수행에 대해서 0 μs가 걸리기도 하고, 10 μs의 배수에 해당하는 시간이 걸리기도 합니다. 여기서 이상한 점은 0 μs인 경우가 있다는 점입니다. 수행에 10 μs의 시간이 필요하다면 0 μs인 경우는 있을 수 없으니까요. 이에 대해 가능한 추측은 Cache / Scheduling 입니다.

아시겠지만, 컴퓨터는 늘 동일하게 작동하지 않습니다. Cache Locality & Temporality에 의해 동일하거나 메모리상 근사한 위치의 연산은 빠르게 작동합니다. 이런 의도로 작성된 프로그램을 cache friendly 하다고 합니다. 이런 관점에서 10 μs는 수행 시간이 아니라 memory uploading에 필요한 시간으로 생각할 수 있습니다. SSD의 속도를 300 MB/s로 가정하면 10 μs에 읽을 수 있는 memory는 100 byte입니다. 단순한 오브젝트 하나의 크기로 설득력 없는 크기는 아닙니다.

두 번째 가능성은 OS의 scheduling에 의해 지연되어 실행되는 경우입니다.

Multiple of 10 μs - testing

이에 대한 테스트로 다음과 같은 코드를 사용했습니다.

// profile 1+1
this.addRibbonIcon('dice', 'test', () => {
    measureFinerLatency(() => {
        1+1;
    }, 'test')
});

그리고 다음과 같은 결과를 얻었습니다.

비슷하게 10 μs의 결과가 때때로 나오는 것을 볼 수 있습니다. 따라서, 이는 operation에 필요한 시간이 아니라 별도의 지연 시간이 있다고 생각할 수 있습니다. (단, 이는 확정적인 증거는 아닙니다.)

Conclusion - initial loading

Initial Loading의 time complexity는 새로운 노트가 추가될 때마다 $O(h)$만큼 증가합니다. 따라서 비정상적으로 긴 keyword만 사용하는 게 아니라면 노트의 수가 20배가 될 때, initial loading에 걸리는 시간은 12.9 ms 의 20배, 258 ms로 추정할 수 있습니다. 이 정도도 눈치 채기 어려운 속도이므로 당장은 개선이 필요 없다고 결론 내리겠습니다.

다만, 사용 후기에 따라 metadata에 추가적인 최적화(크기 제한)를 할 수 있습니다.

Conclusion - Operations

1. 0 μs latency인 케이스가 Search, Add, Change, Deletion 모든 경우에 있으며, 빈도가 적지 않다는 점
2. 10 μs ~ 40 μs도 노트 어플리케이션으로서는 충분히 빠른 latency라는 점

으로부터 이 플러그인의 반응 속도는 충분히 빠른 편이라 결론 내리겠습니다. 따라서 추가적인 최적화 작업은 후순위로 미루기로 결론 내리겠습니다.

Extreme Cases

각 노트 별로 4개의 search keyword를 추가하여 1000개 ~ 5만개 노트에 대해

1. Prefix Tree를 구성하는 시간
2. Prefix Tree에서 검색하는 시간
3. Prefix Tree를 업데이트 하는 시간

을 조사했습니다.

samples	Prefix Tree Setup (ms)	Search (ms)	Update (ms)
1000	56.3615	0.2757	1.2077
5000	495.6186	0.1668	3.9746
10000	1684.605	0.2064	2.6911
20000	7212.5582	0.1604	6.4002
50000	62611.6993	0.195	43.0781

Conclusion: sample이 늘어날수록 Prefix Tree를 구성하는 시간과 업데이트 하는 시간이 늘어나는 것을 볼 수 있습니다. 이중 Search time은 sample 수에 무관한 것을 볼 수 있고, sample 수에 따라 무작위로 달라지는 것은 임의로 정한 keyword의 길이에 따라 다른 것으로 보입니다. Update time은 5만 개의 노트에 대해서도 43 ms로 준수한 편입니다. 하지만, Prefix Tree를 구성하는 시간은 1만개 부터 1초 이상으로 증가하는 것을 볼 수 있습니다.