Indexing and Sorting

to be continued.

Once the posts are stored in the state machine, we encounter the next challenge: retrieving not just a single post but a list of sorted posts from the chain. To maximize user experience, we also need to provide lists such as hot topics, community topics, followers’ posts, recommended posts, category posts, and posts with user mentioned and under different topics.

We avoid using third-party data processing services because they can increase dependencies, reduce decentralization, and undermine user experience. You can understand the challenge like to query a pre-sorted holders list of Bitcoin in real-time through RPC endpoints.

On-chain Indexing and Sorting

The solution is to build an on-chain indexing and sorting system by utilizing the IAVL tree (Immutable AVL tree) for efficient state management, maintaining various pre-sorted lists real time, enabling direct search of any tagged content, providing REST API for front-ends directly without dependency of off-chain data processing.

Implementing these strategies is pivotal for ensuring a seamless user experience in a decentralized social media platform. By designing key structures and indexing mechanisms, Tlock will enable efficient data retrieval for various user-centric features.

Hierarchical and Composite Keys

Tlock’s key schema is designed to support multiple index by organizing data hierarchically and using composite keys that combine multiple attributes to facilitate secondary indexes sorting and range queries.

following:<user_id>:<inverted_timestamp>:<post_id>
category:<category>:<reputation_score>:<post_id>
mentions:<mentioned_user_id>:<inverted_timestamp>:<post_id>

Maintaining Indexes on Transactions

Every transaction affecting the data (e.g., creating a post, commenting, liking) will update relevant secondary indexes.

func (k Keeper) updateIndexByComment(ctx sdk.Context, postID string) {

    oldInverted := maxScore - currentScore
    newInverted := maxScore - newScore

    oldKey := fmt.Sprintf("recommendation:%06d:%s", oldInverted, postID)
    newKey := fmt.Sprintf("recommendation:%06d:%s", newInverted, postID)

    store := ctx.KVStore(k.storeKey)
    store.Delete([]byte(oldIndexKey))
    store.Set([]byte(newIndexKey), []byte(postID))

    k.SetPostScore(ctx, postID, newScore)

}

Prefix Iterators and Pagination

Our KV store is built on top of IAVL, which inherently maintains keys in lexicographical order. This ordered nature is pivotal for the efficiency of prefix iterators. It can efficiently traverse keys starting with a specific prefix by leveraging the tree's ordered structure.

This also helps implement customized queries and pagination to manage large datasets without overwhelming the system. Use inverted values for timestamps, reputation scores and other attributes to facilitate descending order traversal using prefix iterators. This ensures that the most recent or highest-scoring items are retrieved first without additional sorting overhead.