App Engine - Chain of entities generates exceptionally long entity keys

Question

I am writing an application which allows users to send messages between them. I am using transactions to ensure that there is only a single "top" message between any two users, and this "top" message has a link to the "next" message, and so on.. forming a sort of of linked list of messages. The messages reference each other through reference properties, and are placed in the same entity group by declaring each new "top" a having the previous "top" as its parent.

However, the problem with this approach is that each new entity has a key that includes the entire key of the previous entity (ie: new_top_key == old_top_key + new_stuff). This results in entity keys growing at a large rate, and probably very bad behavior after a few hundred messages in a single chain (but I haven't actually tested).

So, my question is: 1) Is this an intentional feature of the App Engine. 2) Should I be avoiding this type of a structure -- or is it somehow efficiently dealt with by the App Engine internally? 3) Do you have any suggestions on what is the correct approach for a linked-list-of-entities type of structure?

Thank you and kind regards Alex

Answer 1

Are you using python or java? The detailed answer will depend a bit on which API you are using.

I'm pretty sure that having your keys grow indefinitely is not the best plan. (it might be a good test case for the app engine api though :)

I think the solution will be to separate the entity group information from the message linking information. In order to do transactions on a thread/conversation/chain/whatever, all your messages need to be in the same entity group. However, they do not need to be in a hierarchy that exactly matches the structure of the links between messages. You should explicitly set the parent (entity group) of all your message entities to be the same, in a flat structure. So each entity would be a sibling of the others, in the sense of entity groups. You would also need a field in your entity to link to the next (and/or previous) message. So you would still have a linked list (or tree or whatever) in terms of the "previous message" links.

Both Python and Java have methods for creating an entity with a specific parent/entity group. (In fact, you can even specify a nonexistent entity to be the root of an entity group hierarchy!)

Now the key of each message will be a fixed length, so your "next" and "previous" reference properties will be nice and safe from overflowing some limit on key length.

Answer 2

In order:

1. Yes. Each entity is uniquely identified by its kind, key or id, and those of all its parents, which means that the entire chain is necessary to identify an entity.
2. Yes. Instead, have a "conversation" entity (which could be the first message, as well), which is a direct parent of all the posts. If you still need to maintain parent/child relationships within a conversation (instead of just ordering them by timestamp, for example), declare an explicit SelfReferenceProperty.
3. See #2, above.