A control node of a multi-tenant stream management service receives a request to initialize a data stream to be comprised of a plurality of data records. The control node determines, based on a partitioning policy, parameters to be used to configure subsystems for ingestion, storage and retrieval of the records. The control node identifies resources to be used for a node of retrieval subsystem The retrieval node is configured to implement programmatic record retrieval interfaces, including respective interfaces to implement non-sequential and sequential access patterns. The control node configures the retrieval node using the selected resources.