# spotify/annoy architecture

> Architecture diagram of the GitHub repository spotify/annoy, generated by GitDiagram from its file tree, README and a sample of source files (last updated 2025-01-12). It is an AI-made overview: check details against the source.

- Interactive diagram: https://gitdiagram.com/spotify/annoy
- Repository: https://github.com/spotify/annoy

## Overview

##### Main Components

a. Core Library Components:
- C++ Core Engine (src/annoylib.h)
- Random Number Generator (src/kissrandom.h)
- Memory Mapping Handler (src/mman.h)

b. Language Bindings:
- Python Module (src/annoymodule.cc)
- Go Module (src/annoygomodule.h, .i)
- Lua Module (src/annoyluamodule.cc)

c. Storage Components:
- Memory-mapped Index Files
- In-Memory Index Structure

##### Key Architectural Patterns

- Read-only file-based data structures
- Memory-mapped file sharing
- Multi-process support
- Tree-based index structure

- C++ Core Engine    |

- Vector Space Engine  |
- Tree Builder         |
- Distance Calculators |
- Memory Manager       |

- Python    |  |    Go     |  |    Lua    |
- Binding   |  |  Binding  |  |  Binding  |

- v            v             v

- C++ Core Engine         |

- In-Memory Index| <-> | Memory-mapped    |
- Persistent Index |

Following interactions:
- Index building flow
- Query flow
- Memory mapping flow
- Inter-process sharing

##### Important Elements to Highlight

- Multiple distance metrics support (Euclidean, Manhattan, cosine, Hamming, Dot Product)
- Tree structure for approximate nearest neighbor search
- Memory mapping mechanism
- Process sharing capabilities
- Build vs. Query phases

##### Technical Details

- Support for different vector dimensions
- Tree building parameters
- Search parameters (n_trees, search_k)
- Memory optimization features

##### Implementation Notes

- Separation between index creation and querying
- Static nature of the index after building
- Memory-mapping optimization
- Multi-threading support for building

- Component types
- Special symbols

## Diagram (Mermaid)

```mermaid
graph TB
    subgraph Core
        Engine["C++ Core Engine"]
        RNG["Random Number Generator"]
        MemMap["Memory Mapping Handler"]
        
        subgraph DistanceMetrics["Distance Metrics"]
            Angular["Angular Distance"]
            Euclidean["Euclidean Distance"]
            Manhattan["Manhattan Distance"]
            Hamming["Hamming Distance"]
            Dot["Dot Product"]
        end
        
        Engine --> DistanceMetrics
        Engine --> RNG
        Engine --> MemMap
    end
    
    subgraph Bindings
        Python["Python Binding"]
        Go["Go Binding"]
        Lua["Lua Binding"]
        
        Python --> Engine
        Go --> Engine
        Lua --> Engine
    end
    
    subgraph Storage
        InMem["In-Memory Index"]
        DiskIndex["On-Disk Index"]
        MMap["Memory-Mapped Files"]
        
        InMem <--> DiskIndex
        DiskIndex <--> MMap
        MMap --> Engine
    end
    
    subgraph Features
        MT["Multi-Threading"]
        MP["Multi-Process Support"]
        TreeBuild["Tree Building"]
        Search["ANN Search"]
        
        TreeBuild --> Engine
        Search --> Engine
        MT --> TreeBuild
        MP --> MMap
    end
    
    classDef core fill:#b3d1ff,stroke:#333,stroke-width:2px
    classDef binding fill:#c2f0c2,stroke:#333,stroke-width:2px
    classDef storage fill:#ffd9b3,stroke:#333,stroke-width:2px
    classDef feature fill:#d9b3ff,stroke:#333,stroke-width:2px
    classDef metric fill:#ffb3b3,stroke:#333,stroke-width:2px
    
    class Engine,RNG,MemMap core
    class Python,Go,Lua binding
    class InMem,DiskIndex,MMap storage
    class MT,MP,TreeBuild,Search feature
    class Angular,Euclidean,Manhattan,Hamming,Dot metric
    
    click Engine "https://github.com/spotify/annoy/blob/main/src/annoylib.h"
    click RNG "https://github.com/spotify/annoy/blob/main/src/kissrandom.h"
    click MemMap "https://github.com/spotify/annoy/blob/main/src/mman.h"
    click Python "https://github.com/spotify/annoy/blob/main/src/annoymodule.cc"
    click Go "https://github.com/spotify/annoy/blob/main/src/annoygomodule.h"
    click Lua "https://github.com/spotify/annoy/blob/main/src/annoyluamodule.cc"
    click MMap "https://github.com/spotify/annoy/blob/main/examples/mmap_test.py"
    click Angular "https://github.com/spotify/annoy/blob/main/test/angular_index_test.py"
    click Dot "https://github.com/spotify/annoy/blob/main/test/dot_index_test.py"
    click Euclidean "https://github.com/spotify/annoy/blob/main/test/euclidean_index_test.py"
    click Hamming "https://github.com/spotify/annoy/blob/main/test/hamming_index_test.py"
    click Manhattan "https://github.com/spotify/annoy/blob/main/test/manhattan_index_test.py"
    click MT "https://github.com/spotify/annoy/blob/main/test/multithreaded_build_test.py"
    click DiskIndex "https://github.com/spotify/annoy/blob/main/test/on_disk_build_test.py"
```
