In most cases, SP doesn't know user is removed from IdP. If there's a need for such feature, you resort to shared sessions - IdP has control of storage service where SP's save sessions (say, Redis). Once user is removed from IdP, IdP deletes the session record in Redis and SP loses all user info.
This implementation happens rarely.
The single logout process is often flawed since it depends on SP's accurately processing the request and returning the user back to IdP if a session has been successfully destroyed. This often fails due to network connectivity, problems with session destroying at the SP, SP's not implementing the SingleLogout properly etc. What I've experienced and seen in many cases is that IdP simply kills the session it has on the user and stops right there, then the rest of the SP's handle it through back-channel.
I work in this area so I'm relaying my experience through past 10 years of implementing SSO for various enterprises.
In reality, the SAML protocol is quite straight-forward but something odd happens when people hear the term SSO. It's not magic, it's quite trivial but takes a bit of discipline to grasp it fully and implement properly.
I've been tasked with authenticating in an existing application via SAML 2.0 I've got the whole SAML 2.0 specification printed and sitting on my desk right now. It sure doesn't look trivial.
When people say "Don't roll your own encryption" or "Don't implement $ALGORITHM, just use libsodium", I think that also applies to web authentication (be it OAuth or SAML).
If you are the 'client' that wants to authenticate an incoming user, then I'd point you to an existing SP like Shibboleth or SimpleSAMLPHP or even CILogon (which bridges SAML and OAuth). If you are handing out authentications, then you are an IdP and I'd point you to something like Shibboleth or ADFS or Okta.
It is good to have the relevant RFCs to hand, but I would not make an implementation from scratch, unless there was a very good reason for it.
I'm trying to build an "SP" or "relying party" as I've learned in the jargon of the domain. Building an implementation from scratch is the last thing I want to do. I feel like I'd rather pull out my own teeth. But a difficulty of finding any information about it has lead me to start reading all the official specs as a kind of last resort.
In my initial research, I did discover Shibboleth, but was under the impression that it was an IDP only. I will check out the SP component, because I would love to not implement it from scratch.
It installs as an apache module and I am building a flow from my load balancers to hit the apache/SP and proxy some traffic to the application after authentication success so we can create our login session.
I have a PoC going now, but the documentation is not terribly clear to me and it is really confusing me about some options I need to tune.
For my initial testing, I built the SP and used https://samltest.id/ to test against an IDP.
If your language/environment supports using Apache HTTPD as a proxy, then you can use mod_auth_mellon to secure your web application. That's just one option, there are lots of others.
I have heard about these options, but the problem for me is identifying any of them and figuring out how to use them. My web server probably has to be IIS or Kestrel. I've been trying to figure this out for a few weeks now. And I've spent about a day trying to figure out how to do anything with the Shibboleth SP. I think I got it installed, but I can't really tell if it's doing anything or how to use it. And even then, there doesn't seem to be any information on how to actually use it for authentication in my application.
From my perspective as an application developer, writing an application that authenticates via SAML 2.0 is a nightmare, despite the ubiquitous claims of how simple it is.
If your app is .NET, look at Sustainsys (https://saml2.sustainsys.com/en/2.0/) or ITFoxtec (https://www.itfoxtec.com/IdentitySaml2) libs. Unfortunately there isn't a clear architect/dev-level guidance at the protocol level on key decisions that need to be made when implementing SP that tightly integrates with your app. Give one of these a shot and post your questions on StackOverflow.
If you're willing to use PHP, there's also "the award-winning" SimpleSAMLphp (https://simplesamlphp.org/), which can operate as IdP or SP. I can tell you that many big names in the TV Everywhere space are using it.
You're reading the entire spec, but the flow is what's trivial. 2 systems are exchanging info, they use cryptograhpy to assert that message is coming from a valid, registered resource and the message carrier format is XML. You ask for info, you get XML back, verify the sender and if correct trust the info is valid. That's the gist of the protocol and the tedious part is parsing the XML you receive.
The flow/concept is simple indeed. But with saml the devil is really in the details and they created way too many details by offering way to many options in the spec.
What's the best practice on when a user session is destroyed at the SP's end? After receiving the LogoutResponse from IdP or before sending the LogoutRequest to IdP?
The other responses answer your direct question, but I was confused about similar flows when learning about SAML so I'll comment in case this is helpful.
SAML is just an authentication protocol, it doesn't really handle user provisioning. Which was confusing to me, because any time you'd use it you typically also need some kind of provisioning mechanism.
SAML does have a concept of "just in time" provisioning, which is what I've seen small SAAS companies typically support when they say they have SAML support. But basically all it can handle is creating accounts in the SP the first time a new person logs in (with valid credentials signed by the IDP). For user provisioning though what you really need is full programmatic CRUD access for accounts in the SP, which is outside the scope of SAML. I don't really understand why the SAML protocol bothers having such half-baked support at all, because you immediately run into issues. For example, giving some users different permissions than others in the SP, or updating accounts in the SP that already exist.
For user provisioning, for SPs that support it you can use the SCIM protocol alongside SAML, which gives you full control over provisioning accounts the way you need to. Then for instance instead of just logging someone out of the SP when they were removed from the IDP, it can fully deprovision the account in all your SPs as well so you're not left with orphaned accounts sitting around.
Or what happens when the user is removed from the idp? How does service provider know the user is supposed to be logged out?