Query for deleted entities in Dynamics 365 XRM Tooling SDK

I am writing a generic integration that needs to use the database in Dynamics 365 for Customer Engagement as the system of record. I will be polling it from time to time to keep data up to date in other ancillary systems. I can know, of course, when records have changed by inspecting the "modifiedon" attribute. I can build a query saying "give me all the records that have changed since the last time I asked". It would, however, also be optimal to be able to know what records have been DELETED since the last time I asked. I have a similar integration with Salesforce, and that is trivial to do with the SalesForce API, but I can't see how to do it with the Dynamics 365 API.

It appears that the only option to me might be to keep a list of all the record primary keys in my integration, and download on each poll ALL records existing in CRM and then figure out the deleted ones on my own by their absence. That is pretty ugly and inefficient though.

Any ideas or advice?

MS introduced change tracking for this purpose.

The change tracking feature in Dynamics 365 for Customer Engagement Customer Engagement provides a way to keep the data synchronized in a performant way by detecting what data has changed since the data was initially extracted or last synchronized.

The sample web api request below:

GET [Organization URI]/org1/api/data/v9.0/accounts?$select=name,accountnumber,telephone1,fax HTTP/1.1
Prefer: odata.track-changes

Response will have delta link with a delta token:

"@odata.deltaLink": "[Organization URI]/api/data/v9.0/accounts?$select=name,accountnumber,telephone1,fax&$deltatoken=919042%2108%2f22%2f2017%2008%3a10%3a44"

When you use the above URI, you can get the changes including deleted entries.

{
          "@odata.context":"[Organization URI]/data/v9.0/$metadata#accounts(name,telephone1,fax)/$delta",
          "@odata.deltaLink":"[Organization URI]/api/data/v9.0/accounts?$select=name,telephone1,fax&$deltatoken=919058%2108%2f22%2f2017%2008%3a21%3a20",
"value":
    [
        {
            "@odata.etag":"W/\"915244\"",
            "name":"Monte Orton",
            "telephone1":"555000",
            "fax":"10101",
            "accountid":"60c4e274-0d87-e711-80e5-00155db19e6d"
        },
        {
            "@odata.context":"[Organization URI]/api/data/v9.0/$metadata#accounts/$deletedEntity",
            "id":"2e451703-c686-e711-80e5-00155db19e6d",
            "reason":"deleted"
        }
    ]
}

Sample: Synchronize data with external systems using change tracking