Trajectory data is very useful for many urban applications. However, due to its spatio-temporal and high-volume properties, it is challenging to manage trajectory data. Existing trajectory data management frameworks suffer from scalability problem, and only support limited trajectory queries. This paper proposes a holistic distributed NoSQL trajectory storage engine, TrajMesa, based on GeoMesa, an open-source indexing toolkit for spatio-temporal data. TrajMesa adopts a novel storage schema, which reduces the storage size tremendously. We also devise novel indexing key designs, and propose a bunch of pruning strategies. TrajMesa can support plentiful queries efficiently, including ID-Temporal query, spatial range query, similarity query, and k-NN query. Experimental results show the powerful query efficiency and scalability of TrajMesa.